tomboのブログ

競技プログラミングのことをいろいろ書きます AtCoder A茶H水

将棋ライクLv.20クリアしました!

(アップデートが頻繁に行われているらしくて、最新の情報じゃないかもしれないです。この記事は2024/05/04に書きました。)

今回は、主にノーマルモード(Lv.1~Lv.10)について書いていきます。

目次

  • 完走した感想
  • ゲームの概要
  • 具体的な戦略
  • おすすめコンボ
  • 駒の取得優先度ランキング
  • 意外と強くない駒
  • ハードモードについて
  • まとめ

完走した感想

面白かったです、将棋とは完全に別ゲーですが、ちゃんと頭を使って戦略を練って戦うのがすごく楽しいゲームでした。自分はちなみに将棋から入って、そしたら開幕「怨霊(倒された相手も道ずれにする)」っていうのが出てきたのでその勢い(?)でめっちゃ笑ってました。


夜10:00に始めて、朝の4:00にLv.20までクリアしました。けっこう難しかった、もっとステージがあったら無限にやってるかもしれない()運が絡んできて、場合によってはすぐに行けたり、苦戦したりすると思うので、そこも将棋と違ったゲーム要素って感じで好きです。それでは、攻略記事みたいな感じで、自分が攻略したときの情報を書いていきます。

ゲームの概要

将棋のように駒を動かして、相手の王城に3ダメ―ジ与えれば勝ちです。駒は将棋に登場するもののほかに、オリジナルのものがたくさんあり、こちらがメインになります。駒には手動と自動があり、自動の駒は手数が増える分、シンプルに強いです。また、駒には普通・銀・金の3つのランクがあり(Lv.20クリア後にシークレットが解放される)、基本的には金駒が強いですが、「機兵」と「金船」は最後まで使っていける優秀な銀駒で、取っておいて損はないです。

自動の例

  • 機兵(銀駒)
  • 機龍(金駒)
  • 金船(銀駒)
  • 不沈(金駒)
  • 腐敗(金駒)

自動に関しては、範囲内の敵を優先するので、完全にランダムというわけではなく、ある程度敵に近づいたら勝手に攻撃してくれます。

具体的な戦略

Lv.1~Lv.5

最大の関門はLv.3の女傑のような気がします。初めて出てくる金駒ですね。めちゃくちゃ強いです。対抗するためのおすすめの駒を紹介します。

  • 主盾:攻撃と防御で上回っており、シンプルに強い。
  • 魔女:女傑を豚兵に変えてしまって勝ち。
  • 金船:自動制御。防御1で倒されないので強い。不沈になるとさらに強い。
  • 機兵:自動制御。防御1で倒されないので強い。機龍になるとさらに強い。機龍は2回行動。

その他、角を成って馬で攻めたり、邪剣で殴ったりして、うまくかみ合って勝つこともあります。できれば上の4つの銀駒のどれかが欲しいかなーと思いました。

Lv.6~Lv9

Lv.6の腐敗がしんどいです。対策を知らないとけっこう負けます。おすすめの駒を紹介します。

斜めの駒で、初手角道オープン→相手の王城を直接殴る(終了)で勝てます。または、騎馬で跳ねていってそのまま重騎で殴れば勝てます。腐敗に巻き込まれないように気を付けてください。


Lv.9の女帝×2もきついかもですが、金船→不沈とか、機兵→機龍、十三でスナイプ、魔女で封印、洗脳で味方にする(下の画像)など、そこまで駒が増えたらいろいろ対策できると思います。駒の取得優先度ランキングも見てみてください。


それ以外では、例えばLv.7なら、このように不沈や機龍に攻撃させておけば、だいたいうまくいきます。

Lv.10

これ、運ゲーです。聖獣が瞬間移動して殴ってくるので、お願いしますーーーって言いながらプレイしてください。(言わなくていいです)あと、邪神と聖神が召喚してきた邪徒、聖徒の場所と被ると、召喚時にそのままダメージを受けます。輪廻で行ったりする場合は、これもお願いしますーっていいながら、慎重に横を通り抜けてください。王城に近づければあとはやるだけです。負けパターンは基本的に、道中が苦しくてたどり着けないという状況か、早々に自分の王城が攻撃されるパターンです。


突撃する駒は、機龍や不沈の自動で待っているか、手動ならぬにがいいです。輪廻審判でランダムスポーンを狙ってもいいですが、輪廻は耐久面が終わってるので、少しでも距離があるとなかなか王城にたどり着けないと思います。Lv.10は「魑魅魍魎が跋扈する」的な表現が正しそう(?)


魔獣には洗脳が通ります。


おすすめコンボ

魔女審判

脳死破壊コンボ。(?)魔女で相手の駒を豚兵にすると、審判の効果でその駒を破壊できます。魔女は個人的に癖が強くて、扱うのが難しいと思っているので、味方の駒を巻き込んだり攻めのルートを消したりしないようにしながら、相手の強い駒を倒すようにするといい感じになります。

輪廻審判

魔女審判ほど強くはないですが、輪廻は倒されると寝返って、そのとき審判の効果で倒されてもう一回寝返り、ランダムスポーンして味方として復活するので、審判が生きている限り輪廻は不死身になります。また、輪廻は攻撃3なので王城をワンパンできます。機動力が低いのが難点。

駒の取得優先度ランキング

あくまで個人的な、ざっくりとした感覚です。ステージレベルや自分のデッキによって多少変わってきます。また、人によって使いやすさや癖が強いと感じる部分があると思うので、その辺りはお任せになってます。


1位 機龍(金駒)

自動で動き、2回行動、ステータスが優秀で、メイン火力にも防御にもなります。とりあえず取っておくと、いろいろ活躍してくれて助かります。2回行動ができるのはこの駒だけです。


2位 主盾(銀駒)→ ぬに(銀駒)

防御特化かと思いきや、ゆっくり進出していってぬにとなった途端、最強のステータスになります。他の駒の能力も受けない。もちろん王城もワンパン。さすが唯一ぬに。


3位 金船(銀駒)→ 不沈(銀駒)

自動制御で、斜めに突っ込んで不沈になりやすいです。不沈になると、高いステータスに加えて、HP自動回復も付いてかなり優秀です。機龍と同じく攻めにも守りにも使えます。


4位 増殖(金駒)

分厚い層を形成して、圧縮してゴリ押しみたいなムーブになります。Lv.10で聖徒と邪徒の大群に殴り勝てます。しかし成ると死ぬので、やっぱり機龍や不沈で火力を出していきたいです。


5位 審判(銀駒)

相手の特殊召喚された駒を即座に破壊します。魔女や輪廻と相性が良いですが、自分では何もできないので状況によって選びます。タンクとして使えます。何より、Lv.10の邪徒を召喚と同時に倒せるのがデカすぎて、重宝します。聖徒には無効なので、左から殴りたいところです。


6位 魔女(銀駒)

周囲の駒をすべて豚兵にします。相手の強い駒をとりあえず豚兵にしておけば、火力を抑えられたり、そのまま審判と合わせて消してしまうなどができま
す。


7位 機兵(銀駒)→ 機龍(金駒)

機龍に成れるので、少しずつ前線に上がっていきたいです。そのままでも防御1があるので、結構戦えます。機動力が低いのが難点です。


8位 十三(金駒)

相手の強力な駒(女帝、機龍など)を開始から3ターンの間、ターンごとに1体ずつ抹消できます。(バチコリ)駒自身で戦うことはできないので、主戦力にはならないですが、厄介な駒を破壊できるのは便利です。

意外と強くない駒

  • 張飛(銀駒)
    • 飛車先の歩を突くのが遅い。(角道ならすぐに開く)
    • 飛車はデフォルトの将棋の駒であり、攻撃と体力が1、防御が0になっている。


  • 全能(金駒)
    • 相手の駒と一緒に自分の駒も消してしまうので、Lv.10の大量の駒相手に分が悪い。
    • 運が悪いといきなり主力駒が消えたりして、自傷ダメージが大きい。


ハードモードについて

ハードモードでは、金 駒 が 使 え ま せ ん 。( そ ん な ) 気合で頑張ってください、ただ、汚忍→空蝉が使えます。これが聖獣みたいな感じの瞬間移動で、かなり強烈なので、必ず取ってください。ノーマルに対して、実はハードは全然苦労しない印象でした。空蝉が強いのかも。ベースはノーマルと同じなので、機兵や金船で行けます。

まとめ

いろいろと戦略があって面白そうで、アップデートも来ているらしいので、ぜひぜひやってみてください。あと、マリオや砲塔が使えなくて大変なので、その辺の情報をください(?)ちなみに、本家の将棋も面白いです。シークレットの五条が強すぎた。

AHCのローカルテスタの使い方

AHCのローカルテスタ、自分も最初使い方が分からなかったので、それについて書きます。WindowsPowerShellなので、それ以外の環境の人はまた調べてみてください← 言語はC++を想定していますが、コンパイルやファイルの実行を言語に合わせて書き換えてください。

PowerShellのコード

Param($l, $u)
$num = 32
$num_txt = "AHC{0:D3}" -f $num
Set-Location "実行するコードへの絶対or相対パス"

g++ -O3 -D_GLIBCXX_DEBUG -std=c++2a "$num_txt.cpp" -o AHC.exe
for ($i=$l; $i-lt$u; $i++){
    $tmp="{0:D4}" -f $i

    # non-interactive
    Get-Content in/$tmp.txt | ./AHC.exe > out.txt
    Write-Host -NoNewLine $i": "
    ./vis.exe in/$tmp.txt out.txt
    
    # interactive
    # Write-Host -NoNewLine $i": "
    # Get-Content in/$tmp.txt | ./tester.exe ./AHC.exe > out.txt
}

<#
実行コマンド
ファイル名.ps1 -l 0 -u 50
#>

Param()で引数を2つ受け付けています。$numはAHCの番号です。(3桁で0埋めしています)Set-Location (Linuxのcd) で移動しています。どこで実行してもいいようにするためです。-D_GLIBCXX_DEBUGで、index out of rangeのときに表示してくれるようにしています。(行数の表示方法は分かりません)


これはC++なのでコンパイルしていますが、Pythonなどのインタプリタは、./AHC.exeのところで直接ファイルを実行してください。


入力ファイルの番号は [l, u) の半開区間になっています。4桁で0埋めしていますが、AHCではダウンロード時のデフォルトで、0000~0099までしか入力ファイルがないので、seeds.txtに欲しい入力ファイルの数字を書いて、gen.exeを実行すると生成してくれます。


実行は

ファイル名.ps1 -l 0 -u 50

で出来ます。(0000~0049の場合)

並列実行について

並列実行すれば、並列した数だけ速くなります。(それはそう)マルチプロセスのことだと思います。ちなみにマルチスレッドは、スレッドが分かれるだけで速度は変わらないと思います。並列で1万ケース回すみたいな話も聞いたりしていて、たくさん回せばその解法の評価がより正確になるので、良かったら試してみてください。自分はよく分かっていません(そんな)

まとめ

AHCは楽しいので、ぜひぜひって感じです。

マージソートを、書きます。

tomboです。マージソートを、書きます。(書くので)

安定して速いです

マージソートは安定ソートで、ソートしたいデータ数  N に対して最悪ケースの時間計算量が  O(NlogN) です。例えばクイックソートは不安定ソートで、ピボットの選び方によってはマージソートより遅く  (O(N^2)) なったりします。色々な言語のソート関数でも、内部でマージソートが実装されているんじゃないかなーと思っています。(思っているだけ)

実装の方針

分割倒置法をします。「困難は分割せよ」の精神で (DP的な) 、分割してソートしながらマージしていって、最終的に全体のソートを達成します。分割は二分木のようにします。今回は再帰関数を使います。(他の実装をしらない←)

二分木の高さは、要素数 N として  O(logN) になるので、マージの処理には  O(N) かけても、全体で  O(NlogN) になることが分かります。そして、再帰的にマージするときの一番のポイントが、マージするたびに要素がソートされるということです。

問題と実装

verifyにはこの問題を使いました。
アルゴリズムと数学 演習問題集 027 - Sorting

提出
https://atcoder.jp/contests/math-and-algorithm/submissions/52793571

再帰関数の説明をします。
まず、左右に分けながら帰りがけ再帰をします。

vector<ll> left, right;
ll n = v.size();

// 左半分
rep(i, 0, n/2){
    left.push_back(v[i]);
}
// 右半分
rep(i, n/2, n){
    right.push_back(v[i]);
}

// 左右それぞれ帰りがけ再帰
vector<ll> v1, v2;
if (left.size()>=2){
    v1 = merge_sort(left);
} else {
    v1 = left;
}
if (right.size()>=2){
    v2 = merge_sort(right);
} else {
    v2 = right;
}

このとき、木の高さは  O(logN) なので、配列長が  O(N) であっても、これらの操作は間に合うことが分かります。( 1 \leq N \leq 10^5 くらいの入力の大きさを仮定しています)
素数が1になったら、そこからマージしながらreturnします。

ll i1 = 0;
ll i2 = 0;
ll n1 = v1.size();
ll n2 = v2.size();
vector<ll> ret;
while (true){
    // 両方のインデックスがsize()未満のとき
    if (i1<n1 && i2<n2){
        // 小さい方の値をretに入れる
        if (v1[i1]<=v2[i2]){
            ret.push_back(v1[i1]);
            i1++;
        } else {
            ret.push_back(v2[i2]);
            i2++;
        }
    }
    // 片方だけのときはそのまま入れる
   else if (i1<n1){
        ret.push_back(v1[i1]);
        i1++;
    }
    else if (i2<n2){
        ret.push_back(v2[i2]);
        i2++;
    }
    // 両方の値を見終わったらbreak
    else {
        break;
    }
}

return ret;

マージは、左右の配列のインデックスを進めていきながら、小さい方をretに入れていきました。ここで  O(N) でソートされた配列を構成できるのは、マージ前にすでにそれらの配列がソートされているためです。


帰りがけ再帰なので、まず再帰の一番深いところ(要素数が1)のところまで降りてから  ( O(logN) )、戻りながらマージして  ( O(N) )、マージ後には値がソートされているわけなので、  O(NlogN) でソートを達成することができました。

まとめ

分割統治法は、細かく問題を分割してそれぞれ解いてからマージするという手法です。ソート以外にも使い方があると思うので、調べてみて下さい。自分も、いつか分割統治+FFTを理解します(いつか)

初心者から初心者に向けた焼きなましのすすめ

どうも、tomboです。初めてブログを書きます。

この記事では、焼きなまし初心者が、AtCoderのアルゴやヒューリスティックの問題に焼きなましを適用して解いてみた、ということを書きます。厳密なことはよく分からないので、焼きなましの知識が全くない初心者に、直感的に伝えるみたいなことが目標になっています。それではどうぞ(?)

焼きなましとは

焼きなましとは、ある状態Xに少しの変化を加えてX'(近傍)にして、評価値を計算し、評価値と温度からその近傍を採用するかしないかを決める、ということを繰り返して、大域最適解に近づいていくという感じのアルゴリズムです。これは、山登りと呼ばれるアルゴリズムの拡張です。山登りは、近傍を取りながら、改善したときだけ採用します。それに対して、焼きなましは悪化してもある程度の確率で採用します。採用する確率は、改善した幅(負の場合も含めて)が大きいほど高くなり、スコアの変化が0以上のとき100%採用します。(スコアを最大化したいとき)

ここから評価関数を山にたとえますが、高いとは評価値がいいことを意味するとします。

まず、悪い解を採用するメリットですが、山登りが評価関数の今いる山の頂上で止まる(局所最適解)としたら、あえてそこから脱出することで、大域最適解に辿り着きやすいということです。そうして評価関数上を移動しながら、たまたま大域最適解を含む山に来たとき、遷移確率関数から、山の頂上が高いほど、その山から脱出しにくくなり、少しずつ正解の山の頂上に登っていきます。遷移確率関数は、有名なものがあるのであとで紹介します。その関数には便利な性質があり、自分も初めて見たときはすごいなーと思いました(?)

また、温度は温度関数によって決まり、線形 (1次関数) や非線形 (線形でない関数) のものがあります。これもあとから紹介します。

AHCの問題では、インタラクティブとノンインタラクティブがありますが、焼きなましは主にノンインタラクティブの、盤面を自由に動かせるようなときに使います。理由としては、インタラクティブは操作回数が制限されていて、焼きなましのポイントである大量の試行回数を稼げないためです。それに対して、毎回入力を受け取って何かを出力するようなインタラクティブでは、貪欲やビームサーチ、モンテカルロなどが採用されます。

実際に解いてみる

この記事では、言語はC++を使います。

EDPC D - Knapsack 1

みなさんおなじみ、ナップサックDPです。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]);

という遷移で解けます。(詳細略)
実際の提出(DP)
https://atcoder.jp/contests/dp/submissions/52731892


これを焼きなましで通します。問題を理解していない場合は、一度読んでみてください。まず近傍を考えます。袋に1個追加する近傍と、袋から1個削除する近傍がよさそうです。今回は、袋の重さ上限を超えないようにしています。ギリギリまで詰まっているときには、一回袋から取り出してから別のものを追加しないといけないので、入れ替える近傍もあった方がよさそうです。実際に、addとremoveに加えて、swapをすることでやっと通りました。
実際の提出(焼きなまし) https://atcoder.jp/contests/dp/submissions/47296658

  • add近傍
// 20%の確率で操作を行う
if (rd<20){
    // 採用するindexを乱択する
    ll i = next_idx_add();
    // 袋に入るかどうか
    if (add_ok(i)){
        // 遷移確率を取得する
        double p = prob(value+v[not_having[i]], value, temp)*100;
        // 採用するとき
        if (p>rand(0, 100)){
            // スコアを更新する
            value += v[not_having[i]];
            // 答えを更新する
            ans = max(ans, value);
            // コストを更新する
            cost += w[not_having[i]];
            // 状態を更新する
            having.push_back(not_having[i]);
            //// 後ろに回してからpopするとO(1)
            swap(not_having[i], not_having.back());
            not_having.pop_back();
        }
    }
}

最初に、乱数を取得して、20%の確率でaddをしています。採用するインデックスは乱択しています(next_idx_add)。次に、袋にその荷物が入るかを判定しています(add_ok)。そして遷移確率を取得します(prob)。遷移する場合は、実際に答えと状態を更新します。今回は答えの更新がO(1)でできるので毎回行っていますが、状態のコピーにコストが大きくかかるとき、毎回コピーするとボトルネックになるので、差分更新をO(1)で行って、最後の状態をそのまま答えにすると思います。removeやswapもaddと同様に行っています。

  • 遷移確率関数

これには有名なものがあります。

 probability = e^{\Large \frac{newScore-preScore}{temperature}} \, (eは自然対数の底 \, ( \sim 2.718))
ネイピア数 - Wikipedia

例えば、温度temp=3のとき、以下のグラフになります。

xはnewScore-preScoreということで、スコアの増加分になります(最小化するときはpreScore-newScoreになります)。tempをいろいろ変えてみると、温度が高いときx=0に近づいて、低いとき遠ざかることが分かります。また、newScore>=preScoreのとき、prob>=1になり、遷移確率が100%以上になります。つまり、この関数は「評価値が改善するか同じとき、遷移確率が必ず1以上になり、そうでないとき、温度が高いほど遷移確率が上がる(1未満)」という関数になります。

double prob(ll new_score, ll pre_score, double temp){
    double e = 2.7;
    double p = pow(e, (new_score-pre_score)/temp);
    return p;
}


  • 温度関数

線形と非線形があります。

線形の例

double temp_init = 500;
double temp_finish = 10;
int time_limit = 1980;
double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;

startは開始時の時間計測、nowは現在の時間計測で、now-startで経過時間を表しています。この式は、

 tempInit-tempFinish = coolingWidth

 \Large \frac{now-start}{timeLimit} = \normalsize elapsedTimeRate

とすると、

 temp = tempInit - coolingWidth \times elapsedTimeRate

となり、初期温度から時間経過に応じて冷やしていく、というのが分かると思います。


非線形の例

double temp_init = 300;
double temp = temp_init;
double temp_finish = 5;
double max_iter = 3e5;
double change_rate = pow((temp_finish/temp_init), 1/max_iter);
for (i=0; i<max_iter; i++){
    // 処理
    temp *= change_rate;
}

これは、

tempFinish = tempInit \times decreaseRate^{maxIter}
\\ decreaseRate^{maxIter} = \Large \frac {tempFinish}{tempInit}
\\ decreaseRate = \Large \frac {tempFinish}{tempInit} ^ {\frac {1}{maxIter}}

というように、初期温度にdecreaseRateをmaxIter回かけて、最終的にtempFinishになってほしい、という式を変形して、1回当たり何倍すればよいのかを求めたものです。

競技プログラミングの鉄則 B23 - Traveling Salesman Problem

以降は問題についてのみ言及していきます。

この問題は、巡回セールスマン問題(Traveling Salesman Problem)で有名です。TSPといえばILS(Iterated Local Search、反復局所探索法、山登り+kick)ですね。(文脈を知らない人向け→ https://twitter.com/tombo_choco/status/1707402075540431138)(ほとんどの人が知らないと思います)(はい)
1msでfastestなので、うれしかったです。(bitDPで十分)


というのは置いておいて、まぁとにかくbitDPなわけですが、焼きなましをします(?)


実際の提出(bitDP)
https://atcoder.jp/contests/tessoku-book/submissions/50409603
実際の提出(焼きなまし)
https://atcoder.jp/contests/tessoku-book/submissions/46032854
実際の提出(ILS)(1ms)
https://atcoder.jp/contests/tessoku-book/submissions/46014747


  • 近傍

ランダムに隣り合うインデックスを選んで、順番を入れ替えています。

(参考:2-opt法によるTSP | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】
このような2-optをしたかったのですが、これがそうなっているのかよく分かっていません(そんな)
とにかく、これで通りました。

vector<ll> next_state_rand(vector<ll> v){
    if (N<=3){
        return v;
    }
    ll r = rand(v.size()-3)+1;
    ll tmp = v[r];
    v[r] = v[r+1];
    v[r+1] = tmp;
    return v;
}
double temp_init = 1e4;
double temp = temp_init;
double ans = inf;
const ll max_iter = 1e6;
ll c = 0;

while (c<=max_iter){
    c++;

    // 2-optで焼きなまし
    vector<ll> next = next_state_rand(state);
    double new_score = calc(next);
    ans = min(ans, new_score);
    double p = prob(new_score, score, temp)*100;

    // prob()の確率で遷移する
    if (p>rand(100)){
        state = next;
        score = new_score;
    }

    // 温度関数を更新する
    temp *= 0.999995;
}

今回は、temp *= 0.999995としました。

AHC024 A - Topological Map

これはヒューリスティックコンテストなので、最適解ではないですが、延長戦順位表で1849パフォが取れているので、そこそこ参考になると思います。

この解法には、山登りの前処理が含まれていて、それについても簡単に説明します。

  • 問題の概要

色の連結関係をキープし、色ごとに連結成分を1個に保ちながら、なるべく面積を小さくするというものです。

  • アプローチ
    • 行列削除山登り
    • 隣接侵食焼きなまし

(この2つの語感すき)


まず、行と列で消しても問題ない箇所があるので、それを山登りで削除します。貪欲みたいな感じですね(?)そこから焼きなましに移行します。隣り合うマスに色をコピーします。白いところを塗るのが悪化する遷移、白いマスを増やすのが改善する遷移です。制約を守るのがめんどうですが、3x3マスの中心1マスに向けて色をコピーすることを考えると、結構分かりやすくなります。詳しいことを聞きたかったら、コメントやXなどで質問してもらえれば答えます、自分に答えられる範囲で()

ビジュアライザ

  • 近傍

(山登りは省略)

// その方向から色を移せるか判定する
bool move_ok(ll i, ll j, string dir_from){

    // 変化前の9マスの中心
    ll pre_col = c[i][j];

    // 同じ色に移すときfalse
    if (dir_from=="U" && c[i-1][j]==pre_col ||
        dir_from=="D" && c[i+1][j]==pre_col ||
        dir_from=="L" && c[i][j-1]==pre_col ||
        dir_from=="R" && c[i][j+1]==pre_col){
            return false;
        }
    
    // その色がなくなるときfalse
    if (cnt_color[c[i][j]]<=1) return false;
    

    // 3x3マスをコピーする
    vector new_c(3, vector(3, ll(0)));
    rep(p, 0, 3){
        rep(q, 0, 3){
            new_c[p][q] = c[i+p-1][j+q-1];
        }
    }

    // 実際に色を移す
    ll new_i = 1;
    ll new_j = 1;
    if (dir_from=="U") new_c[new_i][new_j] = new_c[new_i-1][new_j];
    if (dir_from=="D") new_c[new_i][new_j] = new_c[new_i+1][new_j];
    if (dir_from=="L") new_c[new_i][new_j] = new_c[new_i][new_j-1];
    if (dir_from=="R") new_c[new_i][new_j] = new_c[new_i][new_j+1];

    // 変化後の9マスの中心
    ll new_col = new_c[new_i][new_j];
    
    // 色間の連結保持判定
    map<ll, set<ll>> pre_color, new_color;
    rep(p, 0, 3){
        rep(q, 0, 3){
            ll a = i+p-1;
            ll b = j+q-1;

            // 変化前の連結関係
            if (a-1>=i-1){
                pre_color[c[a][b]].insert(c[a-1][b]);
                pre_color[c[a-1][b]].insert(c[a][b]);
            }
            if (a+1<=i+1){
                pre_color[c[a][b]].insert(c[a+1][b]);
                pre_color[c[a+1][b]].insert(c[a][b]);
            }
            if (b-1>=j-1){
                pre_color[c[a][b]].insert(c[a][b-1]);
                pre_color[c[a][b-1]].insert(c[a][b]);
            }
            if (b+1<=j+1){
                pre_color[c[a][b]].insert(c[a][b+1]);
                pre_color[c[a][b+1]].insert(c[a][b]);
            }

            // 変化後の連結関係
            if (p-1>=0){
                new_color[new_c[p][q]].insert(new_c[p-1][q]);
                new_color[new_c[p-1][q]].insert(new_c[p][q]);
            }
            if (p+1<3){
                new_color[new_c[p][q]].insert(new_c[p+1][q]);
                new_color[new_c[p+1][q]].insert(new_c[p][q]);
            }
            if (q-1>=0){
                new_color[new_c[p][q]].insert(new_c[p][q-1]);
                new_color[new_c[p][q-1]].insert(new_c[p][q]);
            }
            if (q+1<3){
                new_color[new_c[p][q]].insert(new_c[p][q+1]);
                new_color[new_c[p][q+1]].insert(new_c[p][q]);
            }
        }
    }
    // 色の連結性が違ったらfalse
    if (pre_color!=new_color) return false;

    // 同一色の連結保持判定
    // 変化後の色ごとの連結成分の個数が2以上でfalse
    used.clear();
    rep(p, 0, 3){
        rep(q, 0, 3) seen[p][q] = false;
    }
    rep(p, 0, 3){
        rep(q, 0, 3) if (used.count(new_c[p][q])==0) dfs(p, q, new_c);
    }
    rep(p, 0, 3){
        rep(q, 0, 3) if (seen[p][q]==false) return false;
    }

    // 色を移すことができる
    return true;
}

近傍というか、遷移できるかどうかの判定になっています。近傍は座標を乱択しています。

// 同一色の連結保持判定
// 9マスの中で色ごとに連結成分の個数を数える
void dfs(ll p, ll q, vector<vector<ll>> new_c){
    seen[p][q] = true;
    used.insert(new_c[p][q]);
    if (p-1>=0 && new_c[p-1][q]==new_c[p][q] && !seen[p-1][q]){
        dfs(p-1, q, new_c);
    }
    if (p+1<3 && new_c[p+1][q]==new_c[p][q] && !seen[p+1][q]){
        dfs(p+1, q, new_c);
    }
    if (q-1>=0 && new_c[p][q-1]==new_c[p][q] && !seen[p][q-1]){
        dfs(p, q-1, new_c);
    }
    if (q+1<3 && new_c[p][q+1]==new_c[p][q] && !seen[p][q+1]){
        dfs(p, q+1, new_c);
    }
}

同じく、遷移できるかどうかの判定です。条件としては、色の連結関係が変わらないか、連結成分が1個であるかの2つがあるので、近傍を乱択してから判定してOKだったら遷移しています。

double temp = temp_init-(temp_init-temp_finish)*(now-start)/time_limit;

温度関数は線形ですね。遷移確率関数は上と同じです。ちなみに、乱数生成器はmt19937(メルセンヌ・ツイスタ)を使っています。

mt19937 mt(now());
ll rand(ll a, ll b) {
    if (b<=a){
        cerr << "RandRangeError" << " a:" << a << " b:" << b << endl;
        return -1;
    }
    return mt()%(b-a)+a;
}

実際の提出 https://atcoder.jp/contests/ahc024/submissions/49364292


以上で3つの問題への、焼きなましを使ったアプローチの説明を終わります。自分は、焼きなましには圧倒的なパワーがあると思っていて、GA(遺伝的アルゴリズム)のように時間がかからず、ビームサーチより汎用性が高い気がして、すごく便利だと思っています。雑に殴ればいいじゃんてきな?いや、分からないですが、楽しいのでぜひぜひって感じです。

おまけ

  • 動きが悪かったら評価値の変化が小さいかもなので100倍とかしてみてください、動きがある程度大きい方がよく解空間を探索できてうれしいです。初期温度も高くしてみてください。
  • 温度は自分は線形のものを使っています。
  • アルゴがACできると楽しいです、特にDPは割といけると思います、EDPCとか。

まとめ

いかがでしたか?(言いたいだけ)
いろいろガバかったらすみません、これはあくまで自分の感想を共有するみたいなノリで軽く眺めてほしくて、本格的に焼きなましをやりたかったらrhooさんの記事(p/tech/.md at main · rhoo19937/p · GitHub)とかも参考になると思います。C++の実装が読みにくかったり、質問があったり、間違いの指摘などがあったらどんどん言ってもらえれば、自分に対応できる範囲でいろいろやります。これからもなにか思いついたら書いていくかもなので、またよろしくお願いします(?)