誤読をしない

サンプルを試す

模擬国内予選2017参加記

模擬国内予選2017にチームintuition(自分、nyashiki君(@sizensuN)、おかゆ君(@okayunonaha))として参加しました。

4完以上目標で挑んだのですが、結果はABCの3完で50位でした。

 

 

以下当日の記録

 

開始前

研究室の合宿で栃木にいたので、模擬国内に間に合うかは微妙だったが、なんとか30分前に着く

1時間開始が延長されたので、のんびり待つ

 

開始(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くらい

30分延長される。

おかゆ君が他の問題を考察してたみたいなので行けそうな問題があるか聞いてみるが、厳しそうなのでDと心中することを決心する

 

3:10

ここら辺でシミュレータ内で探索している区間の関数が単峰で、実装した二分探索では上手く行かなさそうな雰囲気を感じる

自分「これ冷静に考えたら3分探索とかいうのをしなければいけないのでは?」

nyashiki君「でもそれ書いたことないんだよね」

自分「同じく」

それっぽく色々いじってみるがWAを量産してむなしく終了

 

 

コンテスト後

次の日にDと再び格闘してみたが、どうしてもdiffファイルと一つだけ答えが合わない

大人しくkomiyamさんの記事を見て実装したところ、上手く行った(この過程で尺取り法を思いついたので試したがそちらでもACしたので辛くなった)

 

d.hatena.ne.jp

 

反省

Dで問題文の見落としによって最後の詰めまでたどり着くのに結構時間かかったので、本当に気を付けたい。(そうすればもしかしたら尺取り法は思いつけたかもしれない)

後ライブラリを印刷し損ねたので本番は忘れないようにしたい(戒め)

 

 

 

Dのソースコード

二分探索

gist.github.com

 

尺取り法

gist.github.com