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' …