Dijkstra 法の納得感のある説明について考えている

以前からときどき考えています。完成はしていません。

基本的には距離の短いほうから探索するだけだと思うので、それを典型的な DP っぽく書いてみます。

dp[v][d] := 頂点 v までの距離がちょうど d の walk が存在するかどうか

としてみます。都合で path ではなく walk にしていますが、辺の長さが正なら最短な walk は path なので結果はどっちでも同じです。

そうすると dp[v][d] が成り立つのは v が始点で d = 0 のときと、ある u から v への長さ c の辺があって dp[u][d-c] が成り立っているときなので、d が小さいほうから DP するとテーブルが埋まります。

配る DP で書くとこんな感じになります。

dp[s][0] = true
for d from 0:
  for (u, v, c) in E:
    if dp[u][d]:
      dp[v][d+c] = true

でも最短距離が知りたいだけだからこんなに大きなテーブルは必要なくて、最適化すると Dijkstra 法になると思うんですけど、ここから先があまりうまく導出できない。

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

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

今回の問題設定で最初に思いつく方針は第3回同様焼き鈍しなんですが、最近焼き鈍し以外の方法を試したい気持ちがあったので別の方針を考えていたらうまくいきませんでした。それで結局残り時間が少なくなってから焼き鈍しに切り替えましたが、いろいろ分析する時間がないと厳しいですね。そもそもいい貪欲法を思いつくまでの時間が長すぎというのもありましたが。

最初にやろうとしたこととか

問題文を読んでみたら、いくつかわからないところがあるので generator のソースを読んでみる。

• 同じ品目を複数の設備で作れる場合がある。それどころか、1/2ぐらいの設備で作れる
• 粗利は注文ごとに入力されるが、実は品目ごとの粗利が決まっていて、それとオーダ数との積で算出されている
• 最早開始時刻から納期までの時間は、各設備での製造時間の平均の2倍と Dmax の min 以上
  • ということは、速い設備が都合よく使えれば間に合う
• それ以外のパラメータはだいたい一様ランダムと思ってよさそう
  • 製造速度もランダムで 1-200 とかなので特定の品目に関して使える設備は事実上一部に限られそう

焼き鈍しではない方針として最初に考えたもの。

1. とりあえず貪欲を書く
2. 貪欲法にランダム要素を入れてみる
3. ランダム入り貪欲法を使って playout をするモンテカルロをする

最初に、納期でソートしてその順に割り付け先の設備を決める貪欲を書いてみた。これでだいたい2900億ぐらい。このときは単純に粗利からペナルティを引いたもので評価したけど、後で考えてみるとこの評価のしかたは今見ている工程が後ろに続く工程にどういう影響を及ぼしそうかが考慮されてなくて、それほどうまくいきそうにない（例えば割り付ける工程の品目を下手に選ぶと次にすごく長い段取り時間がかかるかもしれない）。

当初の予定では、途中まで割り付けを定めた計画の評価値として、残りを上記の方法で貪欲に割り付けたときのスコアを使うつもりだったのだが、それだと遅すぎるしスコアもそんなによくはない印象。

ビジュアライザで見てみると、無駄な空白時間がたくさんできているようだ。どうも割り付けの順番を固定して後ろへ割り付けていくという戦略はあまりよくなくて、途中の隙間にも入れるとかしないといけないらしい。

焼き鈍してみた

どうもいい方針が浮かばないので、今あるコードに焼き鈍しを入れる最短の手順として、割り付けを決める順番を焼き鈍すということを試してみた。このあたりでとりあえず提出してみたら 2976 ぐらい。たぶん近傍がよくないのと、貪欲法があまりうまくないのだと思ったが、どうにも解決策が浮かばず。

とりあえず同じ品目がもっと並んでいてほしい気がしたので、ランダムに区間を選んで品目番号でソートするとかいう強引なことをしてみたら、スコアは上がったが 2993 ぐらいで 3000 までまだだいぶ距離がある。

貪欲法を改善してみるなど

やっぱり初期解が悪すぎるのではという気がして、別の貪欲法を考えた。注文と設備の組を全通り試して、割り付けたときにその前にできる隙間時間と段取り時間と終了時刻の和が最小になる組を次に割り付ける、という貪欲をやったらそれだけで 2990 ぐらいになった。前の初期解が 2900 ぐらいだったのでだいぶよくなった。

あとは結局焼き鈍し。各設備についてどの注文をどの順番で処理するかを決めると最適な割り付けは自明に定まるので（asprocon3 と同じで、できるだけ早い時間に割り付けていけばよい）、それを焼き鈍した。近傍は単純で、同じ設備の二つの工程のランダム swap と、ランダムに選んだ工程をランダムに選んだ別の場所へ移動するのを試した。

これだけだとあまりにも単純なので、いろいろ近傍を工夫しようとしたけど何をしてもよくならなかった。以下考えたこと（なんか全部スコアが下がった）。

• 同じ品目どうしの swap でないとほとんどよくならないので同じ品目の組が高確率で選ばれるようにする
• あまり時間的に離れた組の swap や離れたところへの移動をしても改善しそうにないので、ある程度移動範囲を絞る
• ある工程を別の設備に移動する場合、前後どちらかに同じ品目があるところへ移動する確率を高くする
• swap や移動の距離の上限を、時間経過とともに小さくする（焼き鈍しの温度を下げるのと同じ要領）
• 納期遅れの発生している注文を高確率で選ぶようにする

あと細かい高速化。

• 遅延がないときに penalty の計算をしない（浮動小数点数の演算があるのでけっこう違いが出る）
• スコア計算式の粗利のところは全注文の pr の総和が足されるだけなので、入力を読んだときに総和を覚えておいて、あとで足せばよい
• a はペナルティ計算のときしか使わなくて必ず pr/a の形で出てくるので、はじめから pr/a だけ覚えておけばよい

ヤマト運輸プログラミングコンテスト2019

https://atcoder.jp/contests/kuronekoyamato-contest2019 に参加した。登録してないと問題文が読めないみたいですが。

問題1

クエリ数がまあまあ多いので全点対間最短距離だと思い、有向グラフを作って Warshall-Floyd をした。頂点数 2000 ぐらいにしかならなくて時間が 10 sec あるので実装が楽な Warshall-Floyd でやったけど、余分な辺を作らなければたぶん辺数が 10000 にもならないと思うので Dijkstra を頂点数回やったほうが速そう。

車両と台車で同じグラフを使おうとすると頂点を同一視していいかどうかとかの区別が面倒なので、二つ別々に作ったほうが楽だった。「辺を張る」と書いてるところは、Warshall-Floyd なら単に距離行列に値を書き込むだけでよい。

• 車両用のグラフ: 各道について、両端点に対応する頂点を作る。道は順方向と逆方向を区別して、それぞれ別々に作る。各駐車可能箇所にも対応する頂点を作る。同じ道の上にある頂点（駐車場所と端点）間にその間の距離に等しい長さの辺を張る（向きに注意）。さらに各交差点について、進入可能な端点の組み合わせすべてについて、長さ 0 の辺を張る。
• 台車用のグラフ: 道の向きを区別しないことと配達先も頂点にする以外は車両と同じ。辺もほぼ同様だが、交差点ではそこへ合流しているすべての道の端点の間に長さ 0 の辺を張る。

たぶんテストケースにひとつだけ交差点に駐車できるケースが含まれていて、これの処理を間違えて WA をもらった人がたくさんいそうだと思った（もらった）。

問題2

貪欲 + DP

配る順番を固定すると DP で最適経路が求まる。dp(i, p, k) = 「i 番目まで配って車が p にいて台車に荷物が k 個乗ってる状態になる最短の時間」とすると、O(荷物数 * (駐車場所数 * 台車容量)^2) 時間でできる。ということは、安直に考えると配る順番をうまく見つければよいことになる。

配る順番は、短い経路を見つけたいのだから直感的には短そうなハミルトンパスを探せばよさそう（ただし台車の容量とかの制約があるので最短のハミルトンパスが最適解になるとは限らない）。なのでそれっぽいヒューリスティクスを調べてみたら、一番近いところから訪問する貪欲法が一番簡単そうだったのでそれでやってみた。

ただし単純に距離だけ見て貪欲法をやると時間指定を考慮してないのでうまくいかないことがある。そこは指定時間で配達先を分類して別々にパスを作ってつなぐとかしてごまかす。始点によって実行可能解ができたりできなかったりするので、始点を全通り試す。それぞれの点から始めて貪欲法でパスを求めて、それに対して DP をして、最終的に一番よかったものを解として選ぶ。

とりあえずこれで 712 万点ぐらい出た。

bit DP

台車に荷物を乗せてそれらを配ってまた車のところに戻ってくるまでを一つのターンと考えることにする。

あるターンにおいて出発する駐車位置と配る荷物が決まっていて、荷物の個数が D のとき、そのターンの最適な行動はハミルトン閉路と同じ要領で bit DP をすれば O(2^D*D^2) で厳密解が出る。一ターンに配る荷物は10個までなので、これくらいの計算量なら問題なく最適解が求められる。そこでときどきこれをやってターンごとの経路の最適化をした。焼き鈍しの遷移の一部として書いていたけど、あらためてまとめを書いていたらこれは遷移とは性質が違う気がしてきたので、もっと別の扱い方があったかもしれない。

ちなみに荷物の個数や駐車場所が決まっていなくて D 個の荷物を配る最短時間を求める DP は、駐車場所の数を P, 台車の容量を K として O(2^D * (DPK)^2) になる（と思う）のであまり D を大きくできなくて、部分的にやるとしてもやや厳しいかなと思った。荷物12個で駐車場所固定とかだったらできるので二ターンまとめて最適化をちょっとだけやってみたけど、あまり効果がなさそうだったので没にした。

山登り・焼き鈍しの遷移について

列を変化させるというとすぐ思いつきそうなのが次の二つ。一つめは TSP とかでよくある 2-opt と同じだと思う。

• 区間を選んでその範囲の順序を反転する
• ひとつ要素を取り除いて別の場所に挿入する

二つの要素の swap も一瞬考えたけど試さなかった。ランダムな swap だとあまり効きそうになかったから検討しなかったけど、よさそうな組を探して swap すれば効果はあったかもしれない。

これに加えて上に書いた bit DP もときどきやってみた。

このあたりの近傍を使って山登りをしたら 739 万ぐらいまで、焼き鈍しと諸々の高速化や温度調整をやっていたら 746 ぐらいまで上がった。さらに初期解を改善したり、よさそうな遷移を選ぶ確率が高くなるようにしたりして 750 ぐらい。

あるとき10000点の境界が壁になってるのが問題であることに気付く。例えば 800010 点とかの時間ぎりぎりで最後の荷物を配達する経路を見つけたときに、ここからスコアが上がる近傍がほとんどないみたいな状態になる場合があって、下手にここにはまると遷移がほとんどできなくなって詰んでしまう。こういうときには一度790000点台(実際は790100点とかになる)に下がることを許容したい。

これに気付くとまずは温度を上げたい気持ちになるのだが、-10000点をたまに受け入れるような温度にすると小さなスコアの低下はほぼ必ず受け入れることになってしまう。そんなことをするのもどうかと思ったので、温度は上げないで、普通の判定とは別に-10000点ぐらいだった場合に遷移するかどうかの判定をアドホックに追加した。

焼き鈍しの高速化について

DP がけっこう時間を食うので高速化が必須、なのだが結局それほど頭のいいことはしてない。

• 差分計算。遷移で変えたところより手前は計算し直さなくてよい。
• DP の途中で時間がかかりすぎてそうな状態からの遷移は考慮しないようにする。
• 焼き鈍しの途中で現れる解の中で使われる駐車箇所は、手元でテストした限り全駐車箇所の一部だけだったので、、最初の 20 秒の間にどれが使われたか記録しておき、残り 40 秒は使われなかったものを無視して DP する。

これで数倍から10倍くらいにはなっていそう（いろいろ変更しながら最終的に上のようになった、という感じなので、あまり正確な比較はできてない）。DP の枝刈りをどこまでやるかはけっこう微妙なところかもしれない。

評価関数について

今回あまりうまい評価関数を思いつかなかったのだけど、この問題のスコア関数はそのままだと焼き鈍しに向かない気がするので、本来はもっと力を入れるべきところだったかもしれない。

一応、配れなかった荷物についてもなんとなく惜しそうだったら点数が追加される感じにした。残りの荷物それぞれについてどれくらい時間オーバーするか計算して（正確に計算すると時間がかかるので単純に台車での移動時間と滞在時間を足していった）、オーバーする時間に対して指数関数的に小さくなる項をスコア関数に足した。

これにどの程度効果があったのかはわからないが、10000点ぶんぐらいは貢献しているかもしれない。手元でテストしたときはむしろ悪くなってるのではと思ったけど提出してみたら少なくとも悪くはなってなさそうだったから消さないでおいた。

もうちょっと真面目に検討するならまず怪しい気がするのが台車の容量を無視しているあたりで、単純に移動時間を足すよりももっと正しいやり方があったのかもしれない。DP を最後までやるのが数値的には一番正しく出るけど、そこまでやると正確に計算できるメリットよりも計算時間がかかりすぎるデメリットのほうが大きそう。

もっと細かい点では、時間の単位を 1/50 秒にしていたので（そうするとすべての時間が整数で計算できる）、本来のスコアの値それを 50 倍にしたものを使っていた。切り捨てが発生しないのでこのほうが精度がよさそうな感じがしてそうしたが、実際はどちらでも大差なさそう（焼き鈍しの遷移判定のときに若干の違いは出る）。

いろいろ

• 配達順序を焼き鈍す方針をとってみたが、これだと駐車位置のことはほとんど考えなくなるので楽な面もある一方で、せっかく使える情報を捨ててしまっていたようにも思える。
• 提出ごとに何を変更したか、スコアがどうだったかを見やすく整理できる仕組みがあるとよさそう。
• generator を書いたのでけっこう自分で生成したテストケースを使ってテストしたが、細かい変更に対してスコアが改善するかどうかは手元でのテスト結果と提出結果で一致しないこともよくあった。
• visualizer も書こうとしたけど見やすい表示方法を思いつかなくて使えるものができなかった。どう表示するのがよかったんだろう。絵にこだわらないでテキストでもいいからいろいろ解の情報を書き出したり、手動で解をちょっと変更してスコアがどうなるか観察できるようにしておくとよかったかもしれない。

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

第3回 Asprova プログラミングコンテストに参加しました。1位だったようです。最後にパラメータをいじって数回提出したら900万点ぐらい上がってしまった結果なので、3位から上のスコアに本質的な差を感じられず、その点は運がよかったなあという感想になりました（完全に偶然上がっただけというわけではありませんが）。

コンテスト中にやったことをまとめてみます。

問題

その前に問題の内容ですが、ここには雰囲気だけ書くことにします。もとの問題文と違うことを書いていたり情報が足りなかったりするので、正式かつ正確な内容は問題文を見てください。

あなたは工場を持っています。工場には複数の設備があり、それらを動かして複数の品目を生産しています。それぞれの品目は複数の工程を経て完成し、各品目の各工程に使用する設備は一意に決まっています。

工場ではたくさんの注文を受け、それらを受けた順に生産することになっています。注文にはそれぞれ納期が決まっており、それに遅れるとお金はもらえません。

ある日あなたは、注文を受けすぎて現状の設備では納期までに全く対応しきれないことに気付きました。そこであなたは資金を投資することで設備の生産性を上げることにしました。

適切に投資して利益を最大化する計画を立ててください。なお必ずしもすべての注文を納期に間に合わせる必要はありません。

方針が固まるまで

各工程を割り付ける設備は一意に決まっているし、同じ設備に割り付ける工程の順番も決められているので、設備の能力の上げ方を固定すればなるべく早い時間から貪欲に割り付けていくのが最適スケジュールになる（と問題文にも書いてある）。そうすると、考えるべきことはどの設備の能力をどの日に上げるかだけなる。

よくわからないけどとりあえず山登り、と思ったがこれはよくなかった。ほとんどスコアが上がらない。考えてみればそれはそうで、近傍のとり方が下手だと初期状態から遷移できる先でスコアが上がる状態がほとんど存在しない。そしてこの段階でとった近傍はだいたい下手である。

こういう状況でまず最初に思いつくのはスコア関数をいじることで、今の場合だと納期遅れを一時的に許容したい感じなので、納期遅れが発生したときは遅れの量に応じて利益に一定の割り引き係数をかけてみた（元々のスコア関数は少しでも遅れると 0 になる）。ところが、これは係数が大きすぎると遅れをあまり気にしない計画になって能力追加するメリットが少なくなるし、係数が小さすぎると能力追加コストが見返りに勝ってしまうので何もしないほうが得になってしまう。ということであまりいい結果が出ない。

ビジュアライザを見た感じだと、広範囲に対してまとめて能力追加しないとあまり効果がなさそう。追加コストの評価も一時的に小さくする、とか考えられないわけではないけど、こういうことを積み重ねるのもちょっとアドホック感が出てくるきらいがある。

そこで別の方針を考えた。能力をちょうどいいところまで上げる問題ではなく、最初に多すぎるくらい追加しておいてちょうどいいところまで下げる問題だとみなす。これがわりとよかったようだ。何しない状態だとスコアの上がる遷移があまり見つからないのに対して、上げすぎの状態は不要なところをちょっと下げるだけでスコアが上がるので、スコアが更新される遷移がたくさんあるのだ。

まず最初に、コストパフォーマンスのよさそうな（性格には、単位資金あたりの短縮稼動時間が最大の）設備を選んでちょっとずつ増やすループを回し、遅れがなくなったらそこから各設備と各日付けについて減らしても大丈夫ならちょっと減らすループを回して解を作ってみた。練習用データだといい具合になったと思ったけど、提出してみたら一部のテストケースで大幅にマイナスになって-10億点が出た。負の点数でも一応 AC は出るようだ（最高点が負だと新システムの順位表では0点になり、旧システムだと負の点数になって未提出よりも下位に表示される？）。

スコアは負になったけどこれを初期解にして山登りでもするか、という気持ちになって試してみたらすぐ局所最適解に到達したので、焼き鈍すことにした。近傍のとり方は設備と連続する何日かをランダムに選んで、その日の能力を 8〜現在値+8 の範囲でランダムに変更する、とかだったと思う。ここまでのことを実装して 957875042 が出ている。

焼き鈍しができたので、高速化する意味があるかどうかを見るために回す時間を伸ばしたところ、まだけっこう上がるようだった。

このあたりまででだいたいの方針は出ていて、あとはずっと焼き鈍しを頑張る感じになった。後半は高速化にかなりの時間を費やしていた気がする。細かいところでは 1.1 乗をメモ化するとか温度の計算を 256 回おきにするとかメモリアクセスの局所性を頑張って上げるとかいろいろよくある最適化をした。高速化はループ回数という形でわかりやすく結果が出るので楽しいのかもしれない。最終的に焼き鈍しのループは practice05 で322万回ぐらい回っている。

あと、そろそろテストケースを手元で作るべきなんだろうなと思い始めたけど、結局作らなかった。

焼き鈍し周り

近傍のとり方

日をランダムに選ぶと全く稼動してない日を選んでしまう可能性がそこそこあって無駄になってそうだと思ったので、日を直接選ぶのではなく工程を選んでそれが割り当たっている日を取得することにした（各工程の開始と終了の時刻を覚えておく）。

practice04 の局所最適解（後述）を見て、同じ品目の連続する二工程に対して変更をするのも近傍に追加してみた。効果がどれくらいあるか実ははっきりしなかったのだが、平均的にはスコアはよくなってるようにも見えるので採用することにした。

近傍は時間経過に合わせてだんだん狭める。具体的には、x = (経過時間)/(制限時間) として ±(2+log_2(x)) の幅で能力追加量を変化させる。ただし一番スコアがよかった提出では x < 0.15 のときはもっと大きく動かしている。ちなみにこの式は x = 1, 0.5, 0.25 でそれぞれ 2, 4, 6 ぐらいになってくれるとまあまあよさそうな感じが（実験的に）したのでそれっぽいのにした。別にきれいな式にする必要はないし折れ線とか階段でもよかったと思う。

最後の 0.1% の時間は、追加能力を減らす方向だけを試す山登りにする（たぶん運がいいとこれで数十万点上がる）。

差分計算

一部の追加計画を変更すると何も割り当たっていない時間に能力追加してしまって無駄が発生することがあり、それが嫌だと思ってスコア計算中にいろいろ書き変える仕様にしてしまったため（そうする必要があると思ったのかどうかよく覚えていない）、状態を変更してスコアを計算し直す際に元の状態を丸ごとコピーしなければならなくなった。ここが最初ボトルネックになっていた。結局、状態とその一時保存先へのポインタを持っておいて、保存するときは memcpy して元に戻したいときはポインタの swap をするだけで済むようにした。

利益の差分計算は、最初に工程間の依存関係を表すグラフを作り（各工程から同じ設備の次工程と同じ注文の次工程へ辺を張る）、変更の影響を直接受ける工程から到達可能な工程だけ計算し直すようにするとやや速くなる。

能力追加コストの計算は、能力追加量を変更するときに毎回更新すればよい。

スコア関数

高速化と近傍のとり方以外でスコアに効いたかなと思うのは、評価関数を少しいじったこと。最初のうちは納期遅れをやや許容する形の式にして、時間経過とともに許容度を下げて、最終的には本来のスコア関数と一致するようにする。初期に試してうまくいかなかったやつだけど、能力を上げすぎて下げる方針に変えたのでまた状況が違う。

局所最適解にはまる様子

なかなかスコアが安定しないなあと思いながらずっとやっていたのだけど、結局最後まであまり安定しなかった気がする。特に practice04 のスコアがかなりぶれるので（平均で2600万ぐらい出るが悪いときは2500万ぐらい）、解をたくさん作って様子を見てみたところ、局所解はまりポイントが（少なくとも）二つあり、それぞれ50万点ぐらいずつもっていかれる様子が観察できた。

ひとつはオーダー番号4の注文で、これは主に設備7, 8を強化すると間に合うのだが、7により比重をおくのが正解で、8のほうに比重をおきつつ10も少し強化するというのがはまる局所解のようだ。近傍をうまくとれればたぶん脱出できるのだが、複数設備にまたがった変更が必要なのが難しいところか。この状況が存在することに気付いたので二つの連続する工程の位置に同時に変更を加えるという近傍を追加してみた。

もうひとつは終盤の品目3に対する注文群で、間に合わせようとするとコストが大きくなって割に合わないので切り捨てるのが最適のようなのだが、それなりの数をまとめて切り捨ててやる必要があるためか、頑張って間に合わせるスケジュールが局所最適になって抜け出しにくいらしい。こっちは対策できていないけど、あまりこれにはまるケースは多くはなかったような気がする。

焼き鈍しのスコア変化の様子

温度を変えながらそれぞれ10回ずつ実行したときのスコア上昇の様子をグラフにしてみた。

温度ごとのスコア変化の様子。右のほうが温度が高い

温度が高めのときにはあるところまで下がりぎみで、途中から上昇に転じる様子が見えたので、それなら上昇を始めるあたりの温度を初期温度にすればいいのでは、と思いそうしてみたところ具合がよさそうだった。そうすればいいと思ったのは理論的な根拠があったわけではなくてなんとなくなんだけど、これって一般的にうまくいく方法なんだろうか。

その他

終了後に、初期解をそのまま返すコードを投げてみたら 669780418 が出た。2000ms ぐらいかかっていて、わりと想定外だった。手元で真面目にテストケースを作ってみていたら事前にわかっていたのかもしれない。

でも今回は前回に比べるとある程度ちゃんとデータを見ながら正しい方向に改善を考えられた気がする。テストケース作らなかったけど。

Marathon Match 107

マラソンマッチ始めてみました。問題文

問題概要

縦 H 横 W のグリッドがあります。各マスに 9 以下の非負整数が書いてあります。マスのいくつかを塗って、塗られたマスに書いてある数の合計を大きくしてください。ただし 縦 h 横 w のどの長方形も塗られたマスを Kmin 個以上 Kmax 個以下含むようにしなければなりません。

とりあえず正の点をとる方法

h×w の subgrid の中から Kmin 以上 Kmax 以下の個数を塗る任意のパターンを作る。左上から順番に塗るとか、何でもいい。それを H×W に周期的に拡張すれば制約を満たす塗り方ができて正の点が得られる。

その後のいろいろ

初期解が作れるようになったので、とりあえずこれを動かして山登りをしてみた。何箇所か塗る/塗らないの状態を flip したものを近傍にした（最終的には二箇所だけにした）。提出してみたら 930070.87。この時点ではまだいろいろ効率のよくない部分があったが、高速化はいつでもできそうなので後回しにして、方針を改善できないか考え直すことにした。

初期解を作るときに点数が高くて端に近いやつを優先的に塗る（マスの点数をそのマスを含む subgrid の個数で割った値を優先度にする）ようにしたら、それだけで最初の山登り解と同じくらいのスコアが出ることに気付く。ただ、これだけだと問題があって、たまに制約を満たすものが見つからないことがある。中央付近があまり塗られてなくて周辺がたくさん塗られすぎている状態になってしまった場合、追加で塗るマスをどう選んで制約を満たせなくなる。例えば H = W = 4, h = w = 2, Kmin = 1, Kmax = 2 で以下のような配置になった場合とか。

 ****
 ....
 ....
 ****

そこで、うまくいかなかったらちょっとランダム性を入れて何度か作り直すことにした。それでもだめだった場合は周期的な解の中で一番スコアが高いのを作る。これは以下のようにすれば作れる。まず 0 <= i < h, 0 <= j < w の範囲にある各 (i, j) について (x, y) = (i, j) mod (h, w) になるような (x, y) のマスの値の総和を求める。和が大きいほうから Kmax 個まで (i, j) を塗って、それを周期的に全体に拡張する。

5×5 の場合は全探索で間に合うのでそうした。もう少し大きいケースも枝をちゃんと刈れば厳密解が出せたかもしれないがやらなかった。このあたりで 958728.41

高速化と焼き鈍しをやって、細かいことをいろいろやって、焼き鈍しのパラメータ調整をして 989241.86

ところで貪欲解の構成に成功した場合は焼き鈍しをやってもほとんどスコアが上がっていないケースが多いようだけどこれはどう解釈したらいいんだろうなあとずっと思っていた。

学びと反省

• 時間を測るのに chrono を使ったら TLE が出た。調べてみると、rdtsc を使うとよいという情報が出てきたので真似してみたらまあまあいい感じになった。50ms ぐらい余裕をみておかないと TLE するときがあるみたい？
• 盤面が制約を満たしているかどうかの判定をたくさんやってるので segment tree を使ったら速くなるだろうと思ってやってみたら遅くなったので悲しみを感じた。（落ち着いて考えてみると調べる矩形が O(HW) 個あるので全部で O(HWlogHlogW) になっていて遅いに決まっているのでは）

Asprova コンテストに参加した

年末年始は Asprova Programming Contest をやってました。なんか問題文が軽い気持ちで読むには重すぎる感じなのですが，短くまとめると

• いくつかの設備を備えた工場があり，そこでいろんな製品を生産しています
• 各製品はいくつかの工程を経て完成します
• 各製品の各工程は処理できる設備とできない設備があります
• いま，どの製品がいつまでにいくつほしいという注文が200件来ました
• いい感じの稼動スケジュールを求めてください

という感じです。実際にはもっと条件があります。

やったこと（だいたい時系列順）

数字はその時点でのスコアです。ちなみに配布されてるサンプルコードをそのまま提出すると408307056327点です（試してないけどたぶん）。

• 問題文が何度読んでもよくわからないので，とりあえず配布されてたサンプルコードを読んだり入力を読むコードを自分で書いたりしてみる。
• サンプルコードを読んで出力を見てみたら，常に最初に見つかった設備に割り付けるようになっており，何も割り付けられない設備がたくさんあることに気付く。ちゃんと分散させたらそれだけでもスコアが上がるはずなので，それを実装してみることにする。
• 割り付け可能なすべての設備について，すでに割り付けられている一番遅い工程の終了時刻が一番早いところに割り付ける貪欲を書いた（つまりサンプルをすべての設備を見るように変えた）。ついでに注文を納期の早い順にソートしておくことで早く着手したほうがよさそうなものを早い時刻に割り付けるようにした。447088233657
• 出力を眺めていたら，一部の設備への割り付け時刻がどんどん後ろに遅延していく様子。たぶん単純に後ろに置いていくだけだと前のほうにたくさん隙間ができていそうで，そこに割り付けられる工程がありそう。そこで別の工程の間に入れられそうな隙間があったらそこに詰め込むようにした。段取り時間を計算し直す必要があったりしてこのあたりからだんだん実装がややこしくなる。448737404998
• 基本的に納期に対して遅れがちになるみたいなので，着手遅延を狙うよりは早めに着手して納期の遅れを減らすほうがスコアはよくなる傾向がありそうだと予想し，なるべく早い時間に工程を詰め込む方針考えることにする。ただし納期遅れが発生していない場合には，最後に納期の範囲内で全体を後ろへずらして着手遅延ボーナスを稼ぎたい。工程が複数ある入力でこれをやるのが面倒だったので，input 1（マスターデータ 1 から作られたやつ）の場合だけ最後にその処理を入れることにした（たぶんスコアへの貢献はかなり小さい）。
• 今までは開始時刻が最小のところに割り付けていたのだが，段取りのペナルティの係数をちょっといじったものを開始時刻に足した値が最小になるよう割り付けてみた。係数はいろいろ試して一番よかったのを採用する（この評価値，落ち着いて考えてみると質の異なるものを足しているのでどういう意味があるのか疑問だったのだが，最後までこれよりもよいものは見つけられなかったのでしかたなく使い続けた）。449614829656
• 簡単なビジュアライザを書いた。input 3 では最初の1/3を除いてずっと遅れが発生しているような状態になるらしいことがわかった。この入力だと最初のほうの工程を担っている設備が1--6で他の設備と担当できる工程が disjoint なのだけど，1--6がほとんど休みなしで稼動してこれだけ遅れているので，大幅な改善は難しそうに見える。この時点で上位陣は 4498 に乗っていたので，どこに改良の余地があるのだろうかと不思議に思い始める。ただ，納期の比較的早いものがずっと後回しにされているような印象はあったので，その部分をうまく解決する方法を考えられればよかったのかもしれない。
• 一つの注文は複数の工程からなっているのだが，注文ごとではなく複数の工程を別々に処理したほうが効率よく割り付けられるのではないか，と思い試してみる。優先度つきキューに処理すべき工程を入れて順に割り付けていくのだが，優先度のつけ方を納期の早い順にすると前よりも少しよくなった。449640963038
• さらに納期から所要時間の見積りを引いたものを優先度にしてみたり評価関数のパラメータの動かし方を変えてみたりパラメータをひとつ追加したりした（何も割り付けれていない隙間ができることに対してペナルティを課す項を足した）。449730476138
• 貪欲でこれ以上根本的な改善ができる気がしないので，乱数に頼るかという気持ちになり、ここまでで得られた解から始めて山登りをした。既に割り付けられている注文のいくつかをランダムに除去して割り付け直して，スコアが上がったら採用，を繰り返す。割り付けの制約が複雑なので，制約に違反しないように割り付け直すのがかなり大変で苦労する。assert をたくさん書いた。あと細かいことをいろいろ試して 449800668222
  • ちなみにこのスコアが出たとき提出したコードにはバグがあって手元で動かすとときどき segmentation fault が出るのだけど，このバグ（スコアにはさほど影響するとは思えない）を直すとスコアが1000万点ぐらい落ちるので困惑した。手元では直してもそんなに悪くなっているようには見えず，結局何が起きていたのかわからないままである。もしかしたら，たまたまジャッジサーバで実行したときにいい乱数が出るコードだったのかもしれないが，そんなことあるだろうか？

できるかもしれないと思ったけど結局やらなかったこと

• 高速化。山登りが2秒では全然収束してなかったのでできたらよかったのだけど。割り付けられそうな隙間を探すときに，線形に探索するのではなく区間木のようなデータ構造を持っておけば効率よく見つけられたかもしれない。線形探索でも平均すると10〜20回ぐらいループを回せば割り付け箇所が見つかっているようだったし，更新のオーバーヘッドも大きくなるはずだし，本当に割り付けられるかどうかは前後の工程とか見ないと判断できないしで，全体として本当に改善するのか確信がなったのでやる気が出なかったところはある。
• ビームサーチ。使えるタイプの問題なのかなと思ったけど，どういう探索木を考えればいいのかよくわからなかった。そもそもビームサーチを使ったことがないので勝手がわからないというのもある。
• この問題自体はかなり複雑だけど，適当に問題を単純化したら厳密解が出て，そこから始めてうまく補正したらいい解が作れないかとちらっと思った。そこまでアルゴリズム力がないので詳しく検討せず。

感想

終わってみると，貪欲法で4497が出たあたりから先は問題の特性をうまく捉えて利用するという意味で本質的にいい改善はできなかったように思う。改善できるとしたら納期遅れペナルティを減らすことなんだろうと思ったけどどうすればそれがうまくできるのかわからなかった。

後半でいろいろ細かいことを試せたのはそれなりに勉強になったし悪くはなかったと思う一方で，根拠があるのかないのかわからない思いつきをいろいろ試していただけで意味のある洞察が新しく得られたということはなかったようにも感じる。後者の意味では後半の試行錯誤を振り返ると何をやっていたんだろうなという気もする。

二分探索

二分探索は，値の探索に使うという認識が一般的だと思いますが，実際にはもっと守備範囲が広いです。ということでなるべく一般的な形で書くとどうなるのかを整理した話を書いてみることにしました。why3 で書いて正しいことを検証してみたらけっこうすっきり理解できた気がします。

int 上の述語 f があるとします。f を真にする a と偽にする b がひとつずつわかっていて，a < b であるとしましょう（requires のところ）。そうすると，f x だが f (x+1) ではない x を求めることができる（ensures のところ，result が戻り値），というのが関数の仕様です。

中身はまあ普通の二分探索なのですが，上限 ub は必ず f を満たさないように，下限 lb は必ず f を満たすようにするとわかりやすくて不変条件が簡単に書けます。

ソートされた列 A から値 v のインデックスを求めるよくある二分探索は，f x として A[x] <= v をとった場合になります。

ちなみにコード中では f に特に条件を付けていませんが，真偽が頻繁に入れ替わるような述語に対して使うケースはあまり見た記憶がありません。ある値を境にしてそれより下で真，上で偽（あるいはその逆）になる述語を考えて，その境界の値を求めるのに使うことが多いです。また a, b は自分で与えないといけませんが，たいてい自明な上界と下界があります。

上のコードが正しいことのチェックは，例えば手元の環境では why3 prove -P cvc4 binsearch.mlw を実行すると

binsearch.mlw BinSearch WP_parameter binsearch : Valid (0.03.s)

と出て，正しいことが自動証明できました。int の長さが限られている言語だと足し算がオーバーフローした場合に正しく動かない気がしますが，そこまではチェックしてないようです。

今回は整数上でやりましたが，実数上でも適当なεに対して f x だが f (x+ε) ではない x を求める，のような形で書けるでしょう（たぶん正確にはちょっと違う）。