AtCoder1600点
AtCoder
AGC-F
数え上げ問題
操作後の結果の数え上げ
操作
条件の言い換え
二項係数
DP
区間分割型ナップサックDP
探索順序を工夫して解く
選択肢が広い方か狭い方から決めていく
トポロジカルソートの数え上げ
挿入DP
DP高速化
DP高速化:累積和
AtCoder1600点
ダブルカウントを防ぐ場合分け
操作によって作れるものの集合を考える(判定関数を考える)
DP状態削減テク:全部分集合でなく個数のみ持つ
銅色diff
高度典型
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
文字列
場合分け
Greedy
DP
辞書順
DP値:文字列
テク:区間ごとに分割する
AGC-E
AtCoder
AtCoder1600点
prefixとsuffix
赤色diff
Greedy:辞書順最小を求める
こういうのちゃんと解き切れるようになりたい... なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう... 問題へのリンク 問題概要 N 個の 'a' …