【問題集】累積和
すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
二次元累積和！！ ジャッジページ 問題文 問題概要 のグリッドが与えられる。各マスには整数値 が描かれている。整数値は 以上 以下である。 これらのグリッド中の の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含ま…
累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…
累積和の累積 max 問題へのリンク 問題概要 数列 が与えられます。 この数列は負の要素を含むかもしれません。 数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。 正の向きに 進む。 正の向きに 進み、正の向きに 進む。 正の向きに …
Zero-Sum Ranges の応用問題だけど、最初難しく考えてしまって「解けない...」となってました ジャッジページへのリンク 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。…
「3 つのものの真ん中に着目する」という典型が学べる。面白かった！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…
二次元累積和のいい感じの練習問題！！ ただこれ水色って......現代なら、茶色くらいに感じる。 問題へのリンク 問題概要 市松模様に塗られた のマス目があって、各マスには整数値が書かれている。以下の条件を満たす長方形領域の面積の最大値を求めよ。 そ…
Zero-Sum Ranges だった！！！ 問題へのリンク 問題概要 'A', 'G', 'C', 'T' からなる文字列 が相補的であるとは、 を並び替えてできる文字列 が存在して、 T[ i ] = 'A' ならば T'[ i ] = 'T' T[ i ] = 'T' ならば T'[ i ] = 'A' T[ i ] = 'G' ならば T'[ i…
まさかの既出！！！しかも割と最近の ABC-E！！！ drken1215.hatenablog.com 問題へのリンク 問題概要 から までの数字のみからなる文字列 が与えられる。 の連続する区間であって、 の倍数であるものが何個あるのかを求めよ。 制約 考えたこと 実は完全にマ…
200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました！ qiita.com
これも累積和！！！ ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com
累積和を用いる典型な感じ！ atcoder.jp ここで解説を行った: qiita.com
累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…
とりあえず 1 問目やってみた！累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される N × M の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) …
かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…
AGC 023 A - Zero-Sum Ranges とほぼ同じ問題になってる。ただし、バケットを愚直に確保すると 109 サイズになってしまうので map とか連想配列が必要になる。 問題へのリンク 問題概要 個の整数 の連続する部分区間のうち、その総和が の倍数となっているも…
累積和の典型問題 問題へのリンク 問題概要 WWEWEEWWEE のような文字列が与えられる。 文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。 制約 解法 累積和を用いる。 #include <iostream> #includ</iostream>…
