hogecoder

tsutaj 競技プログラミングの記録

HACK TO THE FUTURE 2022 予選でやったこと

競プロ (マラソン)

AHC でレートがつくようになってから、マラソンにも挑戦しているこの頃です。今回のコンテストは初めて初日からフル参加できました。せっかくなので、予選でやったことを共有していこうと思います。

atcoder.jp

基本的に時系列順に書いていますが、記事の後半には使った技術・ツールの説明も載せています。

コンテスト中にやったこと

このセクションだけ、文体はですます調にしていません。

1 日目 (11 月 3 日: 81084 点)

深夜に問題文を見始めた。そこまで難解ではないので、問題設定の理解はすんなり。

タスクを頂点・依存関係を辺に見立ててグラフにすると、タスクの id が小さい方から大きい方へ向けて有向辺が張られているような DAG になる。

辺の張り方的に、id の小さい方から貪欲に使うと筋が良いし実装も簡単だろう、と思って実装すると 81084 点 が得られた。同じ点数を取っている人が割といたけれど、たぶん考えていたことは一緒なんじゃないかな。

2 日目 (11 月 4 日: 86851 点)

1 日目の解法はチームメンバーとタスクの相性を全く考慮していないので、少し考慮するようにしてみた。

  • そのチームメンバーが過去に行ったタスクを完遂するのにかかった日数をベースに相性を考慮: 86265 点
  • 上の解法 + 参照する過去のタスクは日数の少ないものに限定する: 86617 点
    • 日数が多いとブレが大きいかもと思ったため。今思えばそこまで重要ではないかも
  • タスクにチームメンバーをマッチさせるとき、現在は選べないチームメンバーも考慮: 86851 点
    • 少し待ってあげて、相性の良いチームメンバーとマッチさせたほうが良くなるかも？という仮説のもと実施

ちまちま改変してこの日は終了

3 日目 (11 月 5 日: 88561 点)

チームメンバーとタスクの相性を「過去のタスクの情報ベース」で決めてはいたものの、各チームメンバーの能力値を推定する機構はまだ入っていなかった。能力値を推定し、それをもとに相性を計算する方針に転換しようと試みた。

  • 日数が十分少ないタスクのみを参照し、各チームメンバーの能力を max(過去に行ったタスクで必要となる能力値) と決めて推定: 88045 点
  • ここから少し迷走・・・直感を働かせていろいろな推定方法を試してみたがどれもパッとせず、時間だけが過ぎた
  • あまりにも何も分からないのでとりあえず 10 万ケースぶん回してデータの特性と得点の傾向でも見ることにした。直感的には「能力パラメータ数 K」と「依存関係数 R」が大きくなればなるほど難しい問題に思えるが、具体的にどれくらい難しくなるかを見てみた
    • なんとなく予想していた通り線形に難しくなっていそうだった。ただ K, R が似通っている場合でも分散がそこそこあるように見えて、ここをなんとかしないといけないんだろうなという気がした
  • 推定したものが大きく間違っていた場合にペナルティを設けるべきでは？と思い、ペナルティの概念をつけると少し上がって 88561 点

4 日目 (11 月 6 日: 90839 点)

あるチームメンバーについて、タスクとの相性計算の際に使っていたデータは「過去のタスクの情報群にある代表値 (max とか)」であり、言ってしまえばたくさんデータはあるのに実際に参照しているものはごく限られた範囲のものでしかなかった。全てのデータを有効に使って推定できないか考えた。

  • あるチームメンバーが N 個のタスクを過去に行っていたとする。 i 番目に行ったタスクの j 番目の能力パラメータ値が d _ {i, j} で、チームメンバーの j 番目の能力パラメータ値 (推定) が s _ j であるとする。また、 i 番目のタスクを完遂するのにかかった日数を a _ i とする。
  • 推定値 \mathbf{s} = \left( s _ 1, \ldots, s _ K \right) がどれくらい良いものであるかを示す「評価値 V 」を、 V = \sum _ {i=1}^{N} \left| a _ i - \sum _ {j=1}^{K} \max \left( 0, d _ {i, j} - s _ j \right) \right| と定める
    • 数式にすると仰々しいですが、結局「推定値をもとに日数を計算したとき、実際の日数とどれくらいずれているか」の合計を求めています。ずれは少ないほど良いので、評価値が低くなればなるほど価値があります。
  • 評価値が良い状態になる (値が低くなる) よう、山登り法で \mathbf{s} を動かす。近傍は、能力値をどれか 1 つ選んで ±v (v は最大 5 くらい) するというシンプルなもの
  • 提出結果: 90839 点 (ここでやっと 9 万点に到達！)

正直、山登り法だとそこまで精度は良くならなくて焼きなまし勝負になるかな、と思っていましたが、山登りの時点ですでにいい感じに推定が出来ていたのでびっくり。

5 日目 (11 月 7 日: 92439 点)

4 日目に実装したものを焼きなまし法で実装しようということで、診断人さんのブログを参考にしながら温度などを調整しつつコードを直した。

shindannin.hatenadiary.com

山登り法よりも少し良い解が得られるようになったので提出してみると、91308 点 が得られた。

もうすこし大きな得点アップをしたいが難しいな寝るか、と思ったそのとき、評価関数をいじると良くなるのではないか？とひらめいた。具体的に言うと、各タスクについての相性の誤差は線形に評価値に反映されていたが、誤差の二乗の和をとってそれを評価値としたらどうかということだった。

これはつまり、前述の式を V = \sum _ {i=1}^{N} \left( a _ i - \sum _ {j=1}^{K} \max \left( 0, d _ {i, j} - s _ j \right) \right) ^ 2 に変化させるということ。そもそも推定値というのは、どのタスクを持ってきたとしても日数がそこそこ合っているようにするべきで、そうしたいのならば線形和よりも二乗和のほうが適していそうだった。

コストをそのように直して、ついでに焼きなましのステップ数も増やして提出すると 92439 点 が得られた、かなり伸びた！

ただ、ステップ数の変更を適当にやりすぎて 2700ms くらい (タイマー仕込んでいないので 3sec で終わる保証がどこにもない) の実行時間になってしまったのでそこは反省。まだチューニング段階でもないけれど、この辺をちゃんとやるならタイマーし込んだりプロファイル取ったりしないと厳しそうだなと思った。

6 日目 (11 月 8 日: 92662 点)

昨日書いたものは実行時間があやしかったのでどうにか速くならないかなと思ってコードを見たところ、その日に仕事を終えていないチームメンバーについても能力値更新の処理が走っていて、これは明らかに無駄なので直すと爆速になった。乱数を使うタイミングが変化するので点数も若干変化して 92662 点 が得られた (手法を改善しているわけではないのでたまたま上がっただけ)。300ms を切るようになったので大丈夫そう。

さらなる改善をしようと思っていたが、この日は時間があまり取れずここで終わり。

7 日目 (11 月 9 日: 93891 点)

さて、実行結果をビジュアライザの estimation gap (推定日数と実際の日数との誤差) で見ると、終盤には推定が結構うまくいってそうだった。以下の画像は seed = 0 の終盤のもの。

なので、今後は能力値推定の機構ではなく以下を詰めるべきかなと思った。

  • 推定がうまくいくまでに必要なターン数を少なくする (できるだけ早い段階でビジュアライザが緑一色になってほしい)
  • タスクの割り振りを真面目に考える
    • 誰に割り振るか
    • どういう順番で割り振るか

推定に関しては中盤でもそこそこうまくいっていて、ここに手を加えるのは急務ではなさそうだった。なので、タスクの割り振りのほうを気にすることにした。

依存関係を無視して、まだ引き取り先が決まっていないタスクをチームメンバーに配分するような山登り法をまず試してみたが、これが全然うまく行かない・・・コスト関数が悪そうではあるけれどどうすると良くなるかすぐにはわからなかった。

仕方ない、寝るか・・・と思ったそのとき、「簡単すぎるタスクは他の人にあげる」のを前日までのコードに実装するとどうなるだろう？とふと気になった。能力高めのチームメンバーに簡単なタスクが割り当てられることがたまにあったが、これは無駄そうだったからだ。数行書き加えるとかなりスコアが良くなり、93891 点 になった。なんとか進捗が出てよかった。(ちなみにここの対応はバグらせていたが、バグっていたほうが点数が高かった。何も分からん)

8 日目 (11 月 10 日: 95480 点)

これまでのタスクの割り振りは、「それを誰かに割り当てたときの評価値 (= 日数) をそれぞれ計算し、最も少なく済みそうな人に貪欲に割り当てる」というものだった。

ところで、これはまだ改良の余地があった。日数が少なく済むかどうかという観点に加えて「スキルを無駄遣いしていないか」も見るようにした。

例えば \mathbf{d} = \left( 3, 1, 4 \right) のとき、あるチームメンバー \mathbf{s _ 1} = \left( 10, 0, 7 \right) と、もう一人のチームメンバー \mathbf{s _ 2} = \left( 4, 1, 3 \right) のどちらに割り当てればよいかを考えてみる。日数を計算するとわかるがどちらも 1 日で終わる (ノイズ r は無視している) ので、その観点だけでみると両者に差はない。しかし、前者のほうがスキルがオーバーキル気味なので、せっかく持っているスキルを無駄にしてしまう。後に来る別のタスクのことを考えると、どちらかといえば後者に割り当てたいところだ。

なので、評価値を (推定日数) + (スキルを無駄にしている度合い) とした。日数が延びるほうが問題になりそうなので、推定日数の方を比率重めにしてある。ちなみに比率を同じにすると 1 日目の貪欲にすら勝てないらしく、根拠を持ってパラメータを決める重要さを痛感した。 今までのコードを少しいじるだけで実装でき、これで 95480 点 が得られた。根拠があるとはいえ、こんな簡単な改変でスコアがかなり上がるのか・・・となった。何も分からん。やはりタスク配分を考えるほうに注力したほうが良さげなのかな。

9 日目 (11 月 11 日: 97042 点)

ソースコードにはいくつか謎ヒューリスティックがあって、なぜこれをいれると点数が上がるのか理解できない部分があった。昨日にいくつか変更したし、試しに謎パートを消したらどうなるかなと思って試したらスコアが伸びて 96524 点 になった (え？)

謎パートのひとつとして、「簡単すぎるタスクはスキップする (のをバグらせたもの)」があった。バグを取って実装するとスコアが下がるのだが、特定のケースには効くのではないかと思い、適用前後で 5000 ケースを試して比較した。

「簡単すぎるタスクはスキップ」を入れたほうが点数が良くなるものが青色で、そうでなければ赤色になる。どうやら依存関係数 R が少ないときは有効らしい。これは入力で与えられる変数なので簡単に分岐できる。書いてみると 96638 点 になって微増。

ヒートマップでいろいろ捗りそうだったので、作っておいてお蔵入りになっていたタスクの評価関数も見てみることに。すると、依存関係数が少ないときは評価関数を有効にしたほうがよさそうなことがわかった。図で見ると効果が一目瞭然になっていた。

書き換えたところ 97042 点 になった。かなり伸びてうれしい、データの分析って大事・・・！

10 日目 (11 月 12 日: 97050 点)

7 日目に挑戦した「タスク割り当ての焼きなまし」を再挑戦してみた。

前回挑戦したときは依存関係を無視した状態で行っていたので、さすがにこれが良くなかったのかなと思い、依存関係を考慮しつつ焼きなましをするやつを書いた。しかしこれも全然うまく行かず、見てみると近傍のとり方に苦労しているようだった (近傍を取った結果依存関係を満たさなければ無視していたが、無視される割合が高かった)

結局この日は手法検討に失敗したので、前日のコードを少しパラメータ調整して 97050 点を得た。冒険に出たとはいえ、1 日の改善幅が 8 点なのはかなり痛い・・・

11 日目 (11 月 13 日: 98034 点)

さすがにタスク割り当ての焼きなましはもう諦めて、他で改善できるところを探した。

ヒートマップを見ることで改善できたのは依存関係が少ない場合のみだったので、多い場合になにか出来ないかを考えることにした。できるだけシンプルで効果のありそうなものを考察すると、「そのタスクをこなした後にしかできないタスクの数」に着目するのが良いのではないかとなった。そのようなタスク数が多いようなタスクから貪欲に選んでいくことで、あとあと選択の幅が広がることを期待した。

実際にこれを実装するとかなり良くなり、98034 点が得られた。進捗出てよかった。

多くのケースで効きそうなパラメータ調整をいろいろやって、コンテスト終了。このへんは pretest では効果が分からないので少しこわいところ。

最終提出を 5000 ケース回したときの得点分布は以下のようになりました。

使った技術・ツール

基本的には以下の流れで作業していました。ビジュアライザ以外は極力ターミナルで行えるようにしました。

  • デバッグ用・リリース用のシェルスクリプトを叩いてスコアを手元で確認する
    • assert など、処理のチェックを担う文はデバッグモードでのみ有効
    • 単一のシェルスクリプトで テストケース作成・実行・実行結果データ群の可視化 を全部やる (中で Python スクリプトを呼んだりしている)
    • 50 ケースだと心もとないので、1000 ケースを 4 並列で実行して評価
  • 提出したくなったらコマンドを叩いて提出する
    • online-judge-tools/oj を使いました

github.com

作業している中で便利だったものを紹介します (よく知られたものが多いです)

並列実行 (Python の multiprocessing)

大量のケースを実行して評価するときには、早く終わらせるために並列実行が欠かせません。Python では並列実行ライブラリ multiprocessing が用意されているので、使い方をいろいろ調べて手元の PC で並列実行していました。

ちなみに、プログレスバーを表示するライブラリ tqdm は並列時でも使えるようで、pool.map() の代わりに、ループの範囲を明示したうえで pool.imap() を使うと良いらしいです。

blog.imind.jp

Seaborn

データのプロットに使いました。matplotlib でも良いのですが、細かく設定せずともいい感じにプロットを出してくれるので、手軽に可視化するにはおすすめです。

今回特に役立ったのは、上でも何度か紹介しているように、2 手法比較のヒートマップです。合計を見るだけでは見逃してしまうような改善を見ることができるのでとても助かりました。

試してみたもののあまり役立たなかったものは、スコアをバイオリン図でグラフにしたものや、入力グラフの次数分布・タスクの処理日数分布などです。(あくまで、自分視点で役に立たなかったに過ぎません)

Jupyter Notebook

大量のケースの中から、自分の知りたい条件に合うケースを探すのが大変だったので Jupyter Notebook で対話的にフィルタリングしました。先ほど紹介した Seaborn でのプロットもここでやりました。

手軽に WebUI 付きのアプリを作れる Streamlit も気になったのですが、今回やりたいこととは少しずれてそうだったのと、書いたことがなかったので今回は見送り。他の長期コンテスト (マラソンに限らず Kaggle とかでも) で有用な可能性はあるし、個人的に興味がある技術なので、そのうち書き方を覚えたいです。

所感

長期間のマラソン型コンテストに初日からみっちり参加したのはたぶん初めてです。見ての通り 1 日の間に出来たことはさほど多くありませんが、着実に改善を重ねていけたので良かったです。

ただ、タスク割り当てパートが最後まで貪欲頼りになってしまったのは少し残念かも。引き出しの少なさを感じました。

仕事柄、問題解決力が要求される機会がたまにあったりしますが、今回の思考プロセスを活かせたらいいなあと思います。あと早く上位の解説が見たいなー

pretest 時点で 53rd / 766 (追記: 最終順位 52nd / 744) と、自分にしては良い順位でしたが、今後マラソンがっつりやるならこれでも満足できなくなりそう (いいこと)。今後もたぶん参加します。