第2回 RCO日本橋ハーフマラソン 本戦
作成日：2018.03.10
カテゴリー：競プロ 参戦記録
目次
A問題の方針
問題文
初めは壁を十字に並べただけだった。これで16887点であった。
入り組んでいた方がスコアが良くなると思ったので、下図のようなフラクタルを構成した。
妖精の始点・終点が壁のあるマスであったらその壁を消す処理を加えると、34174点であった
これまでの壁の配置では距離を稼げていなかった。
ジグザグの道を作れば良いと思ったのでそうした。すると$159371$点となった。
B問題の方針
問題文
$D=10.0$にした時に上手くいきそうな方法を初めに考え始めた。
この時、平均で10個に1個の文字が採用されるから、同じ文字を10個並べると上手く行きそうだと思った。
文字種は$a$を$0$、$z$を$25$とした時に$(26m+n)$番目は$na_m$$(mod \: 26)$の文字種を選んでいくことにした。
但し$a_m$は$13$を除く正の奇数を順に並べたものである。
開始位置の復元は、同じ文字が連続している部分を圧縮した上で文字種の値の差分を取り、$m$として$a_m$及び$2a_m$が差分として最も出てきたものをとる。
そして$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 (新しい記事)＞