Codeforces Round #488 (Div. 1) E. Nikita and Order Statistics (R2300)

累積和数列 FFT 区間各kに対して多項式・FPS(形式的冪級数) 高速畳み込み計算 Codeforces CodeforcesR2300 CodeforcesDIV1-EFG バケット集計処理累積和テク:条件を満たすものの個数を累積和で表す

FFT 勉強シリーズその 2。うーん、、、これ思いつけるもんなんかいな...... Codeforces 488 DIV1 E - Nikita and Order Statistics 問題概要要素の整数数列と整数が与えられる。数列の連続する部分列のうち、「未満の値となっているものが個ある」と…

2018-06-23

CS Academy 082 DIV1 C - City Break

しゃくとり法累積和数珠 CSAcademy 操作後の結果を求める問題

しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかも CS Academy 082 DIV1 C - City Break 問題概要円環状に個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街 1 …

2018-06-07

AtCoder ARC 097 E - Sorted and Sorted (黄色, 600 点)

DP 前処理累積和操作:swap 最小回数・最小個数を求める操作 AtCoder AtCoder600点 ARC-E 操作:隣接swap ソートすることが目的の操作の問題最小コスト黄色diff DP状態:吸い出しと吸い込み要素の並び替えを管理するDP そのまま覚えたいシンプル設定の中堅以上の典型問題最適化問題

600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…

2018-05-30

AtCoder ABC 098 C - Attention (ARC 098 C) (茶色, 300 点)

累積和 AtCoder300点 AtCoder ABC-C 茶色diff 最適化テク:最適解の形を考える前処理累積和テク:左右両端からの累積和や累積結果を前処理 N個のものうち1個を変更・削除したものを解く ARC-C そのまま覚えたい典型問題累積和テク:累積和や累積結果を前処理しておく DP DP状態:フェーズ(耳DP) ナップサックDP DP状態:on/off 0と1の問題累積和テク:条件を満たすものの個数を累積和で表す典型要素を詰め合わせた教育的問題【問題集】累積和

累積和の典型問題問題へのリンク問題概要 WWEWEEWWEE のような文字列が与えられる。文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。制約解法累積和を用いる。 #include <iostream> #includ</iostream>…

2002-08-01

TopCoder SRM 452 DIV1 Medium - IOIString (本番 19 人)

SRMDIV1Medium ワイルドカード問題調和級数全探索 0と1の問題文字列禁止文字列条件の言い換え操作によって作れるものの集合を考える(判定関数を考える) 補集合を考える必要条件を列挙したら十分条件になる等差数列 indexベースで考えるある量を固定して考える差分更新累積和 TopCoder

すごく面白かった！問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列が IOI 文字列であるとは、ある正の整数が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。いま、"I", "O", "?" のみか…