takitamo_software.log

はじめに AtCoder Heuristic Contest 069 に参加し、568位(perf1202 )でした。 今回は考えたことのメモ書き程度になりますが参加記として残しておこうと思います。 問題 https://atcoder.jp/contests/ahc069/tasks/ahc069_a 縦50x横50のグリッドがある。 グリッドには障害物がランダムに配置されている。 グリッドに指定されたサイズ・時間のマス（以下グループと呼ぶ）を割り当てる。 グループを割り当てると割り当てたグループに応じた報酬が得られる。 配置するグループは分離不可（上下左右に連結である必要がある）。またグループの形状は正方形に近いほうが高報酬。 グループの割り当ては拒否することもできる。その場合はそのグループ分の報酬は得られない。 途中でグループを再配置することが可能。ただしコストがかかる。 割り当てるグループ情報は先読み不可（インタラクティブ問題）。 得られる報酬を大きくするのが目的。 今回の取り組み方 前回は生成AI未使用でしたが、今回は生成AIを少し使用しています。使用したのは主に Gemini 3.6 Flash のブラウザチャット（無料版）です。 序盤は自分でコーディングして、生成AIはデバッグや出力結果の整理など補助的な用途で使用しました。 終盤、自分でできることが減ってきてからは 現状のコードの改善点の案を出してもらう 出してもらった改善点でコードを直してもらう いくつか入力・出力結果を与えて結果を分析してもらう（今回だと拒否すべきでないグループを拒否していないかなど） など用途を広げました（ただ、結果にはそれほどつながってません）。 解法・考えたこと もしかしたら最終提出コードに反映されてないかもしれませんが、解法と試した点を記載します。 グループ受け入れの判断 マス・時間当たりの収益で評価して、基準値以上、かつ空きがあれば受け入れるようにしました。収益の基準値については固定とはせず以下に記載する内容で変化するようにしました。 現時点の空き状況 空きが多い場合は比較的収益が低いグループも受け入れられるよう緩めに、空きが少ない場合は収益が高いグループが来た時に受け入れられない事態を避けるよう厳しめにしました。 経過ターン数 開始直後は受け入れ余力が大きく、また終了直...

はじめに AtCoder Heuristic Contest 068 に参加し、555位(perf1088 )でした。 今回までは短期AHCでの生成AIの使用がOKでしたが、次回の短期AHCでは使用禁止になるので先を見据えて生成AIなしでやってみることにしました。 成績も成績なので有益なことはあまり書いていないですが、生成AIなしでやるとどうなるかという意味ではもしかしたら参考になるかもしれません。 問題 https://atcoder.jp/contests/ahc068/tasks/ahc068_a 正方形状のグリッドマスがあり各マスに番号がかかれたカードが置かれている グリッドのマスの境界の一部には仕切りがある 仕切りで遮られない長方形を選んで上半分と下半分、または左半分と右半分のカードを入れ替える操作を行うことができる なるべく少ない操作数でカードを正しいマスに並べ替えるのが今回の目的 解法 操作は隣り合うカードを交換する操作のみとし、カードを1枚ずつ順番に正しいマスに運びました。一度処理し終わったカードの位置は固定し再び移動しないようにしています。 1. 処理するカードを決める 2. カードの現在位置から目的地マスまでの経路をBFSで求める 3. 上記2で求めた経路に沿って縦2x横1 or 縦1x横2の長方形を選ぶ操作を行うことでカードを交換して運ぶ 処理するカードの順番 ランダムに選んだマスを根とする木を乱択DFSで作成し、DFSの帰りがけ順に操作しました。 問題文中の例を見ると、なるべく端・壁際から順番に処理したほうがよいのだろうと思い、最初は次数が少ないもの順としていたのですが、その方法だと途中で連結が切れてしまい全部のカードを処理できない問題が発生しました。 連結が切れないように毎回UnionFindで確認することも試みたのですが、それだと処理時間が間に合わなくなり断念。 グリッドから木を作って木の葉に当たる方から処理すれば連結が切れることなく処理できると考えてこの案に落ち着きました。 DFSで作った木から順番を決めることで連結は切れなくなりましたが、端・壁際でないマスが比較的早い段階で処理されてしまい効率が悪いことには、ビジュアライザを見てすぐ気づいたのですが、コンテスト中に解決することはできませんでした。 なお、根とするマスやDFSの向きはラン...

 はじめに AtCoder Heuristic Contest 067 に参加し、397位(perf 1304)でした。 考えたことや反省点などを簡単にまとめたいと思います。 結果が結果なのであまり参考にはならないかもしれませんが悪しからずご了承ください。 問題 https://atcoder.jp/contests/ahc067/tasks/ahc067_a 迷路状になっているグリッドマスがある 迷路を進む相手を妨害するのが今回のミッション スイッチと仕掛け扉（以下扉）を配置して、相手がスタートからゴールまで到達する手数をできるだけ稼ぐ スイッチと扉には番号が付いていてスイッチを押すと同じ番号の扉の開閉が切り替わる 扉は最初開/閉どちらの状態で置いてもよい 相手が理論上ゴール不可能な状態にしてはいけない（ゴールできる範囲で手数を稼がせる必要がある） 解法 ゴールを扉0(閉)で囲んでふさぎ、その扉0(閉)を開けるためのスイッチを扉1(閉)でふさいで・・・を繰り返しました。 公式の解説放送の「線形スイッチ解法」とほぼ同じかと思います。 https://www.youtube.com/watch?v=MmtDPoffLe0 スイッチを置く位置はBFSで求めて決めました。最初のスイッチ0はスタートからスイッチ0を経由してゴールまでの距離が一番遠くなるようなマスに置き、以下同じ要領でスタートからスイッチ0までの距離が一番遠くなるマスにスイッチ1を置いて・・・を繰り返しました。 この方法だと置くことのできる扉の数が余るので、余りはランダムに扉0(閉)を置いて距離を稼がせる山登りをしました。 スタート時点：ゴール・スイッチの前に扉を配置 ゴール後：状態が有効活用できてない コンテスト後に試した解法 ゴールの前に追加で扉1(開)～扉9(開)を置くようにしました。コンテスト中に提出した解法ではゴールを守る扉0(閉)を開くためにはスイッチ9～スイッチ1を順番に押していく必要がありますが、扉0を開いたときには今度はゴールの前にある扉1～扉9が閉まっていてもう一回スイッチ1～スイッチ9を順番に押さないといけないという狙いです。 スタート時点：ゴール前に多重に扉を配置 スイッチ0到達時点：新たに扉が閉まっている ゴールの前の扉は、ゴールからBFSを行い、最短距離の変わり目に距離に応...

 はじめに AtCoder Heuristic Contest 066 に参加し、438位(perf 1447)でした。 結果は微妙ですが、少し特徴のある解法を試したので、その辺りの説明を中心に参加記を残したいと思います。 問題 https://atcoder.jp/contests/ahc066/tasks/ahc066_a グリッドに番号のついたボールとかごが散らばっている ロボットを操作してボールを同じ番号のかごに入れる ロボットは最大1個のボールを運ぶことができる ロボットの基本動作は'F'(直進)、'R'(右回転)、'L'(左回転)、'S'(今いる位置に置いてあるボールと持っているボールを交換) 上記基本動作のほか、ロボットにはマクロ機能がある 'M': マクロ記録開始/終了。開始～終了までに実行した操作列がマクロに記録される。 'P': 記録したマクロを実行する マクロは1つしか登録できない。新しいマクロの記録終了まで古いマクロが有効。 なるべく少ない操作列ですべてのボールをかごに入れる ただしTターン以内に収めること。'P'でマクロを再生した場合、そのマクロの長さ分だけターン数を消費することに注意 解法 マクロを固定してボールの処理順を焼きなましました。マクロは3～8回連続で直進するものを用意してその中で一番結果が良かったものを採用しました。 この解法にプラスして一気にまとめて処理できそうなボールはグループ化して回転ベルトコンベアマクロを作って一気に処理しました。 ボールの処理順 まず最初に使うマクロを決めたとき(例えば3回連続直進)に開始点および各ボール/かご同士の移動にかかる操作数をBFSで求めました。遷移は'F'(直進)、'R'(右回転)、'L'(左回転)、'P'(マクロ使用)です。今回は向きを変えるのにも1手必要になるため、向きも考慮した頂点倍化BFSを使っています。 これを使って操作列が少なくなるようなボールの処理順を焼きなましで求めました。 ただし次に述べる回転ベルトコンベアマクロで処理するボール群は除いています。 回転ベルトコンベアマクロ 例えば4つのボールがあった...

はじめに 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の数が...

はじめに AtCoder Heuristic Contest 064 に参加し、440位(perf 1298)でした。 成績は芳しくないですが、参加記を残そうと思います。 問題 https://atcoder.jp/contests/ahc064/tasks/ahc064_a ルールベースで車両を1台ずつ順番に揃えていく方法を採用しました。 指定された線路に車両を指定された順番に少ないターン数で並べていくのが目的。 線路には最終的に列車がならぶ出発線のほか、バッファ的な意味合いの待機線がある 車両は全部で100台、出発線・待機線はそれぞれ10列。 列車は出発線ー待機線間を移動可能（出発線同士、待機線同士の直接移動は不可） 1ターンに車両が衝突しない限り（＝移動線が交錯しない限り）同時に複数の移動が可能 解法 ルールベースで車両を1台ずつ順番に揃えていく方法を採用しました。 ターゲットとする車両（以下、対象車両）を以下の3ステップで目的の場所へ運びます。  1. 対象車両を待機線の先頭へ移動 対象車両が出発線、待機線のどちらにいるかで分岐します。 出発線にいる場合：その列の末尾から対象車両までを待機線へ移動。 待機線にいる場合：対象車両より前にある車両を、目的以外の出発線へ一時退避   2. 目的地の整理  目的の出発線にある邪魔な車両を、対象車両がいる待機線とは別の待機線へ移動。  3. 目的地への移動 対象車両を待機線から目的の出発線へ移動。  出発線・待機線間の移動は、物理的な距離が近くなるものを優先して選択しました 。 処理順は「IDの下1桁（＝格納先の列番号）」が小さい順とし、同グループ内はランダムに決定。制限時間いっぱい試行してベストなスコアを採用しました。 最後に、全手順を見直して独立して行える（＝移動線が交錯しない）操作を1ターンに集約する後処理を行っています。  反省点 車両をひとつずつ処理することに縛られてしまった この手順に縛られている限り、一つの車両を正しい位置に移動させ終わるまで、ほかの車両のことを考慮することが全くできません。 この手順の制約が大きすぎて改善する余地がほとんどありませんでした。 車両の処理順を一部ランダム化して山登り（あるいは多点スタート）のような形を試しま...