累積和テク:条件を満たすものの個数を累積和で表す
いい感じの教育的典型問題。いもす法したあとに累積和する！ 問題へのリンク 問題概要 個のマス がある。 個の区間があって、それぞれマス からマス までを連続して覆っている。 個の区間によって一回以上被覆されるマスの集合を とする。 各区間について、…
ほどよい全探索問題！ 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！ 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか？ 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
二分探索すれば楽できることをすぐに思いつけてよかった。 問題へのリンク 問題概要 o と x のみからなる長さ の文字列 が与えられる。 文字列 を 回繰り返して得られる文字列 を考える。この文字列 に対して、最大 回まで、x を o に書き換える操作を行うこ…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
「3 つのものの真ん中に着目する」という典型が学べる。面白かった！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…
比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり！ 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…
教育的ないい問題！！！！！ 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか？ 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…
これも累積和！！！ ただちょっとややこしい... atcoder.jp ここに色々書いた qiita.com
累積和を用いる典型な感じ！ atcoder.jp ここで解説を行った: qiita.com
とりあえず 1 問目やってみた！累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) に O が…
FFT 勉強シリーズその 2。 うーん、、、これ思いつけるもんなんかいな...... Codeforces 488 DIV1 E - Nikita and Order Statistics 問題概要 要素の整数数列 と整数 が与えられる。数列 の連続する部分列のうち、「 未満の値となっているものが 個ある」と…
累積和の典型問題 問題へのリンク 問題概要 WWEWEEWWEE のような文字列が与えられる。 文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。 制約 解法 累積和を用いる。 #include <iostream> #includ</iostream>…
