セグメント木を用いた DP 高速化！ 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…

備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …

北大セットの D 問題。人生で初めて行列木定理を使った！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。 今、このグラフにおいて連結性を保ったまま 本の辺を削除する。そしてこのとき閉路が 1 個残るので、閉路…

o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…

「戻す DP」または「FPS」で！ 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…

少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…

よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]：残…

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…

久しぶりのカッコ列の整合判定問題！！！ カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…

文字列の練習問題 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。 から文字 a, e, i, o, u をすべて取り除いて得られる文字列を出力せよ。 解法 「取り除く」という処理を書くのは面倒なので、代わりに「 の文字のうち、a, e, i, o, u 以外…