70,980点で 192位/678人 でした。
今回は方針を途中までしか実装できず、苦しい回でした。
正直かなりやらかしたつもりだったのですが、それでも上位30%には入れていたので、 他の参加者も同じく苦戦していたのではないかと思っています。4時間だとちょっと短すぎたような。
解法
方針
枠に沿って二重四角を描く方針を取りました。
具体的な手法としては、ビームサーチを使いました。 設定は、
- 状態: フォーカスする座標と、どの方向からそこへ入ったか
- 遷移: 回転することで可能な移動全て
- 評価値: 四角形を描く方向に進んでいるかどうか
- ビーム幅: 2,000
としました。
しかし、実装は終わりきらず、下画像のように大外の四角を作るところで終わってしまいました。 評価値も雑で、あんまり壁沿いにできてもいないです。
提出コードはこちらです。 Submission #31233452 - ALGO ARTIS Programming Contest 2022（AtCoder Heuristic Contest 010）
方針の考察
ビジュアライザの手動操作モードで遊んだところ、そもそも閉じるのが難しくない？という気持ちになったので、できるだけ単純な図形を大きく用意しようと考えて、二重四角を描く方針を取りました。
が、コンテスト後のTLを見ていると、DFSをやれば割と自然に環は閉じられるっぽいですね。
所感
冒頭で書いた通り、実装時間が足りなくて苦しかったですね。
TLを見た感じだと、上位勢はDFS+焼きなましが多そうでした。 AHC002が似たような感じだったので、これを思い出して試そうと思えたら良かったのですが。。
