atcoder.jp 解法 最小回数で到達できないといけないので，１回あたりでできるだけ先に進む必要がある． また，辞書順で最小ということは，最初の方はなるべく小さい歩数でいきたい． ということを考えると， 最初の方は控えめ→あとの方でなるべく大きく進む …

ARMERIAさんのブログが非常にわかりやすかった 問題 atcoder.jp 解法 '(':+1 ')':-1 と対応させると，適当に文字列を構成した時に累積和Sが以下を満たすようなパターンは存在するか？という問題に言い換えられる． 1.任意のindexに対してS[index]>=0 2.最終…

色々実験して性質を観察するの大事・・・ 問題 atcoder.jp 解法 とりあえず頂点数が小さい範囲でどのような向き付けができるかを見てみる． すると任意の２頂点u,vに対して u→vの向きづけがあるならば，c[u]>=c[v] が成り立っていることがわかる． あとは，…

問題 atcoder.jp 解法 問題のタイトル通りナップザック問題を考える． dp[i][j]:i番目までの要素までを用いた部分集合Sを考えたとき，総和がjになるようなSの部分集合の数 とすると，dp[n][s]が答えとなる． すると，遷移としては以下が考えられる． （要素a…