今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題！！！ 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…

メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…

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

区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…

意外と罠にはまりやすい問題かもしれない！！！ この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…

累積和！累積和！累積和！！！ でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…