2024/03/22 から 2024/04/01 までの期間に開催された MC Digital プログラミングコンテスト 2024 (AHC 031) に参加した。
この記事では今回の参加について振り返る。
問題概要
atcoder.jp
W x W (W = 1000) のグリッドを長方形の区画に分割して、与えられた予約に割り当てる。
このとき、
それぞれの予約に対して割り当てる区画の大きさがその予約が要求する大きさを下回るとコストが生じる。
連続する日付に対して区画の区切り線の変更があると、区切り線の長さに応じてコストがかかる。
問題例 (seed=1)
結果
プレテスト 89 位, 最終 94 位 (パフォーマンス 2051)
AHC 011 以来 2 回目の 2 桁順位をとることができた。
長方形への分割戦略として比較的良いやり方を早い段階で考えられた点が良かったと感じている。
最終的な解法
最終的な解法はおおまかには次の 3 ステップからなる。
グリッド全体をいくつかの横線で区切る (この横線は全ての日程で共有する)。
1 でできた横長の長方形内部に縦線を引いて日ごとの予約に対する区割りを決定する (焼きなまし)。
隣接する日付について、縦線を少し移動させることで縦線を再利用できないか試す。
1 では、s_k を「各日付の k 番目に大きい予約のうち最も大きいもの」としたとき、上から順に s_1, s_2, ... の大きさの長方形を確保するように線を引いていくことにした。
このようにした意図は、特定の日付に大きめの予約が固まって出てきたとしても要求を満たす区割りが実現できるようにと考えたためである。
1 でつくった横線は全ての日付について動かさず必ず再利用されるので、この部分については区切りの変更によるコストがかからない。
2 ではとりあえず縦線の再利用については考えずに日ごとに独立に、各予約を面積要求を満たすように 1 でつくられた行に割り当てる方法を考える。
これは、問題文で与えられたスコア関数をほとんどそのまま使って焼きなましでつくる。
近傍としては、以下の 3 種類を用いた。
予約を 1 つランダムに選んで割り当てる行をランダムに移動させる (20.0%)。
予約を 2 つランダムに選んで割り当てる行を交換する (79.7%)。
行をランダムに 2 つ選んでそれらに含まれる予約を貪欲に割り当て直す (0.3%)。
計算時間のほとんど (2800ms) をこの焼きなましステップで使っている。
最後に、3 で縦線の共通化 によるペナルティ削減を試みる。
まず 2 で求めた各日付の配置について行ごとに小さいほうの予約から順番に左から詰めていって日ごとに仮配置を決める。
その後隣接する日付の配置を見て、縦線を少し右にずらすことで予約に対する面積不足を発生させることなく縦線を共通化 できるならそれを採用する。
「i 日目の配置を j 日目の配置を見て変更する操作」を (i, j) と表わすとき、(1, 2) → (2, 3) → ... → (n-1, n) → (n, n-1) → ... → (2, 1) のような順で操作を一通り繰り返すというのを、5 周分行った結果を最終的な結果とする。
複数周分回すのは、一度合わせたつもりの区切りが参照先としていた配置自体が後から変更されてずれてしまった場合に区切り位置を合わせなおすために行っている (つもり)。だいたい 3 周もすれば基本的に配置が動かなくなった。
以下に、実行例を示す。
seed=0 の実行例 (score: 860)
seed=1 の実行例 (score: 73385)
提出コード
https://github.com/sankantsu/competitive-programming/blob/master/ahc/ahc031/main.cc
日記 + 考察過程
03/22 (金)
前回の AHC 030 から競プロに復帰していて、今回は復帰後 AHC 2 戦目。
開催開始後に気づいた前回と違って今回は始まる前から楽しみにしていた。
初日は出先だったのでコードは書けないが、とりあえず問題を読んでおく。
ざっと読んだところだと、最終的に面積不足のペナルティと区切り線変更のペナルティがどのくらいの比率で効いてくるのかよくわからないが、とりあえず面積不足のペナルティは最低限減らせるようにしないと厳しそうである。
余剰スペースがほとんどないとして、面積不足を発生させないように長方形をつくり隙間なく敷き詰める問題を考えてみるが、結構難しそう。
その後で入力生成方法をよく読んでみると多少スペースの余りが出るように入力がつくられていることがわかり、一番簡単なケースでは平均で 1/4 も面積が余るようにできているらしい。
前回 AHC 同様に相対スコア制なので簡単なケースでベストに近い点数を出すのは重要だし、難しいケースで面積不足ペナルティが発生するのは多少許容してとりあえず面積余りが出やすい条件をターゲットにして、線を再利用しやすい配置を考えてみると良いかもな、というぐらいの考察をしておいて実装はせずに初日は終了。
03/23 (土)
前日の考察もふまえて実装を行っていく。
最初にやったのは、サンプルの移植と、サンプルについて長方形の縦幅を予約を満たすように広げるようにした拡張版。
それに続いて、スコア計算を問題文どおりに実装した。
素直に定義通り一般の配置に対するスコア計算をやると結構計算が重いので、後々焼きなまし等にもっていくなら差分計算できるように制限して解を考えるのは必須だろうと感じた。
ここまでの考察をふまえて、
いくつかの線を再利用し続けられる
スコアの差分計算を行いやすい
という点を念頭に、配置方法を日が変わっても動かさない横の固定線 + 日ごとに動かす縦の変動線 の組みあわせで構成する、いわゆる「短冊配置」戦略を中心に考えてみることにした。
縦線の隣接日程での共通化 は念頭にはあったが、とりあえずは日ごとに独立に面積不足を出さない配置ができないか考える。
固定線の配置については最低限、全日程で最も大きい予約を入れられる大きさは確保しなければならない。
そのように確保した区画に仮に各日付で最も大きい予約を詰めるとしたら、次に面積不足に陥いる可能性があるのは「各日付の中で 2 番目に大きい予約のうち全日程を通して最も大きいもの」であると考えたので、これに合わせて次の固定線を決める。
このような調子で「各日付の k 番目の予約のうち最も大きいもの」に合わせて固定線をつくれるところまでつくるという方針で固定線を引くことで面積不足が発生しづらい固定線の引き方が達成できそうだと考え、この方法を採用することとした。
結局この固定線のつくりかたは最終解法までそのまま引きつがれることになる。
縦の変動線 については、各日付ごとに独立に 予約 id -> 割り当て行 の対応を解くことで決定する。
具体的には、各日付について最も大きい予約から順に予約を満たすことのできる行のうち最も残り面積が小さいものから順に割りあてる貪欲法を採用した。
ここまでで横線を完全に横線を再利用しつつ、面積余りを発生させる頻度がそれなりに少ない解法を組むことができたので提出してみると、一瞬だが 9 位という好位置につくことができた。
一瞬でもこのような順位をとれたことは無かったのでこれは嬉しい。
03/24 (日)
この時点でわりと方向性としては悪くない解法を引けている感覚があったので、さらに改善すべく変動する縦線の隣接日程間での共有に考えをうつしてみる。
隣接する日付の予約で面積が近いものがあれば、小さいほうの予約を大きいほうの予約の面積に合わせることで区画の大きさを共通化 できるはずである。
この考えに基づいて、隣接する日付の予約から面積の差が最も小さいものからいくつかペアをつくる。
そのうえで、ペアにしたものについて同じ区画を優先的に配置した後で、残りをこれまでと同様大きい予約から順に貪欲に割り当てるという解法を試してみる。
しかし、この解法はうまくいかなかった。
うまくいかなかった原因は、より大きい予約よりもペアになっている小さい予約を配置してしまうために、後から大きい予約を詰められないケースが出てきて面積不足ペナルティでスコアが大幅に悪化してしまっていたためだった。
結局この日は提出は行わず。
03/25 (月) - 03/29 (金)
今回は結局平日は全く時間がとれず、たまに考察はしてみるものの実装は全く進まなかった。
03/30 (土)
一度は 9 位まで上がった順位もほぼ丸 1 週間も放置したので 220 位台ぐらいまで下がっていた。
縦線の共通化 は結構難しそうかつできたとしても少し共通化 できるぐらいだと限定的な効果しか無いだろうと感じていたので、一度立ちもどって日ごとの縦線の配置を貪欲解法ではなく焼きなましで改善するのを試みることにした。
これでより面積ペナルティを少なくすることと、縦線の長さの合計を減らすことを狙う。
解としては各予約に対して割り当て先の行を対応させる長さ N の配列を持つことを基本として、スコア計算を O(1) にするために行ごとの割り当てた予約の数と割り当て面積の合計を同時に更新する形とした。
近傍は、最初予約の割り当て行の移動と swap の 2 種類で実装した。
近傍が上の 2 種類だけだと面積不足が発生していても局所解から抜け出しにくい傾向があるように感じられたので、もう少し大幅に状態を変化させる近傍として、2 行選んでそれらに含まれる予約すべてを貪欲に配置しなおすという近傍を追加した。
この近傍は他と比べて計算が圧倒的に重いので、iteration 回数を確保するために使用頻度はかなり小さく設定したが、それでもスコア上昇の効果はあったようである。
焼きなまし解法を使うことで、正確な順位は覚えていないが 70 位台ぐらいまで回復した。
03/31 (日)
日ごとの区画方法決定部分の焼きなまし化もとりあえずできたので、改めて縦線の共通化 に取り組んでみる。
共通化 を優先して先に配置したりしていると面積要求を満たせなくなって本末転倒になることを先週の実装で学んでいたので、今回は縦線の共通化 はあくまで補助的な手段で、運が良いときだけできれば良いぐらいの感覚で行ってみることにした。
アイデア としては、隣りあう日付で偶然近い位置に縦線があったら一方をずらして同じ位置まで持っていけないか考えてみるというものである。
より具体的には、隣りあう日付についてある行の配置を取りだしてきて、一方の配置の縦線位置を左から見ていったとき、もう一方の配置内に存在する縦線位置に重なるところまで右方向に動かせるなら動かすという貪欲法で縦線を重ねていくことにした。
一回の処理では隣接する日付しか扱えないので、これを全ての隣接する日付のペアについて繰り返していく。
最後に、visualizer や繰り返し数のログを観察しながら焼きなましのパラメータを調整する作業をして最終提出とした。
04/01 (月)
改善のアイデア として
細い長方形区画が連続する配置が出現するなら区切りの方向を変えることで長さを削減する
縦線の共通化 を試す前の仮配置として面積順に詰めるのではなくシャッフルしてみるなどして探索パターンを増やす
といった候補を考えていて、余裕があったら試してみようと考えていたが、結局実装する時間がとれず試さなかった。
最終日はときどき順位表を開いて順位が下がっていくのを眺めるだけになっていた。
終了後の感想・反省点
上位陣の解法を見ても配置方法はいわゆる「短冊型」が多く、おおまかな配置戦略としては当たりを引けたかなという感じがした。
ただ、一見似たような短冊型であっても内部の配置を決めるための方針には意外とそれぞれの参加者ごとに工夫があって、スコアもかなり差がついているという印象だった。
解説放送で説明していた固定線と中身の配置の 2 重の焼きなましや、変動線 部分の共有を行うための焼きなましなどにつても、いずれも自分では思いつかなかった部分であり面白いと感じた。
これらの情報を見たうえで考えたところスコア影響がありそうな反省点としては、以下などがあげられそうである。
横の固定線配置を貪欲で決めうったまま最後まで改善しなかった。
固定線の配置を今回の自分の解法で割りふると、固定線の配置間隔が必要以上に離れたものになってしまうことがあるように思われる。
これによって、縦線一本あたりの平均コストが必要以上に高くなってしまったり、区画内部の面積余りが発生しやすく最終的に面積不足ペナルティを解消しづらくなっていた可能性がある。
詳細順位表の情報から、自分の提出は N が小さいケースで弱かったことがわかっているが、N が小さいケースでは特に固定線の配置間隔が広がりやすかったと想像される。
今回の問題では、一部パーティション を全く動かさずスコア 1 を達成できるパターンが存在する。
このこと自体は固定線配置のための貪欲を考察の延長として気付いていたが、スコア 1 が達成できるパターンを実際の入力ケースの中に探したり達成できているか動作を見たりすることはしなかった。
実際 seed 32 がそのようなパターンに相当することを後から知ったが、自分の解法の動作を見てみるとスコア 1 を達成していないことがわかった。
解説放送内での発言によればシステムテスト ではスコア 1 可能パターンは 28 個あったらしくこれらを取れていると特に自分の順位帯にとっては無視できないスコア影響がありそうである。
今回はコンテスト自体にあまり時間がとれなかったこともあり、基本的に解法の評価を seed 0 - 5 あたりの visualizer で確認するぐらいしかしていなかった。
ローカルテストを気軽に行えるような手順の整備などは今後の長期コンテストに向けての課題である。
また、入力の分布の分析などもやらなかったので、例えばスコア 1 達成可能パターンの発生確率なども評価できていなかった。
解説などで紹介されている方法をいくつか延長戦で試して、また次の AHC に備えたい。
