第2回 RCO日本橋ハーフマラソン 本戦
作成日:2018.03.10
カテゴリー:競プロ 参戦記録
目次
A問題の方針
問題文
初めは壁を十字に並べただけだった。これで16887点であった。
入り組んでいた方がスコアが良くなると思ったので、下図のようなフラクタルを構成した。
妖精の始点・終点が壁のあるマスであったらその壁を消す処理を加えると、34174点であった
これまでの壁の配置では距離を稼げていなかった。
ジグザグの道を作れば良いと思ったのでそうした。すると159371点となった。
B問題の方針
問題文
D=10.0にした時に上手くいきそうな方法を初めに考え始めた。
この時、平均で10個に1個の文字が採用されるから、同じ文字を10個並べると上手く行きそうだと思った。
文字種はaを0、zを25とした時に(26m+n)番目はnam(mod26)の文字種を選んでいくことにした。
但しamは13を除く正の奇数を順に並べたものである。
開始位置の復元は、同じ文字が連続している部分を圧縮した上で文字種の値の差分を取り、mとしてam及び2amが差分として最も出てきたものをとる。
そしてnは、mが定まれば文字種から復元できる。
これによって371259点となる。
先の得点は、同じ文字種が並んでいるところは先頭を選んでいた。
これを同じ文字種が10個並んでいるうちの6番目を基本的に選ぶが、先頭の文字種が複数あったらより前を選ぶことにした。
さらにD=4.5にするとより良い結果が出たのでそうした。
最終的には406840点であった。
コンテスト後(結果)
A問題は159371点の44位、B問題は406840点の12位、総合は25位。
A問題はジグザグに至るまでに時間がかかりすぎた。
しかも斜めに並べることを思いつかなかった。
上位のスコアを見て、壁のマスがもっと少なくて済むことに気付くべきだった。
また、A問題は妖精を無視して壁を作り続けると172071点となった。
あまりスコアが稼げない時は壁の構築を優先すべきだったようだ。
B問題は自明な300000点を最初の方針で超えることができたのは良かった。
文字を並べたり復元したりするのが楽であるからこの方針を取ったのだが、時間制限が15秒とかなり長かったから正確に期待値を計算してみることを考えるべきだったのかもしれない。
<(古い記事) Topcoder Marathon Match 97 最終結果
Topcoder Marathon Match 99 (新しい記事)>