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

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

バケット

鉄則本 B09 - Papers (2Q, ★4)

二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…

鉄則本 B08 - Counting Points (2Q, ★4)

二次元累積和の練習問題! 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか?」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…

鉄則本 B06 - Lottery (4Q, ★2)

累積和をやって、その次にやる類題として、そりゃこれを出すよね!! って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…

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

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

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

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

AtCoder ABC 350 B - Dentist Aoki (6Q, 灰色, 200 点)

「集計処理」の基本問題! 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…

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

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

AtCoder ABC 328 C - Consecutive (灰色, 300 点)

すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…

AtCoder ABC 261 A - Intersection (灰色, 100 点)

区間の交差を求めるのは頻出の典型処理だし、実務でも使えるテクニックなので、このまま覚えてしまって良いと思う! 問題へのリンク 問題概要 数直線において、 から までの部分をすべて赤色で塗り から までの部分をすべて青色で塗った このとき、赤色と青…

AtCoder ABC 325 B - World Meeting (灰色, 250 点)

会議設定時間を 0 時、1 時、2 時、...、23 時をそれぞれ全探索するのが一番分かりやすいと思う! 問題へのリンク 問題概要 キーエンス社員の 個の拠点に対して同時に会議を設定したい。拠点 には社員が 人いて、時差 (世界標準時で 0 時のときの時刻) は で…

AtCoder ABC 322 C - Festival (灰色, 300 点)

for 文を回していくときに「前回の値を活用する」というテクが登場する問題。このテクは、後に「累積和」や「DP」を学ぶ際の大切な基礎となる。 問題へのリンク 問題概要 日間のうち、 日目には花火が上がる。 各日について、何日後に最初の花火が上がるかを…

JOI 予選 2007 E - 品質検査 (AOJ 0514, 難易度 5)

この辺りから難しくなって来てる。「 で合格・不合格」という条件をどのように適切に言い換えるかが問われている。 問題へのリンク 問題概要 電源が 個、モーターが 個、ケーブルが 個ある。電源は と番号づけられていて、モーターは と番号づけられていて、…

AtCoder ABC 306 C - Centers (灰色, 250 点)

バケットを使ってもいいし、set や map を使ってもいいかもしれない 問題へのリンク 問題概要 が 3 回ずつ表れる長さ の数列 が与えられる。 を「数列 において 2 回目にその値が登場する index」が小さい順にソートせよ。 制約 考察:まず問題を掴む 最初の…

AtCoder ABC 241 B - Pasta (灰色, 200 点)

素直な実装でも解けるけど、C++ の map 型や、Python の Counter 型が使えると、すごく簡単に解けます! 問題へのリンク 問題概要 本のパスタがあって、それぞれ長さは である。 高橋君は 日間パスタを食べる。 日目にはそれぞれ長さが であるようなパスタを…

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

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

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

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

DISCO presents 2016 予選 B - ディスコ社内ツアー (青色)

シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…

AtCoder ABC 249 C - Just K (茶色, 300 点)

ビット全探索もついに茶色 diff ですね! 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです! drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…

AtCoder ABC 212 H - Nim Counting (橙色, 600 点)

コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…

AtCoder ABC 170 D - Not Divisible (緑色, 400 点)

数列をヒストグラム化することで解決できるタイプの問題!特に今回みたいに、数値の値も 以下と小さい場合はすごくそれっぽい! 問題へのリンク 問題概要 長さが の正の整数からなる数列 が与えられる。以下の条件を満たす の個数を求めよ。 なる任意の に対…

JOI 春合宿 2007 day2-2 Fermat (難易度 7)

これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…

AtCoder ARC 022 B - 細長いお菓子 (試験管水色)

しゃくとり法のいい練習問題!! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。 制約 考えたこと 今回の問題には、次のような著しい構…

CodeChef Practice(Easy) GCD Sum

添字 GCD 畳み込みの練習問題! 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

AtCoder AGC 038 C - LCMs (黄色, 700 点)

添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…

AtCoder AGC 047 C - Product Modulo (橙色, 800 点)

AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…

Codeforces Round #681 (Div. 1) B. Identify the Operations (R1800)

どんな風に操作しようとも、毎回「左右のうちの何個選べるか」が変わらない!! 問題へのリンク 問題概要 の順列 と、空の配列 が与えられる。これらに対して以下の操作を 回行うことで、配列 が に一致した状態にしたい。 そのような操作方法が何通りあるか…

yukicoder No.843 Triple Primes

エラトステネスの篩の練習問題に良さそう 問題へのリンク 問題概要 以上 以下の素数の組 であって、 を満たすものの個数を求めよ。 制約 考えたこと のときは明らかにダメ。 また、偶数かつ素数である整数は 2 のみであることに注意する。 がともに奇数とす…

AtCoder ARC 107 B - Quadruple (茶色, 400 点)

半分全列挙した! 問題へのリンク 問題概要 正の整数 と整数 が与えられる。以下の条件を満たす正の整数 の組の個数を求めよ。 制約 考えたこと 愚直な方法としては、次のように 4 重ループをする解法が考えられるかもしれない。しかしこれでは の計算量を要…

AtCoder ABC 177 E - Coprime (緑色, 500 点)

結構教育的!! 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらのうちのどの 2 つも互いに素であるとき、"pairwise coprime" そうではなく 個の最大公約数が 1 であるとき、"setwise coprime それ以外のとき、"not coprime" と出力せよ。 制約…

AOJ 2957 MOD Rush (HUPC 2019 day2-F)

これ好き!! 問題へのリンク editorial 問題概要 長さ の整数列 と、長さ の整数列 が与えられる。 すべての に対する % の値の総和を求めよ。 制約 考えたこと や の値が 以下であることがポイントに思えてくる。一般に に対して = % の総和がどう求められ…