こんにちは。競技プログラミングのコンテストに参加しているyunixです。 estie プログラミングコンテスト2022(https://atcoder.jp/contests/ahc014)に参加しました。2週間は長くて超大変でしたね。 コンテスト中に考えたこととかやったことを書いていこうと思います。
解法概要
焼きなましです。ランダムに長方形を破壊して、新しく長方形を繋ぎ直しました。スコアは手元の環境で大体1.24Mくらい(500ケースの平均, 50ケースだと62M)でした*1。 主な工夫は以下の2つです:
- 一定の確率で前の状態で存在していなかった長方形を優先的に作るようにした
- 同じ状態の出現を防ぐ目的
- 初期配置の密度の高い盤面で中央の部分だけを焼きなましした
- 得点源は外側に伸びるツノ状の構造物なので、それが構築されやすいように土台を整える焼きなましをしました
- 中央部分だけを焼くと外側の部分を作らないでいいので、焼きなましの回数の面でメリットがあると思ってやりました
- 土台の部分を伸ばしやすいように、長方形を破壊する場所は土台の根本付近が多くなるようにもしました
密度が高い盤面での工夫: 中央部分を先に焼く(seed=4)
ただし、上の工夫がクリティカルに効いたかと言われると微妙で、ナイーブに小さな領域を壊してつなぎ直すを時間いっぱいやるだけでも50ケースで59Mくらいは出ました。 工夫はいろいろ他にも考えたのですが、一番スコアに効いたのは処理の高速化でした...
問題概要
- グリッド上(一辺の大きさ=N: 31~61)の中央付近に点が配置されています
- 中央のN/4 ~ 3N/4の領域にのみ点が配置されていて、点の密度は大体0.1~0.4くらいです
- 点を3つ選んで、その3つの点を通る長方形ができるように新しい点を打ち、線を引きます
- この際に、線を引くときに他の点の上を通るような線は引けません
- また、長方形は軸に並行、または45度傾いた方向のものだけしか作れません
- 得点はグリッド上の点の数で決まり、外側の点(すなわち初期配置から遠いような点)の方が配点が割り振られています
最初に問題を見て思ったこと
- 問題がシンプルだな。。。4時間用のコンテストの問題と間違えたのでは? 簡単そう。
- (上の感想の5分後)めちゃくちゃ大変だった。どうアプローチしていいかさっぱりわからない。
- 外側の点の方が得点が高いみたいだけれど、どうやって外側に長方形を伸ばしていけばいいかさっぱりわからない
- 多分あまり長い辺があるのは好ましくなさそう。途中の長方形の可能性を摘んでしまう。
問題に対するアプローチ
方針を決める際に考えたこと
何もわからないので、とりあえず順番に長方形を繋ぎまくってみました。
その結果、いくつか点数が高いseedがあり、それを調べてみると以下のような感じの結果になっていました:
ここまできて解法のアプローチを決めました:
- 大雑把にはツノ状の構造物を大きくすることができればいい
- 最初の盤面がまばらなときには難しそうだけど...
- 長方形の構築に順序関係があるし、いかにもビームサーチが有効そう
- しかしビームサーチは経験不足で良い評価関数が作れる気がしなかった*2
- 一方で、長方形の構築の影響は割と小さな領域に限られそう
- 外側にツノを伸ばすには外周付近の条件が整えばいいので、局所的に何度も壊してつなぎ直すを試すと良い解見つかりそう
- 焼きなましが結構うまくいきそう?
というようなことを考えて、焼きなましでやってみることにしました。
最終的な解法
- 基本的には一部の領域(１辺が1~2くらいの長方形)に被っている長方形を全て破壊して、新しく長方形を繋ぎ直しました。
- 繋ぎ直すときにランダム性を持たせたのですが、小さな長方形が先に作られやすいようにしました
盤面のサイズや点の密度にもよりますが、大体30,000 ~ 80,000回くらい遷移をしていたと思います。 内側の領域を焼きなます際の評価関数などについて後で書こうと思います。
実装面での工夫
以下のようなクラスを作りました:
- GridPaperクラス: 方眼紙の状態を保持するクラス
- どこに点が置かれているか、どこの長方形が繋がっているか、次にどこに長方形を繋げられるかなどの情報を管理
- 長方形を追加したり、消したりするようなメソッドを外部に公開している
- Neighborhoodクラス: 焼きなましの近傍のためのクラス(というか抽象クラス)
つまり、
- 盤面の状態を保持し、それを変更するための(抽象的な概念の)メソッドを提供するためのクラス
- 盤面に対して操作をする戦略(焼きなましの近傍)を保持するためのクラス群
を分けて作りました。
以前は盤面の状態を保持するクラスの方に操作をする戦略(焼きなましの近傍)を書いてしまっていたのですが、クラスが肥大化していていつもストレスに感じていました。 今回は近傍処理を別のクラス群に切り出すことによって多少マシになりましたし(それでも状態管理のクラスはでかいのですが...)、以下のようなご利益も感じました
- 状態管理の具体的な実装方法が外部に漏れないので、焼きなましの操作を書くときに抽象的な命令だけを書いていけば良い
- 同じ理由で、状態管理の具体的な実装を変更して高速化したい、というようなときに、状態を保持するクラスだけを変更すればよくて、変更理由が異なるものが別れていて高速化しやすかった
- 近傍処理を同じ抽象親クラスを持たせるようにしたことで、焼きなましをする際にどの近傍かを使う側で気にしなくて良くなった(ポリモーフィズム)
状態管理のためのクラスを実装しているときには単体テストを書いてもいいかもしれないと感じました。 外部に公開するメソッドは結構変わりにくいような気がします。それだったら2週間くらいのコンテストではペイするかもしれません。 そうでなくても複雑なことをしないといけないので、単体テストを捨てることを前提でテスト駆動開発をしても良いかもと思いました。C++のテストフレームワークを勉強してみるか...
そのうちもう少し詳しく実装の工夫を書くかもしれませんが今日は時間がないのでここまでにしておきます。
