AtCoder Beginner Contest 017

　解いてるっていうより消化みたいになってる。よくない。

結果

　201/401　17:20　158位相当

　開始時刻　2017/08/01 17:12:00　提出履歴

A: プロコン - AtCoder Beginner Contest 017 | AtCoder

　0:58(AC)

　s*e/10を3回やって足し合わせる。整数になることが保証されてるのでintでOK。

B: choku語 - AtCoder Beginner Contest 017 | AtCoder

　3:38(CE)

　これは言い訳なんですけど、CEに気づいていませんでした。まあコンテスト時間後に問題文読み間違えててCE直しても一回WAだったんですけど。

　前から順にchoku語かどうか試していけばいいだけ。

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder

　17:20(AC)

　区間…セグ木か！？って思ったけど、勉強したばかりのアルゴリズムが本当に必要かよく考えろって教えをどこかで見たので考えた。ちなみにセグ木は必要なかった。

　魔王が復活しないっていうのは、言い換えればどこか一つ選ばない区画があるということなので、各区画のスコアの重みを調べて、削って良さそう（一番スコアが小さい）場所を全スコアの和から取っ払えばOK。累積和なのでいもす法が使える。

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder

　未提出

　なんだろうなぁ…方針は立った（解説と同じだった）けど、実装はできなかった。

　とりあえずDPっぽいなぁと思ったので、30点でも取ろうかとDPを考える。i番目のサプリを食べる時、f[j]=f[i](j<i)となる最大のjからi-1までの総和がdp[i]になる。ここで、jはi未満の範囲で単調に増加するだけなので、しゃくとり法が使えそうだと気づく。これで実装できれば100点…だったけど、実装できず。

　まず詰まったのは、f[i]=f[j]となるようなjが存在することを判定する方法。結局setを使った。ただ、その次、総和をうまく格納できず、これは解決できずに、あたふたしてる間に2時間が経過した。悔しい。

感想

　実装は頭でアルゴリズムがスッキリ組めてないとダメだなぁ。もっと単純明快に物を考えれるようになりたい。