中間値の定理
方程式を解くタイプの二分探索の問題ですね。 問題へのリンク 問題概要 正の整数 が与えられます。 秒後のボールの位置 は で表されます。 を満たす実数 の値を十分高い精度で求めてください。 を満たせば正解とみなされます。 制約 解へのアプローチ の解を…
Codeforces
CodeforcesDIV1-D
CodeforcesR2600
CodeforcesR3000
Zero-Sum Ranges
色に関する問題
種類数
最頻値
連続部分列を扱う問題
O(N^2)個のものを考える問題
中間値の定理
ギリギリ
端点のみを考える
解を変形していく(最適性を失わずに)
ヒストグラム
平方分割
緩和しても良い
標高図を考える
場合分け
区間
平面走査
しゃくとり法
総和がNになる整数組の種類数はO(√N)
O(√N)まで考えれば十分
数列
各アルファベットごとに考える
ある量を固定して考える
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ!」という教育的なものだった! 問題へのリンク 問題概要 円形状に並んだ 個の椅子がある ( は奇数)。各椅子は 男性がいる 女性がいる 空席 のいずれかである。どの隣り合う 2…
の場合の場合分け中で出力時に "! " を入れるのを忘れていることにずっと気づかずに WA Rush という...ひどい......コンテスト本番じゃなくてよかった。。。 問題へのリンク 問題概要 (インタラクティブ) を奇数とする。 個のボール があって、そのうちの 個…