非自明な線形時間
スタックの応用問題！ ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの値は互いに相異なる。 各 に対して、次の条件を満たす整数 の個数を求めよ。 なる任…
この手のスタックの問題はもうすっかり常識と化した！ 問題へのリンク 問題概要 ビル がこの順に並んでいる。ビル の高さは である。 各 に対して、ビル の間にビル より高いものがないような () の個数を求めよ。 制約 考えたこと いかにもスタックを使いそ…
が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…
stack を使ってカッコ列判定をする問題の亜種！ 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…
Cartesian Tree を実装しよう！ 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…
セグ木とか必要なくて、本当に単純な実装で解けるの面白い 問題へのリンク 問題 制約 考えたこと まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。 カッコ…
「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題！ 問題へのリンク 問題概要 正の整数 に対して、 レベル のダンゴ文字列とは、以下の条件を満たす文字列である。 o と - からなる長さ の文字…
Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった！ 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…
これを機会に SA-IS を整備した！ 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字目以降のみからなる部分文字列を と表すことにします。 のそれぞれに対して…
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…
これ茶色はさすがにびっくりした！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…
以前にしゃくとり法の記事で特集した問題のひとつだった！ 問題へのリンク editorial 問題概要 環状のバームクーヘンを 3 つに分けたい。 バームクーヘンは下図 (問題文から引用) のように 個のピースに分かれていて、それぞれのサイズは となっている。 バ…
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個ずつ) のことを指すものとする。 文字…
カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…
頑張って DFS だけで通した！！！ 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
for 文って、本当に 1 回回すだけでいろんな処理ができる！！！ 問題へのリンク 問題概要 の順列 が与えられる。 が の最小値となっている という条件を満たす が何個あるかを数えよ。 制約 考えたこと つまり「先頭から 個もってきたときに、 番目が最小値…
時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…
教育的な典型問題！ 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…
頭の整理が大変！！！ 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …
教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…
超定番の「対応がとれている」カッコ列を題材にした問題。 ある文字列が与えられたときにそれが正しいカッコ列かどうか判定するのは、AGC 005 A - STring の方法でできる。 問題へのリンク 問題概要 )()()(((())())()())()()() のような 文字のカッコ列が与…
