操作:1文字を変更する
ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…
差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…
操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題！ 問題へのリンク 問題概要 文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。 そのう…
ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色（整数値）がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…
この問題は、ハミング距離と呼ばれる超重要概念！ 問題へのリンク 問題概要 2 つの長さが等しい文字列 が与えられる。次の操作を繰り返して を に変更するとき、操作回数の最小値を求めよ。 操作： の 1 文字を選んで別の文字に書き換える 制約 考えたこと …
for 文のループカウンタ が偶数か奇数かに応じて処理を変える問題！ 問題へのリンク 問題概要 長さが奇数 の文字列 が与えられる。 この文字列に対して、次の操作をすることで、"IOIOIO...OI" というように "I" と "O" を繰り返す文字列にしたい。操作回数の…
今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題！！！ 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…
メビウス関数を用いた約数系包除原理を使いこなそう！ 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…
慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…
とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…
辞書順最小の教育的例題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…
意外と罠にはまりやすい問題かもしれない！！！ この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…
累積和！累積和！累積和！！！ でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…
最初スライムの色の種類が 種類かと思ってしまって、 の場合が面倒じゃないかと思ってしまった。 Colorful Slimes 2 へのリンク 問題概要 (AGC 026 A) 1〜10000 の整数からなる 要素の数列が与えられる。 数列の好きな箇所を選んで 1〜10000 のうちの好きな…
