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

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

累積和

AtCoder ABC 334 D - Reindeer and Sleigh (3Q, 茶色, 400 点)

この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ! 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…

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

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

鉄則本 A10 - Resort Hotel (2Q, ★4)

左右からの累積和・累積 max を前処理で求めておくのは、よくある典型!! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…

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

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

鉄則本 A09 - Winter in ALGO Kingdom (2Q, ★4)

二次元いもす法! 問題へのリンク 問題概要 のグリッドにおいて、 日間雪が降った。 日目には、マス を左上とし、 を右上とする長方形領域に雪が 1 cm だけ降った (溶けないとする)。 最終的な各マスの積雪量を求めよ。 制約 解法 二次元いもす法をします。…

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

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

鉄則本 A08 - Two Dimensional Sum (2Q, ★4)

二次元累積和! 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…

鉄則本 B07 - Convenience Store 2 (3Q, ★3)

これは A07 と大体一緒ですね! 問題へのリンク 問題概要 あるコンビニは時刻 0 に開店し、時刻 に閉店する。 人の従業員が働いていて、従業員 は時刻 に出勤して、時刻 に退勤する。 について、時刻 に何人の従業員が働いているかを求めよ。 制約 解法 gith…

鉄則本 A07 - Event Attendance (3Q, ★3)

いもす法!! 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照!! コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…

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

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

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

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

AtCoder ARC 176 D - Swap Permutation (4D, 橙色, 700 点)

行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…

JOIG 2023 E - 運河 (難易度 7)

UnionFind を使って、差分更新を頑張る! UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います! 問題へのリンク 問題概要 のグリッドがあって…

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

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

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

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

AOJ 2426 Treasure Hunt

BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…

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

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

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

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

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

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

AtCoder ABC 265 F - Manhattan Cafe (黄色, 500 点)

次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…

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

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

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

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

EDPC (Educational DP Contest) M - Candies

DP 高速化に累積和を使う問題! 問題へのリンク 問題概要 人の子ども に、 個の飴を分けることにした。 ただし、子ども に分ける飴は、 個以上 個以下のする必要がある。 各子どもへの飴の分け方の総数を、1000000007 で割ったあまりを求めよ。 制約 解法:…

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

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

JOIG 2021 C - イルミネーション 2 (AOJ 0703, 難易度 4)

落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…

AtCoder ABC 187 E - Through Path (水色, 500 点)

これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…

AtCoder ABC 134 C - Exception Handling (灰色, 300 点)

個のものから 個除いたものを考えるのは色々定石がある! 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、 を除外した 個の整数の最大値を求めよ。 制約 解法 (1):アドホックに考える まずは素朴な解法を考えてみる。たとえば とかだったと…

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…

JOI 春合宿 2007 day1-3 Mall (難易度 5)

二次元累積和!! ジャッジページ 問題文 問題概要 のグリッドが与えられる。各マスには整数値 が描かれている。整数値は 以上 以下である。 これらのグリッド中の の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含ま…

JOI 本選 2007 A - 最大の和 (AOJ 0516, 難易度 4)

累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…