chokudai contest 001
問題ページ
Tasks - Chokudai Contest 001 | AtCoder
唐突にマラソンがやりたくなったのでジャッジが公開されているマラソンのchokudai contest 001を試しにやってみることにした。
6:46 問題を読む グリッドゲーで操作にかかる手数をできるだけ小さくしたいらしい。
8:40 プロ各位のマラソン入門ブログを読み漁る。時間で殴る、問題の性質をちゃんと理解する、探索空間をうまくとるあたりが大事らしいことを学ぶ。とりあえず正の点数を取れるプログラムを出すことにする。1以上のマスがあったらそのマスから右下左上の順でいけるところまで行くコードを出す。0indexで出力して1回WAをもらうがとりあえずAC。541378点で202位/224相当。80万点で本番の上位50%みたいなのでとりあえずそこを目標にいろいろ試すことにする。
9:20 手元で試せるようにテストケースをつくる。本番10個らしいしそこまで偏らなさそうと思ったのでとりあえず15個用意した。いちいち実行するのはアホらしいのでpythonでまとめて実行したりそれぞれのテストケースで実行時間を測れるようにしたのをつくる。
盤面と開始するマスを決めればそのマスから一手番で取れる最長の取り方は決まる。右下左上の順で適当に探索するのからその最長の取り方に変える。サンプルを実行してみると長さ1の取り方ばかりしている。よくよく考えると1から100の均等配置で偶然並ぶ確率はだいぶ低そう。とりあえず出すだけ出す。544856点で予想通り低い。
10:30 何をしていいかよくわからなかったので有名アルゴリズムのビームサーチをとりあえず実装することにする。ビームサーチの1世代を1手番にしたりすればいいのかなあとか考える。queにvector<pair<int, int>>をつっこめばできないことはなさそう。計算量について考える。世代数×ビーム幅×遷移数とかになりそう。遷移数はO(HW)、世代数はこれまでの結果を見るに50000くらいになりそうで、1手番を選ぶのにO(HW)掛けているので大体k510^8くらいになりそう。ビーム幅kかなり小さい気がするけど大丈夫なのか…？
13:30 大きい値のマスから開始するものを先に選ぶようにすれば連続で並ぶ列ができやすいのでは?!と考えてとりあえず出す。510000点で最低記録を更新した。あとから考えると連続で並んだ列の数のどこかと同じ数があれば連続で消せるのに別の方に飛ぶのでこれが論外なのはそれはそう。
14:20 ビームサーチをしても幅が小さいと1手番で1マスしか操作できず、評価が難しい最初のほうでいいのが消えて結局いいのが残らないのではと思ったりする。焼きなましの方が向いているのか？と思ったりしたが焼きなましとビームサーチの違いもよくわからないのでうーん。
とりあえず1手番で何マスも操作できるようなのをどうやってつくるかが鍵っぽい？一回連続で並んだマスをつくればそこを何回も取れそうで連続列をつくっていくのが大事そう。(20 19 18 17 16と並んだマスをつくれば16回1手番で5マス操作ができる) 適当にやってたところで連続列はあんまりできなさそうだし連続列をうまく作ってやるのが大切そうに思える。
15:00 LISみたいなものを求めてその列に対して手番を行うを繰り返すとかを思いつく。
2日後の5:00 LISのを実装することにする。バグらせまくる。途中経過を見ると1手番で多くても6,7マスしか取っておらずそんないい影響はなさそう。
7:00 ようやく実装ができたのでとりあえず出すが572649点とそこまで上がらない。連続列をつくる方針は良いと思うのでもっと長い連続列をつくれるような貪欲を書いてみることにする。途中で小さい数が来ると短い列になってしまいそうなのでできるだけ大きい数の方向に進んでいくような列をつくってその列に対して操作を行うとした。
8:35 バグらせつつようやく実装を終える。737247点で161位/224相当でようやくマシな点数を出せた。
9:00 全てのマスを始点として試して、最も長い列であったものに対して手番を行うと変えてみる。むしろスコアが下がった。
10:40 大きい数を入れると連続にするために使う手数が増え、小さい数を入れると列の長さが減る。長さNの連続列があったとき、もっとも悪い取り方をするとN*(N+1)/2手番なところをN手番で取れるのでO(N2)からO(N)への改善となることを考えると列が長い方が大事そう。
10:55 考えてても何もわからなかったので途中でつくっている列の長さだったりを表示してみる。大きい数の方に進んでいく貪欲のコードを2番、長い列を貪欲に選ぶコードを3番と呼ぶことにする。列の長さの平均は6から7くらいで予想より短かった。(10くらいはあると思っていた。)想定どおり3番が2番よりも長い列を選ぶことはできていたが全体のスコアは低い。
11:30 最初の連続列30個で手数を見てみると、3番の方が7000手近く多い。そこからの手数消費は2番よりも小さいくらいなので最初が問題そう。連続列の長さに対する手数の比率を表示してみると2番は30から40くらいなのに3番は50近くいっているものもある。つまり連続列の中に大きく外れた数が存在する…？
12:00 連続列の決定方法として差が小さい方に貪欲に進んでいくとする。（これを4番と呼ぶ） 提出すると742553点で156位/224相当。一応上がった。あとは時間を全然使ってないのでこの時間をつかって探索して連続列をもっとうまく選べないか考える。連続列の選び方でビームサーチすることにする。
12:30 ビームサーチの実装を何となく考える。BFSからちょっと変えればいいだけに思えるので実装する。
queue<state> que
while(que.size()) {
priority_queue<state> pq
// このループでビームサーチ1段分の探索をする
while(que.size()) {
top = que.top
// top の状態から遷移したのを pqに突っ込む
}
// pqの上位k個をqueに突っ込む
}
13:00 評価関数の部分をどうするか悩む。とりあえず連続列から手番の操作を生成するコードをコピーしてきて 手数/連続列の長さ を評価関数の値として返すことにする。
15:00 バグらせ続ける。pop忘れて無限ループとか評価関数で例外処理が抜けてる部分があったり色々とひどかった。
翌日の4:00 手数の操作を順番に求める必要はないので評価関数をちょっと軽くしたりして改善する。とりあえず動くようになった。スコアがむしろ落ちている。TLを無視してビーム幅を長くしてみると大してスコアが上昇しない。評価関数をただの手数に変えてみる。大してスコアは上がらない。atcoderとローカルの実行時間の比較のためにとりあえず出してみる。ローカルで7秒くらいのを出したら4.3秒しかかかっていない、atcoder優秀。ローカルの2/3くらいになるかなーといった感じ。
4:30 評価関数を手数/連続列の値の和としてみる。連続列の長さの比よりもこっちのほうがよさそう。提出すると787405点で136位/224相当でいい感じ。
6:00 評価関数をいじったり、貪欲と合わせたりいろいろしたがスコアはむしろ下がる。
7:00 ビーム幅調整とか色々するがスコアが上げられる方針が一向にみつからない。
8:00 連続列を選ぶところをビームサーチの遷移にするようなのを考える。連続列の候補を何個か貪欲で選んでそれを遷移にするようなのを考える。
10:00 実装途中にとんでもない事実に気がつく。priority_queueの中身の順序がまずいので評価値順に並んでいないのとか評価値が低い方からk個選ぶようなとんでもないコードになっている。まともに直したらビームサーチ部分がやたら時間がかかるようになってビーム幅が2になった…
提出したら805260点で121位/224相当になる。目標の80万にとりあえず届いてよかった。
感想
とりあえず80万点は届いてよかった。ただ時間かけすぎだったり連続列をつくるべきなのに気づくのが遅すぎたり色々反省。ビームサーチとか手元にジャッジ環境つくるのとか何となくマラソンの雰囲気がわかったので色々やっていきたい。コードの管理がひどかったのでこれからはちゃんとgitで管理したい。
解説記事を読んで復習しようとしたがtopcoderのMMが始まってしまったのでそっちが一区切りついたら復習して追記するつもり。
