過去問埋め1
気になった問題5個ずつぐらいまとめて放出する
A - Zero-Sum Ranges(AtCoder Grand Contest 023 - AtCoder)
復習のために
与えられた数列の中から総和が0となる連続した部分列を数える問題
部分和を取ってsum[j]==sum[i](i<j)ならばiからj番目で条件を満たす数列となるので
mapで数え上げる
オーバーフローに気をつけてちゃんとlonglongにすべき(n回目)
No.617 Nafmo、買い出しに行く - yukicoder
いわゆるナップサック問題
制約が甘いからbit全探索でいけるみたいだけど複雑になるとdpで解く必要がある?
>>dpでも通した。与えられる値域によってはdpが早いかも
B - 山のデータ(AtCoder Regular Contest 036 - AtCoder)
与えられた数列から条件を満たす3組の場所(s,t,u)(s≦t≦u)を見つけu-s+1の最大化
O(n^2)で通らなくて絶望してたら工夫して計算量落とすだけだった罠
もっと効率いい解法あるのかと思ったじゃん・・・?
B - 特別賞(AtCoder Regular Contest 028 - AtCoder)
数列のi番目まででk番目に小さい値を見つけて場所を取り出す(k≦i)
k番目まで見たときから遷移させればいける気がしたけどコードごちゃごちゃになりすぎてリタイア
他人の解答見たら値が必ずk以上(自明)であることを利用して後ろから見てた、天才
B - マス目と駒(AtCoder Regular Contest 038 - AtCoder)