ハーフマラソンの立ち回り
はじめに
主に自分がハーフマラソンでやっていることを書きます．あんまり技術的なことは書きません． 技術的なことは色んな人が書いてるし，説明できるほど自分はちゃんと理解していません．どちらかというと事故を避けるための立ち回りを中心に書きます．
ハーフマラソン
競技プログラミングの一種にマラソンというものがあります．出された問題のスコアを期間内にできるだけ上げていくものです，期間はだいたい1〜2週間です．ハーフマラソンはそのマラソンをもっと短期間でやるものです．具体的には4時間(日本橋ハーフマラソン)や8時間(HTTF)などです．
各時間でやること
開始
最初はゆっくり問題文を読みます．問題を勘違いすると致命的なので10〜15分ぐらいかけて問題を噛み砕いて方針を固めます．このときコードは書きません．ツイッターで誰かがマラソンは最初はコードを書かずに考察したほうがいいといっていたのを参考にしています．ただし4時間マラソンは結構時間ギリギリなので，方針固めと次のクラスづくりの工程を同時に行ったりします．
問題理解後
まずは問題内に出てくるオブジェクトのクラスを作ります．例えばHTTF2019の問題なら，討伐依頼とスキルと行動です．あとはスコア計算などの不変な計算．使う定数などを書いておきます． これら基礎となる部分は方針にかかわらず無駄にならないので．最初に作ると間違った方針を立てててもリカバリーしやすいです．
基礎作成後
まずは入力を受け取り．自明に得点を取れるコードを書きます．そういうのが難しい問題もありますが．とりあえず一番最初に思いついて実装が簡単なやつです．だいたい貪欲になります．他の人も同じようなことをやっているはずなので．これを提出すると順位表で得点が横並びになります．ならなかったら作った基礎などのバグを疑ったほうがいいです．このときのスコアは後の方針に対するベンチマークにもなります．
貪欲作成後
このあたりから問題によっていろいろ変わります．技術的な話も出てくるのでそのあたりは他の人に任せます． ここでは実装中に気をつけてることを書きます．
高速化は終盤までしない
高速化は大体コードの可読性が下がります．バグも埋め込みやすくなりますし，使い回しもしにくくなります．今の方針がだめだったり新しい方針を思いついたときに，高速化部分が無駄になったり，書き換えが煩雑になったりして余計バグを埋め込んでしまったりしてしまいます．本当に最後に特にやることもなくなったときにしています．
お知らせには気をつける
問題を作っているのも人間です．いくら気をつけててもミスをします．テスターだったりビジュアライザだったり問題文だったりがバグっていることがあります．おかしいと思ったら質問の欄をみたり公式のツイッターを見たりします(動き出しが遅いので，自分が気になったことはだいたい先に質問されてて質問をしたことはない)．Atcoderの新仕様なら全体公開の質問・解答がされた場合わかるようになってたと思います(質問タブの横に数字がでた気がする)．重要な修正があったりするので気をつけてます．
最後の最後は作法を無視する
これはまあ自然にそうなるんですが，残り10分で実装しようとしてるときとかは可読性とかプログラミングの作法とか全部無視して書きます．変数の使い回しとかグローバル変数かコピペとか．ギリギリになると読み返すこともまず無いし．バグらせたらその時点でほぼ詰みです．
おわりに
以上です．もしかしたら誰かの参考になるかなという気持ちもありますが，主に自分のハーフマラソンでの行動を整理するために書きました． もちろんその人に会う立ち回りというものがあるので，一つの参考として見てもらえればありがたいです．急ぐと頭が回らなくなる人には合ってると思います．(自分がそうです)
RCOハーフマラソン2017
予選
貪欲。
本戦
A問題
本番
sellコマンドの最初にnを出力するのを見てなくて20分ぐらい取られた。
- 30以上買ってくれる客に売れるなら売る(sell)
- タンクの容量が合計40以下なら一番小さいのから取り替える(change)
- まだ石油入れてないタンクに石油入れる(fill)
- 上記をすべてやっていて、単価30以下か、現在のタンクで支払えない客なら帰ってもらう(pass)
っていうのをifelseで書いたら、その時点で5位ぐらいだったのでそれ以降ほぼ手を付けなかった。
最後に売る客のしきい値を25に変えたら60000ぐらい上がったのでそれだけ。 現在のタンクの組み合わせで実現できる数が少ないとき（同じ容量のタンクばっかりとか）にやたらパスしてたので、その時もchangeするようにしたかったけど時間足りず。 最終 6315976点 13位
反省
解説で聞いた、売るときにどのタンクから売るかを考慮に入れてなかった。 sellでハマってたときにテスターのバグとすら思っていた（テスターのデバック上ではnにあたる数しか表示されず、手入力で入力を与えたら普通に出力されたため）ので、出力の形式はちゃんと読もう。（というか解答側が自由に個数指定して出力する問題で個数出力し忘れるの何回もやってる気がする……。）
B問題
本番
方針が定まらずとりあえず貪欲書いていろいろパラメータいじって試してた。 この時「ターン数かけてきっちり揃えに行くより数百ターンで雑に近づけた方がいい」と思ってしまって方針を間違えた。（移動不可な場所を壁として経路探索してたのでターン数かけると時間が足りなくなってたのも原因）
最終的に、 ゴールの位置が外側の車から動かして
- ゴールへの経路があるものはその経路に従って進む。
- 経路が無いものは
- 2割の確率で壁を無視してゴールにまっすぐ向かう。
- 8割の確率でランダムに動く。
というふうなのを300ターン行った。
最終 8918点 22位
反省
ランダムに動くときに動ける方向のみから選ぶだけで点数もっと上がった気がする。
→実際に実装してランダム移動する確率5割ぐらいにしたら2倍ぐらい点数上がった。
全体
最終順位：13＋22＝35 で全体13位 学生8位 社会人のおこぼれで賞金をもらえた。 プロコンで入賞できんたのが初めてなので嬉しい。 雑に点数が取れる方針を立てる能力は高いので、自分に有利なコンテストだった。（テスターなどがJavaで提供されてるのも有利）
RCO紹介
競プロer向けにわかりやすい企業紹介だった。 17時出社が魅力的だった。
懇親会・解説
B問題のビジュアライザを用いた解説は見ててとてもおもしろかった。 ピザとチキンだけだったので胃に重かった。 8時に新幹線だったので早退した。
反省
コミュ力。
終わりに
4時間ぶっ続けで考えるのは疲れるけど楽しい。問題も面白かったので、またあったら参加したい。
その他
・マウスを忘れたので近場でマウスを買った。
・朝7時起きは辛い。
・A問題のテスターはEclipseのMainファイルと同じ場所置いてテスターのmainメソッドに
command = “java -classpath bin Main”;
と書くとEclipse上だけでテストできて便利だった。
・B問題は出力をテキストにするためにわざわざ自作ゲームライブラリのテキスト出力クラスを使った。（絶対コマンドライン使いたくないマン）
・Eclipseに出力をファイルに書き出す機能はありそう。
■
A問題
読んだけど飛ばす
部分点Cにあると思ってた。部分点狙う。
1つか2マス移動してゴールめざす。N=8ならMODいらないかな。
ごーるする順番の数だから最大は順列で8！かな？
ゴールが妨げられる場合は2つ異常連なっててさらに移動したらゴールしちゃうとき。 つまりゴールx＝0から複数個連なるのが途中で出ちゃうとき。
xが(n-1)*2内にn個以上ロボがいるとき最初のゴールがnに制限される。 一回制限されるたびに次のnがひとつ下がっていく。コレで行く。
かんがえるちからがなくなった なにもかんがえられない
8 1 2 3 4 5 6 7 8
B問題
部分点狙いに行く
横を記憶して縦に書き出す問題。N=3の場合のみを考える。 はば優先探索でとりあえずやってみる。
部分点は取れた。charじゃなくてboolにして枝刈りしたらいけるかな。まああとで。
まとめ
脳が正常に働かなくなったので撤退。最近脳つかいすぎてたかな……。なにもかんがえられないだめだ。
AGC010
いつも通りにコンテスト中に考えてたことそのまま書いてる
A問題
偶奇の問題。足せばきは遇に遇は遇になるから木の数が偶数ならYES
AC
B問題
一周回りながら減らしていく問題。1~n足したやつで割り切れなければとりあえずNO
割り切れればその数が集会する回数。
½(n+1)n忘れてた。
集会する数をkとする。 とりあえずずらして足したやつ見る。 1234 2468 3575 1 1 1 -3 4646 2 2 -2 -2 5357 3 -1 -1 -1 12345 57468
うーんDPっぽい。でも普通にやったらメモリ持たなそう。とりあえずやる。
いやDPでも毎回N*Nあるから無理じゃね？
一番小さい数字を1～nの数字で分割する？
数字にNたしてkずつ上がってたらいいんじゃね？なんかコーナーケースありそう。 6 9 12 5 13 3 3 3 -7 -2 113 122 3 3 3 -2 -7 1 1 1 1 1 12345 34512 23451
なにもなければ次との差はk、切れ目があれば次との差は切れ目の数＊nでこれを調べればいい。
WA
オーバーフローかな……。区切りの数がkと同じか確かめるやつも入れてみた。
多分オーバーフローだった……。 AC
C問題
頂点から石を取り除く問題もう時間無いし無理そうとりあえず他の問題見る。
D問題
とりあえずこっちしてみる。数字から1引いて最大公約数で割る問題？ なんか全部から1引いて足したの2で割るクソコード投げたけどまあWA。
終了。頭の隅にちらっと出てきたやつを考えずにまっすぐ進もうとするのをやめないと……。
■
ARC068
C問題
5と6を往復させてれば最初はいける。最後に1か2がくるとどうだろう？
どっちでもそれとは逆が最後に下にくるようにすればいいだけか。なら小さい数字が厳しそう 1～6は大丈夫。
x点ちょうどだと思ってた。以上なら簡単じゃん。
提出。誤読気をつけないと……。
AC。
D問題
抜き出すカードは1枚は重なってるカードじゃないと意味ない。 残るカードはそういうカードが存在するかだけが重要。
同じカードの奇偶で調整。とりあえず1枚か2枚になるまですべての種類で減らす。 いやこれだと3344455のときが……おかしくならないな2枚あるの保証されてるからそれ選べばいい。
カードの種類＋（偶数の種類の和が奇数のとき－1）？
例で試す
4-1
7+0
例はそうっぽいとりあえずこれでいく
提出した。ちょっと怪しい。
WA。2残ったやつの消し方もっと詰める。 でもこれもうつめられなくね
案の定コードミスってた。最後の種類の数の偶数カウント漏れ。
AC。
E問題。
特定区間でのみ買える品をすべての間隔について何種類買えるか。 つまりいくつの区間に接触出来るかをすべての間隔で調べろってことかな？
脳が死んできた。
間隔がd以上ならdにはそれが必ず含まれる。 なんか数直線をいい感じにして入ったら＋出たらーして数えていく方法使えばできそう。名前忘れた。
戻ってきた。時間無いけど。
F問題
EわかんあいからFちょっと覗いた。
1は始めにいれるからあとはK-1回とN-K回それぞれ入れられてその組み合わせを割る？
つまりN-1からN-Kを選ぶ組み合わせっぽい？
誤読してた……。食べるのもどちらかから指定できるのか……。
もう一回組み合わせ計算していい感じに掛ければいけそうと思ったけどそもそも前提破綻してるじゃん。
無理そう。
終わり
なんか最後の方無駄に頑張らずに復習のために体力残しておくほうがいい気がしてきた。 誤読は多分どうしようもない。
AGC008に参加した頭が働かない人のログ
※コンテスト中に考えまとめるために書いているので人に読ませるために書いてません。誤字とか誤変換とかは後で読むように多少訂正してます。
A問題
Bを押すタイミングは始めと終わりだけっぽい。 全パターン2＊2＝4やってみるか
通った。
B問題
マスが負の値を持つことに思い至らなくて、しばらく?マークついてた。
塗る回数に制約ないから最終的にどんなふうに濡れるか考える問題っぽそう。
Kの連なりが必ず1つは出来るけどそれ以外は自由っぽい。
なんか本当にそうか分からないけどそれなら初めからN個色塗ってそれ以外＋なら黒でーなら白に塗るのを全部探索すればN*Kでいけそう
一つずらすたびに、ずらした分だけ足し引きすればNでよくない？
サンプル合わない
繰り返し回数をK-Nにしてた なぜか白く塗ったところを0ではなく符号反転して加算してた。なんで？
サンプルあった。通ると良いけど……。
通った
C問題
テトロミノみただけで面倒くさい問題っぽい感じがする。
縦は2マスだけなので同じところにずっと積んでいく感じかな
なんか飛ばしたほうがいい問題っぽそうだと思って順位表見たら赤数字沢山ついてたので一旦D読もう。
D問題
問題文が読めない
なんとなく読めた。数字IがI番目に出てくる番地が数列XのI番目の数字と同じになればいいのか
Xの順番は判定では意味なさそう。I番目にでてくるのが必要なんだからいるわ
とりあえずXで決められてる番地に数字を固定する。 Xの数字が小さい（Aの先頭に近い方から）方から順に条件満たすように前に詰める形で数字いれていけばいい？
とりあえず、これで行けそうだからこれでいく。
集中力切れてる。言い訳すると部屋が暑い。
とりあえず矛盾しないように埋めることはできたんだけど、後ろ側の0が埋まらない。残ってるので適当に埋めればいいか。
Eclipseが固まりかけた……。
－1に初期化してたとこ更新されない場合見落としててエラーなってた
後半ほとんどREとWAだった……。
REは前に詰めてたら足りなくなってXIこえちゃったとき確かめるのがきちんと判定されてなかったからっぽい。WAはしらないあと5分じゃ無理そう。（だいぶ頭働いてない）
とりあえずWAには変わった。ここから考えるのは無理そう。
半分ぐらいWAなので多分根本的なこと見落としてる。
コンテスト終了
本来ならDの最初当たりでやめてた気がするけどコレ書いてたからやめなかった気がする。書いてったほうがいいな。
集中切れてから明らかにIQが3程度まで落ちてるから集中切らさない方法が必要。
Cこっち解いてたほうが行けた気がする……。
DはIQ3状態では多分どうしようもなかった。
D解こうとしてるけど、前から埋めたことを忘れて後ろから埋めようとしてたのでまだ頭働いてない。
WAはへったけどWAが取れないしこれ以上思考が持たないので終了。
提出
http://agc008.contest.atcoder.jp/submissions/all?user_screen_name=kiki33
