問題 反省 解法は解説見ればわかるのでなんで反省点のみ. {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を定数倍高速化しようとしたが無理だった. これは約数を全…