累積和
「二項係数の和」は結構なんとかなることを学んだ！ 備忘録程度に書く。 問題へのリンク 問題概要 下の図のように、 グリッドを、レベル の L 字で隙間なく埋め尽くす (レベル の L 字の定義は問題文参照)。 マス を指定したとき、次の 回のクエリに答えよ。…
いい感じの教育的典型問題。いもす法したあとに累積和する！ 問題へのリンク 問題概要 個のマス がある。 個の区間があって、それぞれマス からマス までを連続して覆っている。 個の区間によって一回以上被覆されるマスの集合を とする。 各区間について、…
「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…
これ面白かった！ 問題へのリンク 問題概要 数列 が与えられる。この数列の連続する部分数列について「その総和を で割った余り」を考える。 連続する部分数列をすべて考えたときの、「その総和を で割った余り」の総和を求めよ。 制約 考えたこと この問題…
方針を立てるのは難しくないけど、とにかく重たい問題だった。 問題へのリンク 問題概要 人 に対して合計 票が集まった。これらの人のうち条件「自分よりも多くの票を集めた人が 人未満」を満たす人が当選となる。 票のうち途中まで開票されて、各人 には 票…
円環上の Zero-Sum Ranges!! 問題へのリンク 問題概要 円周上に 個の地点 がこの順に時計回りに並んでいる。地点 から地点 （ のとき とする）まで時計回りに移動するのに要する時間は である。 次の条件を満たす の個数を求めよ から時計回りに へと到達す…
面白かった！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい！！！ きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
しゃくとり法の練習問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 editorial に詳しく書かれている。 github.com コー…
この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！ 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…
この手の累積和高速化が半端じゃなく苦手なことがわかった。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で…
左右からの累積和・累積 max を前処理で求めておくのは、よくある典型！！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…
二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…
二次元いもす法！ 問題へのリンク 問題概要 のグリッドにおいて、 日間雪が降った。 日目には、マス を左上とし、 を右上とする長方形領域に雪が 1 cm だけ降った (溶けないとする)。 最終的な各マスの積雪量を求めよ。 制約 解法 二次元いもす法をします。…
二次元累積和の練習問題！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか？」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…
二次元累積和！ 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…
これは A07 と大体一緒ですね！ 問題へのリンク 問題概要 あるコンビニは時刻 0 に開店し、時刻 に閉店する。 人の従業員が働いていて、従業員 は時刻 に出勤して、時刻 に退勤する。 について、時刻 に何人の従業員が働いているかを求めよ。 制約 解法 gith…
いもす法！！ 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照！！ コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…
累積和をやって、その次にやる類題として、そりゃこれを出すよね！！ って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…
累積和に関する問題！！ 問題へのリンク 問題概要 日間にわたるイベントを開催し、日 には 人が来場した。次の 回のクエリに答えよ。 【クエリ】 各クエリでは が与えられるので、 日目から 日目までの間に合計何人が来場したかを答えよ。 制約 解法 累積和…
行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…
UnionFind を使って、差分更新を頑張る！ UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います！ 問題へのリンク 問題概要 のグリッドがあって…
次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…
BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 を満たす組 の個数を求めよ。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めてい…
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
ほどよい全探索問題！ 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！ 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか？ 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
二分探索すれば楽できることをすぐに思いつけてよかった。 問題へのリンク 問題概要 o と x のみからなる長さ の文字列 が与えられる。 文字列 を 回繰り返して得られる文字列 を考える。この文字列 に対して、最大 回まで、x を o に書き換える操作を行うこ…
