indexベースで考える
シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…
SRMDIV1Medium
ワイルドカード問題
調和級数
全探索
0と1の問題
文字列問題
禁止文字列
条件の言い換え
操作によって作れるものの集合を考える(判定関数を考える)
補集合を考える
必要条件を列挙したら十分条件になる
等差数列
indexベースで考える
ある量を固定して考える
差分更新
累積和
すごく面白かった! 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…
「次の要素」へのポインタを求める
JOI
JOI予選
JOI難易度5
AtCoder
AOJ
愚直シミュレーション
グリッド
一直線上のN点の問題
点が移動していく問題
><
所要時間を求める問題
操作後の結果を求める問題
indexベースで考える
駒を動かすゲーム
結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…
JOI
JOI本選
JOI難易度6
二分探索
しゃくとり法
0と1と2の問題
非自明な線形時間
操作
最小コスト
ある量を固定して考える
lower_bound
「次の要素」へのポインタを求める
Greedy
AtCoder
状態遷移していく部分列
indexベースで考える
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個…