AHC069参加記

はじめに

AtCoder Heuristic Contest 069 に参加し、568位(perf1202 )でした。

今回は考えたことのメモ書き程度になりますが参加記として残しておこうと思います。

問題


  • 縦50x横50のグリッドがある。
  • グリッドには障害物がランダムに配置されている。
  • グリッドに指定されたサイズ・時間のマス（以下グループと呼ぶ）を割り当てる。
  • グループを割り当てると割り当てたグループに応じた報酬が得られる。
  • 配置するグループは分離不可（上下左右に連結である必要がある）。またグループの形状は正方形に近いほうが高報酬。
  • グループの割り当ては拒否することもできる。その場合はそのグループ分の報酬は得られない。
  • 途中でグループを再配置することが可能。ただしコストがかかる。
  • 割り当てるグループ情報は先読み不可（インタラクティブ問題）。
  • 得られる報酬を大きくするのが目的。

今回の取り組み方

前回は生成AI未使用でしたが、今回は生成AIを少し使用しています。使用したのは主に Gemini 3.6 Flash のブラウザチャット（無料版）です。

序盤は自分でコーディングして、生成AIはデバッグや出力結果の整理など補助的な用途で使用しました。

終盤、自分でできることが減ってきてからは
  • 現状のコードの改善点の案を出してもらう
  • 出してもらった改善点でコードを直してもらう
  • いくつか入力・出力結果を与えて結果を分析してもらう（今回だと拒否すべきでないグループを拒否していないかなど）
など用途を広げました（ただ、結果にはそれほどつながってません）。

解法・考えたこと

もしかしたら最終提出コードに反映されてないかもしれませんが、解法と試した点を記載します。

グループ受け入れの判断

マス・時間当たりの収益で評価して、基準値以上、かつ空きがあれば受け入れるようにしました。収益の基準値については固定とはせず以下に記載する内容で変化するようにしました。

現時点の空き状況

空きが多い場合は比較的収益が低いグループも受け入れられるよう緩めに、空きが少ない場合は収益が高いグループが来た時に受け入れられない事態を避けるよう厳しめにしました。

経過ターン数

開始直後は受け入れ余力が大きく、また終了直前は機会損失の可能性が減るためともに収益の基準値を緩めにしました。

障害物の分布

ビジュアライザで結果を確認していて体感ですが、障害物マスが多い場合は受け入れ条件を厳しく、少ない場合は緩くするのがよさそうに見えたので、調整しました。

グリッドを5x5の小領域に分割して割り当てるグループを管理

グリッド全体を5x5の小領域に分割して、その単位でグループ割り当てを管理するようにしました。グループのマス数が大きい場合は小領域を連結することで、大きなマス数を確保可能としました。

狙いとしては以下の2点です。
  • 配置先候補を探索するための計算量の削減
  • 配置する形がきれいな形になりやすいようにする
    • 小さな正方形（もしくはそれを何個か連結した形）に収まるように配置されるため、おのずときれいな形になりやすくなる

配置先の選定

上記の小領域の単位で探索を行い配置先を決めました。

配置先の決定方法ですが、以下の方針にしました。
  • グループのマス数が少ない場合
    • 小領域を固定して割り当てる都合上、隙間ができやすいため隙間が少なくなる小領域を選ぶ
      • たとえばグループが12マスの場合、空きますがちょうど12マス（小領域自体は5x5=25マスなので、障害物が13マス）あるような小領域がベストと判定する
  • グループのマス数が多い場合
    • 小領域を連結するため、使用する小領域数が少ない候補を選ぶ
      • 使用する小領域数が少ない＝障害物などで形が崩れにくい

なるべくきれいな形状でグループを配置

最初は（小領域の連結、小領域内の配置マス決定とも）BFSで行っていたのですが、どうしてもひし形に近い形が出来上がってしまうために、始点からのチェビシェフ距離（縦方向の距離と横方向の距離の長いほう）を使ったダイクストラ法で作るようにしました。

また、出来上がった領域に対して一マス別の場所に付け替える山登りを行い、きれいな形に近づけるようにしました。ただし、計算量が重いため、実行時間が制限時間に近づくにつれて回数を減らして最終的には山登り自体をスキップするようにしました。

移動について

受け入れたいが空き場所が確保できない場合は、グループの移動を試すようにしました。移動については配置済のグループをランダムに1つ選んで別の場所に移動する方針としました。

移動先はランダムではなく現時点での状況で改めてルールベースで置きなおしたものとして考えました。移動先も複数候補を試したほうがよいとは思いますが、そこまで手が回りませんでした。

グループを移動することによるコスト（移動に伴うコスト＋移動後の形が崩れることによるコスト）と受け入れ可能となるグループからの収益を比べて、プラスになるなら受け入れるようにしました。

こちらも計算量が重いため、実行時間が制限時間に近づくにつれてランダムに試す回数を減らし、最終的にはスキップするようにしています。

反省点

確証はないのですが、5x5の小領域にこだわったのが良くなかったかもしれません。小領域で考えることで見通しがよくなることを期待して採用したのですが、隙間がどうしても多く生まれてしまうため、多くのグループを受け入れられなくなる要因になってしまっているかもしれません。

また、これはコンテストの立ち回りになりますが、システムテストでWAが2つ出てしまったのも反省点です。2つなので順位への影響はあまりないと思いますが、これまで長期コンテストでは必ずやっていた1000ケース以上での動作確認を怠ったことが原因なので、やれることをやらなかったという意味では結果以上に反省点だったと思います。

感想

出したアイディア自体はそこまで悪くなかったと思います。それだけにスコアが伸びなかった原因をつかめていないのは気になりますが。

ここまで読んでくださりありがとうございました。

このブログの人気の投稿

AHC063参加記

イメージ
はじめに AtCoder Heuristic Contest 063 に参加しました。 その参加記です。 問題 問題はこちらです。 https://atcoder.jp/contests/ahc063/tasks/ahc063_a 自分なりにかいつまんで言うと 正方形状のグリッド上を蛇が移動できます。蛇の体自体もグリッドの連結した数マスを占めます。 グリッドのマス目には色のついた餌が散らばっています。 蛇が餌を食べると蛇のしっぽが長くなり、長くなった部分は食べた餌の色になります。 グリッド内の餌をすべて食べたときに蛇の色が指定通りになっている、つまり正しい順番で決められた色の餌をできるだけ少ないターン数で食べていくのが目標です。 ただし、胴体と頭が重なると胴体を噛みちぎります。噛みちぎられたしっぽ側はその位置で再び餌となってグリッド上に配置されます。 つまり、順番通りに餌を食べられなかった場合は、噛みちぎることで途中からやり直しすることができます。 解法 ルールベースに一部ビームサーチを採用しました。 正しい餌を食べるルートをビームサーチで一気に決定し、正しい餌が見つからない状況や間違った餌を食べてしまっている状況はルールベースで打開。 具体的には、完成するまで以下1～3のいずれかの行動をとります。数字が小さいほうが優先です。これを完了するまで（もしくはターン数や制限時間に達するまで）繰り返します。 1. 間違った餌を食べてしまっている場合 頭から間違った餌までのどこかの胴体を噛みちぎって分離し、その後正しい位置まで胴体を復元。 胴体を噛みちぎるための経路をBFSで求めています。ただし最短経路だけにすると手詰まりになりやすいため噛みちぎることが可能な行き先マスをすべて求めてその中からランダムに決定するようにしています。 2. 正しい餌が見つかる場合 途中で違う餌を食べることなく、かつ胴体を噛みちぎることなく正しい餌を取ることができる場合、次の餌までの移動を1遷移としたビームサーチを行い、最も多くの餌を取り続けられるルートを採用。餌の数が同じルートが複数ある場合はターン数が少ないものを採用としました。 次の餌までの移動を1遷移とした理由は、自分がビームサーチをほぼ初採用という状況だったのでビームサーチで解くところを単純化したかったためです。例えば1ターン1遷移などとし...
続きを読む

AHC066参加記

イメージ
 はじめに 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つのボールがあった...
続きを読む

AHC064参加記

はじめに 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ターンに集約する後処理を行っています。  反省点 車両をひとつずつ処理することに縛られてしまった この手順に縛られている限り、一つの車両を正しい位置に移動させ終わるまで、ほかの車両のことを考慮することが全くできません。 この手順の制約が大きすぎて改善する余地がほとんどありませんでした。 車両の処理順を一部ランダム化して山登り（あるいは多点スタート）のような形を試しま...
続きを読む