AHC056参加記【最終22位】

解説

問題

atcoder.jp

　色と内部状態を元に、動くロボットがある
　ある色と内部状態の時、あらかじめ決めておいた（遷移規則）塗り替える色・次の状態・移動方向　の行動を行う
　決められたターン以内に、全ての目的地を順に訪問する問題
　スコアは、色数と内部状態数の合計が小さい程よい

解法概要

　目的地を後ろから見て、使う経路と適用する遷移規則を差分更新型のビームサーチによって決めます

ビジュアライザ

seed=0, score=24 (C: 12, Q: 12)

後ろから貪欲

　詳しくは他の人が書いてくれることを期待して、自分の方法を書きます

　色c、内部状態qの時適用される規則を、次の色nc、次の内部状態nq、移動方向dir
　(c, q) => (nc, nq, dir)　と表すとします

　経路を固定して後ろから考えると、nc, nq, dir は自動的に決まるため、そのような遷移規則が既にあるか調べることで再利用ができます
　ない場合でも、c, q は未使用の内から自由に選んで新たに作ることができます

　後ろから決めると、スタート地点の色や状態がおかしなことになりますが、スタート地点の数字が(0, 0)になるように出力値に対してmodを取ればよいです

ビームサーチの遷移

　ビームサーチライブラリは、thunderさんのものをNimに書き換えて使っています
　差分更新ビームサーチライブラリをテンプレートメタプログラミングでつくってみた #AtCoder - Qiita

　目的地の最後から、Tを超えない範囲で1マスは移動できる方向への遷移を検討します
　既存の遷移規則を再利用すれば良い場合は、必ず採用します

　ない場合は、(c, q) を1つずつ増やしたリストの先頭から5つまで次の候補へ追加します
　(0, 0) (1, 0) (0, 1) (1, 1) (2, 0) (2, 1) (0, 2) (1, 2) (2, 2) のような増やし方でリストを作りました

　その場停止や、壁に当たって止まるような移動は一切しません
　（処理の書き分けが面倒なのと、遷移先を絞るために使っていません

　ターン数は、min(1.5X, X+5000)ターンまでとしました
　ビーム幅がそれほど大きくないため、大きな迂回路が採用できないためです
　ビーム幅はseed=0では1500程度でした

評価関数

　以下の評価値をoptunaで最適化後、手でキリよくした重みで足し合わせています
　主に効いているものを太字にしています

• 色の種類数、内部状態の種類数
• 割当済みの遷移規則数
• 当初のX/Tに対する現在のオーバー量
• 色の変更回数、状態の変更回数
• 隣接色が同一である個数
• 同方向へ進んだ回数 － 反転方向へ進んだ回数
• 目的地到達回数
• 残り迂回可能距離
• 2ターン前と同じマスを踏んだフラグ
• 遷移規則の出力が既存と被っているフラグ

盤面の重複削除

　ZobristHashで重複盤面の削除をしています

• これまで通ったマス集合
• 今のマスの色、状態
• 目的地達成回数
• 残り迂回可能距離 div 4

細かい工夫

　既存の遷移規則を検索する際に、(c, q)を全探索していると遅いので逆引き用の配列を作りました
　revList[nq][dir] = seq[(nc, c, q)] として、現在の状態と移動方向の添え字でアクセスできるようにしていました

　nc がキーでなく値にいるのは、初期盤面を自由色-1としているからですがどうやら不要だったようです...
　自由色の更新がなければ、revRule[nc][nq][dir]のように一発アクセスできるので、こちらの方が絶対いいです

提出コード

　Nimです

atcoder.jp

参加記

はじめに

　久々な長期コンな気がします
　少し競プロから離れていたため、Nimを書くのも1カ月ぶりくらいでしょうか

　できるだけ時間の都合をつけて1ページ目順位目指して頑張ります！

最初の考察

　遷移という文字を見つけて、また確率か！？と身構えましたがそんなことは無かったです
　色・状態・方向と定義が色々あって問題理解がやや難しいですが、AIに要約してもらって一旦理解は出来ました

　色を1色のみとすると、内部状態をどんどん進めていけば任意の方向へ行動できる
　色と内部状態の組み合わせによって遷移規則が作られるため、表現できるのは色と内部状態の種類の積
　評価されるのは、色と内部状態の種類の和なため同じ種類数用意するのが良さそう

　特徴的なseedは、seed=2が小さく、seed=3が大きめ、seed=19は更に大きめといった感じ
　壁の有無はseedでかなり差があり、全く壁のない場合もあれば1マス幅でしか通れない場合もある

　場所・色・内部状態が同一になると無限ループになってしまうので避ける
　　→嘘でした
　経路を最初に決めて、遷移を最適化するとか？
　同じマスを何度も通ると、状態を増やし続ける必要があるので嬉しく無さそう
　同じマスを通らないように最短経路+αを構築するとか

　グリッド2次元x色x内部状態の4次元のグリッド空間を、干渉しないように動くイメージが浮かぶ
　3次元に落としてみると、子供のジャングルジムみたいな

　経路さえ決まれば、逆向きに貪欲できそう

逆走査貪欲解法

　目的地順に適当にbfsをして最短経路を見つけます
　経路を逆に辿りつつ、各マスを次どの色にすべきか、と今の内部状態を持って順番に決めていきます
　これまでの遷移規則で再利用できるものは再利用したり、色をまだ確定させなくてよい場合、などを実装して提出すると40位程度

　最初は(0, 0)でないといけないのに、そうでない場合が発生してしまう重大なバグを取り除くと、初日の26時で暫定4位になれました！

改善検討

　経路に被りが少ない方が、状態を増やさずに済みそうなため試してみます
　目的地間の経路を一つ選び、最短経路内という制約内で他の経路と被りの少ない経路を選びなおす乱択を1000回実施して貪欲をしました
　スコアが1,2改善するケースもありましたが、悪化する場合もありました

　逆に、被りの多い経路を選ぶように乱択すると、ほとんどの場合悪化しましたが良くなる場合もありました

　経路のみを最適化するのは、現時点では難しそうです

　ビジュアライザからヒントが得られないか考えてみます
　右のヒートマップを見ると色の薄い箇所(使用回数が1回)がかなり多くあります

　状態を使いまわせていないのが問題なようです
　後ろから決めている関係上、序盤に特殊な状態を作る必要があるのも問題です

seed=0

　手で最適化できそうな盤面(seed=93)を持ってきました
　色々試して、ちょっとだけ良い動きのパターンが見えました

　９、１２へ向かう線では、１２へ向かう途中で９へ曲がっていきます
　これは問題ない動きで、曲がった後に１２へ向かう色を揃えることが出来るためです

　直線に動いて、曲がりたい時は、曲がりたい場所の色が異なるor1マス手前で状態を変更しておく必要があり嬉しくなさそうです

　他にもなんとなく傾向はありそうですが、全て言語化するのは難しそうです

経路乱択

　良い解法が思い浮かばないので、一旦今の解を改良してみます
　実行時間6ms程度のコードなので、経路を適当に引き直して貪欲を行い最も良いスコアの解を出力することにします

　各seedで1,2の改善は見られたので、経路最適化による効果はあるがかなり微小

　遷移規則の決め方などの方を根本的に見直さないと、まともにスコアを改善するのは難しそう

　新しく採用する遷移規則を乱択する方がややスコアが伸びました
　このことからも、改善すべきは遷移規則の決め方っぽい気がします
　実装大変だがビームサーチを書くべきか、、、悩む

壁当たり操作追加

　問題文にあった、壁方向へ移動すると停止するが色や状態は変化する。という処理を使ってみることにします
　後ろからの貪欲なため、壁へ当たってから移動してくる。ような操作になります

　この機能を追加するだけなのに、かなりバグらせて大変な思いをしました
　悲しいことに、実装しきってもほぼスコアは変わりませんでした、、、

ビームサーチ実装

　重い腰を上げてビームサーチを実装してみます
　スマートなデータの持ち方は後にして、とにかくバグらせないように気を付けます

　実装しきると、一応動いていましたが元の貪欲よりスコアがやや悪いです
　ChatGPTに聞いて、評価関数にC+Qだけでなく割り当て済みの遷移の数も加えると10%程スコアが改善しました
　ビームサーチにしただけで、スコアが改善するとはあまり思っていなかったので驚きました

seed=0, score=37

　提出すると、火曜日夜時点で35Gの24位となりました
　この方針を詰めていけば良さそうな兆しが見えたので、沈みかけていたやる気が復活してきました

伸び悩み

　ビームサーチのハッシュ方法や評価関数を調整したりしましたが、いまいちスコアが伸びません
　何より、ビーム幅や時間を伸ばしても大して効果がないので高速化しても無意味そうなのが厳しい感じがします

　木曜日夜の時点で30位なのは悪くはないですが、このままだと50位も怪しいです
　根本から何か違うような気がしてきました

　盤面の小さいケースは割と最適な気がしているので、N=10~14のみの提出をしてみます
　17ケースACで相対スコア12.6Gでした
　これは、元の50ケースのスコアと大差ありません
　全てに共通した改善事項(本質)があり、自分はまだ見つけられていないようです

壁当たり移動

　処理の書きやすさから、移動する行動のみを候補としていました
　が、候補手は全て試した方が良さそうに思えたため実装してみます

　メチャクチャバグらせて、一旦諦めて、やっぱり修正してというのを2,3日繰り返してなんとか実装しました
　原因は、方向の反転をk^2で行っていたのですが、壁に当たる時は反転してはいけないのをずっと見逃していました

　苦労して壁停止処理を導入しましたが、大体のケースでスコアが落ちる結果でした
　明らかにビーム幅が取れなくなってしまったので、選択肢の広さが仇になったようです

評価関数見直し

　ChatGPTと壁打ちしながらとにかく色々試すことにしました
　過去のビムサ回のXを見返したりして、評価関数を増やしていきます

　上手くいかなかった項目もありましたが（経路dpで求めた通過期待値を重みに使う、盤面全体の色合計値）、効いていそうな項目も見つけることが出来ました

　連続した進行方向や、隣接色の関係などは良さそうな感じです

　他にも、遷移規則の類似度を評価してみたり、重みをoptunaで最適化してみたりと微妙な改善で最終日まで1ページ目に残ることは出来ました

最終チェック

　長期コンのシステスでACをあまり取れていないので、今回はしっかりチェックします
　3000ケース回して、異常がありそうなケースに対応していきます

　まず、実行時間が異様に早いケースがいくつかありました
　これは、盤面のハッシュ化が甘すぎて小さいケースにおいて、ビーム幅があまり広がっていないようでした
　重複削除を緩めつつ、大きな盤面での多様性維持のバランスを見ながら修正しました

　次に、実行が終わらず無限ループするケースがありました
　ビームサーチライブラリの不具合をChatGPTと一緒に追いましたが、見つからず。結構な時間をかけて突き止めたのですが、ビーム幅が自作のハッシュテーブル幅を超える場合に無限ループが発生していました
　ビーム幅の最大に合わせてハッシュテーブルを設定すべきですが、大きくし過ぎてもデータの初期化に時間がかかるため、ビーム幅を最大30000程度に落とすことにしました
　小さな盤面での最適解が見つからなくなる恐れがありますが、今回は大丈夫なようでした

　他にも小さな高速化をして今回のAHCを終えました

暫定順位表

　システスで上振れるか、下振れるかドキドキです

終わりに

　最上位解法ではないだろうなと思いつつ取り組んでいましたが、氷の床のような発想は実現すると思っていなかったので驚きでした
　それでも、同じような解法の中では割と詰めれた方だと思うので満足度は高いです

　今回の結果で順位が10上がって65位になりました
　50位が一つの目標なのでひとまずそこまでは頑張りたいです

AHC054参加記【最終111位】

参加記

はじめに

　今回は、自主制約を極力排除した方針を考えることを目標にして取り組みます
　前回の長期AHCの反省を活かして、1ページ目に入れるように頑張ります

問題

atcoder.jp

　NxNマスのグリッド上の (0, N//2) を開始地点として、ランダムな1マスに花が植えられている
　迷路を動的に生成して、できるだけ花へ辿り着かないようにする

考察

　いつものdiscordメモです

乱択解法

　考察の参考にするため、いつも通りChatGPTに簡単な解を書いてもらいます

　まず、花の3方を木で塞ぎます
　その後、冒険者の4方の未確認マスにランダムに木を置きます
　ただし、開始位置と現在位置から花へ到達できない場合は木の設置を乱択し直します

seed=0, score=244

　目的地へ向かう関係上、思ったよりも勝手に行き来してくれそうです
　木の置き方によって到達不可能なマスがあると、もったないため3x3の連結判定などで塞がないようにした方が良さそうです
　また、木を遠くに置くと間が全て空マスだと判明してしまうので、あまり嬉しくなさそうです

　冒険者の動きに合わせて、適応的に迷路を作ることが肝になりますね

　初日0:20の順位表です
　まだまだ伸びるとは思いますが、現時点でも8倍の差があるのはびっくりです

斜め移動方針

　斜めに経路を作れば視界も広がらず、良さそうだなーと考えました
　実際には、既存の木が邪魔でそのまま構築はできず実装は諦めました

　ただ、直線よりはこういった形の方が良さそうな動きは見えたので後で何かに使えるかもしれません

オフライン焼きなまし

　全然良い解法が思いつかないため、良い迷路の形をチートして見てみることにしました
　ローカルの入力には、目的地の順もあるためこれを使って正確なシミュレートを行うことができます

　マップ全体に対して、木を置くか置かないかを焼きなましによって最適化します
　前回の解を利用できるようにして、60秒焼きなましを何度も行いました
　流石にオンライン実行でこれほどのスコアは出ないと思われます

seed=0, score=2,240

　見つけた良さそうな方針をメモしていきます

斜め移動

　冒険者に与える情報を最小限にできる

花への経路が奥まっている

　花の座標が目的地に選ばれた時しか、訪れないような迷路が構築できていると良さそう

木で囲われた小規模な領域

　この状況が作れると、周りの木全てを確認済みにして周る必要があるため、かなり時間稼ぎになります
　広い面積を囲ってしまうと、一度確認しきったらその分目的地がスキップされてしまうため、小さい面積のみが良さそうです

現在値から４方向へ木を配置する貪欲

　冒険者目線で結局影響があるのは、現在値から４方向に木があるかどうかなためこれを評価値貪欲で決定していくことにします

　花へ到達しにくくするため、以下のような障害を設けることにします
　左右反転+回転4方向の計8パターン試して置けそうな配置のうち、開始位置から遠くなるような置き方を選びました

　木の配置は、現在地から４方向に距離５までの範囲の総組み合わせを試して、以下のような評価をしました

• 木の配置数が多いと減点
• 現在値中心に7x7範囲に、2x2の空マスがあれば減点
• 花を囲う木の周りへの木の設置は減点
• 次のターンで増える確認済みマス数減点
• 現在地からゴールまでの距離が遠いほど加点

seed=0, score=1,036

　貪欲にしては悪くない動きをしているように見えます
　提出すると、得点 296,742 を得て暫定30位になりました
　相対スコアは約52Gなため、あと2倍程度スコアが伸びるようです

　ざっくりの方針として、オンラインで木の配置を決めていくのは間違っていないような気がします

2分岐解法

　現状の解法を見ていると、まっすぐ斜めに進んで壁に当たると脇道を生成しつつ、再度ななめに進むような形しかつくれないことに気付きました
　開始地点から1直線に進むと、その道は二度と戻ることは無いのでもったいないような気がします

　道の端を分岐点にして、必要な時に分岐を作るようにしてみます
　作り方はdfsで生成した全経路について適当に評価して、良さそうな経路をまず1本選びます
　2本目も同様の考え方で、1つ目の経路の根から順に作ろうとしてみます

　実装してみると、あまりスコアが出ませんでした
　分岐ポイントに到達する毎に分岐させていく解法だと、冒険者が行きたい方向へ動けてしまう。というのがありそうです
　いいタイミングで通行止めにして歩いてきた道を戻らせるようにしたいです

4隅後回し戦略

　あまり良い考えが浮かばず、悩み続けて気付いたら週末になっていました
　大体100位前後でこんなにも何もわからない回は久しぶりです

　改めて、オフライン焼きなましのビジュアライザを眺めていると気付いたことがありました

　中央付近を蛇行させておいて、4隅に未確認マスを残しておけば行ったり来たりの距離を稼げるのではないか。と思いました

　良い構築を考えてみますが、あまりに難しい
　思いつかなかったため、焼いてみることにします

　以外にも、それっぽい形ができました
　が、スコアは微妙でした...検討からズレているとしか思えません

seed=0, score=718

領域2分方針

　4隅残しでなく、全体を横断するような経路を作ってしまえば、それらを行き来するにはその経路を通るしかない。という状況を作れそうです
　それを再帰的に構築すれば、目的地間の距離を稼げそうです

　と思っていましたが、既存の木が邪魔で上手く構築できず諦めました

パラメータ最適化

　日曜日まで何も思いつけなかったため、元の貪欲を仕方なく詰めることにしました
　評価値全てに係数を設けて、これらをoptunaで最適化しました

　pahcerの使用で驚くほど簡単に実行することができました（terryさんありがとうございます！
　パラメータ調整のみで、10~20%程スコアが上がったと思います

　最後に、3000ケースでのACと最悪パターンの確認をして終了しました

最終スコア

seed=0000, score=  700
seed=0001, score=1,925
seed=0002, score=  190
seed=0003, score=5,656
seed=0004, score=3,762
seed=0005, score=8,434
seed=0006, score=  740
seed=0007, score=2,591
seed=0008, score=5,511
seed=0009, score=2,432
seed=0010, score=3,408

終わりに

　ここまで何も分からない長期コンは久々でした...
　帰って来た情報を全く活かすことができずに終えてしまったので、上位解法を見て復習したいと思います

AHC051参加記【最終24位】

解説

問題

atcoder.jp

解法概要

　以下のような手順で解を出しました

1. 全座標を使ってドロネー三角形分割を行い、交差しないグラフを作成
2. 貪欲法で2分木の初期解作成
3. 焼きなましで2分木の構築を最適化
4. 山登りで処理装置の配置を最適化しつつ、分別器を仮決定
5. 焼きなましで分別器の種類を最適化

ビジュアライザ

seed=0, score=249,367,309

前処理

　ドロネー三角形分割による交差しない辺リストの作成は、ChatGPTにお願いしたら書いてくれました

　分別器は完全ランダムに生成されるため、似ている形を削除しました
　ユークリッド距離とコサイン類似度を使って、両方閾値を超えている場合のみ未使用分別器として排除しました

　以下のような組を似ているとして片方を使わないようにしました
　seed=0だと、2, 8, 12, 26, 32, 37が弾かれているようでした

初期解作成

　搬入装置から直接接続するノードは、全処理装置から多始点bfsをして一番遠いノードとしました(搬入装置の隣接ノードのうちで)
　ただ、この後の処理で全処理装置へグラフが伸びなかった場合は、搬入口の隣接ノードからランダムに選びなおしています

　2分木の接続は、bfsの要領で決めていきました
　接続された本数・処理装置への距離・周囲の未確定ノード数を使った評価値で、2つまでのノードへ接続します

　また、サイクルが出来てはいけないのでDAGを維持できるかチェックしながら接続をしました
　接続したいノードが、自身の祖先でないかだけ確認できれば良いです
　実装では、ノードNoを配列に追加しつつトポロジカルソートをしていました

　最後に、子を持たないノードを再帰的に削除して正しい木に修正します

　seed=0では、以下のような2分木が出来ました

2分木構築最適化

　TL1.0秒まで焼きなましによって、2分木構造を改善します
　近傍は、適当にノードを一つ選び今の子の数によって変えています

• 子0：親ノードを一つ選び、その子ノードとの間に挿入する
• 子0：親ノードを一つ選び、自身を介して別の隣接ノードへ接続
• 子1：隣接ノードを一つ選び接続する
• 子2：子ノードを一つ選び、接続を切る
• 子2：子ノードを一つ選び接続を切った上で、別の隣接ノードへ接続する

　評価関数は、根から各処理装置の位置へ到達しない確率の推定値の和としました

　 ノード から処理装置位置 へ到達できる確率として、各処理装置の対応した位置を1.0, その他を-0.1で初期化します
　トポロジカル順の逆に見て、2つの子の内確率の大きい方にx0.7、小さい方にx0.3した値の和をそのノードの値にしました
　-0.1は、到達できないノードへの分別に対するペナルティです

　実際にその確率で分別できる訳ではありませんが、ざっくりの到達確率としては十分機能しました
　計算量としても、で比較的軽いです

　分かりやすいようにビジュアライザ上で矢印を足しました
　(矢印を足すブックマークレットをChatGPTに作ってもらいました)

処理装置の配置最適化

　] を、番目の位置にどの処理装置を置くか、として探索しました
　1000回or1.7秒で打ち切っています

　近傍は以下の4つにしました

• 1~N/3 右回転
• 1~N/3 左回転
• 2点swap
• 3点swap

　 ノード にゴミ種 が存在する確率として、トポロジカルの順に分別器を全探索して最も良いものを配置していきます

　先ほどのevaluate配列を重みとして使い、dp[i]*evaluate[c1]*P[k] + dp[i]*evaluate[c2]*(1-P[k])　を最大化します（出口1,2を入れ替えた計算も)
　気持ちとしては、evaluate配列が到達期待値を表していると考えて、そのノードで分別した結果の期待値を最大化しようとしています

　スコアは誤分別の確率の和を正しく計算しています
　計算量は、と結構重めです

分別器の種類を最適化

　最後に、2分木構造と処理装置の位置を固定して分別器の種類を焼きなましによって最終調整します

　近傍は、まず確率を上げたい処理装置・変更するノードを乱択した上で、分別器の種類を乱択します
　その上で、分別確率が上がりそうな向きに出口を入れ替えて評価します

　スコアは誤分別の確率の和を正しく計算しています
　計算量はですが、変更ノードより上流のみ更新しているので実際はもう少し軽いです

暫定順位表

参加記

最初の考察

　処理装置を置く場所は最悪固定で考えてみても良さそう
　分別器の種類・配置・接続の自由度が高すぎて大変 & ベルトコンベアが交差してはいけないという制約が結構難しい
　→ドロネー三角分割で得られる辺のみを使えば交差を考えなくてよい

　フィルタリングするような貪欲をしたいが、どう実装したらよいかパッと出ない
　紙で分岐を書いていい感じに特定の種類のゴミだけを分けられないか試したい

　焼きなましをする場合、木構造焼きなましのようになりそう
　→閉路を作ってはいけないため、親リストや深さをノードに持たせることになりそう

分別器の特徴可視化

　分別器の特徴を見たくなったので、ChatGPTにレーダーチャートを書いてもらいました
　極端な値を持つ分別器が良さそう？と何となく思いますが、活用方法が全然思いつきません

　0.5付近の値を持つ分別器はよく無さそうということだけは分かります

seed=0, 0<=K<=14

2分木構築

　遷移確率は0.1~0.9の範囲で生成されるようなので、全てのゴミを完璧に近い分別をすることは不可能な気がします
　また、分別器の特徴を見ていてもある1つだけ極端に確率が偏っているようなものが作られるのは、あまり無さそうです

　そこから、分岐する毎にゴミをざっくり分けていく2分木の構築をしたいと考えました
　ただ、これがあまりに難しい（ChatGPTに聞いてもあまり筋の良い解法は得られませんでした

　妥協解法として、まず搬入口から適当に近いノードを選んで根とします
　根から2分木を作っていって、不要な葉を最後に削除することにしました

　dpぽくスコア計算するために、経路圧縮したりと地味に大変な実装を乗り越えて、接続を適当に固定して分配器を焼きなます処理が完成しました
　処理装置は、確率の最も高いゴミと場所を順番に決定していく貪欲です

　pythonで実装した上、高速化もしていないので微妙な出来ですが、正しい出力ができていそうです

seed=0, score=629,131,337

　提出すると、ACがとれました
　相対スコアは22Gで思ったより低くはありません
　暫定一位は、平均70%くらいは正しく分別出来ているようです

8/3(土)24時

分岐の数を増やす

　DAGを構築しつつ、再帰的に矛盾を解消する処理をすることで、後から有向辺を追加できるようにしました
　これによって、一応2分木構造を探索できるようになりました

処理装置の位置を焼きなまし

　0~N-1のノードに、どの処理装置を置くかを焼きました（2分木構造は固定
　各ノードに処理装置までの距離に基づく評価値を振って、K種類の分別器を評価値によって決めました

構築の検討

　今の解法が伸びる未来が見えないので、どんな形の接続をすれば良さそうか改めて考えてみました

　左のように、0.8/0.2に分けられる分別器をそのまま使うと、正しい分別確率の和は1.6となります
　右のように、間にかますと正しい分別確率の和は1.792まで伸びます
　正しい分別確率を上げるためには、このような形にする必要がありそうです

　今想像しているのは、下のような感じです
　各処理装置へつながるメインの経路があり、経路間は先ほどのように分別器を介して接続されています
　各分別器は、メインの経路に近づくようにゴミを"寄せていく"ことで、正しい分別確率があがる想定です

　これを見ると、根から処理装置へは遠い方が良さそうに見えます
　また、処理装置へのメイン経路同士も離れている必要がありそうです

　平面上でどうやって構築したらいいんでしょうね...

木構造焼きなまし

　良い案が浮かばないため、焼くことにします

　各処理装置から有向辺を逆にbfsして、到達ノード数を出します
　これらの和を最大化するように、辺の貼り方を焼きました

　単純和の最大化・最小値の最大化・ExpSumLogの最大化を試して、ExpSumLogを採用しました
　ただ、構築の評価が微妙らしく実行ごとにスコアが10%程度バラツキます

seed=0, score=453,587,182

3段階焼きなまし

　木構造の探索・処理装置の配置の探索・分配器の種類の探索の３つを順番に焼きなましで最適化しようとしています

　出てきた解を見てみると、木構造の出来によってかなりスコアがバラツキます
　そこで、評価が重くても、最初の二つの探索を同時にやってしまうことにしました

　木構造の探索をメインにしつつ、時々処理装置の配置も探索するようにすると小さめの盤面ではスコアが改善しました

理想盤面の検討

　一応焼きなましでそこそこの解が出るようにはなって来たため、長時間かけて実行して高得点が取れる盤面を作ってみます

　seed=3で平均85.6%の解が出来ました
　処理装置には、必ず複数の有向辺が接続されていることは分かります

　試しに、処理装置に3つの有向辺を入れることを許すと、スコアが伸びました
　ただ、seed=0のN=13のようなケースでは逆にスコアが落ちました

　分別の自由度と、処理装置への集約のトレードオフがありそうです

seed=3, score=143,900,796

最後の週末

　評価関数の変更など色々試していましたが、記事を書く時間が作れず...
　さぼるために、今の方針を公開されたばかりのGPT5に要約してもらいます

• #幾何: 点集合=処理装置N+分別器M+入口(0,5000)。ドロネー三角分割→交差しない候補エッジ集合を得る（平面性担保）。

• #有向グラフ生成: 「分別器→隣接」方向に有向化、入口→近傍分別器に出辺。処理装置は終端。

• #root選択: 逆BFSで処理装置に遠い（hop長が長い）入口近傍を self.root に。

• #初期木/有向DAG: rootから広げて子を貪欲に生やす。checkDagUp でトポ順を保ちつつ閉路回避。浮いた葉を削除。

• #評価系:

  • getScore は“厳密DP（後ろ向き）”：葉（処理装置ノードj, 対応機種p）に dp1[j,p]=1 を置き、分別器uの dp1[u, i] = p_k[i]*dp1[c1,i]+(1-p_k[i])*dp1[c2,i]。rootの dp1[root,i] が q_i になる。

  • calcProb / evaluate1 は簡略値（最大側の子に重み寄せ）で、構造探索/貪欲のガイドに使う。

  • getScoreGreedy は forwardに流量(dp1)を持ちながら各分別器で候補Kからタイプkと子の左右を選ぶ近似貪欲。

• #最適化:

  • sa1: 構造近傍（挿入/付け替え/割り込み）＋ calcProb を目的に 〜1.5s。

  • sa2: 処理装置の並べ替えを軽い山登り（100手）。

  • sa3: 分別器タイプ＋左右スワップをSA（〜残り時間）。

残った数日

　考えていた方策はほとんどやり尽くしてしまったので、パラメータ調整とバグ出しをとりあえずやっていきます
　1000ケース回すと、いくつかWAを出してしまったので対応します

　搬入口と処理装置位置が複数近いと、全く木が広がらない場合がありました
　根の位置を適当に張り替えて上手くいくのを祈るようにしました

　バグ修正をした後、念のため5000ケース回して全ACを確認しました
　これで今回は全ケースAC出来るはずです

　5000ケースで一番スコアが良かったビジュアライザです
　約98%正しく分別出来ています！

seed=1114, score=17,990,870

　残り数時間で、出来ることも無かったため解説を書き進めていました
　最後の焼きなましに差分更新の処理を入れ忘れている事に気付き慌てて修正しました

　また、合わせてバグをいくつか取り除くと最終日だけで10%ほどスコアが縮みました
　1ページ目には入れなさそうですが、バグなく終えることが出来そうでホッとしています

おわりに

　AHC051お疲れさまでした
　始めは全くとっかかりが分からなかった問題でしたが、要素ごとに分けて考えることで割と戦えて楽しかったです

　相対スコアを見ると、更に倍スコアが縮むようでちょっと信じられない気持ちです
　最近、推定でない確率を扱う問題が多く、若干苦手意識があるので他の人の解法を見て、理解しなおしてみたいと思っています

AHC050参加記【最終25位】

はじめに

　AHC050にて、ChatGPTとのやりとりで得られたコードのみを用いてタイトル通りの成績を出すことが出来ました
　今後の参考のために、やりとりなどを残します

問題

atcoder.jp

• 舞台: N×N のスケートリンク上でゲームを行う（外周と一部マスに岩があり通行不可）。

• 初期状態:

  • 岩がすでに M 個置かれている（位置は与えられる）。

  • ロボットが岩のないマスのうち 1 つにランダムに初期配置される。

  • あなたは、残りの岩のないマス（N²−M 個）を順番に並べたリスト P を宣言する。

• ゲームの進行（ステップ i = 0, 1, ..., N²−M−1）:

  1. ロボットがランダムな方向（上下左右）を選ぶ。

  2. その方向に岩にぶつかるまで滑って移動。

  3. マス P_i に岩を置く。

     • そのマスにロボットがいたらゲーム終了（賞金ゼロ）。

     • ロボットがいなければ 1 円獲得。

• 目的:
  期待される**獲得賞金（= 生き延びた回数）**が最大となるように、並べる順番 P を決めよ。

やり取りと得られた解法

　「指示 + 何かのコピペ」というスタイルでいつも使っています
　AHCの最初には、「以下の問題文を読み込んで下さい <br> "問題全文のコピペ"」を入力した上でその後の指示を出しています

特定の領域にロボットを閉じ込める方針

　問題を読んで、狭い場所にロボットを閉じ込めておけば、それ以外の場所がフリーで潰せる。と思い以下のような指示をしました

　「再帰的に、特定の領域にロボットを閉じ込める方針をrustで実装して」

　提出もしましたが、相当弱かったと思います

seed=0, score=247,309

存在確率による貪欲解

　続いて、以下のような指示を出しました

　「各マスの存在確率を管理して、貪欲に各ターンの解を求めたいです
　各ターン、存在確率の上位100マスまでを4方向に動いた場合のシミュレーションをして、次のターンの存在確率を出します
　その後、正規化して100%に直します

　選ぶマスは、残った全マス評価し、存在確率の最も低いマスのうち
　存在確率の高いマスに近いマスを選びたい」

seed=0, score=624,402

ボツ解法色々

　「焼きなましで解を求めたい。高速なスコア計算と、近傍を考えて」

　→動くコードは出てきたが、指示が曖昧過ぎて良い解が得られず

　「袋小路に誘導するような経路を壁で表現したい。良い盤面を探索して」

　→返答から、木構造というワードを入手できた
　　確かに！と思ったが、具体的な指示に落とし込めず諦め

貪欲解改良

　以下の指示をしました
　伝わりにくい文章ですが、この時は意味を汲んでくれました

　「各ターンの貪欲解を修正します
　あるマスに置いて、そのままの盤面で10ターン進めた時の状態を評価したい
　少量の確率の大きいマスとなっていることが良い状態とする評価関数として」

　大体、部分修正を依頼してきますが、面倒なので「提出できるフルコードを提供して！」と全文書き直してもらうことが多いです

　なお、コードがTLEしたため、「置くかどうかを調べるマスは、存在確率の低い方から100だけにして」と追加依頼もしました
　が、何かの指示に引っ張られているのかTLEが解決しません

　以下のような指示をして強引にコードの内容を戻しました

　「以下の貪欲コードを改造したい
　低確率マス100個を選らび、それぞれについて置いた後の1ターン存在確率の遷移を確認して、高確率のマスが固まるようなマスを選びたい
　"動いていた時の貪欲解コード全文コピペ"」

　エラーが出たので、修正依頼とそれに加えて以下の修正もしました
　(ビジュアライザで色付きのマスを踏んでいる様子から気付けました)
　「ロボットが1度動いてからターンが始まるため、最初に存在確率の更新をしてほしい
　これは、全マスについて行うこと」

　2.3秒ほどかかりますが、割と良いスコアが得られました

seed=0, score=923,552

高速化

　「以下のコードをベースに高速化したい
　特に行動シミュレーションの所で、愚直に４方向動いているが、
　各行列の障害物の座標をsortedSetのように持っておいて、2分探索すればlognで取得できます
　"動いていた時のコード全文コピペ"」

　これを指示した後、全然エラーが解消せず苦労した上、遅くなりました
　「処理が2sec -> 9secになりました。何故ですか」と聞くと、小さな盤面では線形走査の方がマシと言われ、高速化の代案もいくつか出してもらえました

　案の中にあったので「行・列畳み込みの“倍々”高速化　したい」と指示しました
　ただ、提供されたコードを動かしてもスコアがただ下がっており、畳み込みのコードも解読できないため諦めました

　「今の場所から配ることをしているが、今の場所に存在確率を集めるような計算方法をしたら速度アップするか」
　毎回停止マスを探索するより、前計算した方が早い。と言われたためお願いしました
　コード実行は成功するものの、スコアが低い解が得られました

　「その機能を以下のコードに追加して
　"動いていた時のコード全文コピペ"」

　コードを貼って指示し直すと高いスコアに戻りました
　どこが違っていたか把握出来ていませんが、それも聞けば教えてくれたかもしれません

seed=0, score=956,383

更に高速化

　チャット自体が重くなってきたので、新しいチャットを立ち上げ問題文の読み込みをさせなおしました

　「以下のrustコードを用いているが。高速化できる箇所を高速化したい
　"コード全文コピペ"」

　ビットボード高速化を提案してきたためお願いしました

　すると、ほぼ満点に近いようなスコアが出ました
　後から気付いた点としては、高速化の寄与ではなく存在確率の低いマスの選び方が何故か盤面全体に散っていることが要因なようです

seed=0, score=993,398

　以下のコードで低確率マスを選択しています
　前のコードと違う点は、select_nth_unstable_by()を使用している事なので、その辺りが偶然効いたようです

　最後に、シミュレーションするターン数や選択する低確率マス数のパラメータ調整を手で行って、提出して。で終了しました

延長戦

　コンテスト自体は25位で終了して、どんなコードだったのが眺めていると想定と違う箇所がありました
　低確率マスをいくつか選んだ後、シミュレーション後の盤面評価のみで障害物とするマスを決定するようになっていました

　これを、存在確率と盤面評価の加重平均に修正してもらうと本番3位相当のスコアが出てしまいました
　(シミュレーションターン数を一律でなく、最初は多めに回すような修正も入っています)

seed=0, score=997,427

学び

• 極端に曖昧な指示や自分が理解できないような解法の指示は避ける
• ある程度のやり取り回数で、チャットを新たに建て直す
• スコア計算や過程の出力もさせて、動作を理解しながら使う

おわりに

　正直、AI出力のコードだけでAHCに取り組むのは本意ではないです
　ただ、序盤の1時間などで解法お試しを高速に繰り返すことが出来るのは明確な強みだと思っています

　今回はラッキーもあり、高順位に入れましたがビジュアライザから読み取って、自分で指示して改善しないといけなかったな。という反省にもなりました

　頼り切るだけでなく、自分の力もちゃんと付けたいですね

AHC048参加記【最終42位】

解説

　解説は書けたら書きます

問題

atcoder.jp

　K種類の絵具を良い感じに混ぜて、H種類の目標色を順番に渡す問題
　NxNマスを自由に仕切ったり繋げて良いが、Tターンまでしか行動できない

参加記

最初の考察

　最近は自分用のdiscordを作って、適当に書き連ねてメモとしています
　そのまま貼りますので興味のある方はどうぞ

AI実装

　週末疲れ+子供の寝かしつけのため、布団の中でスマホコーディングすることにしました
　実際には、ChatGPTに考察を投げて実装してもらうだけですが...

1gずつ使う貪欲

　どれくらい使い物になりそうか確かめるため、1g出して1g提供する貪欲をpythonで書いてもらいました
　得点109,690,905を得て、相対順位は大体3Gでした
　今の得点からおよそ1/14にすれば1位相当だなと思っていました

複数絵具を混ぜる貪欲

　2x2サイズの容量4のウェルに固定して、3色まで追加して目標色に近づける貪欲を書いてもらいました
　得点18,092,839を得て、1ページ目に入っていました

4色まで絵具を混ぜる貪欲

　2x2のサイズはそのままに、4色まで追加するコードを書いてもらいました
　また、D*0.1*n/H (nは現在の使用絵具量)を絵具の使用コストにしました
　手元では明らかに改善しましたが、提出するとTLEでした(AC 11ケース)

　K=20から4つを選ぶ重複組み合わせは、8,855組ありこれだけなら計算は間に合いますが、H=1,000 x ウェル数100 が乗ると流石に間に合わないようでした

　計算量改善をお願いすると、KD-Treeで最近傍探索をすると間に合うと言われたので、目標色の近くL個を選んで評価してもらいます
　得点13,009,463を得て、相対スコア23Gで8位になりました

隣接を一瞬接続して戻す

　あまり効くイメージが無いですがお試しで
　使用コストをD*0.05*n/Hに変更もしてみました（絵具をより使っても色を合わせに行く
　得点11,906,526と伸びましたので効果はあったようです

隣接を接続して、戻したうえで絵具を足す

　上記が効いたのならと、評価する行動を増やします
　得点10,666,560とちょっと伸びました

　また、左に区切りを入れておいて、下or右に区切りを入れると現在の量の50%、75%を使用して色を作る遷移も入れてみました
　現状のseed=0の最終状態は下のような感じです

　土曜日の夕方あたりの順位表です
　7位にも関わらず、17Gしかないのでまだまだ伸びしろがある問題なようです

調査フェーズ

　seed=0では、score=188,194が出ていて、うち誤差が142,329 絵具が45,864です
　合計の誤差量は14.232936となっていますが、ケースごとの値を見てみます

　seed=は0 (K=4, D=3822)絵具コストが高いため、後半程色合わせに苦労している様子が見えます

　seed=11です(K=20, D=47)
　最初の数ケースで大きめの誤差が出ており、あとは同じような感じに見えます
　絵具コストが低いと最後まで色合わせを頑張っているみたいです

　絵具コストは全体の1/5程度のため、1位相当になるには誤差を1/4～1/5まで減らさないといけないようです（驚愕

エクセルで実験

　seed=0の2ケースについてソルバーで理想の混ぜ比率を出してみると以下のようになりました

　さらに手動で操作を最適化すると、

1. 容量20のウェルにK=2の絵具を1g出す
2. 容量2と18に分割して、容量18側を捨てて分割を戻す(1/10の濃度)
3. K=1の絵具を1g出し、容量1と19に分割する
4. K=0の絵具を容量19側に1g出し、容量1と18に分割する
5. K=3の絵具を容量18に1g出す

　すると、誤差0.000891の色を作ることが出来ます
　上手く分割をして濃度を調整して、色を混ぜていくことが大事そうです
　ただ、操作回数が増えるため注意が必要そうです

　意気揚々と実装を開始しますが躓きました
　下のように、容量20や容量400のウェルにして、任意濃度を作って...を試しましたが、実装に手こずるのと、思ったよりスコアが出ないため一旦諦めました
　ただ、分割で濃度を操作するのは流石に必須な気もするので、別の形を考えます

貪欲解の行動評価

　貪欲解が実際に行動として選択した内容をカウントしました

　回数の多かった順に、どんな操作か書くと

• merge_add2：ウェル2つをマージして絵具追加、目標色提供後マージ解除
• merge_add：ウェル2つをマージし、マージ解除後に絵具追加、目標色提供
• merge_take：ウェル2つをマージし、そのまま目標色提供
• add：そのまま絵具追加、目標色提供
• take：そのまま目標色提供

　ほぼマージ操作が絡んでおり、結構想定外でした
　チューブ色の凸包内に目標色がほぼ入っていることを考えると、平均を取る行動だけでも目標に近づきやすい上、微調整の役割も担えているようです

マージ戦略の強化

　現状は隣接ウェル2つのマージしか行っていないため、これを増やしてみます
　3つ4つと増やすにつれて、スコアも上がりますが時間も伸びます

　下のように4つのウェルがちゃんと繋がっている様子もビジュアライザで確認できました
　ただ、操作数も増えるため、入力の値に応じて切り替えないと厳しそうです

初期盤面に色を散りばめる

　ビジュアライザを見ていると、新しい領域を使って色を作っている場面があまりなく、既存の色をマージしていることがかなり多いことに改めて気付きました
　そこから、最初から絵具を適当に置いておけばいい感じに使ってくれるのでは。と考えて1gずつ置いてみるとスコアが上がりました

絵具の混合を考える

　CMYを、3次元ベクトルとして捉えると見通しが良さそうですが、ChatGPTに聞くと凸結合などと言われますが正直良く分かりません
　一旦2次元ベクトルで考えてみると割と納得できた気がしたので書き残します

　2色混ぜる場合、その比率で平均する(加重平均)ので、ベクトル同士を結んだ点線上の色を作ることが出来ます(これを凸結合と呼ぶらしい)
　3色混ぜる場合、ベクトル同士を結んだ点線三角形の中の色を作ることができます

　これを3次元に戻して考えてみると、次元が1つ増えるため4色を任意の比率で混ぜることで目標色が作れそうです
　この4色による凸包が目標色を含んでいることが前提です
　ただ、毎回4色を使う、かつ任意の比率で混ぜれるわけでないことに気付いてしまいました...

チューブ本数による違い

　seed=0, 1 を並べました
　入力生成方法から読み取るべきでしたが、チューブの傾向に結構引っ張られていて目標色が作りやすいようになっているようです
　色ごとに合わせやすさの係数を掛けると、若干スコアが上がりそうでした

方針再検討

　ChatGPTがカッコいい事を言っています。やりたいことはその通りです
　2x2のウェルで固定すると、多様性は増しますが終盤に無駄な余りが結構出てしまいます
　最後、余りを減らすため4x4の区切りに広げることでもったいない絵具を減らしてみました
　Dが小さいケースでは、最後まで色を合わせに行く方が良さそうだったため、Dの値で実施するかは切り替えました

　他に量を調整しつつ上手い事やれる方針がないかな、と考えてみましたが
　........色々検討して気付いたら最後の週末でした

chokudaiサーチ

　現状、評価値貪欲だけで500msec使っており全体でビームサーチなどを走らせる余裕はありません
　最終盤だけなら？と思い、実装が簡単なchokudaiサーチを取り入れました
　実装自体はAHC038で経験済みなので、2時間程度で動くものは出来ましたがスコアが伸びません
　なんなら評価値貪欲だけの方が強い状態です

　探索するノードを選ぶにあたって盤面評価をする必要があるのですが、これがまた難しい
　最終スコアで評価すると絵具を使わないことが重視され過ぎて、累積エラー率で評価すると絵具が使われ過ぎるという困った状況です

　最終的に、絵具の使用コストは sqrt(D)に、使用量の傾斜を変化させたものを使いました
　こういったものはOptunaで最適化するべきですが、めんどくさがって今回もやれませんでした

最終ビジュアライザ

seed=0, score=66,499

シード毎のスコア

　今回、TやDといったパラメータによってスコアが大きくばらつくようでした
　期間中はあまり気にしていなかったのですが、極端に差のつくケースがあるかどうかは順位に影響するので探してみても良かったように思います

seed0 = 66,499
seed1 = 91,256
seed2 = 206,553
seed3 = 78,617
seed4 = 121,631
seed5 = 101,294
seed6 = 79,377
seed7 = 131,733
seed8 = 201,698
seed9 = 82,908

おわりに

　問題のパラメータによって最適な解法が色々ありそうな、面白い問題で今回も楽しめました！
　結局実装できたのは正方形区切りだけでしたが、過程では最上位の方針と近いことを考えることも出来ていました
　なんとなくできそうだな。から実装まで持っていく実力がまだまだ足りていないと感じました

　今回は時間減衰に勝てそうですが、ジリ貧になりつつあるので力を付けてもうひと伸びしたいですね！

AHC046参加記【最終49位】

問題

atcoder.jp

　20x20のグリッドグラフ上に、0〜39の数字が書いてある
　0から始めて昇順に全ての数字を訪問するという問題
　移動は、1マスずつの移動と、壁まで一気に滑走することができる
　また、自身の4方にブロックを追加したり、取り除いたりできる

解法

　必要な時にブロックを過去に作ったことにする、過去改変貪欲を実装しました

　初めて実装したので、最適な書き方では無いと思いますがご了承ください

ビジュアライザ

seed=0, score=1,450

概要

　0番から順に、bfsで次の数字へ到達する最短経路を探索し最初に見つかった経路で行動します

　0→1は、過去改変する過去が無いのでただ滑走or移動の行動になります
　行動の復元時に、各マスの上下左右のマスに対して過去改変用の情報を書き込んでおきます

　すると以降の探索時に、過去の場面でブロックを作ったことにする(取り除いたことにする)ことが可能になります

　小さい盤面で説明します

過去改変パート

　過去にブロックの変更を行うには、ターン数と方向だけ分かっていれば良いです

　移動を伴う行動の出力配列と、ブロックを変更する行動の出力配列を別に持つことで、過去に操作を挿入しても移動のターン数は変更されません

　注意としては、移動で乗るマスとブロックに変更を加えたマスは、改変用の情報を消しておく必要があります

　コスト2の行動が増えるため、普通のbfsでなくダイクストラ法で最短経路探索を行う必要があります(012bfsでも良いです)

　経路探索中に通ったマスをブロックに変えてしまう操作や、滑走で壁として使ったブロックを取り除くような操作をすると、出力が壊れてしまいます
　必要なブロックの情報を持ちながら探索するか、ブロックの操作時に行動を復元して判定を行うことで対策できます

提出コード

　上記の過去改変貪欲を実装することで、score=218,052で本番49位のスコアを出すことが出来ます(実行時間は7msです)

　Nimの提出になります

atcoder.jp

延長戦

　本番中は、ブロックを置く場合のみ過去改変を行い、ブロックを取り除く操作は1マス移動時のみしか行えていませんでした
　ブロックを取り除く操作も同じく過去に”やったこと”にできるため実装します

　すると、score=218,574で本番28位のスコアを出すことができます

　また、実行時間が余りまくっているため乱択山登りも実装してみます
　bfsでの探索中に、過去改変をする確率を90%にして実行時間の限り回します
　乱択ではなく、本当はビームサーチを実装した方がよいですが、時間に限りのある短期AHCでは乱数を使って、得点の上振れを期待するのも良い作戦だと思います

　実行すると、score=219,600でなんと本番10位相当になりました！

最終ビジュアライザ

seed=0, score=1,459

おわりに

　過去改変貪欲は、AHC042でadminのwataさんが使われていて、
Submission #62337792 - AtCoder Heuristic Contest 042　良い実装はそちらを見て下さい
　AHC042より今回の方が、過去改変という意味では理解や実装がしやすいので、取り組みやすいかなとは思います

　今回もなんとかレートの増価を継続できました
　3:30までバグがとれず、score=204,033で終了しそうでしたが、諦めずにバグを探し続けることで何とかなって良かったです
　問題を上手く分割して、小まめにテスト出来るような実装手順を確立するのが、短期に向けた次の目標になりそうです

　全体50位を目指せそうにもなって来たので引き続き頑張ります

Nim言語の良さを伝えたい

はじめに

　先日、AtCoder Heuristic First-step Vol.1 - AtCoder が開かれたこともあってか、ヒューリスティックに関する話題を良く見かけます
　AHCの参加人数が増えるのはとても良い事なので嬉しい流れだと思っています

　少しの懸念としては、Python等の実行速度が遅い言語で参加して、それを理由に諦めてしまう人がいるかもしれない。ということです
　私自身、取り組み始めてから約1年はPythonでAHCに参加しており、実行速度を理由に諦めかける時もありました(Pythonだけでも強い人は何人もいます)

　そんな人たちに選択肢の一つとしてNim言語を紹介することで、あわよくば使い手になって欲しいなと思い記事を書くことにしました
　良ければ読んでいって下さい

良いと思う点

実行速度が早い

　Pythonと比べると。という意味では速度が一番のメリットです

　Nimは、C++にトランスコンパイルしてから実行されるため高速に動作します
　実装方法によってかなり前後しますが、C++はNimの2倍程度速く、NimはPythonの5倍程度速いイメージです

　いい感じのベンチマーク結果を見つけられなかったため、ABCの提出時間等で比較してみてください
　大体上記のような感じになっていると思います

文法がかなりPythonに似ている

　文法が似ている≒学習コストが低いと言えます
　Nim言語は、型が付いただけのPythonと呼んでも差し仕えない程度には似ています

　ABC402 B - Restaurant Queue で比べてみます

Python

from collections import deque
Q = int(input())
q = deque()
for _ in range(Q):
    buf = [int(i) for i in input().split()]
    if buf[0]==1:
        x = buf[1]
        q.append(x)
    else:
        print(q.popleft())

Nim

import std/deques
var Q = input(int)
var q = initDeque[int]()
for _ in 0..<Q:
    let f = input(int)
    if f==1:
        let X = input(int)
        q.addLast(X)
    else:
        echo q.popFirst()

　dequeを使った実装ですが、型の指定以外はほぼ同じ記述です
　インデントでブロックを区切る、セミコロン不要、などは親和性が高いのかなと思います

　ちなみに、nimのdequeはランダムアクセスがO(1)です

enumerateを書かなくてよい

　Pythonで配列Aの中身とインデックス番号を同時にループで回すには以下のように書くと思います

A = [1, 3, 5, 7]
for i, a in enumerate(A):
    print(i, a)

　Nimでは以下のように書けます

var A = @[1, 3, 5, 7]
for i, a in A:
    echo (i, a)

　i, をfor文の最初に付けるだけでインデックス番号も一緒に取得できます
　もちろん、for a in A: のように書くだけにしてループを回すこともできます

block文で多重ループを一気に抜けられる

　Pythonで多重ループを抜けたい場合、フラグなどを用いて処理するかと思います
　もしくは、for-elseを用いてもループ内のbreakを検知できます

flg = False
for i in range(10):
    for j in range(10):
        for k in range(10):
            if i+j+k>=10: 
                flg = True
                break
        if flg: break
    if flg: break

　Nimには、block文があり、ラベルを指定してbreakすることができます

block loop:
    for i in 0..<10:
        for j in 0..<10:
            for k in 0..<10:
                if i+j+k>=10:
                    break loop

　インデントが一段深くなってしまいますが、シンプルに記述できるのは嬉しい人も多いのではないでしょうか

コンパイル時の前処理が簡単

　Pythonでコンパイル時間を利用した前処理を書くこともできるようですが、あまり実用的でない(Cythonのみ?)と認識しています

　Nimでは、コンパイル時に計算できる処理であれば、constを付けて宣言するだけでコンパイル時に前計算を済ませておくことが出来ます
　いくつか自分が使用している例を置いておきます

エラトステネスの篩で素数を列挙しておく(ACL-Nimを利用)

import atcoder/extra/math/eratosthenes
const primes = initEratosthenes(10**6).prime

焼きなまし遷移用の乱数準備

var rng {.compileTime.} = initRand(0x1337DEADBEEF)
const logList = newSeqWith(0x10000, ln(rng.rand(1.0)))

　他にも、固定マス数のグリッドグラフの隣接リストやZobristHash用の配列を作ったりしています

糖衣構文(シンタックスシュガー)が面白い

　聞き慣れない言葉だと思いますが(自分も調べて今知りました)、同じ意味の処理を複数の書き方(より簡単な)が出来るというものです

proc add1(a: int): int=
    return a + 1

let x = 10

# 引数が複数あっても使える書き方
echo add1(x)
echo x.add1()

# 引数が1つの時のみ使える書き方
echo add1 x
echo x.add1

　引数が1つの時のみ、括弧()を省略することができますが、これを使うかどうかは人によって好みが分かれるようです（自分は好きです）

　ところで、Nimにはclassという概念がありません
　その代わり、関数宣言の第一引数のオブジェクトにバインドしているかのように記述することが出来ます(上記のドット記法)

Pythonでのクラス定義とメソッド

class Person():
    def __init__(self, height, weight):
        self.height = height
        self.weight = weight

    def get_bmi(self):
        return 10000 * self.weight / self.height / self.height

p = Person(170, 65)
print(p.get_bmi())

Nimで同じような処理を書く場合

type Person = object
    height: int
    weight: int

proc initPerson(height, weight: int): Person=
    result.height = height
    result.weight = weight

proc getBMI(self:var Person): float=
    return (10000 * self.weight).float / self.height.float / self.height.float

var p = initPerson(170, 65)
echo p.getBMI()

　getBMI() の宣言を見ると、第一引数にPersonオブジェクトを取っています
　このような場合、Personオブジェクトのクラスメソッドかのように、p.getBMI() と関数を呼び出して使用することが出来ます

メソッドチェーンでスマートに書ける

　第一引数の型にドット記法で関数を呼び出す事を利用すると以下のような書き方も出来ます

let dx = 10
let dy = 5

echo (dx**2 + dy**2).float.sqrt.int

　上記は整数のユークリッド距離を求めるコードですが、計算結果を変換していく手続きを直感的に書き連ねることが出来ています
　pythonでは、関数を必ず前に書くためこのようには書けません

　また、自分で宣言したオブジェクト以外にも、既存の型に対しても同じように関数を宣言して使用することも可能です(これが好き)
　例えば、以下のようにint型に対して3乗を求める関数を用意することが出来ます。便利です

proc pow3(n: int): int=
    return n**3

let num = 10
echo num.pow3()

演算子を自分で定義し直せる

　Nimでは演算子も関数の一種です(NimWorld | 関数)
　演算子の定義をし直すことで、自分の好みの記述方法に変えることが出来ます

　例えば、累乗の演算は `^` が定義されていますが、Pythonでは xor を表すため紛らわしいです
　Pythonのように書きたければ、以下のように定義し直すことで使いやすくなります

proc `**`(x: int, y: int): int = x ^ y      # ** を累乗の演算子に再定義
proc `^`(x: bool, y: bool): bool = x xor y  # ^ をxorの演算子に再定義

　このように、テンプレートを整備することで自分にとって一番分かりやすい環境を整えることが出来ます

イマイチだと思う点

インデントにTabが使えない

　Nimは、スペース2つをインデントとすることがデフォルトになっています
　pythonから移行した時にここがストレスでしたが、今は全ての言語でスペース4つのインデントに統一したため自分は全く問題に感じてはいません

謎のバグを踏むことがある

　他の言語と比べると、歴史も浅くユーザー数も多いとは言えないため言語自体にバグがあることもあります
　また、検索してもあまりヒットせず解決に時間がかかる場合もあります

　tuple型の要素アクセスに変数を使えないことを知らず、調べても上手く見つからず数時間溶かしたこともあります

ChatGPTのコード生成の精度が悪い

　最新のo3などでは試していませんが、少なくともo1のモデルが正しいNimコードを出力することは難しく、コードの修正だけで2,3回のやり取りが発生しています
　自分が生成AIを使用する際は、pythonで出力してもらったものをNimに書き換えて使っています

　言語の使用者や、ネット上の記事が増えるとそのうち改善されるのかなと思っていますが、正直生成AIの恩恵を受け切れていない感はあります
　良いプロンプトを知っていれば是非教えてください

おわりに

　いかがだったでしょうか
　Nim言語の便利さ、面白さが少しでも伝わっていれば嬉しいです

　いくつかデメリットも書きましたが、それらを補って余りあるメリットもある言語だと思っています

　持ち替え検討しようかなという方がいれば、出来る限りサポートしますので気軽に連絡下さい！