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

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

数列

AtCoder ABC 357 A - Sanitize Hands (7Q, 灰色, 100 点)

意外とミスりやすいかもしれない。慎重に for 文を書こう。 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 に対して、 を順に引いていく。このとき、 が負にならずに引ける最大個数を求めよ。 解法 実際に順番に から引いていって、 で…

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

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

AtCoder ABC 356 E - Max/Min (1D, 水色, 475 点)

面白かった! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい!!! きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…

鉄則本 B13 - Supermarket 2 (2Q, ★4)

しゃくとり法の練習問題! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1):しゃくとり法 editorial に詳しく書かれている。 github.com コー…

鉄則本 A13 - Close Pairs (3Q, ★4)

しゃくとり法の基本! 問題へのリンク 問題概要 個の整数 が与えられる。これらの整数から異なる 2 個を選ぶ方法のうち、2 個の値の差が 以下であるものの個数を求めよ。 制約 解法 (1):しゃくとり法 鉄則本の問題なので、鉄則本を参照 #include <bits/stdc++.h> using nam</bits/stdc++.h>…

AtCoder ABC 355 B - Piano 2 (6Q, 灰色, 200 点)

ソートの練習! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。なお、これら 個の値はすべて互いに相異なる。 これらをすべて混ぜた 個の値を小さい順に並べたとき、数列 の要素が 2 個以上連続する箇所があるかどうかを判定せよ。 制…

AtCoder ABC 048 C - Boxes and Candies (2Q, 茶色, 300 点)

とても教育的な Greedy 問題! 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…

AtCoder ABC 173 E - Multiplication 4 (1D, 青色, 500 点)

個から 個を選ぶ設定の問題! 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…

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

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

AtCoder ABC 207 E - Mod i (2D, 青色, 500 点)

この手の累積和高速化が半端じゃなく苦手なことがわかった。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で…

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

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

鉄則本 A06 - How Many Guests? (4Q, ★2)

累積和に関する問題!! 問題へのリンク 問題概要 日間にわたるイベントを開催し、日 には 人が来場した。次の 回のクエリに答えよ。 【クエリ】 各クエリでは が与えられるので、 日目から 日目までの間に合計何人が来場したかを答えよ。 制約 解法 累積和…

AtCoder ABC 085 B - Kagami Mochi (6Q, 灰色, 200 点)

古き良き、ABS にも収録した問題! 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…

AtCoder ABC B - AtCoder Amusement Park (6Q, 灰色, 200 点)

繰り返し回数を計算する必要もない、本当に愚直なシミュレーション! 問題へのリンク 問題概要 人乗りのゴンドラアトラクションに対して、 組のグループが待機している。グループ の人数は 人である ( が保証される)。 各グループに対して、順に グループ人…

AtCoder ABC 353 A - Buildings (7Q, 灰色, 100 点)

break を忘れずに! 問題へのリンク 問題概要 数列 が与えられる。 を満たす最小の を求めよ (存在しなければ -1 を出力せよ)。 解法 for 文を用いて、調べていこう。 条件を満たすような最小の を求めたいので、for 文での探索中に見つかったら、その瞬間に…

鉄則本 B03 - Supermarket 1 (6Q, ★2)

「組」を全探索する問題! 問題へのリンク 問題概要 個の整数 から 3 個選んで、その和を 1000 にすることが可能かどうかを判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; </int></bits/stdc++.h>…

鉄則本 A03 - Two Cards (7Q, ★1)

二重 for 文の練習! 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう! コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

鉄則本 A02 - Linear Search (8Q, ★1)

線形探索法の基本問題! 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です! コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…

AtCoder ABC 352 G - Socks 3 (3D, 橙色, 600 点)

「回数の期待値」は、(k 回以上の確率) の総和に一致する!! あとは有名な「 個の一次関数の積は二分木のような計算順序で の計算量で求められるという話! 問題へのリンク 問題概要 色が であるような靴下が 枚ずつある。いずれも 2 種類以上ある。 これら…

JOI 一次予選 2024 (第 1 回) D - 現れている数字 (6Q, 難易度 2)

とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1):値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…

AtCoder ARC 176 E - Max Vector (5D, 赤色, 800 点)

面白かった!! 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…

AtCoder ABC 335 G - Discrete Logarithm Problems (橙色, 600 点)

この問題を思い出した! 問題へのリンク 問題概要 素数 と、 個の 1 以上 以下の整数 が与えられる。 を満たす整数 が存在するような の組の個数を数え上げよ。 制約 考えたこと 一瞬、原始根を考えたくなったが、原始根ではなく「位数」を考えた方が計算量…

AtCoder ABC 330 E - Mex and Update (緑色, 475 点)

データ構造をいい感じに設計する地力が問われる! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…

AtCoder ABC 330 A - Counting Passes (灰色, 100 点)

最近、易しめのいい感じの A 問題多いね! 問題へのリンク 問題概要 個の整数 のうち、 以上であるものの個数を求めよ。 解法 配列を使って入力を受け取って、for 文を使って配列の要素を 1 個 1 個見ていけばいい。 #include <bits/stdc++.h> using namespace std; int mai</bits/stdc++.h>…

AtCoder ABC 329 D - Election Quick Report (灰色, 350 点)

「差分更新」の良い練習問題! 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…

AtCoder ABC 329 B - Next (灰色, 200 点)

昔の ABC B 問題って感じ! 問題へのリンク 問題概要 長さ の数列 が与えられる。すべての値が等しいわけではないことが保証される。 これらのうち、最大値でない中での最大値を求めよ。 解法 まず for 文を回すなどして、 個の値 の最大値を求める。たとえ…

AtCoder ABC 307 A - Weekly Records (7Q, 灰色, 100 点)

for 文の練習。色んな書き方がありそう。 問題へのリンク 問題概要 高橋君は 週間歩いた距離を記録した。 日目には、それぞれ 歩歩いた。 各週について、高橋君が 1 週間で歩いた歩数の合計を出力してください。 解法 前提として、配列を 0 始まりで考えるこ…

AtCoder ABC 308 A - New Scheme (灰色, 100 点)

「単調増加かどうか判定」は典型。そのような処理の実装に慣れよう! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列が以下の条件を全て満たすかどうかを判定せよ。 広義単調増加である すべて 100 以上 675 以下である すべて 25 の倍数であ…

AtCoder Library Practice Contest K - Range Affine Range Sum (2D)

遅延評価セグメント木の練習! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数列の区間 内の要素の総和を 99824435…