takitamo_software.log

 はじめに 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つのボールがあった...