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

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