操作をstackを用いて高速化する
面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…
弦が交わるかどうかを判定するという、スタックの典型問題！ 問題へのリンク 問題概要 次の図のように、円周上に 個の点 があり、 本の弦がある（図は のとき）。 弦に交差があるかどうかを判定せよ。 制約 考えたこと この問題は stack で解けることで有名…
スタックの応用問題！ ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする！ 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの値は互いに相異なる。 各 に対して、次の条件を満たす整数 の個数を求めよ。 なる任…
スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…
スタックを用いて解決できる典型問題 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、 かつ を満たす最大の を求めよ (存在しない場合は -1)。 制約 メモ スタックを使うと の計算量で解ける。詳細は鉄則本を参照。 コード #include <bits/stdc++.h> usi</bits/stdc++.h>…
スタックを用いて、かっこの対応をとる問題！ 問題へのリンク 問題概要 対応のとれているカッコ列 が与えられる。対応する左かっこ '(' と右かっこ ')' が、それぞれ の何番目と何番目であるかを順に求めよ。 制約 メモ 詳しい解説はここにあるのでメモ程度…
この手のスタックの問題はもうすっかり常識と化した！ 問題へのリンク 問題概要 ビル がこの順に並んでいる。ビル の高さは である。 各 に対して、ビル の間にビル より高いものがないような () の個数を求めよ。 制約 考えたこと いかにもスタックを使いそ…
スタックを活用する系の問題！ 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …
カッコ列に関連してシミュレーションしていく問題！ 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…
stack を使ってカッコ列判定をする問題の亜種！ 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…
アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…
Cartesian Tree を実装しよう！ 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…
カッコ列の整合性判定問題の亜種と言える。 問題へのリンク 問題概要 文字列 が cat 文字列であるとは、次の条件を満たすことをいう。 は空文字列である ある cat 文字列 が存在して、 と表せる 与えられた文字列 が cat 文字列であるかどうかを判定せよ。 …
これは学びの深い DP 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
セグ木とか必要なくて、本当に単純な実装で解けるの面白い 問題へのリンク 問題 制約 考えたこと まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。 カッコ…
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…
カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…
えーーー、300 点！？ 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…
これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
区間反転操作問題シリーズ！！！ それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …
教育的な典型問題！ 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…
こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい！！！！！！ ということで教育的な楽しい問題！！！ 問題へのリンク 問題概要 整合するカッコ列 があって、 から以下のように定義される長さ の順列 が与えれる: i …
久しぶりのカッコ列の整合判定問題！！！ カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…
教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…
こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…
