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

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

バケット

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 問題概要 長さ の整数列 と、長さ の整数列 が与えられる。 すべての に対する % の値の総和を求めよ。 制約 考えたこと や の値が 以下であることがポイントに思えてくる。一般に に対して = % の総和がどう求められ…

HHKB プログラミングコンテスト 2020 C - Neq Min (灰色, 300 点)

mex!!!それにしても、ならし計算量解析系が来たのびっくり! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…

Grakn Forces 2020 D. Searchlights (R2000)

すごいよくある感じ 問題へのリンク 問題概要 二次元平面上に 個の点 () と、 個の点光源 () がある。今、 個の点に対して以下の操作を行う 個の点を一律に右に動かす 個の点を一律に上に動かす この操作によって、すべての点について「どの点光源の右下側に…

ACL Beginner Contest D - Flat Subsequence (水色, 400 点)

LIS を求める in-place DP を応用すればできる! でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった! in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…

AtCoder ABC 171 D - Replacing (茶色, 400 点)

差分更新を上手にやっていくという、とても教育的な問題!!! そして、よく似た類題として、以下の問題がある!! atcoder.jp 今回の問題へのリンク 問題概要 個の整数 が与えられる。以下の 回のクエリに答えよ。 各クエリでは 2 つの整数 が与えられる 数…

AtCoder ABC 159 D - Banned K (茶色, 400 点)

差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…

Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …