Hatena::ブログ(Diary)

merom686の日記 このページをアンテナに追加 RSSフィード

2018-03-10

第2回 RCO日本橋ハーフマラソン 本戦 (オープン)

4時間でABの2問。マラソンとしては極端に短い時間だが、各問で考察と実装に1時間かけられるので、最低限のことはできる。珍しく有効に時間を使えたので各提出にコメントを付ける。

A

A問題は、壁が多くなるほど最短経路長は長くなるが、分断されたり出現できなかったりのデメリットも出てくるという問題(それがわかるまでに7分が経過していた)。

さて、まずは自明解。今回は自明解が簡単そうだったのでやってみた。ちゃんと他の人と同じ点数になっていることを順位表で確認。出力の形式が合ってるかなどを確かめられるので、むしろ時間の節約になると思う。

A

タテに棒を引いてみる。下に1マスだけ空きを作り、分断を避ける。ちゃんと得点は伸びてくれたが、上位との差はずいぶん大きい。とりあえずBへ。

B

B問題。問題文がやたら難しそうだが、背景を無視して読んでいくとなんとなくわかってくる。文字列のどこからスタートして作った7文字かを当てればいいようだ。

とりあえず自明解。位置を常に0と推定する。インタラクティブなので、とりあえずACを取っておくのは大きい。WAになってからデバッグしても原因の切り分けができない。

B

順位表を見るとなんか厳密解っぽい数字が並んでいる。言われてみればできそうなので、それを目指してみる。Dを1.0に設定する。

全体を7文字毎の'z'で区切り、'a'から'a'+15までを使った16進法で識別する。繰り上がりが生じるような境界でもたぶん大丈夫というところまで考えたが、そもそもそれが行けるなら全探索でも行ける。O(N*Q)はまあ15秒なので通る(当時10億かと思っていたがよく見ると1億だそりゃ通る)(Mは定数倍みたいな感じで)。

実装して提出したが、WA。ここでテスターをダウンロード。この前のマラソンでjavacにパスを通したので、わりと簡単に使える。<, >, & などを駆使してコマンドを書く。実行すると、WAの原因は出力した文字列の長さが合ってないことだった。ダメな理由や実行時間まで出してくれてすごく親切だ。

B

バグを修正。文字列を見るときにループする問題設定なので、文字列を2回繰り返してそこから検索するようにしていた。それをそのまま渡してたのでWAだったのだ。ところが、そこを修正してもまだエラーが出る。余分に書き込んでたりしてなんか酷いコードだった。今思えば2回分をいっぺんに作らずs=s+s;みたいにしてもよかった。

ローカルでテストできるのは実にいい。無事ACし、300000点を得た。順位表を見るとより高い点数の人もいて、そこでやっと問題の趣旨を理解した。Dを大きくすると点数が増えるけど、そうすると位置が当てづらくなるってことね(超絶今更)。

B

難しすぎると思ったので、無理矢理にでも今までと同じように検索するすることを考えた。最初は、aaaaaaabbbbbbbcccccccのようにすることを考えたが、aaahhhhというクエリから位置を知る簡潔な方法を思いつかない。よく考えるとそもそも精度が大したことない(そのaがどのaかわからない)。ということでランダム文字列に逃げた。

実行時間制限15秒に対し、直前の提出が168msなので、時間には余裕がある。クエリの文字列の各文字は必ず順に元の文字列に含まれるので、それを7*10文字くらいまで全部探索。

Dの値は適当に手で調整して2.7(テスターほんとにありがたい)。あと、連続して同じ文字が出ないようにして、手元のテストでスコアが上がったので採用した。テスターがあるので順当に点数を伸ばしてAC。ここまで2時間強で、既にBが形になっている。次はAだ。

A

妖精の位置を使っていく。壁を消すことはとりあえず考えないことにする。妖精の出入りを邪魔せず分断もないなら、壁は多いほうがいい。そのような置き方が存在しそうか、サンプル入力で調べた。テスターを動かすときcerrで画面に出力できる。

ただ、害にならない場所へ壁を設置しても点数は伸びない。スコアは最短経路長の2乗なので、多くの犠牲を払ってでも距離を伸ばしたほうがいい(分断にだけ気をつけて、一部妖精の出入りができないのは気にしない)。まず思いつくのはうずまきだが、左右にこう反復横跳び?じゃばらスイッチバック?みたいにするので悪くなさそう。それで実装したが、ナナメを思いついた。

ナナメはすごい。なぜか空マスの割合が多くなり、しかもそれがそのまま道の長さにつながっている。ナナメで実装はやや複雑になったが、壁は中央から作っていったほうがいいと思っていたのを自然に実装できた。得点も飛躍的に伸びた。

A

少し改良。壁の価値は中央ほど高いので、端っこで妖精の出入り口となっている場所は壁作成をスキップする(やっと妖精の位置を使った)。

A

どのくらいの時間で壁を作り終わるか調べたらけっこう早かったので、余った時間は妖精の出入りを助けることにする。出口と入り口の片方だけが壁のときに、そのターンだけ壁を取り除く(次のターンで修復)。

ここでまさかのCE。

A

普段はVisual C++をそのまま使っているが、カスタムビルドMinGW-w64のGCCに切り替えられるようにもしてある。調べると、gotoと変数宣言のアレね。エラーを再現させ、修正して通ることを確認し提出、AC。CEの場合は5分間待たなくてもいいようだ。

A

更に改良。一時的に壁を除く機能を付けたことで、将来妖精が出現する場所に壁を作るデメリットが小さくなっていることに気づいた。壁作成スキップの閾値をそのように変化させてスコアが伸びた。2ターンかけて出入り口の壁を除くのはボツ。

ここまで来たら、壁の形を左右反転とか、自明にスコアを伸ばせる方法を試したくなるが、もう時間はない。Aでやれることはないと判断してBへ。

B

クエリでもらう文字列の最初の文字を見つけた場所を推定値として出力していたが、実際は何文字かスキップしてる可能性も高いので、少し戻した値を出力すべきだった。また、このミスはDが大きいときほど影響が出るので、この修正によりDの最適値はより大きくなったはず。テスターを使い適当に手で調整して提出。スコアがけっこう伸びた。終了8分前まで意味のある提出ができて、久しぶりに(短時間だけど)マラソンを楽しめた。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/merom686/20180310/1520703903