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

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

累積和

yukicoder No.973 余興

Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…

yukicoder No.972 選び方のスコア

すごく面白かった!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…

第5回 ドワンゴからの挑戦状 予選 2018 D - Square Rotation (800 点)

すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…

第5回 ドワンゴからの挑戦状 予選 2018 B - Sum AND Subarrays (400 点)

最初、罠に引っかかった 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの連続する区間の総和を書き出していく ( 個ある)。 これらの中から 個選んで AND をとった値として考えられる最大値を求めよ。 制約 嘘貪欲 とりあえず なので、 個の整数…

AtCoder AGC 023 A - Zero-Sum Ranges (200 点)

200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました! qiita.com

AtCoder ARC 099 F - Eating Symbols Hard (1200 点)

楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …

AtCoder ABC 143 D - Triangles (400 点)

教育的ないい問題!!!!! 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか? 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…

AtCoder ABC 143 F - Distinct Numbers (600 点)

かなり辛いことを頑張ったけど、本当はすごく明快な問題だった!! 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…

yukicoder No.886 Direct

添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1:添字 GCD 畳み込み この問題は、線分として 軸や 軸に…

AtCoder ABC 132 F - Small Products (600 点)

こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…

AtCoder ABC 130 E - Common Subsequence (500 点)

共通部分列に関する問題!!!!! 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…

AtCoder ABC 130 D - Enough Array (400 点)

超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…

diverta 2019 E - XOR Partitioning (800 点)

時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…

AtCoder ARC 074 D - 3N Numbers (500 点)

昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…

AtCoder ABC 125 C - GCD on Blackboard (300 点)

累積和!累積和!累積和!!! でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…

Tenka1 2019 F - Banned X (800 点)

かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…

Tenka1 2019 C - Stones (300 点)

これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N -…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

AtCoder ABC 124 D - Handstand (400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AtCoder ABC 124 B - Great Ocean View (200 点)

こういうのが素早くストレスなく書けるようになるといい感じな気がする 問題へのリンク 問題概要 海から順番に建物 があって、それぞれの高さは である。 海が見える建物が何個あるかを求めよ。なお、 番目の建物から海が見えるとは より前の 番目の建物より…

AtCoder ABC 122 C - GeT AC (300 点)

これも累積和!!! ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com

AtCoder ABC 084 D - 2017-like Number (400 点)

累積和を用いる典型な感じ! atcoder.jp ここで解説を行った: qiita.com

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…

AtCoder ARC 045 C - エックスオア多橋君

XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決めて…

AtCoder AGC 008 B - Contiguous Repainting (400 点)

操作を逆順に見るとよいという、すごく良い例題!大好き!!! 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

全国統一プログラミング王決定戦 本選 A - Abundant Resources (200 点)

累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…

AOJ 0660 たのしいたのしいたのしい家庭菜園 (JOI 2019 本選 C)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない」ようにしたい。それが可能となる操…

AOJ 0658 勇者ビ太郎 (JOI 2019 本選 A)

とりあえず 1 問目やってみた!累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される N × M の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) …