HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016)

HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016) - AtCoder に参加しました。暫定49位でした。

解法

  1. εが小さいときは前計算して埋め込んだグラフを使って、編集距離の最も近いものを答えとして出力する
  2. εが大きくてMが小さいときは、辺の数が違うグラフをいくつか作ってそこから推定する
  3. εと M が両方大きいときは諦める
  4. それ以外のときはあらかじめ 5 頂点のグラフ(自己ループあり)を 100 個用意しておき、それぞれの頂点をいくつかの頂点の集合に置き換えたものを G として出力する。自己ループを持つ頂点に対応する集合はクリークにする。推定パートは隣接点の集合が似ているものをまとめるクラスタリングをして、小さいときと同様に編集距離で元の 5 頂点のグラフを推定する。

グラフの構築方法はおおよそ解説配信と同じに見えるし、推定パートもよく似ているので、たぶんクラスタリングと推定の精度が悪い。単純に距離が近いものを答えるだけでは精度が出ないケースがあり、ベイズの定理で推定した方がよかったようです。言われてみれば。

ということで解法のメインの部分は解説してもあまり意味がない感じなので、楽しかった部分のことを書きます。

埋め込むグラフの作り方

注意: 上に書いたように、これは元々の問題の解法として特によいものではないようです。

ε=0 の場合を最初に書いたらεが 0 でなくても小さいときはこれでできるんじゃないかという気がして、そっちにかなりの時間を費やしました。誤り訂正みたいなことができればよいので 100 個のグラフをどの二つも編集距離がある程度大きいように作ればよい、ということでそういう集合の構築をずっとやってました。

編集距離

編集距離(単に距離と書きます)の定義は、辺の有無を何回入れ替えると同型になるかです。より正確には頂点数が等しいグラフ G, H の距離は以下のように定義されます。(ここではこう定義しましたが一般的な定義かどうかは知りません)

  •  f: V(G) \to V(H)全単射とするとき、そのコストを  \#\{ \{u, v\} \in E(G) \mid \{f(u), f(v)\} \notin E(H) \} + \#\{ \{u, v\} \in E(H) \mid \{f^{-1}(u), f^{-1}(v)\} \notin E(G) \} とします。要するに f で写したときに辺の有無が違ってる箇所の数です。
  • G と H の距離はすべての全単射  f: V(G) \to V(H) についてのコストを考えたときの最小値です。

これは f を DFS で構築しながら、既に構築した部分のコストがいくつになるかを覚えておくと  O(N \times N!) ぐらいで計算できます(行き先を一つ決めるごとにコストの増加量を計算するのに O(N) かかります)。途中で f が最後まで構築できたときに距離の上界が求まるので、それ以降はその上界を使った枝刈りをします。また、ある閾値 d があって距離が d 以上のときは求めなくてもいい場合は、DFS の途中で f のコストが d 以上になったら打ち切る、とすると同様に枝刈りできます。これを d = 1 としてやるとグラフの同型判定になります。

どの二つも距離が d 以上になる N 頂点グラフの集合を探したら見つかった集合のサイズは以下のようになりました。行が N で列が d です。やってないところは ? になってます。4 をあんまりやってないのは奇数の方がうれしい気がして最初は 2, 3, 5 しかやらなかったためです。

        距離1   距離2   距離3   距離4   距離5
4       11      6       3       ?       ?
5       34      18      8       ?       ?
6       156     78      32      ?       10
7       1044    522     93      ?       19
8       12346   ?       >=100   247     66

距離 2 以上のは以下の手順で求めました。

  1. 同型でないグラフを全部列挙する
  2. グラフ間の全ペアの距離を求める
  3. 列挙したグラフを頂点とし、距離 d 未満のグラフ間に辺を張ったグラフを作り、最大独立集合を求める

最大独立集合は昔書いた近似アルゴリズムを使ったので厳密解かどうかはよくわかりません。

1.は隣接行列の左上から順番に辺を張るか張らないかで分岐する DFS です。どうせ同型なものは一回しか見なくてよいので頂点番号は次数でソートされていると仮定してよく、隣接行列の各行の 1 の個数が降順になるものだけ列挙したらそれなりに速くなりました。同型判定はまず次数列を比較して、同じだったら編集距離のアルゴリズム閾値 1 として走らせてます。

2.はほぼ上に書いたアルゴリズムで尽きていますが、最初に辺の本数の差を調べて閾値以上だったらすぐ return すると結構効率がよくなりました。

ちなみに N = 8, d = 5 のときに構築されるグラフは 12346 頂点 45270502 辺だったらしいです。結構辺が多くて、やる前は 8 頂点ならサイズ 100 の独立集合が見つかるだろうと思っていたけど見つかりませんでした。(それで d = 4 もやった)

一番重いのは全対の距離を求めるところで、8 頂点のときは閾値 6 としておいたら半日ぐらいで求まりました。もっと効率的な方法あるのかな。(ありそう)

コンテストの反省

頑張ったわりには微妙な順位だなーと思いますが、スコアへの寄与が比較的少ないεが小さい場合とε=0.4の場合にしか時間をかけてなかったので、力の入れどころを間違えただけのような気もします(しかもε=0.4のときは結局うまくいかなかった)。

「だけ」といってもコンテストがスコアを競うものである以上それではダメといえばそうですが、スコアよりも楽しさと学びを重視しているつもりなので、その意味ではまあ悪くなかったかなと思います。

やろうと思ったことを一通りやってから提出しようと思っていたら一度も提出しないまま最終日になってしまったのですが(ε=0.4の場合が全くうまくいかなかったため)、今回は特に提出した結果から推定できることがあるタイプの問題だったので、一区切りつくごとに提出した方がよかった気がします。

estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)

estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014) に参加しました。暫定6位、最終4位でした。久しぶりに上位に入った気がする。

解法の中でやったこと

初期解

貪欲法で初期解を作る。以下の 5 通りの評価値それぞれで解を作って一番スコアの高いものを選ぶ。

  • d(q, p1)2 / (周長) (d はユークリッド距離、q = (-1, -1), (-1, N), (N, -1), (N, N) の 4 通り)
  • p1 の重み(スコア計算に使うやつ)

焼き鈍しの温度

  • 初期温度: N <= 37 のときは 20000、N >= 39 のときは区間 [39, 61] で 30000 から 10000 に減少する N の一次関数
  • 最終温度は初期温度の 1/10
  • 温度は経過時間に対して線形に減らす

近傍

適当に選んだいくつかの長方形とそれに依存するものを削除して、貪欲法で作り直す。ただし、依存するものを削除したときに削除した長方形の合計が min(解の長さ/2, 2N) を超えたときは作り直しをしないで棄却する。

試行回数は大きいケースで4万回(作り直しをしないで打ち切ったときも数えると5万回)、小さいケースで50万回ぐらい。

削除する長方形の選び方は以下のいずれかをランダム(一様ではない)に使う。

  • 依存関係を DAG にして後ろから適当な数だけ削る
  • ランダムに選んだ長方形とそれに依存するものを削除、を適当な数削除されるまで繰り返す
  • ランダムに選んだ長方形とその p1 に隣接する4点または8点(どちらにするかは等確率で選ぶ)を頂点にもつ長方形、およびそれらに依存するものを削除

長方形を作り直すときは、焼き鈍しの試行ごとに以下の選択方法の中から一つ選んでおく。その方法で長方形を候補から選択して盤面に追加し、候補の差分を計算する、という処理を候補がなくなるまで繰り返す。

  • 初期解を作るときと同じ評価値を使い、最大のものを選ぶ(5 種類)
    • ただし、削除した長方形のうち一つをタブーとして一様ランダムに選んでおく。タブー長方形の評価値は他のどれよりも低くする
  • p1 からマンハッタン距離 2 以下の範囲にいくつ使われている点があるかを数え、それが最大なものの中から一様ランダムに選ぶ
    • この場合にタブー長方形を選ばないようにするのを忘れていた(これを書いていて気付いた)
  • 候補全体から一様ランダムに選ぶ
    • この場合にもタブー長方形を選ばないようにするのを忘れていた(これを書いていて気付いた)

その他

  • 候補の列挙をなるべく高速にできるように頑張る。傾いた長方形同士が辺を共有するかどうかの判定は45度回転して座標軸に並行な場合に帰着すると速い、とか。
  • N <= 37 のとき、一定回数最適解が更新されてなくて、残り時間が 500ms 以上あるならそこで打ち切って初期解からやり直す。やり直すまでの回数は、 p = (M - N) / (floor(N2 / 12) - N) として p <= 0.51 なら 20000 回、p > 0.51 なら 10000 回。

解法以外でやったこと

  • N, M, seed を渡してテストケースを生成する generator を書き、N, M がいい感じに均等に分布してるテストセットを生成した。これで N, M の大小による傾向の違いを調べやすくしようとした。
  • EC2 のインスタンスを立ち上げてそっちで 880 個のテストケースを実行できるようにして、パラメータの調整やテストに使った
  • ローカル実行のとき、main の最後で経過時間を見て上限を超えていたら異常終了する(実行時間の制御に失敗していたら検出するため)

コンテスト中の経過

やったことのうちそれなりに重要だったり細かすぎないことをメモから抜粋してみます。2日目から始まりますが、初日はほとんど何も記録が残ってなくて、問題文を読んでビジュアライザを少し触った記憶しかないのであまり取り組んでなかったのだと思います。

22-09-18 (Sun)

2日目。とりあえず貪欲法で作れるだけ作ってスコアを得ました。評価値として追加する頂点の重み / 向かいあう頂点間のマンハッタン距離が大きいものを優先しようとしてみたのですが、実はバグがあってそうなってませんでした。この日のスコアは 33320470

次にどの長方形を選ぶのがいいかをどうやって評価するかがかなり非自明ということがなんとなくわかりました。問題の見た目からビームサーチを検討したい気がしていました。

22-09-19 (Mon)

3日目。祝日だったのでけっこう時間を使いました。

昨日のコードで重みと思っていたものが重みになってなくて、中心ではなく原点からの距離を使っていたことに気がつきました。ただし、この部分を直すとスコアが下がったので、原点から遠いものを優先的に選ぶとなぜかうまくいくらしいことがわかりました。つまり、端の方からきっちり埋めていった方がスコアがよくなる?

すぐに思いつくこととして、途中の長方形とそれに依存するものをすべて削除して貪欲を途中からやり直す山登りまたは焼き鈍しがあります。一つの長方形に依存するものを連鎖的に消していったときに、ほとんど残らなかったりするとあまり意味がなさそうだと思ったのですが、実際に依存関係がどうなっているか確認してみたら、そんなにたくさん削除しなくても済みそうだったのでやってみました。

とりあえず山登りしたら 47126345 で、焼き鈍しに変えたら 53218433 になりました。でも途中の様子を見てる感じだと、うまく探索しきれてないような気がします。

同じ盤面が何度も出現しているのかもしれないと考えて、最近見た盤面とか最近使った長方形を禁止する tabu list を作って重複を回避しようとしてみましたが、スコア上がりませんでした。(でもこのアイデアを最終日に部分的に復活させて「直前に削除した長方形のうち一つを選んで優先度を最低にする」としたらちょっとスコアが伸びたので、ここの考察は無駄ではなかった)

22-09-20 (Tue)

4日目。解の表現を変えたらどうかななどと実験をしたけどスコア上は進展なし。

この時点では、多様性が低いことが一番の問題で、次に計算速度が課題という認識でした。

22-09-21 (Wed)

5日目。パラメータがいい感じに分布したテストセットを作りたいと思ったので generator を書きました。

def generate(n, m, seed):
    random.seed(seed)
    lb = n // 4
    ub = 3 * n // 4
    points = set()
    while len(points) < m:
        x = random.randint(lb, ub)
        y = random.randint(lb, ub)
        points.add((x, y))
    return sorted(list(points))

実装がこれで済むのなら最初に書けばよかった。

22-09-22 (Thu)

6日目。スコアがばらつくときにレプリカ交換法を使うと安定しやすいという話があるので試してみました。

seed = 0 の入力で解法に渡す seed を変えて走らせた結果は以下のようになりました。

焼き鈍し
902477 807067 890458 749102 898790 819738 807067 883187 900870 877892
std = 50878

レプリカ交換法
887537 888294 913446 888294 906638 910326 907205 924132 907205 907205
std = 11561

この入力では安定していい結果が出ていますが、大きいケースだと試行回数が足りてなくて安定して悪い結果が出るようでした。上に書いた generate で N = 61, M = 285, seed = 1 としたテストケースで同じことをやってみた結果は以下のようになりました。

焼き鈍し
1303088 1128350 1305274 1265825 1116739 1261079 1185880 1264542 1116061 1252784
std = 72146

レプリカ交換法
1110614 1047230 1062909 1135390 1064429 1013849 1110354 1055146 1054999 1048891
std = 34923

最終的には 2000 ケースの合計で評価されるのだから、分散が小さいかどうかより平均が大きいことが重要なはず、ということで使うとしても小さいケースだけかなという感じです。(結局最終提出では使わないで、温度を高めにしました)

22-09-23 (Fri)

7日目。ちょっと高速化をしてみたり近傍の調整をしたりしていました。

asprocon2 のときにやった方針(割り当てを2割ぐらい解除して貪欲法で割り当て直す)が今やってることと似ている気がします。asprocon2 ではいい貪欲法を作って貪欲法のパラメータを焼き鈍しで改善するという方針がよかったのですが、今回の問題にはそんなにいい貪欲法がなさそうなのでこの知見は適用できないかもしれません。

22-09-24 (Sat)

8日目。長方形を追加したときに、次に追加できる長方形のリストを毎回一から作っていたのですが、追加前のリストとの差分だけ計算するようにしました。以下の処理をすればよくて、地道に場合分けなどを頑張るとできます。

  • 追加した長方形と重なっているものをリストから削除
  • 追加した長方形の p1 を使ってできる長方形をリストに追加

これで 67444080 に。

22-09-25 (Sun)

9日目。一年半ぐらい停止していた EC2 のインスタンスを起動して使い方を思い出したり、レプリカ交換法の方がよくなるケースがどういうのかを調べたり、プロファイルを細かく見てみたりしていました。

それから焼き鈍しの途中で best がしばらく更新されなかったら何かした方がいいんだろうなとずっと思っていたのですが、温度を上げてみるとかしてもいまいちうまくいってる感じがなくて、とりあえず 10000 回連続で best が更新されなかったら初期解に戻るという処理を入れたりしていました。best に戻すのではなく初期解に戻したのは、best が局所最適に近くてその周りからうまく脱出できない状態になっているだろうと予想したためです。(結局最後までほぼこのままになった)

22-09-26 (Mon)〜22-09-30 (Fri)

ずっと高速化したり削除する長方形の選び方をちょっと変えたりしてました。あとテストケースを 880 個作って評価するようにしました。

880 個は擬似コードを書くとこんな感じで作っています。

for n in [31, 33, ..., 61]: # 16 通り
    for p in [0, 0.1, 0.2, ..., 1]: # 11 通り
        m = round((1 - p) * n + p * (n * n // 12))
        for s in [1, 2, 3, 4, 5]: # 5 通り
            generate(n, m, s)

30日の夜中に温度調整などのための実験を回していました。

22-10-01 (Sat)

最終日。夜中に回してた実験の結果とかこの日に行った追加実験の結果を見て温度などのパラメータをそれっぽく決めました。

29 日に 100 ケースで予備実験して大幅に改善した変更を明らかに上がってるから大丈夫だろうと思って 880 ケースで試さずに commit したら実は 880 ケース回したときには悪化することがこの日に判明して revert したりしました。スコアが安定してないとこういうことが起きるのか。

あといくつか細かいことを思いついて改造して実験したら、よくなったのは以下の二つでした。

  • 貪欲法で次の長方形を選ぶとき、評価関数は複数ある中から一つ選んで使うのですが、その中にチェビシェフ距離 2 以下で既に印の付いているものが多い方がよいという評価関数がありました。これをマンハッタン距離に変えたらよくなりました。(880 ケースの平均が +14000 ぐらい)
  • 削除して作り直したときに完全に元に戻ってしまうことがあったので、それを避けるために削除した長方形のうち一つを選び、作り直しのときにそれをなるべく使わないようにしました。(880 ケースの平均が +7000 ぐらい)

これらを入れて提出したら暫定スコアが下がりましたが、880 ケース自分で回して上がっているのでそっちを信じることにしました。

反省など

ほとんどの時間は細かい調整をしていました。それはそれで退屈ではないのですが、もっと問題そのものの性質をよく見て気付きを得られたらより楽しめたのではないかとも思います。コンテスト中も問題の性質についてほとんど考えていないことが気にはなっていましたが、具体的に何を見たいというのがなかなか浮かばなかったので、とっかかりがつかめないままでした。解説放送を聞いた感じだと、外側に広がるときにどういう仕組みで広がっていくのか、という疑問を持ってよく観察すれば、そこから視界が広がるきっかけを見つけられたのかもしれません。

コンテスト中に難しく感じたのは以下の二点で、こういうのはある程度一般的な話だと思うので、対処法のバリエーションを増やしていきたいところです。

  • スコアが不安定すぎて改善できたかどうかの評価がどの程度正確にできているのかが分からなかった。
  • 温度を高くしても、かなり早い段階で出たスコアがその後全く更新されないということが起こりがちだった。今回は強制的に初期状態からやり直すようにしたが、もっと上手い方法がありそうにも思う。

Topcoder Marathom Match 126

Topcoder Marathom Match 126 に参加しました。ひさしぶりに MM で非自明なことをした気がする。

概要

グリッド上にいくつかのブロックと穴が配置されている。ブロックには 1 から C までの数値が割り当てられている。ブロックに対して以下の操作ができる。

  • 上下左右に隣接するマスに移動させる。このとき移動先に他のブロックが存在していてはいけない。移動先が穴の場合はその穴に落ちる。
  • 上下左右のいずれかの方向にスライドさせる。ブロックは他のブロックまたは端にぶつかって止まるか、穴に落ちるまで進む。

ブロックが穴に落ちるとブロックの数値-1に係数をかけた値が現在のスコアに加算される。係数は最初はグリッドのマス目の個数で、操作を一回行うごとに 1 減らされる。

方針

一手で100点と二手で200点みたいに一手あたりのスコアが同じだったら、それ以降のスコア係数が大きい状態を保てるので前者を選んだほうがよさそうです。

ということは、なるべく早く落とせるものを落としていったほうがよさそうな気がしたので、そういう感じにしようとしました。

Step 1

まず、いずれかの穴と同じ行または列にあるブロックだけをすべて落とす最適な手順を考えます。これは条件に該当するブロックの数があまり多くないので、短時間の SA でそれなりの解が出ます(たぶん)。

ブロックの並び順で前後関係の制約がたくさん付いたり、複数の穴が落とす候補になるブロックもあって解の表現がそんなに自明ではないのですが、穴と移動方向に番号をつけて「穴 i から見て j 方向にあるブロックを k 個落とす」という形の操作列を解の表現にして焼き鈍しをしました。

ただし、本当に対象のブロックを全部落とそうとすると後ろのほうはあまりスコアの入らのない操作ばかりになることがあるので、後ろの方が割のよくなさそうな列になっていたら適当に切り捨てます。

基準は適当ですが、suffix に対して「その操作列で落とされるブロックの数値-1の総和」を操作列の長さで割ったものを考えて、それが C/5 を下回っていたらその部分はこのステップでは解に含めないことにしました。残ったやつは後で回収されます。

Step2

ここまでで残ったブロックを落とす手順を考えます。ある穴を始点にする L 字のパスを考え、その上にあるいくつかのブロックを落とすことを考えます。例えば以下の二つの 2 のようなブロックを落とす一連の操作をひとまとまりと考えます。

  . O . . . .    . O . . 2 .    . O . . . .    . O . . 2 .    . O . . . .
  . . . . 2 . -> . . . . . . -> . . . . . . -> . . . . . . -> . . . . . .
  . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . . 2 .    . . . . 2 .    . . . . 2 .    . . . . . .    . . . . . .

このような操作を全列挙し、一手あたりの評価値が高いものを選択します。評価値は基本的には落とすブロックの数値-1の総和を手数で割ったものです。正確にはそれをちょっといじった変な式を使っています。手数の少ないものを優先したほうがいいのかなと思ったのですが、試してみた限りは別にそんなこともないようでした。手数を多めにかけてでも深いところにある点数の高いブロックを早めに掘り出してやったほうがいいのかもしれません。

これだけだと計算時間が余っていたので、以下のように別のブロックを一手使って移動させることで他のブロックが効率よく落とせるようなケースに対応しました。

  . . . . 1 .    . . . 1 . .    . . . 1 . .    . . . 1 . .    . . . 1 . .    . . . 1 . .
  . O . . . .    . O . . . .    . O . 3 . .    . O . . . .    . O . 3 . .    . O . . . .
  . . . 3 . . -> . . . 3 . . -> . . . . . . -> . . . . . . -> . . . . . . -> . . . . . .
  . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .
  . O . . . .    . O . . . .    . O . 3 . .    . O . . . .    . O . 3 . .    . O . . . .
  . . . 1 . . -> . . . . . 1 -> . . . . . 1 -> . . . . . 1 -> . . . . . 1 -> . . . . . 1
  . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .

現在の盤面から可能な次の手すべてについて、それを行った後で穴から伸びる L 字を全探索してすべて評価して、一番よさそうなものを選ぶようにしました。これがけっこうスコアに貢献しているようです。

ちょっと計算量が大きそうなので高速化が必要だろうと思いながらとりあえず書いたら、わりと何とかなる感じだったので結局高速化はしませんでした。

Step 3

これだけだとまだブロックが残る場合があるので、その場合は各ブロックについて BFS をして最も近い穴を探し、スコアと手数を見てよさそうなものを一つずつ落とすようにしました。この辺はあまり考察ができていません。

この時点で 0 点のブロックが残っているとそれはそのまま放置される評価方法になっているので、0 点に囲まれたブロックは正の点が得られるものも触らずに終了しています。そういうことになるケースはあまり多くなく、スコアへの影響も比較的小さいようですが、たぶん数%ぐらいのケースで発生します。

本当はその場合にも対処しようとしたんですが、対処するとなぜかスコアが大幅に下がり、原因がわからなかったので諦めました(手元で200ケース回したけど問題ないように見える)。

AtCoder Heuristic Contest 001

https://atcoder.jp/contests/ahc001 に参加しました。

凡ミスをして暫定22位から最終77位に下がったので反省をします。

反省

こんな感じの処理を書きました。

for (int maxsize = 1000; ; ) {
  Rectangle rect = random_rect(maxsize);
  if (rect.area() > r[i] * 1.1) continue;
  // なんかを処理していい感じだったら break
  maxsize = round(maxsize * 0.8);
}

maxsize が指数的に小さくなるのでこのループは O(log(maxsizeの初期値)) 回で止まると思っていましたが、3行目で continue すると小さくなりません。r[i] が小さいときはほとんど確実に continue するのでたくさん回ります。(無限ループしてくれればローカルでテストしてる間に気付きますが、たちの悪いことに数秒かけてループを抜けたりします)

こう書くべきです。

for (int maxsize = 1000; ; ) {
  Rectangle rect = random_rect(maxsize);
  if (rect.area() <= r[i] * 1.1) {
    // なんかを処理していい感じだったら break
  }
  maxsize = round(maxsize * 0.8);
}

このバグが原因でシステムテストでTLEを8つ出しました。残念ですね。

これは main の最後に以下のような処理を書いておけば気付けた可能性があります。

if (timer.get_elapsed_time() > timelimit)
    cerr << "TIME LIMIT EXCEEDED; elapsed " << timer.get_elapsed_time() << endl;

ローカルで用意したテストケースの中にバグが露呈するケースが含まれていなければ見逃す可能性はありますが、今回は TLE の数が 8/1000 で、手元で 151 個回していました。自動的にチェックして警告を出す仕組みを用意していれば気付いた可能性はそこそこ高いでしょう。

やったこと

ついでに考えたこととか書きます。

問題を見た直後に書いたと思われるメモはこうなってた。

  • n がそんなに大きくなくて、盤面はわりと大きいので、衝突判定はとりあえず全組み合わせ試してもそんなに悪くはならなそう。
  • 最初は焼き鈍しかと思ったけど、縦長の長方形が実は横長にしたほうがよかったときに横長に修正できるような近傍はあまり自明ではない。
  • 長方形を一つ選んで、そのサイズを極端に小さくして作り直す、とか?
  • 一時的にオーバーラップを許容する評価関数にして焼き鈍しとかはありうる?

そんなに外してはいないと思うけど、ここから掘り下げ切れなかった感がある。

あとは一つの長方形のサイズを変えるとか隣接する二つの長方形で押し合ってみるとか、その程度の局所的な変更ではたいして改善しないだろうと思ってほとんど検討しなかったけど、他の人の方針を見ていると必ずしもそうではないようだ。この辺は直感を信じすぎないで、実装して確認すればよかったのかもしれない。

貪欲法

1x1 の長方形*1を (x[i], y[i]) に作って、それらを上下左右に広げる。

  • 広げる方向は最初はランダムにしていたが、後で複数回実行するようになったのでどの長方形はどちらに広げるとよさそうという優先度の学習っぽいことをしてその優先度に比例する確率で方向を選択した。
  • 要求された面積に対する充足率の低い順でソートした priority queue を用意して、充足率の低いものから優先的に広げるようにするとよくなる。
  • ぶつかった場合に、ぶつかられた方を縮めてもスコアが上がるならそうする。これは充足率 1.0, 0.8 よりも 0.9, 0.9 の方がいいのでけっこう効果がある。
  • サイズを 1 ずつ広げると処理時間がかかるので、最初は200ぐらいずつ広げて、広げる幅をだんだん狭めていく。

ぶつかったら相手をずらすのもやろうかと思ったけど、めんどくさそうだったので後回しにしていたら、最終的にビジュアライザを見た感じで必要ない気がしてきて実装しなかった。

このへんは主に初日に思いついたこと。優先度は初日の早い段階から考えてはいたけど実装は後半になってからやった。

焼き鈍し

スコアを改善するにはちょっとずつずらしてもあまり意味がなくて、大幅に形を変える必要がありそうだと思った。ローカルな変更でそれを実現できるかというと怪しそうだったので、充足率の少ない長方形を選んでそれをランダムな大きさに変更してみた。当然そのままだと周りとぶつかるので、周囲にある長方形を 1x1 に戻して貪欲法をやり直すことにした。

以上の操作で得られる解を近傍として、キックしかしない焼き鈍しみたいなことをした。一応スコアは上がった。

このへんが二日目にやってみたこと。

一回の試行に時間がかかるのでぜんぜん収束せず、実行時間が10倍ぐらいあるとよさそうだと思ったが、この時点では衝突判定でかなり高速化ができると思っていたので試行回数10倍ぐらいにできるつもりでいた。

高速化

衝突判定の高速化を試みた。長方形の各辺の座標がわかっていれば、右端の座標が x のものを x + a にしようと思ったら、左端の座標が [x, x + a - 1] の範囲にあるものをすべて調べればよいはずで、これで高速化できると思っていたのだが、意外とそうでもなかった。でも少しは速くなった。

これが三日目にやったこと。高速化を頑張ったけどあまり成果が出なかった日。

これ以降はわりと細かい調整ばかりしていた。

*1:正方形は長方形です

TopProver Sprint Round 13

A. Flat CPO

Definition task :=
  forall (x y : option nat) (n : nat),
    x = Some n -> x = y \/ x = None -> x = y.

x = y \/ x = None について場合分けするのが簡単です。x = y の場合は自明で、x = None の場合はもう一つの仮定 x = Some n と合わせると矛盾が出ます。

Require Import Problem.

Theorem solution : task.
Proof.
  unfold task.
  intros x y n H [H' | H'].
  - exact H'.
  - rewrite H in H'; discriminate H'.
Qed.

xdestruct する方が素直に思いつく方法かもしれません。どちらでも使う tactic はだいたい同じです。

問題の由来

x <= yx = y \/ x = None で定義すると option nat に順序が入ります。この順序構造は flat CPO と呼ばれるものです(プログラム意味論で出てきます)。この問題は、flat CPO の性質「x が最小元でないならその上界は x 自身に限る」を示せという問題でした。

B. If zero were not nat

Fixpoint plus n m :=
  match n with
  | O => S m                    (* O = One *)
  | S n' => S (plus n' m)
  end.

Definition task := forall x y, plus x y <> y.

nat のコンストラクO がもし 0 ではなく 1 (One) を表すとしたら、足し算に単位元がないことを示してくださいという問題です。

いくつか方針が考えられます。

  • forall x y, plus x (S y) = S (plus x y) を示しておくと、二重帰納法が回ります。
  • forall x y, plus x y = x + y + 1 のように標準の + を使った式に書き換える補題を用意すると、標準ライブラリの定理などが使えます。
  • 主張を強めて forall x y, plus x y > y とすると、x についての帰納法が回ります。

最後の方針だと以下のように証明できます。

Require Import Problem Lia.

Theorem solution: task.
Proof.
  intros x y.
  cut (plus x y > y).
  - lia.
  - induction x.
    + auto.
    + simpl; auto.
Qed.

C. Perfect Square?

Definition task :=
  exists f : nat -> bool,
  forall n, (f n = true) <-> exists m, n = m * m.

与えられた自然数が平方数かどうかを判定する関数を書き、その正しさを証明してくださいという問題です。

計算量については何も要求がないので、m の候補を有限個に絞って全部試せばよいです。例えば n 以下の数をすべて調べれば十分です。以下、この方針での解法を説明します。(NArith を import して N.sqrt とかを使ったほうが楽かもしれません)

まず、一般に k 以下の自然数を全部試す関数は以下のように実装できます。

Require Import Arith.

Fixpoint check k n :=
  if k * k =? n then true else 
    match k with
    | 0 => false
    | S k' => check k' n
    end.

これに対して次の補題が証明できます。

Lemma check_spec :
  forall k n, check k n = true <-> exists m, m <= k /\ n = m * m.

次に task の証明を考えます。まず exists (fun n => check n n). としてから上の補題を使えば、証明すべきことは

(exists m, m <= n /\ n = m * m) <-> (exists m, n = m * m)

になります。これは自分で証明してもそんなに大変ではありませんが、firstorder nia とすると自動で証明してくれます。

D. Eat the Candies

Definition piles := (nat * nat * nat)%type.

Inductive take2 : piles -> piles -> Prop :=
| Take12 p q r : take2 (S p, S q, r) (p, q, r)
| Take13 p q r : take2 (S p, q, S r) (p, q, r)
| Take23 p q r : take2 (p, S q, S r) (p, q, r).

Inductive take_all : piles -> Prop :=
| Takeall_empty : take_all (0, 0, 0)
| Takeall_step c c' : take2 c c' -> take_all c' -> take_all c.

Definition task :=
  exists f : nat -> nat -> bool,
    forall p q r, f (p + q + r) (max p (max q r)) = true <-> take_all (p, q, r).

問題概要

飴の山が三つあります(山は空である場合もあります)。空でない山が二つ以上ある限り、次のことを何度でも行うことができます。

  • 空でない山を二つ選び、それぞれから一つずつ飴を取って食べる。(同じ山から二つ取ることはできない)

山に含まれる飴の個数を p, q, r とします。全部の飴を食べることができるかどうかを判定する関数を書き、その正しさを証明してください。ただし、判定関数には p, q, r そのものではなく、それらの和と最大値のみが与えられます。(p, q, r そのものを与えると全探索で判定できてしまうのでこのような問題設定にしてみました)

必要十分条件

二つずつ食べるので、飴の合計数が偶数であることが必要です。また合計が偶数の場合をいくつか実際に試してみると、一つの山に飴が偏っていなければ可能であることが推測できます。これを手がかりにして、可能かどうかの境界がどうなっているかを調べれば必要十分条件を発見することができるでしょう。

とりあえず p, q, r がわかっているとすると、「p + q + r が偶数かつ p, q, r の最大値が残りの二数の和以下」が必要十分条件になります。後半を「最大値の二倍が全体の和以下」と言い換えることで和と最大値だけを用いて表せる条件になります。

まずはこの条件を判定して bool 型の値を返す関数を書く必要がありますが、これは Nat.evenNat.leb を使えばできます。この条件を P と呼ぶことにします。

十分性

P が成り立っているときにすべての飴を食べきれる戦略を与えればよいです。戦略を与えるときには p, q, r がわかっているとしてよいことに注意してください。直感的には飴の個数の偏りが少ないほうが P が成り立ちやすいので、偏りを減らすように選ぶのが最適であると推測できます。

そこで、残っている飴の個数が多い山を優先的に選ぶ戦略を考えます。この戦略のもとで、初期状態が P を満たしていればその後も P が成り立ち続けることが示せます。飴の数は単調に減少するので、p + q + r についての帰納法で十分性が証明できます。

証明をする際には andb_true_iff, Nat.leb_le, Nat.even_spec などの補題lia tactic が有用です。

必要性

take_all c の導出についての帰納法で示せます。一ステップ戻ったときに飴の数の総和は2増えるのに対して最大値は増えても1だけなので不等式が成り立ち続けることが(数学的には)証明の要点ですが、boolProp に変換してやればそのあたりはあまり自分で考えなくても lia で証明が終わると思います。

TopProver Sprint Round 10

A. Swap Twice

Definition swap (t : nat * nat) :=
  match t with (a, b) => (b, a) end.

Definition task := forall t, swap (swap t) = t.

組を左右を入れ替える関数 swap が定義されていて、それを二回やると元に戻ることを示せという問題です。

t が必ず (a, b) の形に書けることを考えるとあたりまえっぽくて、t(a, b) の形に分解してやればよいです(そのままですが)。これは destruct でできます。

Require Import Problem.

Theorem solution : task.
Proof.
  unfold task.
  intro t.
  destruct t.
  simpl.
  reflexivity.
Qed.

intro してから destruct してますが、intros (a, b) と書いてもいいです。

B. Drinker paradox?

Definition task :=
  forall P : bool -> bool, exists a, P a = true -> forall x, P x = true.

古典一階述語論理で証明できるけど直感に反する論理式として知られているものです。一般の形では Coq で証明できませんが、P : bool -> bool にしてあるので証明できます。

P のありうる値は 4 通りあります(厳密には外延的に等価なものを除いて 4 通りですが、この問題では気にしなくていいです)。P true = true かつ P false = false のときは a = false であればよく、それ以外のときは a = true であればよいです。

あとは場合分けをするだけですが、単純に destruct (P true) などとするとうまくいきません。対処方法はいくつかありますが、分かりやすいのは

forall b : bool, b = true \/ b = false.

のような補題を証明して、これを利用して場合分けをする方針でしょう。

他には destruct eqn を使う手もあります。以下にこちらを使った例を示します。

Theorem solution : task.
Proof.
  unfold task.
  intro P.
  destruct (P true) eqn: Pt.
  - destruct (P false) eqn: Pf.
    + exists true.
      intros _.
      intro b; destruct b.
      * assumption.
      * assumption.
    + exists false.
      rewrite Pf.
      intro f_eq_t.
      discriminate f_eq_t.
  - exists true.
    rewrite Pt.
    intro f_eq_t.
    discriminate f_eq_t.
Qed.

C. Upper triangular (soundness)

(*
                       j
   -------------------->
  | 0  1  3  6  10  ...
  |    2  4  7  11  ...
  |       5  8  12  ...
  |          9  13  ...
  |             14  ...
  |
i V

*)

Inductive visit : nat -> nat -> Prop :=
| visit_first : visit 0 0
| visit_down : forall i j, i < j -> visit i j -> visit (S i) j
| visit_right : forall i j, i >= j -> visit i j -> visit 0 (S j).

Definition task := forall i j, visit i j -> i <= j.

図のような順にマスを踏んでいくとき、(i, j) が踏まれることと i <= j が同値になりますが、次の問題と合わせてこれを証明します。(i, j) が踏まれるなら i <= j を示すのがこちらの問題です。

visit i j についての帰納法を使い、残った細かい不等式などの証明を lia で処理するのが一番簡単です。

Require Import Problem Lia.

Theorem solution : task.
Proof.
  unfold task.
  intros i j H.
  induction H.
  - auto.
  - auto.
  - lia.
Qed.    

ij についての帰納法でもできます。その場合には途中で inversion が必要です。

D. Upper triangular (completeness)

Inductive visit : nat -> nat -> Prop :=
| visit_first : visit 0 0
| visit_down : forall i j, i < j -> visit i j -> visit (S i) j
| visit_right : forall i j, i >= j -> visit i j -> visit 0 (S j).

Definition task := forall i j, i <= j -> visit i j.

C の逆です。こちらはよく考えないと帰納法が回らなくて難しいです。

結論から言うと、変数の順番を入れ替えて j, i の順で二重帰納法をするとうまくいきます。これは各マスがどの順番で踏まれるかを考えると納得しやすいでしょう。図を見れば「j の小さいものが先に踏まれる」「j が同じ二つのマスは i の小さいものが先に踏まれる」ということがわかります。このことから (i, j) たちは j を優先する辞書式順序で小さい順に踏まれるのだから、これに合った帰納法を使えば証明できそうだと予想できます。つまり、外側で j についての帰納法、内側で i についての帰納法をすればよいということです。

順番を入れ替えるには一旦 intro してから revert で内側にしたい変数を戻します。

Require Import Problem Lia.

Theorem solution : task.
Proof.
  intros i j.
  revert i.
  induction j.
  - induction i.
    + constructor.
    + lia.
  - induction i.
    + econstructor; eauto.
    + constructor; [ easy | ].
      apply IHi; lia.
Qed.

E. Infinite duplication

Require Import Arith.

CoInductive stream :=
| SCons : nat -> stream -> stream.

CoFixpoint gen m n :=
  SCons m (if m <? n then gen (S m) n else gen 0 (S n)).

Fixpoint Snth n s :=
  match n with
  | 0 => match s with SCons h _ => h end
  | S n' => match s with SCons _ s' => Snth n' s' end
  end.

(* Show that each natural number occurs infinitely often in [gen 0 0]. *)
Definition task :=
  forall x, forall y, exists z, y <= z /\ Snth z (gen 0 0) = x.

C, D と同じ状況で踏んだマスの i 座標を順番に並べた無限列を考え、すべての自然数が無限回現れることを示せという問題です。gen i j はマス (i, j) から始めたときにできる無限列になります。

C, D で出てきた visit に何ステップ目で踏むかを表す引数を追加したものを考えます。マス (i, j)k が書き込まれていることと visit i j k が成り立つことが同値です。

Inductive visit : nat -> nat -> nat -> Prop :=
| visit_first : visit 0 0 0
| visit_right : forall i j, i < j -> forall k, visit i j k -> visit (S i) j (S k)
| visit_down : forall i j, i >= j -> forall k, visit i j k -> visit 0 (S j) (S k).

D とほぼ同様にして次のような補題が証明できます。

Lemma le_visit : forall i j, i <= j -> exists k, visit i j k.

そうすると、直観的には visit i j k のとき gen 0 0 の先頭 k 個を取り除いた列が gen i j になりそうです。それを表すために、指定した個数の要素を取り除く関数を書きます。

Fixpoint Sskipn n s :=
  match n with
  | 0 => s
  | S n' => match s with SCons _ s' => Sskipn n' s' end
  end.

ちょっとした補題を準備すると次のことが証明できます。

Lemma visit_skip : forall i j k, visit i j k -> Sskipn k (gen 0 0) = gen i j.

これを使って task が証明できます。与えられた x, y に対し visit x (x + y) z となる z の存在が le_visit からいえて、この z に対して y <= z /\ Snth z (gen 0 0) = x であることが示せます。y <= z を示すには一般に visit i j k -> j <= k であることをいっておけばよく、これは難しくありません。

writer 解はこちらにありますgen の定義に CoInductive が使われてますが、有限個の要素しか見ていないので残念ながら余帰納法の出番はありません。

第5回 Asprova プログラミングコンテスト

https://atcoder.jp/contests/asprocon5 に参加しました。

第4回同様焼き鈍しじゃないことをしたいなーと思いながら考えたんですが、結局焼き鈍しをしました。でも焼き鈍し部分にはまだだいぶ改善の余地がありそうな状態だったので(具体的にどこに改善の余地があるかの検討すらできていない)、たぶんアイデアがよかったのだと思います。

オーダをバッチに分けて一列に並べて先頭から順番に割り付ける貪欲法を書いて、バッチの分け方と並べ方を焼き鈍しました。一つのバッチは必ず同じ資源を割り付けるようにします。こうすると作業の間に隙間ができにくくなると同時に、実質的なオーダ数を減らすことができて処理が高速化になります(という証拠をちゃんと持っているわけではないけど、スコアがよかったのでたぶんそういうことだと予想)。

最初にやったこと

とりあえず generator とサンプルのソースを読む。問題文に明示的に書かれていないこととか正しく理解しているかどうか気になったことをいくつか確認する。

  • item, resource を決めると対応する role は(存在すれば)一意に決まる
  • item, role を決めても resource は一意に決まらない
  • 特に、多くの場合は item ごとに main resource が複数ある(サンプルコードを見ると一つしかないような処理をしているけど単に決め打ちしているだけ)
  • order の profit は q と item の profit で定まる
  • 段取りペナルティは副資源の選び方に依存しないで決まる

あとテストケースを生成するスクリプトを書いたり、generator を少し改変したりした(A=1000 のときにペナルティ係数を強制的に1000にする処理を入れただけ)。

output_checker のエラーメッセージをもっと詳しくする作業をやっておくとよかったかもしれないと後で思った。毎回同じことを思っているけど、毎回原因のわからないバグが発生したらその都度必要そうな情報を出力するように書き換えて何とかしている。

次に入力を読むコードを書いてみた。自分でこういう作業をすると問題の意味が少しわかってくるので、じゃあどういう風にしたらいいだろうかということをいろいろ考え始める。(とりあえず自明な貪欲法でいいので最初に自分で書いたほうが理解が早かったかもしれない)

あまりよさそうな方針を思いつかないので、前回までに何をやったか思い出してみた。以下前回のメモの一部。

  • 注文と設備の組を全通り試して、割り付けたときにその前にできる隙間時間と段取り時間と終了時刻の和が最小になる組を次に割り付ける貪欲
  • 遅延がないときに penalty の計算をしない(浮動小数点数の演算があるのでけっこう違いが出る)
  • スコア計算式の粗利のところは全注文の pr の総和が足されるだけなので、入力を読んだときに総和を覚えておいて、あとで足せばよい
  • a はペナルティ計算のときしか使わなくて必ず pr/a の形で出てくるので、はじめから pr/a だけ覚えておけばよい

前回との大きな違いになりそうなのが資源が複数あることで、どの資源に割り付けるかの組み合わせが場合によっては膨大なのでそこを工夫する必要がある。例えば主資源だけ全部試して、副資源は貪欲に決めるとかだろうか?あるいは組み合わせではなく役割ごとに全部貪欲に決めるとか。

とりあえず貪欲

とりあえず何をしたらいいかよくわからないので、注文を開始時刻でソートして貪欲に割り付けてみる。サンプルコードとあまり変わらないけど、全資源を見て一番早くなるように割り付ける。

それだけだとあまりよくなくて、単純に最早開始時刻でソートすると同じ品目の注文がばらばらに割り付けられてしまう。そこで最早開始時刻を適当な値(32768とか)で割った商でソートして、商が同じなら品目番号でソート、とかをいろいろするともっとよくなって手元で生成したテストケースで1960から1970ぐらい出る。

よさそうなのを提出してみたら 1994 が出ていた。手元で試したスコアよりだいぶよいので、もしかしたらある程度いいスコアが出るテストケースが選択されているのかもしれない。システムテストもそうなのかが気になり始める。

そういえばスコア計算をするコード書いてないなと気付いたけどまだ焼き鈍しを書く段階ではない感じなので保留にする。

貪欲法の難しさ

このあたりで気付いた、というか思い出したことなのだけど、途中までの計画ができているときに、次にどの注文をどこに割り付けるといい感じになるかということを評価するのがその時点ではかなり難しい。

余談だけどこれはスケジューリングに固有の話ではなくて、例えば囲碁とかでどの手を打つとその後に有利になるかを評価するのが難しいのと似ていると思う。なので逆に考えると、囲碁とかでこれをどう克服しているかというのが参考になるのではないか、ということは前から思っていて、第4回のときはモンテカルロ木探索みたいなことができないかということを少し考えたのだけど、あんまりうまくいかなかった(素人がちょっと試してみたけどだめだったという話なので、プロがやるともっといろいろやりようがあるのかもしれない)。

とりあえず思いつくこととして、どの注文を割り付けるかも決め打ちしないで適当な評価に基づいてやってみたらどうなるだろうかというのがあるので、それを試すことにした。擬似コードで書くとこんな感じ。

score = -1
next_o = -1
for each o in order:
  for each m in main_resource[o]:
      temp = assign_and_eval(m, o)
      if temp > score:
        score = temp
        next_o = o

割り付けの評価関数に使えそうな要素として思いつくものは、隙間時間・終了時間・段取り時間・遅延ペナルティ(係数の大きさも?)あたりがある。

ちょっと問題なのが遅延ペナルティの扱いで、早く終わる割り付けがあるのにわざわざ遅くなるところに割り付けたくはないので、その観点からは遅延ペナルティをマイナス評価にしたい。一方で、単純にそうしてしまうとどこに割り付けても遅れるような状態の注文がずっと放置されてしまう可能性がある。だからもしかすると遅延ペナルティの発生している注文は逆に優先的に割り付けられるべきなのかもしれない。要するに、遅延の発生をプラスに評価するのかマイナスに評価するのかというジレンマがある。*1

たぶん、割り付けのスコアへの寄与という意味での評価と、割り付けの優先度とは異なる概念なのだろう。それを同じスコアで測ろうとしているのがよくないのだ。でも、仮に別々のスコアを考えたとして、それを使ってどう計画も組み立てるのか?というのがそんなに自明ではない。

そんなようなことを考えながら、遅延ペナルティをプラスに評価して遅延するほど優先して割り付けるようにしたらスコアが上がったりした。

ただ問題があって、次にどの注文の割り付け先を決めかまで毎回全探索するようにしたので、計算時間がかかりすぎている。手元のマシン(AtCoder のジャッジサーバと同じくらいの実行速度)で大きいケースが 6sec とかかかるので TLE になる。

そこでとりあえず実行時間を測りながらあとどれくらいかかるかを推測して、TLE しそうなら探索範囲を狭めるとかしてむりやり対応してみた。

それから少し細かいこととして、後ろに割り付けるだけではなくてある時間帯に暇になっている資源があるときはその隙間に新しく作業を割り付けたい。これを主資源に対してやろうとすると段取り時間の変更でいろんなところに影響が出て大変(第2回のときはそれをちゃんと書いたけど)なのだけど、副資源だけなら後ろに波及しないのでやってみた。ちなみに後で焼き鈍しをやるときはこれをやらないほうが高速で試行回数が稼げてよさそうだったんだけど、一応両方提出しておいたところ最終的に最高スコアを出したのは隙間にも割り付ける版だった。テストケース依存でどちらがいいかが変わりそうなので(ちょっと見た感じだと大きい入力に対しては試行回数を稼ぐほうがいいようだ)、正しく使い分けるようにしたらもっとスコア上がったかもしれない。

ここまでのことを書いて提出してみたら 1997 になった。これ以上の本質的な改善はなかなか思いつかなかったのでちょっと別の何かをしないといけないなと思って考える。

上述のように、途中までの割り付けが与えられたとき、それが残りの割り付けまで考えたときにいい状態なのかどうかを評価するのが難しい。これが本質的な困難な気がして、これは何らかのヒューリスティクスで簡単に乗り越えられるようなものでもない感じがした。こういうときは計算機の力に任せていろいろ試していいやつを選んでいくのがよくて、それはお馴染みの焼き鈍しではないかという気持ちになる。

このあたりの考察をしていたのが1/3の午後。そろそろ残り時間が気になってくる。

バッチ化

副資源がボトルネックのとき、主資源から決めるやり方だと隙間が大量にできてしまう。特に副資源に異なる品目が交互に割り付く形になりがちで、きれいに詰め込まれない。そのせいで副資源に空いているところが見つからなくて後回しになる注文が出てくる。こういう状況がスコアを下げていそうなので、なるべく同じ品目の注文を連続するようにまとめて割り付けることで隙間ができにくくしたい。

これを解決できるかもしれない方法として、同じ品目に対するいくつかの注文をひとまとめにして、まとまりごとに順番に割り付けていったらどうかということを思いついた。ここではひとまとまりの注文群のことをバッチを呼ぶことにする(コンテスト中に提出したコードでは cluster と呼んでいたけどバッチのほうが近い気がする)。

とりあえず注文をバッチに分ける処理を適当に書いてみた。バッチは注文の列で、注文全体はバッチの列として保持される。この列の先頭から順番に貪欲に割り付ける。バッチの順番はこれまでと同じように最早開始時刻でソートしてやって、これと今までと同じようにして貪欲に割り付けてみたら、ただの貪欲よりもかなりよくなった。

ただビジュアライザを見てみると、クラスタサイズが大きいときは二つに分割して手分けしたほうが遅延が小さくなるケースがある。どういうときにどうすればいいかを探りながらヒューリスティクスをコーディングするのは大変そうなので、こういうところの最適化は焼き鈍しが強いのかもしれない。

とりあえずバッチ化がどれくらいの効果を持つのかを確認するために、バッチ化したあと単純な貪欲法をやるコードを提出してみたら 199820474638 になった。実行時間 8 msec でこのスコアだったので、焼き鈍しがうまくいけばだいぶスコアが伸びる気がしてくる。

焼き鈍しをする

3通りの遷移をする焼き鈍しを書いた。

  • ランダムに選んだ二つのバッチの順序を swap
  • ランダムに選んだバッチと、その次に現れる同じ品目のバッチを一つにまとめる
  • ランダムに選んだバッチをランダムな位置で二つに分ける

とりあえず動くものを書いてみたらスコアはかなり上がるようだった。実行時間を伸ばしたらまだ上がるので、高速化がある程度は効きそうだということで、差分計算ができるようにしてみたり割り付けの計算中にペナルティが大きくなったら途中で打ち切ってみたり、データ構造を変えて(サイズが小さいから定数倍の違いが効いて map で O(log N) の処理より vector で O(N) のほうが速いとか)高速化を図ってみたりした。

最後に温度調整もしたのだけど、これはだいぶ目測を誤って低めの範囲で探索してしまって、試した中で一番温度の高いものが最高スコアだった。もっと高い温度にしたらスコアがよくなったかもしれない。しかも時間がなくて温度調整をしながら別のマシンでコードを書き換えていたので本当に適切な温度が選べている可能性は低い。

他の最適化として、結局あまり真面目にやらなかったけど遅延している部分のペナルティ最小化も考えた。隙間のない連続した同品目の割り付けについては a * q / pr の昇順にするだけだから O(NlogN) でできる。ただし、どう並べ換えても全注文で遅延が発生し、かつどう並べ換えても最早開始時刻に違反しないというような条件が必要なはずで*2、たまにこの条件が破られることがあるのでちょっとめんどくさい。

あとコンテスト期間終了後に気付いたのだけど、バッチ中での注文の並べ替えも遷移に入れたほうがスコアが上がった。最初に焼き鈍しを書いたときはあまり効果がなかったように見えて没にしたけど、高速化して試行回数が増えることで状況が変わったのかもしれない。バッチ間の swap に比べるとスコアへの影響が少ないので、試行回数が少ないときは他の遷移のスコア変化に埋もれてしまっていたのが試行回数が増えることで見えるようになったとか?

*1:試さなかったけど、どうしても遅延が発生するときだけプラスにするのはありだったかもしれない

*2:この仮定があれば証明はややめんどくさいけど難しくはない