JOI難易度4
直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()!!! 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …
DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…
AtCoder
JOI
JOIG
JOI難易度4
累積和
前処理
累積和テク:左右両端からの累積和や累積結果を前処理
最適化テク:最適解の形を考える
場合分け
0と1の問題
条件の言い換え
盤面を予め変更する
操作
SをTにすることが目的の操作の問題
最小コスト
最小回数・最小個数を求める
スイッチ
【問題集】累積和
累積和テク:累積和や累積結果を前処理しておく
累積和テク:条件を満たすものの個数を累積和で表す
AOJ
最適化問題
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
JOI
JOI本選
JOI難易度4
累積和
AOJ
AtCoder
データ構造
そのまま覚えたい典型問題
数列
連続部分列を扱う問題
【問題集】累積和
累積和テク:区間の総和を累積和で高速に求める
【問題集】累積和・いもす法
累積和を使う代表的な問題ですね。 ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 前提知識 まず、愚直な解法で…