始めに
先日行われたAHC031にて、システムテスト15位を達成することができました。
私としては異例の好成績であるため、とても喜んでいます。
良い成績を残せた記念も兼ねて参加記を書くことにしました
以下簡単に自己紹介失礼します。
自己紹介に前述したとおり、レートも高くなく、経験も浅いため、高度なテクニックは使用していない(できていない）ので、理論や数学的な分析は殆ど書けないです。発想やお気持ちの部分に重点を置いて書いていくので、その辺ご了承ください。記事内で使用される用語に関しても、雰囲気で使っているので、間違っている可能性があります。
また、問題についてある程度、理解・考察が済んでいる前提で話は進めます。
全体を通した感想
賞金も貰えて、レートも増えて、一枚目に名前を残せて、何より嬉しい気持ちが強いです。結果だけでなく、コンテスト自体も、長期コンあるあるの抜きつ抜かれつの感じが楽しかったです。上位三人は、全く異なる革命的な解法を持っているのかなと思っていたのですが、箱を開けてみれば、同じ方針ということで、同じ方針でもこんなにも差が着くのだなぁ、と驚きました。
高速化が必要ということで、初めての試みとしてPythonをNimに移植したのですが、スコアも二倍近くに上がり、Nimの勉強もできたので充実した十日間になりました。
勝因は、
- 学生で春休みということもあり、時間だけは誰よりもあったので、Hコンにフルコミットできたこと
- 序盤に横の分割を固定するという発想に至れたこと
- Nimはいいぞ、宣伝してくれていた某羊さんがいたこと(マクロもお借りしました)
かなと思います。
初日から最終日まで1ページ目と2ページ目を行ったり来たりしていたのですが、好成績の副産物としてか、ツイッターのFFが増えました。嬉しいです。大した事呟いてませんが、よければフォローお願いします。
問題概要
詳細はこちらをご覧ください。
自分なりに要約したものを以下にまとめます。
最終提出コードの方針、お気持ち
前提の方針
より多い数の行に分けて固定し、縦線のみを移動させることを考えました。
既に分割された複数行の平面をN個の長方形に分けるには、約Ｎ本の縦線を配置する必要があります。であれば、コストは引いた縦線の長さの総和に依存することになります。その発想から、コストを下げたい->縦線の長さ、即ち各行の高さを小さくしたい->分割数を増やしたいという発想の流れになります。
(実際は、実験の中で、分割数増やしたらスコアが劇的に改善したことから、逆算的に上記のことに気づきました。)
コンテスト序中盤は、より縦横比が小さい正方形に近い形こそが至高だと考えていたため、それに気づいた時は目から鱗でした。
シード5(score = 8825)のビジュアライザは以下のようになります。
前提を達成するための具体的な方針
行の分割数、それぞれの高さの決定
より多くの行に分けたい、という気持ちがありますが、行を増やすほど面積の不足なく配置することの難易度が上がるというトレードオフな問題があります。そこで私は、二分探索を用いて、面積の不足なく配置可能な最大の行数を求めました。
(今思えば小さい方から線形に探索しても良かった気がしますが。)
そこで考えなくてはいけない問題が、行の分割方法、長方形の配置の方法です。貪欲で良い分割や良い配置を求めたいですが、私は思いつきませんでした。
良い分割や、良い配置が存在することは分かるが、それに達する手段が分からない->ランダムに決めて、それの良さを評価できれば、山登りできそう?という思考で山登りで行の分割数とその高さを決定することにしました。
行の分割数を決定する山登りに関する詳細
- 初期解
以下のように適当に作りました。お気持ちとしては、各ケースの面積の特性にマッチした初期解になればいいな～ぐらいで、0.25乗の部分も差が大きすぎるのは悪そう+実験する中で良さげだったという感覚的なものです。
- 分割数Bは予め決まっている。(上記二分探索のmidに相当)
- 全日における、i番目に大きい面積の平均Si_avrを計算
- [S1_avr, S2_avr, S3_avr..., SN_avr]を約N / B個ずつ、B個に分割する。
- 分割されたB個それぞれの総和を取り、それを0.25乗したものをh[h_1, h_2, h3, ... hB]とする
- 1000 * (h_i / sum(h))をそれぞれの高さheight_iとする
- 近傍
以下の一つだけです。
- 減らす行iと増やす行jをランダムに選択
- 減らす大きさは、1 ～ (height_i / 4)の中でランダムに選択
- それぞれ、減らす、増やす
- 評価関数
生スコアをそのまま計算
改善すれば採用、悪化すれば不採用のシンプルな山登りです。
与えられた分割数Bそれぞれに対し、この山登りを最大0.3秒行っています。
このパートは、分割行数を求めるのが目的なので、途中で面積を不足なく配置できた場合はその時点で山登りを打ち切るようにしました。
- 配置方法
以下のような適当な貪欲です。
色々試して良さげだったので採用しました。
お気持ちとしては、面積に適した行(大きな面積のものは、高さが大きい行に、小さい面積のものは、高さが小さい行に)に配置されて欲しいという感じです。
- 面積が大きい順に見ていく。
- 配置場所は、配置可能な行の中で最も縦横比が小さくなる行とする。
- どの行にも必要な面積が配置できない場合、はみ出る面積だけコストに加算する以外は特に何もしない。
行の高さを決定する山登りに関する詳細
上記の二分探索と、行の分割数を決定する山登りにより、面積を不足なく配置可能な最大の分割数、B_maxが求まりました。
ですが、このままでは配置は可能ですが、高さとしてはイマイチな状態(っぽい)です。
そこで、二分探索によって最終的に得られた、heightを初期解として、再度山登りを0.3秒実行します。山登りの中身は、面積を不足なく配置できていても続行すること以外はほとんど同じです。
これは、私のローカルテストでは殆どスコアに寄与しなかったのですが、スコアが改善するかつ、heightの分散が小さくなる場合のみ採用するようにしました。お気持ちとしては、後述する別の山登りでスコア増加の確率を上げられそう、というものです。
このパートに関して、後述する別の山登りにより、長方形（縦線）の配置場所はかなり変わるので、意味がないように思えたのですが、行っていた方がスコアが伸びたので採用しました。
ここまでで1.5秒弱くらいを使用しています。
縦線の配置場所の決定
ここまでで、heightを決めることはできましたが、縦線に関しての工夫を一切行っていません。横線は全く動かさないため、それだけでも最低限の改善はできていますが、可能であれば、縦線の移動も抑えたいところです。
そこで、縦線の移動を抑えるため、以下の貪欲法と山登り法による改善を行いました。
貪欲法による改善
二種類の貪欲法による改善方法を用意し、ケースごとに改善量が大きい方を適用するという形を取りました。
- 貪欲法_1
この貪欲は、余る面積が少ない場合に採用されることが多い貪欲法です。
- 1-2日目, 3-4日目, 5-6日目といった感じで2日ごとで区切り、2日単位での縦線の一致を試みる。
- 2日間で、まだ使用していない面積のうち、面積の差が最も小さくなるペアを見つけ、i日目, i+1日目両方で、そのmaxを取った場合に配置可能かを判定
- 配置できれば、ペアの数を増やす、ということを繰り返す
2-3日目, 4-5日目, 6-7日目...で区切るような、偶奇反転した組も試しています。
日付全体で、ペアを作って縦線の場所一致させることができた回数を、偶数スタート、奇数スタートそれぞれで管理して、返すようにしてます。
配置の方法は分割数や高さを決める山登りのものと同じです。
- 貪欲法_2
この貪欲は、余る面積が多い場合に採用されることが多い貪欲法です。
貪欲_1では、2日のペアを作っていたため、ペアとペアの間の部分の縦線は全く考慮していません。
余る面積が大きく、三日以上のペアを作ってもそれなりに一致させられるケースでは、貪欲_1ではイマイチなので、そのカバーを行うような役割を持つ貪欲法になります。
l = 1, r = 2とする。
- l日目からr日目までの中で、面積の大きい順に見ていき、何個目までmaxを取って配置可能かを判定
- (N / 2)個以上maxを取れるならばrをインクリメント、そうでないなら打ち切ってl = r, r = r + 1として、再開
これを繰り返します。 (N / 2)個以上というのも適当な数字です。
上記の例では左から見ていく例を示しましたが、右から見る場合も試しています。
日付全体で、ペアを作って縦線の場所一致させることができた回数を、左スタート、右スタートそれぞれで管理して、返すようにしています。
また、l ~ r日目それぞれのi番目に大きい面積のmaxは、セグメントツリーを用いて取得しました。
配置の方法は分割数や高さを決める山登りのものと同じです。
山登り法による改善
山登り法を行う中で、主に管理したものは以下の二つです。
line[ i ][ j ][ k ] = i日目のj行目のk番目に大きい縦線の場所
surf[ i ] = i日目の盤面の長方形の面積の集合
line,surfどちらも、挿入・削除を高速に行いたかったため、tatyamさんが公開しているpythonで使用できるSortedset,SortedMultisetを改造してNim用に移植しました。データの個数は高々50なので速度的な話で、如何ほど意味があったのかは分かりませんが、直感的に操作できるメソッドが用意されていた分、実装はしやすかったです。
- 初期解
lineを初期解としました。
lineは、上記貪欲法で求めた長方形配置から、縦線の場所を抽出しただけのものです。
- 近傍
最終的に採用した近傍は以下の5つです。
lineのi, j, kを乱択し、line[ i ][ j ][ k ]を移動することを考える部分は共通
- 同一行の、前後日に存在する縦線への移動
- 異なる行の、前後日に存在する縦線への移動
- 同一行の、ランダム左右移動
- 異なる行へのランダムワープ
- 左右にある長方形の場所のスワップ(実質的には1つの縦線の左右移動)
以下近傍設定のお気持ちです。
- 1,2の近傍は直接スコアに寄与する部分なので外せない。
- 3,4の近傍は直接スコアには寄与しないが、1,2だけだと局所解にすぐはまってしまいそうだったので、盤面を良い感じに混ぜて欲しい。
- 5の近傍は評価にかかる計算が軽いため、3,4ほどバリエーションは無いが、軽い計算で盤面を良い感じに混ぜて欲しい。
前述した、heightの分散が小さくなるようにした、というのは、2,4近傍での改善を意識したからになっています。高さが近ければ異なる行への移動の際にも面積変化が少なくて良さそう~と思いましたが、スコアは殆ど変わりませんでした。
割合は、[1,1,1,2,2,3,4,5]としました。と言っても、私が実装した各近傍はそれぞれ探索範囲が異なるので、割合に関しては実装に左右されると思います。
色々と試す中で、これらの近傍をこれくらいの割合で入れると良さげでした。
実装したものの採用されなかった近傍は以下の三つです。
6. 行をまるごと左右反転
7. 二つの行を上下スワップ
8. 同一行の、前後日に存在する縦線との平均への移動
以下近傍設定のお気持ちです。
- 6,7の近傍は盤面を大きく混ぜて欲しい。
- 8の近傍は近傍1,2以外でのスコアに寄与する近傍が欲しい。
いま改めて、採用された近傍、採用されなかった近傍を見比べると、変化量が大きすぎる近傍は良くないのかなー、と感じています。6,7,8全てにおいて、動く縦線が複数なのに対し、1,2,3,4,5はどれも1行のみなので。
それから、各近傍の探索範囲は小さい方が良いのかな、みたいなことも今記事を書きながら考えました。一つの近傍の中で探索範囲を広げても、その盤面から遷移可能な範囲しか到達できないため、それならば、一回当たりの探索量を抑えて、より多様な盤面から探索を試みた方が良さそう、という発想です。
- 評価関数
以下の二つの基準を評価関数としました。
- 移動した後の盤面の中に、必要な面積を配置可能かどうか
- 移動したとして、スコアが悪化しないか
1の面積を配置可能かどうかに関しては、移動後の面積の集合と、その日に要求される面積の集合を比較し、N個全ての長方形において、移動後の面積 >= 要求される面積が満たされるかを判定しました。
その際に、一度盤面上の面積の集合に追加、削除を行い、受け入れられたらそのまま、却下されれば追加削除の逆のことを行いました。毎回新規の集合を作らない分、速度的にメリットがありそう、と思って実装したのですが、実際のところは不明です。
2の移動したとして、スコアが悪化しないか、これに関しては、前後日の移動前と移動後の場所の縦線の存在判定さえできれば計算することができます。
どちらの判定においても、line[ i ][ j ]、surf[ i ]をソートされている状態をキープすることで、高速化できるため、前述のSortedset,SortedMultisetを用意しました。
終わりに
ここまで読んで頂き有難うございました。
最終提出コードはここから見られるので、必要であればご覧ください。
これからも引き続き競技プログラミングを楽しんでいくので、応援よろしくお願いします。
誤植、勘違い、アドバイス等ありましたら以下ツイッターアカウントまでお気軽にご連絡ください。
https://twitter.com/Ang_kyopro
