模擬国内予選2017参加記
模擬国内予選2017にチームintuition（自分、nyashiki君（@sizensuN）、おかゆ君（@okayunonaha））として参加しました。
４完以上目標で挑んだのですが、結果はABCの３完で50位でした。
以下当日の記録
開始前
研究室の合宿で栃木にいたので、模擬国内に間に合うかは微妙だったが、なんとか３０分前に着く
１時間開始が延長されたので、のんびり待つ
開始(0:00~)
印刷が完了するまで、nyashiki君がAを読みつつおかゆ君とBを読む
時間ごとにシミュレーションすればできそうと思いながら、AのコーディングのためにBが閉じられたのでAを読みつつnyashiki君とペアプロみたいなことをする
0:11 AをAC
問題用紙を受け取れたので、Cを読み始める
それぞれの人の最大の得点の中での最大を出せばいいのでは？と考えたが、一人しか正解出来ないパターンがある時にダメなことに気づいてぐぬぬとなる
nyashiki君がBを読み始めて、すぐ行けそうらしいので実装を始めたが、何か問題があったみたいでおかゆ君と相談しつつ進めてた模様
0:29 BをAC
何か見落としてる気がするのでCをnyashiki君にも読んでもらいつつ、自分はDを読み、おかゆ君がEを読み始める
（i(i=[0,n))の人が全て得点した時の得点の最大）-（iの人以外の「一人しか正解出来ない問題以外全てを正解できなかった時の得点」の最小） + 1でいけるのでは？と言われ、パッと証明が頭の中で出来なかったのでとりあえず反例を探す。その間nyashiki君がコーディング
なさそう＆証明も行けそうだと思ったのでペアプロに移り、二人でバグとかをデバッグする
0:57 CをAC
nyashiki君と自分がDを改めて読み始めて、これ二分探索で行けないか？とnyashiki君に言われ色々相談した結果行けそうという結論になり自分が反例を探しつつnyashiki君がコーディングする
バグったらしいので二人でデバッグしつつサンプルは合ったので入力ファイルを試し、提出
1:40くらい DをWA
出力ファイルの中身を見てみると、怒涛の-1出力でビビる
ここで、経験値の得られ方から現在倒せる敵の中で最も強い敵を倒すのではなく、最も良い経験値を得られる敵を探さないといけないことを見落としてたことに気づき、その部分を直してもらって入力ファイルを試す。
2:00くらい
今度は出力が終わらない。
シミュレータ部分の実装が毎回O(N)で最も経験値が得られるモンスターを探してることに気づき、これではO(MNlogN)で間に合わないので、二分探索で求めれば良さそうと思う。
ここからはコーディング交代で、何とか実装を終わらせるが、サンプルすら合わない
色々デバッグする過程で、パラメータの区間の最小を0ではなくs[0]にしてどの敵も倒せないパラメータ設定の場合を除いた。
これで行けるのでは?と思い提出するがWA
2:50くらい
３０分延長される。
おかゆ君が他の問題を考察してたみたいなので行けそうな問題があるか聞いてみるが、厳しそうなのでDと心中することを決心する
3:10
ここら辺でシミュレータ内で探索している区間の関数が単峰で、実装した二分探索では上手く行かなさそうな雰囲気を感じる
自分「これ冷静に考えたら３分探索とかいうのをしなければいけないのでは？」
nyashiki君「でもそれ書いたことないんだよね」
自分「同じく」
それっぽく色々いじってみるがWAを量産してむなしく終了
コンテスト後
次の日にDと再び格闘してみたが、どうしてもdiffファイルと一つだけ答えが合わない
大人しくkomiyamさんの記事を見て実装したところ、上手く行った（この過程で尺取り法を思いついたので試したがそちらでもACしたので辛くなった）
反省
Dで問題文の見落としによって最後の詰めまでたどり着くのに結構時間かかったので、本当に気を付けたい。（そうすればもしかしたら尺取り法は思いつけたかもしれない）
後ライブラリを印刷し損ねたので本番は忘れないようにしたい（戒め）
Dのソースコード
二分探索
尺取り法
Codeforces Round #406 (Div. 2): C.Berzerk
問題
解法
終点(x=0)から逆に辿って行く動的計画法。
Mortyにx=0で手番が回ってくる（つまりMortyの敗北）前の手番では、Rickによってモンスターはx=n-s[0][i](ある0<=i<k1)から遷移してきているので、その座標にRickの手番が来た時はRickの勝利である。その座標に辿り着く場合は
①その座標がスタート地点
②Mortyの手番でx=n-s[0][i]-s[1][j](ある0<=j<k2)から遷移してきた
の二通りが考えられる。
②の場合は、問題の前提から、Mortyによってモンスターがx=n-s[0][i]へ遷移するのは他の全ての手もMortyの敗北である時だけと分かる。つまり、x=n-s[0][i]-s[1][j]からのMortyによる遷移はx=n-s[0][l]（任意の0<=l<k1)のいずれかであることが保証できれば、x=n-s[0][i]-s[1][j]の座標でMortyが来た時は敗北する。ここまでを終点をx=n-s[0][i]-s[1][j]にして繰り返す。
終わったら、Rickにx=0で手番が回ってくる場合でもう一度計算をする。
確定されなかった点はLOOPになる。
ソース
参考
kimiyukiさんの実装を参考（というかそのまま）にした。
Codeforces Round #406 (Div. 1): A. Berzerk · うさぎ小屋
c++の論理否定!の代替表現のnotを初めて知った（小並感）
2016年ICPC国内予選参加記
2016年度ICPC国内予選にチーム「RINKAKU NO DANPEN」で参加して来ました。
私自身は競プロ歴が半年にも満たないレベルのひよっこで、競プロを知ったのが去年の11月、atcoderのABCをある程度真面目に取り組み始めたのが３月後半、ICPCの存在を知ってAOJと蟻本に時間を充て始めたのが５月からという経歴です。
チームは頼み込んでconf君(@confused_uec)、ふーらくたる君(@fooractal)と組ませてもらいました。
５月～前日
５月半ば辺りから同大学の別のチームの方も呼んで３時間３人で一つのPCだけで解くというICPCと同じ形式（２台持ち込んで、一人が一台に打ち込んでる間はもう一台は操作禁止みたいなこともしましたが）で毎週練習会を行っていました。チームメイト二人はICPC経験者だったので色々手取り足取り教えてもらって申し訳なさと感謝しかなかったです。
一週間前の練習会はある年度のICPCの問題セットで解いてみたり、前日は本番環境で解いてみるなど本番が近づくにつれ本番を意識した練習をしていきました。
▲色々犠牲にした結果（１万ポイント行きたかった..）
当日
リハーサルは４完２位でした（私は特に何もしていない）
当初の作戦は、まず自分がAとBを倒してる間にconf君がC以降の幾何を、ふーらくたる君がC以降の他の問題を考えるというものでした。
しかし、A問題を瞬殺できると判断したconf君がまずAを６分でAC（はやい）、その間に自分がBを見て二人がC以降を見る態勢に。
Bはアルゴリズムは割とすぐに分かったけどコーディングを始めるとプレッシャーで頭が真っ白になりバグらせてしまいました。conf君に引き分け時は一番最初にやった方がいいとの助言を頂きとりあえずサンプルのバグを片っ端から取っていってなんとか開始４６分でAC。コーナーを全く考える余裕がなかったので通ってよかった..という気持ちが大きかったです。
その後Cを１４分でconf君が解いて、D以降を残り２時間で考えるという段階で詰まってしまいました。
私はグラフと幾何の問題の経験がほとんどなかったのでそれっぽい知識が必要なさそうなDを考えて、終了１時間前頃に消せるだるまのペアの両端の差が１以内の時だけ再帰で潜って、その種類の消せるだるまのペアがなくなったら、そうでない消せるだるまのペアを最後に一度に消すという方法を思いつくも証明も説明もうまく出来ず。しかも疑似コードの実装すらどうにもならなくて、最後２０分ぐらいでconf君になんとかある程度趣旨伝えて実装を頼むもタイムアップ。
結果はABCの３完でした。
反省
まずBで詰まらせたのがダメでした。正直プレッシャーは慣れの問題と思っているのである程度仕方ない部分もあるとは思いますが..
（二番目の候補者を求める時に後でソートしてから二番目を取ればいいと聞いてマジかと思ってしまった）
次に、幾何とグラフの知識がない故にその系統の解法を聞いてもあまり理解できなかったり、Dの実装の丸投げをするなどの力不足が甚だしかったです。
チームの問題と言うよりも、まず協力体制を敷けるだけのレベル差を埋められてないことをひしひしと感じました。
感想
アジア予選へ通れなかったのがとにかく悔しいです。自分は院進はしないつもりなのでチャンスが後一回だけというのが厳しい。
後、本番が近づくにつれ問題数を積むことばかり考えて解き終わった後の別解の模索や綺麗なコードにするための見直し、また他人のコードを参考にすることをおろそかにしていってしまったので、自分のICPCが終わった今伸び伸びとしてこれらもちゃんと行っていこうと思います。
来年までにもっと鍛えて、実装力・思考力共に身に着けたいと思います（具体的には黄色くらい..行けたらいいな）
後言語能力（日本語英語問わず）
