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

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

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…

Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

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

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

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

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

意外と罠にはまりやすい問題かもしれない！！！ この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…

AtCoder ABC 111 C - /\/\/\/ (ARC 103 C) (緑色, 300 点)

離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…

AOJ 3054 Tunnel (RUPC 2019 day2-D)

整理するのがちょっと大変系。でもとても教育的だと思う！ 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

AtCoder ABC 116 C - Grand Garden (茶色, 300 点)

なんか yukicoder で書いた問題に前半は似てた。でもこの問題の難しいところは後半の方なのんな。。。 問題へのリンク 問題概要 (AGC 026 D) 幅が マス、高さが のヒストグラムが与えられる。このヒストグラムの各マスを白黒に塗る方法のうち どの 2 × 2 の…

AtCoder AGC 026 D - Histogram Coloring (橙色, 1100 点)