AtCoder Beginner Contest 032

 バグが取れない。

結果

 286/400 49:59(1) 148位相当


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

A: 高橋君と青木君の好きな数 - AtCoder Beginner Contest 032 | AtCoder

 2:26(AC)
 GCDを求めてから…ってやってると時間がかかりそうだったので、単純にnからインクリメントして検証していった。AもBも制約が緩いので余裕で間に合う。

B: 高橋君とパスワード - AtCoder Beginner Contest 032 | AtCoder

 5:08(WA)44:59(AC)
 部分文字列をsetに突っ込んでいって、setの大きさが答え。ループの終了条件を間違えてWA。

C: 列 - AtCoder Beginner Contest 032 | AtCoder

 15:45(WA, 20/100)55:32(WA)57:43(WA)64:53(WA)66:52(WA)
 なんでバグ取れないんだろう…。
 基本方針は尺取り法。rを増やした時に、[l, r)間の積がKを超えたら、lをKを超えないところまで引っ張って来る感じ。オーバーフローしてるのかとも思ったけど、Kがせいぜい1e9なので、せいぜい1e18にしかならず、long longなら問題ないはずなんだけど、うーん。
 …とか思ってた時期も僕にありました。なんで終わった後にifをwhileを間違えてることに気づくかなぁ…やってらんない…。
 というかifとwhile間違えて20点取れるテストケースガバガバすぎない?ちょっと面白い(面白くない)。

D: ナップサック問題 - AtCoder Beginner Contest 032 | AtCoder

 43:19(WA, 66/100)
 典型問題らしきもの。
 とりあえず部分点それぞれに対して解き方を構築していく。イメージはICPC2017国内予選D問題に近い。
 N<=200、max(v[i])<=1000の時、ある価値を実現する最小の重みを更新していく。
 N<=200、max(w[i])<=1000の時、ある重みで実現できる最大の価値を更新していく。
 N<=30の時はわからなかった。全探索するとO(2N)になっちゃうので間に合わないよなぁとか思ってた。実際間に合わないけど。解答例は、半分に分けた上でそれぞれ全列挙して、マージするって方針らしい。これはなるほどねって感じ。こうすると、全列挙がO(2N/2)、各パターンと統合できるパターンの検索がO(log(2N/2))で、合わせてO(2N/2log(2N/2))となるので、十分間に合う。

感想

 分割してマージっていうのは思いつかなかっただろうからいいけど、尺取りのミスはちょっと許せないかな…。意外と気づかないものっていうのはわかるけど。次は絶対にしないぞ。