操作
こういうの最初は手で様子を掴むようにしているのだけど、どのタイミングで PC 実験開始しようか悩む。 問題へのリンク 問題概要 整数 と 4 つの文字 が与えられる (いずれも "A" または "B") すぬけ君は文字列 を持っている。 ははじめ "AB" である。すぬけ…
すごい面白い！！ 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…
こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個ずつ) のことを指すものとする。 文字…
カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…
単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …
11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…
簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …
想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは，次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…
面白かった！！ 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます． の連続する 文字を選んで，それらをすべて 0 にす…
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
場合分けやコーナーケース回避がエグい問題！ 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…
少し手を動かせば見えてくる！ 問題へのリンク 問題概要 高橋君、中橋君、低橋君は、それぞれ整数 を持っている。 以下の操作を 回行った後の、高橋君の持っている整数から中橋君の持っている整数を引いた値を求めよ。ただし、答えの絶対値が を超える場合は…
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
最大流問題の構造についての理解を問ういい感じの問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 間の最大フロー (辺素パスの本数) について考える。 今、いくつかの辺を選んで向きを反転するこ…
どんな風に操作しようとも、毎回「左右のうちの何個選べるか」が変わらない！！ 問題へのリンク 問題概要 の順列 と、空の配列 が与えられる。これらに対して以下の操作を 回行うことで、配列 が に一致した状態にしたい。 そのような操作方法が何通りあるか…
区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…
面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…
こういう条件を言い換えながら数え上げる問題好き！ 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…
一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…
最初は文字列 を文字列 にできるかを問うつもりだった。てんぷら君のおかげで、 を真っ白にすることで、シンプルな問題になった！ 問題へのリンク 問題概要 マスがあって最初はすべて白く塗られている。ここに "RGB" のスタンプを押していく。スタンプを押す…
資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…
問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…
2 種類の操作がある系の問題！こういうのは操作の手順を単純化して考えられる場合が多い 問題へのリンク 問題概要 正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく を 倍する に を足す が 以上となってはならない…
操作が「Euclid の互除法」っぽくなっている系の問題！！！そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…
Greedy の一番簡単なパターン 問題へのリンク 問題概要 人が 1 列に並んでおり、前から 番目の人の身長は です。 それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。 条件：踏み台を込めて身長を比較した…
形式的冪級数 (FPS) を用いた「多項式としての除算」の練習に 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 がある。 は初期状態ではすべて 0 である。 に以下の一連の 回の操作を行った。 各操作は区間 で表される ( を満たす) 数列 の該当する区…
