競プロ

AtCoderで解いた問題とか AtCoder:Autumn_A

過去問埋め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)

メモ化再帰(効率化した再帰(違ったら教えて))が使えるらしい

知らなかったので一番奥から勝敗判定つけて擬似的な再帰にした。多分再帰でよかった。