けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

データ構造

AtCoder ARC 167 D - Good Permutation (黄色, 700 点)

モノグサでバチャやって、なんとか通した! 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…

AOJ 1282 Bug Hunt (ICPC アジア 2007 H) (450 点)

アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…

Yosupo Library Checker - Static Range Frequency

Wavelet Matrix の機能の verify 第二弾!!! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 区間 において値 が出現する回数を答えよ。 制約 考えたこと これも Wavelet Matrix の典型機能である。rank() という関数が…

Yosupo Library Checker - Range Kth Smallest

数列の区間について、 番目に小さい値を求めていく。Wavelet Matrix で処理できる典型クエリ! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 区間 において 番目 (0-indexed) に小さい数を答えよ 制約 考えたこと Wavele…

Cartesian Tree の実装 〜 stack を用いた O(N) 時間構築

Cartesian Tree を実装しよう! 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…

AOJ 1549 Hard Beans (ACPC 2014 day2-I)

Wavelet Matrix の prev_value や next_value が使える問題! 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 が与えられるので、数列の区間 の値のうち、 との差の最小値を答えよ。 制約 考えたこと Wavelet Matrix の関…

AtCoder ABC 324 G - Generate Arrays (橙色, 600 点)

Wavelet Matrix の練習に 問題へのリンク 問題概要 初期状態が の順列である数列 が与えられる。 次の 2 種類のクエリに答えよ。なお、 番目 () のクエリをこなした後には、数列は 個に分割された状態となる。 クエリタイプ 1:群数列の 番目について、先頭…

AtCoder ABC 234 D - Prefix K-th Max (茶色, 400 点)

あまりにも色んな解法がある問題 問題へのリンク 問題概要 の順列 と正の整数 が与えられる。 各 に対して、順列の先頭から 個の値の中での 番目に大きい値を求めよ。 制約 考えたこと 次の問題の下位互換と言える。 drken1215.hatenablog.com この上位互換…

AOJ Course RSQ and RUQ (遅延評価セグメント木の練習問題 4)

「区間値更新」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): を に変更する クエリタイプ (1 s t): の総和…

AOJ Course RSQ and RAQ (遅延評価セグメント木の練習問題 3)

「区間加算」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): に を加算する クエリタイプ (1 s t): の総和を…

AOJ Course RMQ and RUQ (遅延評価セグメント木の練習問題 2)

Starry Sky Tree は「区間 加算」「区間最小値取得」を処理する遅延セグ木だった。 今回は「区間 更新」「区間最小値取得」を処理する遅延セグ木を実装する。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は…

AOJ Course RMQ and RAQ (遅延評価セグメント木の練習問題 1)

この問題は、人生で最初に挑む遅延セグ木の問題としてオススメ!Starry Sky Tree と呼ばれるものでもある。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s…

Union-Find の中身のグループ分けを知る関数 groups() を実装する!

多くの競プロerにとって、標準ライブラリ以外で自分の手で初めて実装するデータ構造は Union-Find でしょう。 自分でデータ構造を実装するとき、その中身がどうなっているかをきちんと把握できないと不安を感じてしまうこともあるでしょう。そこで本記事では…

鉄則本 A58 - RMQ (Range Maximum Queries)

セグメント木の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 の値を …

AOJ 2369 CatChecker (JAG 冬合宿 2010 day3-A) (300 点)

カッコ列の整合性判定問題の亜種と言える。 問題へのリンク 問題概要 文字列 が cat 文字列であるとは、次の条件を満たすことをいう。 は空文字列である ある cat 文字列 が存在して、 と表せる 与えられた文字列 が cat 文字列であるかどうかを判定せよ。 …

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

AOJ 3333 Range Xor Query (HUPC 2023 day1-J)

Binary Trie + 平方分割 問題へのリンク editorials 問題概要 数列 に対して、以下の 個のクエリを処理せよ。 クエリタイプ 1 (k x): を xor に置き換える クエリタイプ 2 (l r x): xor の値を出力する 制約 考えたこと これは TL で解法を見た上で解いた…

AtCoder ABC 278 D - All Assign Point Add (茶色, 400 点)

データの持ち方をうまく工夫することで、計算量を改善する系の問題! 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x:数列 をすべて に書き換える i x: に を足す i…

AtCoder ABC 298 C - Cards Query Problem (茶色, 300 点)

クエリ形式の問題に慣れたり、クエリに答えるためのデータ構造を考えたりすることに慣れたりするための練習問題! 問題へのリンク 問題概要 1 から までの番号のついた 個の箱と、何も書かれていない無数のカードがある。今、 個のクエリが与えられるので、…

AtCoder ABC 282 F - Union of Two Sets (青色, 600 点)

コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに!」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…

AtCoder ABC 282 D - Make Bipartite 2 (緑色, 400 点)

一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある! その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる!! 問題へのリンク 問題概要 頂点数 、辺数 の単…

AtCoder Library Practice Contest A - Disjoint Set Union

Union-Find の最も典型的な練習問題 問題へのリンク 問題概要 頂点 辺の無向グラフに 個のクエリが飛んでくる :辺 を追加する : 頂点間 が連結ならば 1、そうでないなら 0 を出力する 制約 解法 Union-Find はグループ分けを管理するデータ構造です。以下…

AtCoder ABC 281 E - Least Elements (水色, 500 点)

よくあるデータ構造問題!! めっちゃ色んな解法がある! 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

AOJ 2207 無矛盾な単位系 (UTPC 2010 D)

これも重み付き Union-Find で解ける問題! 問題へのリンク editorial 問題概要 具体例として一つの入力ケースを示す。 7 1 kilometre = 10^3 metre 1 megametre = 10^3 kilometre 1 metre = 10^-6 megametre 1 terametre = 10^3 gigametre 1 petametre = 10…

AOJ 1330 Never Wait for Weights (ICPC アジア 2012 F) (500 点)

重み付き Union-Find の練習問題! 問題へのリンク 問題概要 個の値 があるが、それらの値がわからないので、特定したい。 次の 2 種類のクエリが 個、与えられるので順に処理せよ。 3 つの値 が与えられる。 であるという情報が与えられる。 2 つの値 を与…

AtCoder ABC 280 F - Pay or Receive (青色, 500 点)

重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…

AtCoder ABC 250 C - Adjacent Swaps (茶色, 300 点)

実はアルゴ式でもよく似た問題をすでに出していました! algo-method.com 問題へのリンク 問題概要 がこの順に並んでいます。この数列に対して 回のクエリが投げられました。 各クエリでは、値 が指定されて、次の操作を実行します。 数列中の整数 に対し、…

AtCoder ABC 245 E - Wrapping Chocolate (水色, 500 点)

これ!!! ABC 091 C - 2D Plane 2N Point とほとんど同じ!! ただ制約が大きいので、貪欲法を高速化する必要がありますね。 問題へのリンク 問題概要 個のチョコレートと、 個の箱があります。 番目のチョコレートはサイズ であり、 番目の箱はサイズ で…

AtCoder ABC 137 D - Summer Vacation (水色, 400 点)

これは難しい!!! 誘惑されそうな嘘解法がたくさんある!! 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…