Topcoder Marathon Match 96
作成日：2017.12.28
カテゴリー：競プロ 参戦記録
目次
1日目(2017.12.21)
問題文をざっくり読んで考察する。
上手く構成すれば良く、焼きなましやビームサーチは使わないように見える。
また前回参加したMM94と異なりスコアが絶対評価なので、他の人の結果から目標を立てやすい。
ローカルテストの環境を構築する。
seed値が$314$から$363$の$50$個でテストすることにする。
とりあえず正の点数を得るためのコードを書く。
しかし、ここで問題を誤読していたことに気付く。
光の位置は固定で、ワイヤだけを動かせるのかと思っていた。
順位表を見ると1位のスコアが$950k$を超えている。
当面の目標スコアを$900k$にする。
2日目(2017.12.22)
外周から上手く敷き詰めていくのが良さそうに感じる。
しかし実装が若干面倒そうなので後回しにする。
4マスからなる最小の輪を作り、そこから2つずつ付け足して輪を大きくしていくことにする。
付け足せなくなるまで続けることにする。
マスの種類はワイヤ6種類、光4種類の24種類であるから、まだ輪に組みこんでいない数を種類ごとに保持していく。
輪を構成しないマスはスコアに関係しないから、最後に適当に埋める。
実装は翌日に持ち越し。
3日目(2017.12.23)
昨日からの実装を終える。
最小の輪を中心付近に配置してみる。
ローカルで$518245.07$点を得る。
ビジュアライザを見ると上方にはあまり広がっていない。
座標の小さいものから順に見ていっているのでそれは当然とも言える。
最小の輪を配置する場所をいろいろ試したところ、右下すなわち座標が一番大きい位置が一番良いようだ。
この時のローカルスコアは$625128.99$点である。
この方針だと目標に到達しなさそうなので、昨日思いついた外周から埋める方法を試す。
とりあえず、外周に輪が作れる時にそれを構成し、それ以降はこれまで同様2つずつ付け足して大きくしていくものを実装する。
するとローカルで$894144.14$点になる。
外周を埋めていくのはうまくいきそうであると感じる。
先の方法は実行時間が高々$0.02$sec程度であったので、時間をぎりぎりまで使うことを考える。
そのためには、ランダム要素を入れて何度も繰り返すのが良さそうである。
ランダム要素として、輪を大きくできる時に実際に行う確率を$1/4$に設定することにする。
これによってスコアが$957703.76$点まで伸び、当面の目標を達成した。
この時点での1位のスコアが$975k$であったから、次の目標は$980k$にする。
本命方針である可能な限り外周から敷き詰めていくものを実装する。
これによりランダムに埋める範囲が小さくなり試行回数が増え、スコアが伸びることが期待できる。
またどの種類のマスも比較的均等に残るようにする。
これでスコアが$964350.40$点になる。
ここでTopcoderに提出しようとするが、test exampleで時間超過してしまう。
clock関数を使っているのが原因らしいので、rdtscを使うように変えようとする。
しかし、上手くいかないので翌日に持ち越し。
4日目(2017.12.24)
過去のマラソンマッチに対する提出から時間の計測方法を探す。
すると、gettimeofday関数を使えば良いということが分かったのでそうする。
提出すると暫定4位の$967195.00$点となる。
前のバージョンと比較してスコアが落ちているケースを見ると、2色しかないものである。
敷き詰めパート終了後に余っているパーツの数を見てみると、偏りがあることが分かる。
3色以上ある場合は問題ないことも一応確認する。
ということで、2色しかない場合は前のバージョンに戻すことにする。
しかし、ほとんどスコアは変わらない。
敷き詰め方をよく見たところ、少し変えるだけで偏りをなくせることに気付く。
しかもそれによって、敷き詰める時に出てしまう空きマスを半分にできる。
これをコードに反映させると、ローカルで$1.5k$ほどスコアが改善する。
5-7日目(2017.12.25-27)
敷き詰め方を変えて、空きマスが出ないようにすればスコアが上がるかもしれないと思ったのでそうする。
すると、今までずっと間違っていたのに気づかずに放置されていた箇所が顕在化する。
だが、前のバージョンでこれを直してテストしてもスコアはほとんど上がらない。
元に戻って、敷き詰め方を変えたものを$3/4$のケースで意図したとおりに動くようにしてテストする。
しかし$953127.90$点しか得られない。
個々のケースを見ると、大幅に上がるものもあればその逆もある。
また前のバージョンにおいて最後の$5$secでスコアが改善されるのは稀であることに気付いている。
そこで、前のバージョンと今のバージョンを$5$secずつ動かして良い方を取ればスコアが伸びるのではと思ったので実行する。
この時のローカルのスコアは$967662.26$点と$1k$ほどだが上がった。
敷き詰め方を変えたプログラムは$1/4$のケースが中途半端な状態である。
そこの部分を完成させ、それ単体のものと2つのバージョンを半分ずつ動かすものの両方をテストする。
前者は$961032.60$点、後者は$967983.61$点となる。
ここで後者をTopcoderに提出する。
すると$972572.78$点を得て、提出直前と同じ6位となる。
ローカル50ケースとTopcoder100ケースで結果が$5k$近くずれているのが少し怖いと感じる。
そこで、ローカルで500ケースのテストを回してみる。
スコアは$968605.23$点となり、Topcoderのとは離れている。
ここでTopcoderの環境の方が高速に動作するためであることに気付いたので、スコアの差については考えないことにする。
500ケースを個々に見ていくとスコアが悪いものがいくつかあることに気付く。
これらを調べてみるとサイズが小さいケースであることが分かる。
この時点でコンテスト終了$12h$であり、良い方法が思いつかないのでそのまま終了。
結果
システムテスト前は$972572.78$点で$8$位。
解法は以下の2つの敷き詰め方のうち良いスコアを採用するというもの。
それぞれ$4.99$secずつで動かし、真ん中付近に空いている空間を埋められなくなるまでランダムに埋めることを時間いっぱいまで繰り返す。
反省
2色の場合において、本当はまだ埋められるにもかかわらず遷移が悪く埋められないという現象が起こった。
またサイズが小さい時にスコアが悪いという現象を解消できなかった。
スコアの計算方法から、サイズが小さい時が特に重要であることに気付かなければならなかった。
アルゴリズムの方は、場合分けをなくしてコード長を短くしバグの発生を防ぐことが大事である。
だがマラソンマッチでは、与えられるそれぞれのケースで最善を尽くすために場合分けを行うべきだということに今回気付いた。
前者の考え方に慣れているので後者は意識しないと難しいし、後者の方が面倒であるから避けたくなりがちである。
期間が長い分、やる気を保つのが難しい。
特にスコアが伸び悩むとつらい。
これはどうしたら良いか分からないから、良い対策があれば教えてほしい。
＜(古い記事)
関連
Topcoder Marathon Match 96 最終結果 (新しい記事)＞
Topcoder Marathon Match 96 最終結果 (新しい記事)＞