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

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

ある量を固定して考える

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 D - Intersecting Intervals (2Q, 茶色, 400 点)

ものすごく教育的な典型問題! 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…

AtCoder ABC 330 D - Counting Ls (茶色, 400 点)

次の問題にとても似ていた! drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…

AtCoder ABC 330 C - Minimize Abs 2 (茶色, 300 点)

文字を固定したり、数式処理したりなど、総合力が問われる問題! 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…

AtCoder ABC 322 G - Two Kinds of Base (赤色, 600 点)

コンテスト後に解いた。なんとか詰め切った。 問題へのリンク 問題概要 非負整数 と整数 に対して、関数 を次のように定義する。 正整数 が与えられて、次の条件を満たす非負整数列 と正の整数 の組の個数を 998244353 で割った余りを求めよ。 () 制約 考え…

AtCoder ABC 321 D - Set Menu (緑色, 400 点)

「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…

Codeforces Round 539 (Div. 1) D. Sasha and Interesting Fact from Graph Theory (R2400)

また一つ、プリューファーコードの練習問題が増えた! 問題へのリンク 問題概要 正の整数値 が与えられる。 頂点数 の重み付き木であって、以下の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 各辺の重みは 以上 以下の整数値である 2 頂点 …

Codeforces Round 824 (Div. 2) D. Meta-set (R1700)

なんとか通した。結構迷走した。 問題へのリンク 問題概要 0 と 1 と 2 のみからなる の行列が与えられる。これらの行列のある 3 つの行が good であるとは、「どの列についても、それら 3 行の値がすべて等しいか、すべて互いに異なる」という条件を満たす…

AtCoder ABC 318 E - Sandwiches (緑色, 450 点)

色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…

AtCoder ARC 055 C - ABCAC (試験管黄色)

Z-algorithm や Suffix Array が使える面白い文字列検索問題! 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

AtCoder ABC 311 E - Defect-free Squares (水色, 475 点)

有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…

AtCoder ABC 311 G - One More Grid Task (黄色, 575 点)

黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた! 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…

AtCoder ABC 302 D - Impartial Gift (400 点, 茶色)

すごく典型的ないい問題! この手の問題は、大抵、二分探索法でもしゃくとり法でも解ける。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらの数列から 1 つずつの値を選ぶ。選んだ値の差が 以下となるようにすることが可能かどうかを判定し、…

AtCoder ABC 254 D - Together Square (緑色, 400 点)

なんかユーザー解説の数がすごいことになっててビビる! 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…

AtCoder ABC 292 C - Four Variables (茶色, 300 点)

これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね! 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…

AtCoder ABC 296 D - M<=ab (緑色, 400 点)

「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…

AtCoder ABC 301 D - Bitmask (緑色, 400 点)

基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける! 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…

AtCoder ABC 256 G - Black and White Stones (黄色, 600 点)

opt さんの得意系って感じだった! 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …

AtCoder ABC 300 D - AABCC (緑色, 400 点)

ほどよい全探索問題! 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける! 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか? 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…

AtCoder ABC 300 F - More Holidays (青色, 500 点)

二分探索すれば楽できることをすぐに思いつけてよかった。 問題へのリンク 問題概要 o と x のみからなる長さ の文字列 が与えられる。 文字列 を 回繰り返して得られる文字列 を考える。この文字列 に対して、最大 回まで、x を o に書き換える操作を行うこ…

AtCoder ABC 286 C - Rotate and Palindrome (茶色, 300 点)

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

AtCoder ABC 250 D - 250-like Number (茶色, 400 点)

緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね! 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…

AtCoder ABC 246 D - 2-variable Function (緑色, 400 点)

前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …

AtCoder ABC 212 G - Power Pair (黄色, 600 点)

原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…

AtCoder ABC 023 C - 収集王 (試験管青色)

これが ABC の C 問題だったとは...!!! 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…

AtCoder ARC 037 C - 億マス計算 (試験管青色)

二分探索法の教育的典型問題ですね!! 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…