AtCoder1300点
AtCoder
AGC-D
AtCoder1300点
二次元グリッド
操作
パズル
個別の要素の動きに注目する
二分探索
単調性に着目する
番兵法
天才な二分探索
順列を題材とした問題
赤色diff
ピラミッド
操作後の結果を求める問題
中央値(メディアン)に関する問題
一目見て、データ構造げーかな...と思ってしまった。そういう先入観を持つと危ない。実際は好みな考察で解ける問題だった。 問題へのリンク 問題概要 正の整数 と からなる順列が与えられる。いま、この順列を下図左のようにピラミッドの最底辺に書き込む。…
文字列
部分列
部分列DP
DP
数え上げ問題
テク:区間ごとに分割する
不変量
パリティ
操作
条件の言い換え
DP高速化
AtCoder
AtCoder1300点
AGC-E
ダブルカウントを防ぐ場合分け
操作後の結果の数え上げ
操作:2つのものを1つにマージ
銀色diff
「次の要素」へのポインタを求める
対象を一意に定める操作列を数え上げる
2 日目:AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…