TL;DR set<int> st; lower_bound( st.begin(), st.end(), 0); // これは O(NlogN) lower_bound( 0 ); // これはO(logN) 解説 この前のABCでハマってしまった. 上のコード 下のコード 異様に遅いしlower_boundあたりがもしかして O(N) になってないか?と思って書き</int>…

はてなブログで数式をなんとかする mathjaxを導入します 参考 完 これは30秒ぐらいで終わります mathjaxが表示されなくてややハマった $$ f(n)=\sum_{0\leq i \leq n} i^2 $$ これをmarkdownでプレビューすると こうなるので $$ f(n)=\sum_{0\leq i \leq n} …

問題 解法 dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた ) として, i 開始の区間を考える. 半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1. 新しく [0,x) から [0,j) ( x < j ) まで消す場合 [ i, j ) は…

問題 解法 n文字からなる文字列の変換の典型として, 'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する この場合でも総和のmod3は保存されることがわかる. この非自明な必要条件が本質. 更に実験すればわかるが,1回以上の操作によって a[i] == a…

問題 反省 解法は解説見ればわかるのでなんで反省点のみ. {a}, {b} をsortして右下から入れていこうとしていた -> 明らかに煩雑. 典型要素として perm を考えるときには挿入/数字が入る場所から決めていく -> 上の数字から入れていくのを a_i = b_j = x なる…

メモ 17完. 解けない問題いっぱいあるなあ 集めるDPの方がバグらせにくくて(当社比),メモ化にもしやすいのでほぼそっちで書いた. 簡潔なまとめはプロのツイッターを見るのが良い. DPコン、解法全部書いた。 https://t.co/BqSnOQIkbR— ꑄ꒖ꐇꌅꏂ (@snuke_) 2…

問題 問題概要 一部が -1 である [1,N] のpermが与えられる. 各-1に等確率で残りの数が入る時,転倒数の期待値を求めよ. 解法 A = もともとある数, B = -1の場所に入る数 とする. A-A, A-B, B-B の期待値を足せば良い. A-A はBITを使って数え上げる. B-B は b…

問題 解法 お絵描きしたのでメモ. 部分点は O(N2) の区間DP. それ以上に早くやるにはどうするか. 遷移が O(1) なので状態を減らすしかない. しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない. よってある状態(操作)を禁止して状態を減らすことを…

問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…