操作
このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…
区間 DP な問題って、あまり見なくなったなと。貴重なので記録。 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、…
また 1 つ、カッコ列に関する問題が誕生した 問題へのリンク 問題概要 長さ のカッコ列が与えられる。カッコ列に以下の操作を好きな順序で好きな回数だけ施して「整合が取れた状態」にしたい。 カッコ列のある区間について、任意の順序に並び替える このとき…
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …
まさか残り 25 分で通し切れるとは思わなかった！ 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…
操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …
操作を 回行った結果を求める系、苦手意識あるけど克服したい！ 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…
少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題！！！ このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…
「操作によって出来上がるものが何通りあるか？」という問題では、まず判定問題を考える！(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…
これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …
気持ち良く詰められた 問題へのリンク 問題概要 のオブジェに対し いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える) という操作を 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点…
D 問題はコーナーケースゲーかと思ったらそうでもなかった。むしろこっちの方が苦しかった。 問題へのリンク 問題概要 要素からなる配列が 個あって、それぞれ最初は で初期化されている。以下の操作を 回終えた段階で、 個の配列が等しい状態とすることが可…
区間加算に対応したデータ構造の出番！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…
辞書順最小の教育的例題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…
すごく面白かった！ 問題へのリンク 問題概要 ある数値が与えられる。ただしその数値は非常に桁数が大きいことがあるので、数値を 10 進法で表したときの文字列をランレングス圧縮した状態で与えられる。具体的には 組の値 が与えられて、 の順に、数値 が …
こういうのをちゃんと解けるようになったのは成長！ 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…
とてもこどふぉっぽい問題だと思った！！！こういうのを得意になるぞー！！！ 問題へのリンク 問題概要 の順列が与えられる。各 に対して、以下の問いに答えよ。 順列の隣り合う 2 要素を swap して、順列のどこかの場所で がこの順に連続で並んでいる状態に…
隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…
面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…
枝刈り探索が根本的に計算量改善することを示せることがある！！！ 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
その 2 と雰囲気は似ているけど、一気に考えづらくなった！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…
ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した！！！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…
面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…
とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…
信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…
とても教育的な Greedy かもしれない！ 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…
