- 0.はじめに
- 1.問題文の概要
- 2.問題の第一印象
- 3.最初にやることと1日目の考察
- 4.2日目の考察と実装（乱択山登り）
- 5.初提出
- 6.スコア計算で閉路検出を書きたかった（けど書けなかった）
- 7.ローカルで100テストケースをまわす（4日目）
- 8.スコア計算ができて貪欲を考えた（けど書けなかった）（5日目）
- 9.ビームサーチとchokudaiサーチを使って、評価関数を考えた（けどできなかった）（6日目）
- 10.決戦は金曜日（コンテスト終了まで残り3日）
- 11.ラストスパート（2022年6月4日。残り２日）
- 12.コンテスト最終日
- 13.最終結果（2022/6/7更新）
- 14.コンテストを終えて
- 15.おまけ（おすすめ資料）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴2年半のかえでです。
今回は11回目の開催となるAtCoder Heuristic Contest 011に参加しました。開催期間は2022年5月28日(土)12:00から2022年6月5日(日) 19:00までと長期コンテストになります。
この参加記は、コンテストの期間中に、自分がどんなことを考えて、どんなことをしたのかをリアルタイムで書いています。（そのため、どうしても冗長な部分があります。そんなときは適度に読み飛ばしていただけるとうれしく思います。）
「ヒューリスティックコンテストって何？」という人も、これを読めば、コンテストに参加した気分を味わっていただけるのではないかと思っています。
「役に立つ」とか「価値がある」参加記を書こうと思っているわけではありません。役に立つ記事を書いてくださる方は他にたくさんいます。それでも私が参加記を書いて公開しようと思うくのは、限られた知識で良い得点を出そうともがいたり、苦しんだり、とび上がって喜んだりと、喜怒哀楽する私の姿に、「面白そう。自分も参加してみようかな」と思ってもらうことです。もしこれを読んだ人が次のコンテストに参加してくれたら、本望です。
そして、今回も楽しい問題を作ってくださったwataさん、いつもありがとうございます！これからもますますAtCoderのヒューリスティックコンテストが盛り上がっていくことを心から祈っています。
それでは、コンテストの開始です。
と言いたいのですが、本日の日付は5月27日。明日の正午からコンテストが始まります。毎回、問題文を誤読したり、バグらせて時間をロスしているので、早くも緊張しています。この「緊張する」性格のせいで、これまでどれだけ失敗してきたかを思うと残念な気持ちになりますが、しょうがありません。
明日の私のためにメッセージを書いておきたいと思います。
・問題文はよく読みましょう。
・実装する前に、考察をきちんとしましょう。
・テストケースは1000個用意しましょう。（これまでは100個でした。）
・貪欲と乱択、焼きなましとビームサーチは全て試しましょう。できれば、BFSとDFSもやりましょう。
・評価関数をきちんと考えましょう。
これだけできれば、そんなに悪い結果にはならないと思うのですが、さあ、どうなるのでしょうか。
1.問題文の概要
コンテストがスタートしました。現在の時刻は2022/5/28、14：20です。連日の睡眠不足で、心身ともに体調はよくありません。（CodinGameというゲームAIの常設コンテストにハマってしまい、連日睡眠を削ってコードを書いていました。）今日は12時過ぎに問題文を見たものの、そのあとは仮眠を取っていました。
起きたので、問題に取りかかります。問題のタイトルは「Sliding Tree Puzzle」。
簡単に問題文の概要を箇条書きにしてみます。
・縦N枚×横N枚のタイルが並べられ、そのうち、ひとつだけタイルが抜いてあります。
（したがって、タイルの総数は（N×N－１）枚です。）
・タイルが空いている場所に上下左右のいずれかのタイルをずらして、描かれた絵を元に戻すことを目指します。
・絵の種類は１６種類（そのうち0は空きマスを表す）。
タイルの絵（AtCoder問題文より引用）
・一回に動かせるのは上下左右のタイルひとつで、最大Ｔ回（=2×Ｎ×Ｎ×Ｎ）まで動かすことができます。
・絵が完成していないときは、閉路を持たない最大の木の大きさを元にして得点を出します。絵が完成している場合は、さらに操作回数が少ないほど得点が高くなります。
・得点を求める式は以下の通りです。
得点の算出方法（AtCoder問題文より引用）
問題文の「例を見る」からWeb版ビジュアライザを見ます。
例を見る（richモード）
ビジュアライザを見るとどんな問題かがわかりやすくなります。
また、使い方が記述されているので、詳細はWeb版ビジュアライザを見てみてください。親切さは前回のAHCよりもさらに増していると思います。
つながっている最大の絵（木）の色が茶色で濃く表示されています。この場合、絵は完成していないので、S<N×N-1の場合となり、連結している最大の頂点数、すなわち14枚が連結しているので、500000×S/（N×N-1）=200000が得点となります。
2.問題の第一印象
ここで思ったのは、Ｔ回以内に全部を連結することがまずは第一の目標であり、その後その手数を短くしていくという２段階に問題が分かれているように見えました。入力の生成で、木になる（すべてが連結できる）ことが保証されています。制限時間は３秒です。まずは第一段階、全てのタイルの絵をつなげて、ひとつの絵にすることを目標とすることにしました。
スライディングパズルが、ヒューリスティックでよく扱われる問題だというのは、最近読んでいた文献に載っていたので、まずは、検索をして文献を探します。Ａ*アルゴリズムを用いて探索することができればと思いました。
3.最初にやることと1日目の考察
いつも他の人の提出を見て、焦ってしまいます。そして順位表を眺めているうちに時間が経ってしまいます。また、Twitterを見ては、他の人はどこまで進んでいるのだろうかと気になってしまいます。時刻は5/28の16：15ですが、Twitterで共有されていたseed0のビジュアライザを見ていたら、もう全てを連結して絵を完成させていました。早い！
他の人がやることを見ているだけでは進まないので、えいやっと順位表を閉じました。その後はTwitterを閉じました。今回はできるだけ、自分の世界に入りたいと思います。
まずはビジュアライザ用のツールをダウンロードします。前回からWindows用のコンパイル済みバイナリを使っていますが、Rust言語のローカル版もダウンロードします。こちらに入っているlib.rsファイルには必ず目を通しています。Rustは未履修なのですが、スコアの計算式等は、問題文の数式を理解するよりはわかりやすい気がしています。
また、私はC++を使っていますが、今年に入ってからクラスを使ってきれいなコードを書くことを心掛けています。今回は特に高速な探索を視野に入れているのでなおさらです。
まずは、入力の受け取り、得点計算用にUnionFindで連結成分の最大頂点数を返すメンバ関数、上下左右に一手動かすメンバ関数、スコアの計算、出力を書きます。
入力を受け取った後は、「４方向に一手動かし、UnionFindを構築し、スコアを計算し、一番良い方向に進むをＴ回になるまで、もしくは2500msec制限時間いっぱい繰り返すこと」をしたいと思います。Greedy（貪欲）です。
-（時間経過）-
上のように、時間が経過している間に、家事とか育児とかをしているのですが、そのときも考察を進めています。（うわの空で家事をやっているとも言えます。）考えていたら、自分のやろうとしていることは山登りだなと思ったので、もうちょっと楽な方法から試すことにしたいと思いました。
- 進める方向にランダムでＴ回分動く。
- UnionFindで連結成分の最大頂点数を計算して、スコアを計算する。
- これを2500msec繰り返して、一番得点の良かったものを出力する。
この流れでコードを書いていきたいと思います。
それから、タイルをどんな風に使って行けば良いのかよくわからなかったので、グループ分けをしてみることにしました。これらのタイルは回転することはないので、端に置いてはいけないタイルや、逆に隅や端にあると良さそうなタイルもあるなと思います。まだよくわからないままなのですが、十字のタイル（f、1111)は端に置いてはいけないということは言えそうです。
4.2日目の考察と実装（乱択山登り）
２日目です。昨晩は提出できませんでした。
昨日は21時からのNOMURA プロコン2022（ABC253）に参加をしたのですが、4問解けてレートが759に上がりました。実は750以上にレートを戻したのが4か月振りなので、とてもうれしいです。一時は639まで下がったので、本当にこつこつとがんばってここまで戻して来れました。「自分はまだ成長できるのか」ということを常に自分に問いかけ続けているので、良い結果が出ることは励みになります。
話をAHCに戻します。順位表を見ました。現在一位のmaspyさんの得点が38,307,047でした。これをテストケースの50で割ると、約766,140。これが何を表すのかというと、木の大きさSがNの2乗-1の場合の得点になります。すなわち絵が完成していると50万点なので、さらにタイルを動かす回数を少なくしてしていっている状態だとわかります。高得点争いに加わるためには、まずは木を完全に復元する必要があって、その先でさらに最短を求めていく必要があるということになります。
これを見て、まずは木の復元をスライディングパズルとは別の方法で解いた方が良いのかもしれないと思いました。スライディングパズルと今回の問題の差異を考えます。スライディングパズルは出来上がりの盤面が決まっている代わりに１対１の対応でGoalの盤面に動かす必要があります。しかし、今回の問題では同じ種類のパーツが複数あるので、Goalの盤面を作った状態から、同じ種類のパーツをスワップして、最短が短くなるなら更新する、みたいなことを時間いっぱい繰り返すことが必要な気がしています。
①Goal盤面をできるだけ早い方法で復元する。
②最短でなくても良いのでGoal盤面を作成する経路を作り、短くなることを目指す。
これを最終目的にしたいと思いました。
ということで、まずは昨日考えた方法で１回目の提出を目指します。
-（時間経過）-
夜です。時刻は23時半。何だかバグっています。いつものことですが。乱択山登りの最初の盤面とスコアは合っているのですが、そこからの遷移がおかしい状態です。ただ何も進捗がないかといえばそうでもなくて、今日はかなり深く考察ができている時間があったので、楽しかったです。また、バグっていますが、一通りコードは書き上げました。早く提出したいです。今日はここまでにしたいと思います。
5.初提出
今の時刻は2022/5/30の朝6時15分です。
昨日はベッドに入っても、なかなか寝付けませんでした。脳内で考察が止まりません。自分の書いたコードを思い出しては、あそこを書き直してみたらどうかな？とか、いったいどこが間違っているのだろう、起きてコードを書こうかと思い悩みます。今何時だろうと時計を見るたびに30分から1時間くらいずつ進んでいました。熟睡した感じは一切ありません。寝たのかよくわからないまま、時計を見ると5時を過ぎていたので、起きることにしました。
あやしい部分を出力してデバッグします。そして、ついに見つけました。
バグっていたのは、2回目以降のときに、スタート位置を最初の位置に戻すのを忘れていたからでした。さて、いくつかのseedで出力結果をビジュアライザで確認し、スコアが出ていたので、提出することにしました。しかし結果は50ケース全てWA。どうして？
出力を確認します。あ、と原因はすぐにわかりました。
ループ回数をカウントしていたのですが、それをcerrではなくcoutで出力していました。
書き直して再提出を試みます。提出は30分間隔という制限があるので、あと18分待たなくてはなりません。この時間が、とても長く感じます。それでもきっと正の得点が出るはずです。どんなスコアが出るのかとわくわくしてきました。
まだ閉路を検出する部分を書いていないので、実際のスコアは自分の計算したスコアより低くなることが想定されますが、それでもランダム解の山登りを書けてうれしく思います。テストケースを1000回まわしてから提出しようとコンテスト前は思っていましたが、とりあえず正の得点が欲しい！という目先の欲にとらわれてしまいました。
次からはせめて100ケースはスコアを出してから提出したいと思います。
得点が出ました。8,456,306点でした。ほぼ予想通りなので、書いたコードに問題は無さそうです。
ACできてほっとしたせいか、今とても眠いので、少し仮眠を取ろうと思います。朝はここまでです。起きたら仕事です。金曜日、有給を取ろうかな。以前、他の人がお休みを取ってAHCをやっていたのがうらやましかったので。
6.スコア計算で閉路検出を書きたかった（けど書けなかった）
5/30の夜です。閉路の検出をできるようにしたいと思います。
難しい...。
ALGO ARTIS プロコン2022（AHC010）では閉路を求める問題だったので、問題文の環状線の長さの求め方のヒントを熟読することにしました。
とりあえず真似をして書いてみます。
う、難しい...。
-（時間経過）-
閉路検出がうまく書けなかったので、今朝の提出を少し変えてみることにしました。これが今朝提出した内容です。
- 進める方向にランダムでＴ回分動く。
- UnionFindで連結成分の最大頂点数を計算して、スコアを計算する。
- これを2500msec繰り返して、一番得点の良かったものを出力する。
①「進める方向にランダムでT回分動く」かわりに、「ランダムで1回動く」をして「スコアを計算し」良いものに取り替えながら、T回分動くコードに変えたいと思います。
②それとも「合法手の中から一番スコアの良いもの」を選択し、変わらないときはランダムで動くにしようかな。
この２段階を試したいと思います。
（…閉路検出はしないとダメ…。後からやります。）
①は5分で書き終えました。やってみたけど、最初の提出よりパッとしない感じでした。配布されているツールのvis.exeを使用して最初の提出とのスコアを比較したいと思います。
100ケースのスコアの総和を2で割った値は今朝の提出が8474497.5点、①が5142265点でした。①を時間いっぱいまわしてみても8260015点だったので、あまり良いアイデアではなさそうです。②に移りたいと思います。
なぜ2で割ったかというと、提出すると50ケースの合計でスコアが出されるので、提出した際のスコアを想像できるからです。（自分の初提出のスコアは8456306点でした。）
＜今日の夜やったこと＞
・ローカルでのテストケース連続処理用に、テキスト入力、テキスト出力のコードを追加。
7.ローカルで100テストケースをまわす（4日目）
2022/5/31の朝です。連日眠れていなかったせいか、さすがに熟睡できました。でも朝4時に目が覚めたので2度を寝したら、会社で怒られる夢を見て起きました。こわかったです。（直属の上司に体調不良を訴えて早退したら、翌日にもっと偉い人から勝手に早退するなと怒られる夢。←現実のことではありません。）
さて、昨日出したスコアは自分の計算したスコアだったので、配布されたツールをバッチファイルで連続処理して、実際のスコアと比較したいと思います。（閉路検出をしていないので、実際のスコアの方が低いはず）
ところで、余談なのですが、全部で500行ほどコードを書いているのですが、メイン関数は12行です。クラスのメンバ関数を呼び出したりするのも別の関数にしているので、かなりシンプルに書けているのではないかと思っています。書き直したり、組み合わせたりするのにとても良いです。
コードの書き方は「世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門」を参考にさせていただいています。
昨日出力した100ケースの実行結果を配布されたツールで処理してみました。
今回は100で割って、1つのスコアで比較します。自分の計算結果の平均は約170125だったに対して、実際のスコア平均は約149611でした。50ケースとすると、約8506268と約7480549になります。13％ほど差が出ているので、何とかしたいと思います。閉路検出を行えば、これくらい上がるのか、それともスコアの計算のしかたが間違っているのか、調べなければと思いました。
それでは、お仕事に行ってきます！
-（時間経過）-
帰宅しました。夜です。
100テストケースの出力から、自分のスコアと実際のスコアを比較してみました。
合っているものが1割しかなかったので、スコア計算を見直したいと思います。表がわかりづらいのですが、55個のケースで、実際のスコアの方が自分の計算値より高く出ていました。これはスコアの計算が間違っている可能性が高いです。低く出ているのは閉路検出ができていないせいなのではないかと思いました。
これからやりたいことは次の３つです。
・スコアの計算を見直す。
・閉路検出コードを書く。
・貪欲を書く。
-（時間経過）-
あーだーこーだーの録画を見ながら、「今日の一問」を解いていたら、眠くなってしまいました。今日は寝ます。（私はAtCorder ProblemsのLongest Streakを続けていて、現在828日連続新規ACをしています。だいたい1問を解くのに毎日1時間くらいを勉強に費やしています。)
8.スコア計算ができて貪欲を考えた（けど書けなかった）（5日目）
2022/6/1の朝です。閉路検出用の配列をAHC010を見ながら書いています。分岐が複数あるのがAHC010と異なる点で、それをうまく書くことができずに悩んでいましたが、完全に現在のタイルを表せなくてもいいかという気持ちになったので、とりあえず動くコードを書く方向に頭を切り替えました。
Twitterでは、タイルの絵を完全に復元できる人が増えてきていて、とても楽しそうです。自分もその仲間に入りたいなと思います。適当にやっても、できあがり図は一つではなく何パターンかありそうなので、意外に絵を復元できるのではないかというのが今の予想です。
あれ？今「閉路検出」を検索してみたら、UnionFindでできると書いてありました。
今書いているコードを少し変更すれば、このまま使えそうです。AHC010の疑似コードをこのUnionFindに足したら、精度が良くなりそうなので、変更したいと思います。また、このUnionFindでスコアを計算していたのですが、辺をつなぐ判定がすごく適当だったことに今気がつきました。スコアの計算で、自分のスコアが低く出ていた意味がわかった気がします。
UnionFindのコードを変更した後は貪欲を書きたいと思います。今より良い点数が出るのは間違いないので。未だに貪欲を書き終えて行けないのはいけない気がしてきました。
＜本日（6/1）の目標＞
- UnionFindに閉路検出を追加、辺をつなぐ判定ををきちんと書く
- 貪欲を書く
そういえば、ふと思い出したのですが、順位表も毎日見ているし、Twitterも見ていました。やめるって言った自分は何？と思いますが、気になるものは気になるので、しょうがないですね。人間らしい自分を認めて、がんばっていきたいと思います。
さて、１個目の目標はクリアです。
一時間もかからずに、意外にあっさりと直せました。
タイルどうしがつなげる場合の条件を、左右のタイル、上下のタイルを全てORで列挙して書きました。また、UnionFindで辺をつなぐ際に、ループになる場合は、スコアを0にしました。その結果、実際のスコアと自分の計算値の差が±1以内になりました。
やったぁ！（←というか最初からきちんと書きましょう。いつも反省している気がします。成長しない自分。）
また、現在の平均試行回数も出しておくことにしました。約3811回でした。（長さTのランダムな操作文字列を作って、スコア計算を行う山登りを2500msec行っています。）
-（時間経過）-
6/1の夜です。5/30に書いていたコードが全く見当違いだったことに気がつきました。
①「進める方向にランダムでT回分動く」かわりに、「ランダムで1回動く」をして「スコアを計算し」良いものに取りかえながら、T回分動くコードに変えたいと思います。
上の文の「良いものに取りかえる」ことを全くしていなかったことに気がつきました。
DL（下左）という進み方ができたとき、LD（左下）という進み方は必ずできるはずで、１マスだけ変えることができるということに、いまさらながら気がつきました。
なので、下のような方法でもう一度試したいと思います。
①’ランダムで長さTの文字列を作る。その後、ランダムで隣同士を一か所入れ替え、スコアを計算し、良くなっていたら取り替えるを時間いっぱい繰り返す。
-（時間経過）-
ん、やっぱり難しい。
手元にスライディングパズルがあるので動かして観察します。やっぱり２個入れ替えるだけでは済まなそうです。
貪欲に戻りたいと思います。
-（時間経過）-
そこまで時間をかけずに、なんちゃって貪欲を書きました。
合法手の中で「最初に連結できるタイルと分かった方向」を選ぶです。
スコアを計算すると1ケース平均約1746738。提出したとしたら、約8733690で微増。うーん、イマイチです。
ビジュアライザで確認します。同じ場所を行ったり来たりしていました。あとスコアの計算を入れていませんでした。もう一度書き直すことにします。
スコア計算を入れたら、かえってスコアが下がりました。1ケース平均1656983。50ケース8284916相当です。う-ん...。
そして、行ったり来たりしないようにするにはどうしたらよいのでしょうか…。
seed0のビジュアライザを見ます。
端に来てはいけないタイルがあるので、端に置けるタイルを限定してみようかと思います。
合法手にこれを入れると、選択肢がゼロになってエラーが出る場合があったので、そのときは全部OKにしました。100ケースを回すと、初めて30万を超えるものが出てきました。逆にこれまで見たことのない3万点といったスコアも出てきました。平均すると1662448、50ケースで8312241。ならしてみると、これまでとほぼ変わらない結果になりました。残念。ただビジュアライザで結果を見ると、悪い考え方ではなさそうだと思いました。
スコアの悪かったものを見たら、答えが出力されていませんでした。バグっているのかもしれません。見直してみます。合法手より、貪欲の条件に入れた方が良さそうだなと思ったので変更します。
-（時間経過）-
「今日の１問」を勉強してきました。今日の自分の自由時間はこれで終了です。続きはまた明日。おやすみなさい。
＜明日やりたいこと＞
・貪欲の条件見直し。
・進入方向を入れる。
・提出をしてスコアと順位を上げる。
余談：コンテスト参加者がだいぶ増えていました。私が提出したときは545人でしたが、6/1の23時は721人に増えていて、194位だった順位は312位まで落ちていました。（まだ乱択解しか出せていない自分が悲しい…。）
9.ビームサーチとchokudaiサーチを使って、評価関数を考えた（けどできなかった）（6日目）
2022/6/2の朝です。順位表を見ました。1位は42,413,042 。すごい！
上位陣がTopcoder Marathon Matchでも常連の方たちになってきています。
これは、ビームサーチかchokudaiサーチをしたい！
実は、１か月ほど前に正しく動かせているのかどうかはわからないものの、ビームサーチやchokudaiサーチを使えるようになりました。
やっとビームサーチが動いた～！！！
— かえで (@kaede20203) 2022年5月8日
priority_queueにクラス入れて、operatorで判定して、幅と深さ決めて上から取っていけばいいはずと思ってから、実際に動くコードが書けるまで、本当に長かった…
…感動した
ただ、評価関数が難しくて、良い結果を出すというところまでは全然たどりつけていなかったり、高速化ができなかったりと問題点はたくさんあるのですが、それでも今回もちゃんと使えています。進歩！
話を今に戻します。というわけで、昨日は合法手に入れて失敗した条件（一番外側のマスにマスの外側につなげる必要があるタイルを置かない）を評価関数に入れてみようと思います。
あと、やはりできあがり図を最初に作りたい気がします。左上の(0,0)位置に置けるタイルは3種類なので、それぞれをスタートとしてパズルを作ってみると完成形を作れないかなと思いました。
「一番外側のマスにつなげる必要があるタイルを置かない」を置いたら減点を評価関数に入れてみましたが、何かイマイチでした。
次に、評価関数で、隣同士のマスで、つながらない部分とつながらない部分が隣り合っているときに加点することにしました。連結している部分はスコアで評価されていますが、良い形を評価できるかなと思いました。
あと、ビームサーチです。ビーム幅と深さは適当。
今の状態だとあまり変わらないようです。
あ、評価関数がまだでした。帰ってきたら続きをやりたいと思います。
・評価関数で、隣同士のマスで、つながらない部分とつながらない部分が隣り合っているときに減点する。
・UnionFindの連結グループの数に応じて、少ないほど加点。
・UnionFindの連結グループの頂点数が1以外だったら加点。
などを考え、ブレンド具合を変えてみましたが、これというものにはたどり着けませんでした。
下の図は、seed0のビジュアライザです。
下の表は、評価関数を変えた時のスコアを100テストケースをまわして調べました。
そういえば、気になるseedを見つけました。seed54です。N=10の今回の最大盤面です。全然できていませんでした。これ、完成させられる日が来るのかな...。
10.決戦は金曜日（コンテスト終了まで残り3日）
2022/6/3金曜日です。昨日の夜はブログを書き忘れていたので、「9.6日目」の途中から6月3日になっています。（こっそりお伝えすると、起床は5時です。）
A「やせたんじゃない？」
— かえで (@kaede20203) 2022年6月2日
B「うん、やせたね。何してるの？」
競プロer「競技プログラミングのコンテスト中だね。長期の。」
A「えー、コンテストに出るだけでやせるの？わたしも出るー！」
B「頭使うからかなー？」
競プロer「...（寝食忘れるから）」
競プロはダイエットの役に立つ
（既出）
twitterと事実はちょっと違っていて、実際は「ただやつれているだけなのでは？」（やせた自覚無し）と答えたのですが、「そんなことない。やせた。」と返ってきて、会話が終了しました。もちろん、ダイエットをしたいなら正攻法をおすすめします。
ただ今の時刻は午前10時です。
あれ？仕事は？と思ったあなたは正しいです。
そう。本日、有休休暇を取得しました。
今日は一日AHCをやるぞー！！！
Twitterでたまに見かけたAHC休暇を取っている方がうらやましかったので、前からやってみたいと思っていました。休んでみてわかったのですが、かなり贅沢気分を満喫しています。
さて、今日は昨日考えていたことを実装したいと思っています。
何を考えていたかと言えば、マス目の(0,0)から順番に埋めていったらよいのではないかということです。空きマスを動かすというのがちょっと難しいとずっと思っていたのですが、必要なタイルの隣まで動かした、必要なタイルの動きのひとマス前を空きマスが先導すると思えば良いのかと思っています。そして、空きマスを動かすときに、これまで揃えていたタイルが崩れることに頭がついていかないと思っていましたが、左上から確定していけば、それなりの数はつなげられるのではないかと思いました。
＜6/3の目標＞
①スタート位置の空きマスから、スタート位置に置ける３種類のタイルのうち一番近くにあるものを見つけて（0,0）に持って行く。
②最初のタイルにつながる、空きマスから一番近くあるタイルを探して、隣に持ってくる。
③以下つながるものがあるうちはつなげる。終端まで来たら、つながるところでつながっていないタイルの位置まで戻る。（この辺の実装は考えていない）
④②'と同じ
⑤右下までいったときに全部できていればOK。できていないときは、ダメなタイルのところまでいって、全探索でハマるところを見つける。（この辺の実装は考えていない）
こんな感じでしょうか。
がんばりたいと思います。まずは朝ごはんを食べます。（←え、起床後5時間経過していますが…。これがやせる原因？）
そういえば、時計回り、反時計回りをすれば崩れても元に戻せるイメージができてきたので、ある程度できあがったら、途中に別のマスを入れる実装もしてみたいと思います。（これができるとかなりスコアが良くなりそう）
あ、ところで、昨日何をしていたかを追記しておきたいと思います。
一つはビジュアライザのマニュアルモードで手動でパズルを完成させようとがんばっていました。
下の図の「manual mode」にチェックを入れると、矢印キーで空きマスを動かすことができます。
自分でやってみてわかったのですが、パズルが難しくて、制限手数以内に完成させることができませんでした。そのときに自分で左上から一つずつそろえていく方法を試してみたのですが、そうすると確定したところをいじらずにある程度埋めていけることがわかりました。
もう一つは、問題文の「共有された画像の一覧」から見ることのできるseed0のビジュアライザ画像を見ていました。
当初から予想していたことではあったのですが、本当にいろいろな「木」がありました。（一段目の右端２段目の左端が同じ盤面だったくらいでしょうか。）また、見た中での最高得点は873843点でした。これは6×6盤面を109手で完成させた得点になります。（制限回数の上限は432手）すごい！
-（時間経過）-
スライディングパズルの解き方を検索してみたら、左上から揃える方法が載っていて、最後の２個だけ順番を変えればよいと書いてありました。え、そうなの！？と驚いてしまいました。最初から調べればよかった。ちょっとマニュアルモードで解いてきます。
午前中よりはきれいな形にできたかもしれません。一番上の行をそろえたあと、下の図の①、②、③のように３か所連結する部分ができました。これをどこから続きをしたら良いのか迷いました。③からやったのですが、すぐに①、②が邪魔になってしまいました。一番上の行を揃えたあとの空きマスは③にありますが、２行目は①からスタートするのが良いのかなと思いました。
ここで思い出したのはf(1111)の十字のタイルの置き場所が難しかったことです。
先ほど集めた完成した木の図を見ていたのですが、四隅にこの卍の形を置くことにすると安定して使えそうだと思いました。
-（時間経過）-
お、いい実装を思いつきました。「１回で５手進むくん（仮）」です。目的のタイルをひとマス進めようとすると、空きマスが一周する必要があります。
書いてみたら思ったより良さそう。上に行きたいときだけでなく、左右と下も後で書いてみたいと思います。
もう今回は（いや、今回も）実装が大変だと思って、くじけそうになること複数回。（このブログでも、時間が経過しているところはだいたいくじけています。）
これなら書けるかも。使うときには、
・動かしたくないマスを含んでいないか
・範囲外のマスを通ることになっていないか
を判定してあげれば良さそうです。
最短ではなさそうですが、もうそれは後回しにします。
ん？この動き、できあがった文字列を入れ替えるのに使えないかな？？？
え、いけそうかも。できあがった文字列の「DR」と「RD」を入れ替えて、A,B,Cのマス目のタイルを動かせばOKそうですね。右下（RD）の入れ替えを山登りに使ってみて良くなったら、右上（RU）、左上（LU）、左下（LD）の３種類も作ってみたいと思います。
あと、「LRL」とか重複した動きの文字列を削除するのも良さそう。短くなったら文字列を足しても良いし。
おおー、横道に逸れているような気もするけど、最初にやりたかったことだから、進んでみようと思います。
書き始めて気がついたのですが、差分を取るのは高速化のときでした。
ということは、
・隣り合った文字列を一か所交換する
・盤面を進める
・評価再計算（全部計算）
をやって、
・隣り合った文字列を一か所交換する
・盤面を進める
・評価再計算（差分のみ）
をやれば高速化できて、ぐーんと得点がアップするのかな？
これは今日のうちに試しておきたい。間に合うといいな。
今書いたことは、AHC011が始まる前に解いていた、 過去の「HACK TO THE FUTURE 2018予選 山型足し算」で同じことをやりました。「競プロ解法紹介～レベル別マラソンの戦い方～」で解法が詳しく説明されていて、それを見ながら真似をしたのですが、とてもわかりやすくて勉強になりました。
高速化していないけど、コードを書き上げました。100ケース回したスコアです。
おおー、上がっている！改善しているのが、テストケースを回しているときからはっきりとわかりました。
やった！久しぶりに提出できます！はぁ、よかった！！！
ドキドキします。
スコアは14,037,336、順位は282位でした。順位は400位近くまで落ちていたので少し持ち直しました。
- 提出（3回目）メモ
・100回ランダム盤面を作って一番スコアのよかったものを初期盤面とする。
・ランダムで２文字をスワップする。
・評価関数は実際のスコアのみ。
・平均試行回数3万回くらい
この文字列スワップをしたときにエラーが出るものがあって、何か調べたら、「UD」「DU」「LR」「RL」でした。確かに、「上下上」ならOKでも、「上上下」はダメな場合がありそうだと気がつきました。ということで、合法手で重複を除く方法がやっとわかったので実装してきます。
重複を除いただけで、だいぶスコアが良くなりました。もう一度提出してきます。
うれしい。（涙）
そして、全然できていなかったseed54がここまでできていました。
感慨深い…。
今回の目標、そういえば、最初に書いたきりでした。
今設定するとしてもやはり各テストケースで50万点を出すこと。提出で25,000,000点を出すことです。全部の「木」を完成させたいです。
まずはseed0でパズルを完成することを目指したいと思います。
余談ですが、先ほどの提出で、制限時間を2500msecから2800msecにしてテストケースをまわしてみました。良くなるかと思いましたが、変わりませんでした。なぜ？やはり山登りの限界なのかな。評価関数を復活してみる？焼きなまし？悩みはつきません。
それでも、今日はがんばりました。
今日のAHCは終わりにして、今から「今日の1問」の勉強をして寝ようと思います。今日はABC253のE問題の復習です。snukeさんの解説放送がなければ、AtCoderを続けることができなかったと思います。いつも感謝しています。
11.ラストスパート（2022年6月4日。残り２日）
2022/6/4の朝です。今日は土曜日。明日の日曜19時がタイムリミットです。
明日になると気持ちが焦って進まなくなると思います。
提出が30分間隔であること、最終提出でシステムテストが行われるため、ぎりぎりでの提出がハイリスクだからです。自分の心配性な性格をプラスすると、かなり余裕を持って終わることになると思います。
さらに話がそれますが、コードを書いているときはずっと音楽をかけています。今回はボカロ100選を流しています。
松阪 on Twitter: "ワイのボカロ100選です！！！… "
この中で気に入った曲が、あめのむらくもPさんの「他人事の音がする」です。だから、AHC011の自分のテーマ曲はこれです。いつかこの先、この曲を聴くと、AHC011を懐かしく思い出す日が来るのだと思います。
話を戻します。
下は昨日の提出のseed0のビジュアライザ画面です。
-（時間経過）-
やっぱり盤面評価を加えて、ビームサーチかchokudaiサーチをしよう！
うん。制限時間を10秒にしてもスコアは上がらなかったから、得点だけでは完成形にたどり着けなさそう。
相変わらずビームサーチとchokudaiサーチはうまくスコアが上がりません。
評価関数を前半はUnionFindのグループが少ないように変えてみました。
100ケース回した平均は変わりませんでしたが、ついにseed70で40万点を達成していました。スコアは提出してみても微増くらいか変わらないくらいだと思うのですが、提出してみることにします。
お、ちょっとスコア上がった♪
何かよくわからなくなってきたので、休憩したいと思います。
（ただいまの時刻は朝の８時。本日も起床は５時です。）
-（時間経過）-
休憩という名前の家事タイムで、どちらが休憩かは傍から見ると逆だろうなと思います。
さて、その間に何を考えていたかといえば、順位表に並ぶ得点です。現在のトップは44,337,283です。今のまま少しずつ改善を加えていけば私のスコアもまだ上がるとは思うのですが、劇的に伸びる感じはしません。何か違う気がしています。
今考えているイメージは、やはり左上から確定していって、探索範囲を狭めていき、右下までたどりついたとき（全て確定したとき）にパズルが完成していなかったらやり直す（全部か途中からかはわからないのですが）といったことが必要な気がしています。
ビジュアライザの動きを見ていると、
・「見たマス」を探索範囲から外すこと
・「見ていないマス」を必ず見ること
この２つが必要だと思っています。その際、「見たマス」を探索から外すと、動かしたいマスが動かせなくなる可能性が高くて、やはり、ランダムに確定するよりは連続性のあるマスを見ていきたいと思うのです。
そうだ、山登りをやったなら、焼きなましもしなければ。忘れていました。
時間経過とともに、高い温度から低い温度に下げていくのですが、以前「山型足し算」で書こうとしたときにはうまくいきませんでした（確率の計算が間違っていた？）。今回はうまくいくといいな。
あー、思い出した！（←突然何？）
ん？
— かえで (@kaede20203) 2022年6月2日
💡😀
自分、えらい！
(帰りたい)
今朝、自分が何を考えていたのかを思い出せません…
— かえで (@kaede20203) 2022年6月2日
6/2の朝、通勤途中にAHCの解法で何かをひらめいていた（らしい）のに、仕事が終わったら忘れていたという話、これかも！（その日もひとつは思い出せたのですが、よく見たらただの誤読だった、ダメじゃんと思っていました。）
パズルのパーツの種類数を数えるといいことがありそうという話です。
公開されていたseed0のビジュアライザ画像で、できあがっていないパズルを見ると、だいたい余っていたのがこの３種類でした（自分もです）。
でも、これらは必ず関節点（名前が合っているのかな？）と連結しているはず。なので、下図のどれかに最終的にはくっつくから、１対１対応になるはず。
間に延長する絵柄は挿入されますが、最終形を考えたときの主要パーツはこれじゃないかなと思ったのでした。
というわけで、各パーツを数えてきます。
う、わからない…。
というわけで、seed0のビジュアライザ画面を印刷して、各パーツに切り分けました。
何か思っていたのと数が全然違う…。並べてみたけど。
よくわからなかったから、これは保留にして次にいきます。アルゴのコンテストでわからない問題が出たらDP（動的計画法）、ヒューリスティックでわからないときは乱択に違いないと思うことにしています。
お、乱択で検索したら、乱択アルゴリズムが出てきて、それを読んで見たら、スライディングパズルが出てきました！やった！読もう。
そして、やっぱり一行目から確定させようと思います。
（あ、焼きなましやってない！と思い出しましたが、次にやります。）
左上から確定するコードを書いていたら、山登りのコードのバグを見つけました。点数が悪くなったときに、元に戻していませんでした！ひぇー！何ということでしょう。
一文書き足しました。
テストケースを回したら、スコアが良くなりました。（それはそう）
しかし、提出してみたら、スコアを更新することができませんでした。なぜ？
15,823,610点でした。
評価関数を入れたのも悪かったのかな...。
うーん、よくわからない...。
Twitterを見ていたら（現実逃避）、なんか見てはいけないものを見てしまいました。seed0のビジュアライザ画像は共有OKなのですが、これ…。
Sliding Tree Puzzleのseed=0で14286点を獲得!!!https://t.co/N1YccYvBHv#AHC011 #visualizer pic.twitter.com/O2DTEdPd8o
— maspy (@maspy_stars) 2022年6月4日
maspyさんは4時間コンテストだと間違えて、初日に38,307,047を取っていた方で、今もその得点が27位という状況です。どうしてバラバラになったパズルを共有したのでしょうか。「つなげる」と「バラバラにする」、共通する何かがありそうです。
…こういうの、自分向けのメッセージではないと思うものの、上位の方の何か言いたげな振る舞いは、本当に気になります。
お昼寝しようかとベッドに横になった途端、ハッと気がつきました。評価関数に入れた、OKマスのカウントを毎回初期化していなかったことに気がつきました。テストケースを回します。う、良くなってる。今度こそ、良くなっているはず！
予測スコアを出します。ドキドキ。良くなっているよね？
ドキドキしながら提出します。出ました。
予想スコア通りの結果、スコアは16,982,989、順位は238位になりました。
やったー！でも17にのせたい。もうちょっとがんばろー。
実は確定マスを決め始めたけど探索から除く部分が書けていません。
どうしたらよいかよくわからなくて…。
考えたいと思います。
（今日は、考えている間に家事をしているから、家の中がどんどんきれいになっています。）
-（時間経過）-
よくわからないので、ビームサーチを100ケース回して、その結果を見ていました。
こちらはものすごく短い文字列が出てきます。
でもスコアの改善が途中で終わってしまいます。
しかしです。ふと思いました。それぞれのマスからOKなパズルピースまでのマンハッタン距離を出して、その総和を評価関数にしたらどうだろうかと。距離の短いものの評価を高くします。OKマスは何かというと難しいのですが、「連結している」ということでしょうか。もしくは「連結しないところは連結しない」ということでしょうか。
ところで、あれ？っと思って組合せをいろいろと試していました。
もうよくわからないけどchokudaiサーチを組み合わせてみたら良い気がすると思って提出をしてみました。
結果がイマイチだったので話を戻します。
ビームサーチを見ていたら、できあがった連結を崩すことができなくなって、連結を壊さない位置にある４マスで空きマスがぐるぐる回り始めるということがわかりました。
これが局所解って言うのかな？と思いました。焼きなませばいいんだっけ？こういうときは。拙い理解が残念に思います。焼きなましがうまくできないから、適当にkickするということを試したら、ひどいスコアになりました。やっぱりちゃんと確率変数を計算しよう！（逃げてばっかり。できるかな？）
12.コンテスト最終日
2022/6/5の朝9時です。昨日の夜はブログを書かずに寝てしまったので、昨日の夜の振り返りから。
ABC254のコンテスト前に、評価関数を前半後半に分けていたのをやめて提出したら、17Mにいきました。267位は今朝の順位です。（昨日の夜はもう少し上だった気もしますが、キャプチャし忘れました。）これ、今だから思うのですが、自分はランダム要素が強いので、特に良くなったわけではなく、誤差ですね、きっと。
それでもうれしかった。
その後ABC254に参加しましたが、ABの2問しか解けず、レートが下がって727に。安定の茶色上位です。
アルゴの実力とAHCの相関は話題になりますが、時間の制限が緩い分、自分にとってはチャレンジしやすいと思っています。AHCの問題は、少しずつでも改善できて、スコアが上がっていくと、順位に関わらず楽しめると思います。
ここからは今日の話になります。
まずは焼きなましをしました。どのくらいに温度を調節したらよいのか（言葉が合っているのかな？）がわからないでいます。なので、確率定数を適当に決めてやりました。
少し上がったかなと思って提出してみましたが、結果は下がりました。
もしかした、Nによって確率定数を変動させると良いのかなと思って変えて、テストケースを回してみました。（Nが小さい方が、悪いスコアを受け入れやすくする）
あまり変わりませんでした…。ここは要勉強です。
とりあえず出してみよう。（今日は最終日なので積極的に提出していきたいと思います。）
下がりました
自分の現在のイメージなのですが、最後のパーツを合わせようとすると、実際のスコアは必ず今よりも下がるときが来るはずで、そこでやめないようにすることが必要だと思っています。しかし今の評価関数だとできないことが予想されます。だから、今の評価関数の限界がここだと思っています。というわけで、今からはやり方を変えます。ただ、自分で思うようにマスを動かすのはやっぱり難しいので、評価関数と合法手を変更したいと思います。
＜今日やること＞
①それぞれのマスがOKなマスか判定し、OKでないときは、一番近いOKなマスのマンハッタン距離の総和を評価関数から引くようにする。
②一番上の行からOKなマスだったら確定し、そのマスは動かさないようにする。（合法手に含めない。）
③自分の最終提出にする予定のコードで1000ケース回す。今日書いたコードど比較して良い方を提出する。
③については、配布されたツールでseeds.txtの中身を0~999に書きかえて、コマンドプロンプトで「gen.exe seeds.txt」を打てば、一瞬で作成されます。自分はローカル用と提出用にtrueとfalseで切り替えています。in_filneme.txtにインプット用のテキストファイル名を入れています。出力はインプットファイル名の先頭に「out」をつけて出力するようにしています。
また、スコア計算は自分でもしていますが、配布されたビジュアライザ用のツールで正しいスコアを取得しています。
テキストファイルで連続処理用のバッチファイルを作ります。最後に拡張子の「.txt」を「.bat」に変えて、コマンドプロンプトで実行しています。
というわけで、17Mだったコードでseedを1000個生成して、テストケースを回しました。
（1000ケース試すのは実は初めてです。エンジニアではない自分がここまでやっているの、すごくありませんか？）
１時間弱かけた結果がこちら。やっぱり提出した際の17Mは上振れを引いただけのようです。
焼きなましも1000ケースやっておこうかな。
うん、あまり変わりませんでした。
ちょっと確率定数変えてみようかな。（その間に朝決めた実装をしよう。）
うん、余り変わりませんでした。でもこちらの方が良さそう。今の実装がうまくいかなかったら、これを最終提出にしたいと思います。seed511で初めて447917というスコアを見ました。
あ、出そうと思ったコードを1000ケースが終わる前に修正してしまっていました…。戻せない…。多分ここしか変えていないと思って、提出してみたら16.5Mでした。うーん、最終提出をどうしよう。（保留）そういえばGitHubでコードを管理したいと思いつつ環境構築ができなくて、未だに「日付+時間+コメント」でナンバリングをして保存しています。
さて、スタート地点から確定していきたいと思ったのですが、まずランダムだと（0,0)マスにいきません。やはり、順番に行くマスを支持しないとダメなようです。時刻は14時。残り5時間です。
とりあえず最初に(0,0)に移動するようにしました。あ、(0,0)だけマスを決め打ちしようかな。あとは、端に来て欲しいピースが端にあるときに加点するとか。
100ケース回して結果を並べていたら、予想スコアが17Mを超えるものが出てきました。提出をすることにします。
スコアは微増しました。
seed0のビジュアライザはこんな感じです。
あ、なんか評価関数のバグを見つけたかも。なんかきれいになった？
さっきから眠いなぁという気持ちが大きくなってきています。それでも、試そうという案がつきるまでは試そうと思います。
だんだん、普通に座っているのもつらくなってきて、椅子の上に、デスノートのエルみたいに体育座りをしてコードを書いています。もう限界？
今も100ケース回している間にブログを書いています。少し良くなっただけかもしれませんが、また30分経ったら提出してみようと思います。
上がりました。
得点は17,187,634点。順位は283位/928人中になりました。
はぁ、よかった。少しでも良くなって。
これを1000ケース回すことにして、その間（約１時間）にお昼寝をしたいと思います。
疲れた～。
点数も限界だし、私も限界です。
1000ケースの結果です。時刻は17時。先ほどの提出を最後にして終了したいと思います。
振り返ればやれなかったばかりだけど、これが自分の実力だと受け止めて、次へつなげていければと思います。ここまで読み直してみたら、後半の記録が雑ですね。すみません。もう右手が痛くて、文字を打つのもつらくなってきました。（このブログ、2万字を超えていて、現在原稿用紙57枚を超えました。）
13.最終結果（2022/6/7更新）
2022/6/7の朝です。システムテストが終わったようです。3000のテストケース全てでACしていました。平均を比べると自分の結果の99.77％でした。0.23％ダウンしましたが、やはり1000ケース試すと、ほぼ同じ結果になることがわかりました。次からはシステムテストと同じだけ試したいと思います。
順位は暫定時より20弱アップしました。（うれしい。）
14.コンテストを終えて
現在の時刻は、コンテスト終了一時間前、2022/6/5の17時50分です。
毎回、くじけては泣きそうになって、もうダメだと思うけど、あきらめられなくて...。そんな思いをかかえながら、「強くなってやる！」と熱い思いを胸にして、コンテストに参加しています。
「もう衰えているんじゃないの？」心の中の私がささやきかけます。
競技プログラミングを始めてから2年半が経ちます。その間にも自分の中の様々な面で老化が進んでいることを感じずにはいられません。
そんな中、今回、自分の目標は達成できなかったけど、ここまでの結果が出せたことに関して、自分を素直にほめたいと思っています。あきらめずに最後までがんばったね、と。
コンテストが終了したら、ツイートでたくさんの解法が流れて、解法のブログが更新されて、にぎやかになることでしょう。私の大好きな時間です。そして、解法を話すスペースが開かれたらうれしいなと思っています。（開かれなかったら自分が開いているかもしれません。）
やっている間は無我夢中で自分がどんな状態なのかがよくわからないけど、終わった後は、寂しくなってしまいます。だから、良い時間を過ごせていたのだなと思います。
つらかったけど、楽しかった！
だから、私はまた挑戦すると思います。
これで私のAHC011参加記は終了です。
ここまで、長い、長い文章を最後まで読んでくださって、本当にどうもありがとうございました！感謝しています。
それでは、また、コンテストでお会いしましょう。
15.おまけ（おすすめ資料）
①AtCoder Heuristic Contest 011 (AHC011) 解説
②Introduction to Heuristics Contestの公式解説
