AHC065参加記
はじめに AtCoder Heuristic Contest 065 に参加し、304位(perf 1471)でした。 今回は初めて本格的にAIを使ってコーディングするスタイルでやったので、そのあたりも含めて参加記を書きたいと思います。 問題 https://atcoder.jp/contests/ahc065/tasks/ahc065_a 縦20x横20のグリッドに番号のついた箱が敷き詰められている グリッドにベルトコンベアを設置して番号順に箱を搬出する（搬出口はグリッドの上部中央のマス） ベルトコンベアの条件 サイクル状でなくてはならない ただし2マスのみからなるベルトコンベアは許容（実質的に隣あう箱をスワップすることになる） 同じマスに置けるベルトコンベアのレールは2つまで 異なるベルトコンベアを同時に動かすことはできない なるべく少ないターン数（ベルトコンベアを一マスだけ進めるのを1ターンと数える）ですべての箱を搬出せよ 解法 縦2x横Nの横長ベルトコンベアと、縦Nx横2の縦長ベルトコンベアを敷き詰め、次の箱を搬出するまでを1遷移としたビームサーチを行いました。 ベルトコンベア 縦2x横Nの横長ベルトコンベアと、縦Nx横2の縦長ベルトコンベアを敷き詰めることでどの位置にある箱であっても上下左右自由に動かすことができるようになります。 これにより次の箱を搬出口まで最短距離で運ぶことができるようになります。 ビームサーチ 次の箱を搬出口まで最短距離で運ぶにしても複数のルートがあるため、ビームサーチで探索してよいルートを選ぶようにしました。 次の箱を搬出するまでを1遷移としています。ルートの選び方は全パターンを試すことはできないため、方向転換を2回まで（例：左右に動いてから上に曲がり、再度左右に曲がるなど）とするルートに絞りました。 評価関数はターン数 + 1～8個先の箱と搬出口までの距離としています。 正確にいうと、T(i) : 箱0～箱iを搬出するまでにかかった通算ターン数、D(i) : 箱iと搬出口のマンハッタン距離とした場合、評価関数 E(i) は E(i) = T(i) + Σ (D(i+j) / j) [j = 1〜8] としています。 意味合い的にはこの後近々搬出することになる箱が搬出口に近いほうがうれしいのでそれを考慮しています。jの数が...