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

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

クエリ処理問題

AtCoder ABC 379 D - Home Garden (2Q, 茶色, 400 点)

「全体に足す」のは難しいから、足す値を別途持っておくというスキル!!! 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1:新たに要素 0 を挿入する(重複もあり) クエリタイプ 2:すでに挿入されているすべての要素に を足す クエ…

AtCoder ABC 278 C - FF (4Q, 灰色, 300 点)

SNS を題材にした set の練習問題 問題へのリンク 問題概要 人から SNS について、次の 個のクエリに答えよ(初期状態では全員が誰もフォローしていない)。 クエリタイプ 1:人 が人 をフォローする(フォロー済みの場合は何もしない) クエリタイプ 2:人 …

AtCoder ABC 235 C - The Kth Time Query (4Q, 灰色, 300 点)

連想配列の練習問題! 問題へのリンク 問題概要 長さ の整数列 が与えられる。この数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、整数列を順に見ていったときの「 個目の値 の要素」の index を答えよ(存在しない場合は -1)…

AtCoder ABC 378 B - Garbage Collection (5Q, 灰色, 200 点)

演算子「%」を上手に使う系の数学問題。 問題へのリンク 問題概要 種類のゴミがある。ゴミ は、 で割って 余る日に捨てることができる。 次の 個のクエリに答えよ。 【クエリ】 ゴミ を、 日目以降に捨てたい。最短で捨てることのできる日を答えよ。 制約 考…

ゆるふわ競技プログラミングオンサイト at FORCIA #7 G - Dot Product Query (4D)

コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…

鉄則本 A59 - RSQ (Range Sum Queries) (1Q, ★5)

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

鉄則本 A53 - Priority Queue (4Q, ★2)

優先度付きキューを人生で初めて試すのにいい問題。 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。販売システムを模している。 クエリタイプ 1:価格が 円の商品が追加される クエリタイプ 2:今ある商品の…

鉄則本 A52 - Queue (4Q, ★2)

キューの使い方の確認! 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。行列管理システムを模している。 クエリタイプ 1:行列の最後尾に さんが並ぶ クエリタイプ 2:行列の先頭にいる人の名前を答える クエ…

鉄則本 A51 - Stack (4Q, ★2)

人生で最初に解きたいスタックの問題 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。 クエリタイプ 1: という題名の本を机の一番上に積む クエリタイプ 2:一番上に積まれている本の題名を答えよ クエリタイ…

JOI 二次予選 2022 A - 図書館 2 (AOJ 0719) (4Q, 難易度 2)

スタックを用いたシミュレーション問題! 問題へのリンク 問題概要 最初、本は積まれていない。次の 回のクエリに答えよ 【クエリ】 各クエリでは文字列 が与えられる。 が "READ" ではないとき、タイトルが である本が新たに上に積まれる が "READ" である…

AtCoder ABC 372 E - K-th Largest Connected Components (1Q, 緑色, 475 点)

Union-Find を上手に使おう! 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1:頂点 間に辺を張る クエリタイプ 2:頂点 を含む連結成分に含まれる頂点の番号にうち、 …

AtCoder ABC 372 C - Count ABC Again (3Q, 灰色, 350 点)

差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…

AtCoder ABC 371 B - Taro (6Q, 灰色, 200 点)

バケットを活用する練習問題! 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は ('M' または 'F')であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…

AtCoder ABC 050 B - Contest with Drinks Easy (6Q, 灰色, 200 点)

for 文を回す処理を 回やる問題 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 が与えられる。 を に変更したときの、 の値を答えよ。(なお、クエリごとに変更は引き継がれない。) 考えたこと …

AtCoder ABC 370 D - Cross Explosion (1Q, 緑色, 400 点)

set を上手に使う系の問題 問題へのリンク 問題概要 のグリッドがあり、最初は各マスに壁がある。このグリッドに次の 回のクエリを実行したあとの、残っている壁の個数を求めよ。 【クエリ】 マス のある位置に爆弾を落とす。 もしこのマスに壁があるなら、…

AtCoder ABC 344 C - A+B+C (5Q, 灰色, 250 点)

とても教育的な問題! ちゃんと解くには、計算量の理解が必要となる問題である。 問題へのリンク 問題概要 3 つの数列 が与えられる。これらの数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、 からそれぞれ 1 個ずつ選んで和を…

JOIG 春合宿 2022 day1-2 JOIG ツアー (1Q, 難易度 7)

「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする! 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …

JOI 予選 2008 F - 船旅 (AOJ 0526) (2Q, 難易度 5)

実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う! 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0:2 頂点 が指定されるので、頂点…

JOI 一次予選 2022 (第 3 回) D - ボールの移動 (5Q, 難易度 3)

どのようにデータを管理すればよいか、難しいと感じるかもしれない。 問題へのリンク 問題概要 最初、箱 にそれぞれボール が入っている。 次の 回の操作を行う。 回目の操作では、ボール が入っている箱から、ボール を取り出して、それを箱 に入れる。 操…

AtCoder ABC 294 C - Merge Sequences (5Q, 灰色, 300 点)

ソートに関する練習問題! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらの数列の値はすべて互いに相異なる。 これらの 2 つの数列の各要素 について、次の値を求めよ。 2 つの数列を連結してできる長さ の数列を小さい順に並…

AtCoder ABC 361 A - Insert (7Q, 灰色, 100 点)

for 文の練習問題。 問題へのリンク 問題概要 長さ の整数列 が与えられる。 この数列の 番目の要素の直後に値 を挿入して得られる数列を出力せよ。 解法 (1):関数 erase() を利用する C++ では、vector 型変数 A に対して、 番目に値 を挿入する処理は A.i…

AtCoder ABC 240 D - Strange Balls (3Q, 茶色, 400 点)

スタックを活用する系の問題! 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …

AtCoder ABC 359 G - Sum of Tree Distance (3D, 黄色, 600 点)

いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …

AtCoder ABC 357 F - Two Sequence Queries (2D, 青色, 550 点)

maspy さんの次のツイートがすべて!! F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…

AtCoder ABC 356 F - Distance Component Size Query (3D, 黄色, 525 点)

苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x:集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x:集合 に…

AtCoder ABC 356 G - Freestyle (5D, 赤色, 575 点)

この見た目で「幾何」になるの、面白い! 問題へのリンク 問題概要 高橋君は 種類の泳ぎ方ができる。 種類目の泳ぎ方では、1 秒間に体力を だけ消費して、 メートル進むことができる。このとき、次の 回のクエリに答えよ。 【クエリ】 正の実数 が与えられる…

AtCoder ABC 334 D - Reindeer and Sleigh (3Q, 茶色, 400 点)

この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ! 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…

鉄則本 B11 - Binary Search 2 (4Q, ★3)

lower_bound() の練習!! 問題へのリンク 問題概要 長さ の配列 が与えられる。この配列に対して 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、配列 の中に より小さい要素が何個あるかを求めよ。 制約 解法 github.com コード #include <bits/stdc++.h> using</bits/stdc++.h>…

AtCoder ABC 205 D - Kth Excluded (2Q, 茶色, 400 点)

色んな方法があるが、できるだけ楽にやりたい! 問題へのリンク 問題概要 単調増加な 要素からなる数列 がある。この数列について、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、 のどれとも異なる数値 (よい数と呼ぶこととする) のうち、…

AtCoder ABC 354 C - AtCoder Magics (2Q, 茶色, 350 点)

いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…