問題文 http://arc055.contest.atcoder.jp/tasks/arc055_b 解法 dp[i][j][ate_max] := i 番目まで見て，j 個食べていて，現時点で最大のものを食べている(ate_max: bool) 状態から始めたとき，最終的に N を食べられる確率 と定義する． dp[N][j][1] が，確…

問題文 http://codeforces.com/contest/516/problem/D 問題概要 木 T が与えられる．また，クエリが q 回投げられる．それぞれのクエリは L を投げてくる． 木 T の頂点 i に対して，i からそこから最も遠い葉までの距離を D(i) とする． 各クエリに対し，T …

問題文 http://joisc2015.contest.atcoder.jp/tasks/joisc2015_a 問題概要 文字列 S が与えられる． S に対して，クエリが N 個投げられる． 各クエリは A, B, C を持ち，これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する． 最…

問題文 https://csacademy.com/contest/archive/task/xor-closure/ 問題概要 N 項からなる数列 {a_n} が与えられる．この数列にいくつか数を追加して，以下の性質を満たすようにする． 相異なる任意の i, j に対して，a_i XOR a_j もまた数列 {a_n} に含まれ…

問題文 http://arc025.contest.atcoder.jp/tasks/arc025_3 解法 制約をみて，なんとなく全頂点を始点としてダイクストラできるなーと検討はつく． とりあえず，目的地を決め打ちしてしまって，目的地を始点にダイクストラする． その後，得られた距離 d[i] …

問題文 http://arc035.contest.atcoder.jp/tasks/arc035_c 解法 頂点数が小さいので，ワーシャルフロイドでよい． ただし，建設するたびにワーシャルフロイドすると間に合わない．よく考えると，x-y 間に橋を作ったときに最短経路が変わるのは，x-yを経由す…

問題文 http://arc023.contest.atcoder.jp/tasks/arc023_3 解法 典型 of 典型みたいな問題．L -1 -1 ... -1 R みたいな区間に分けて考えて，R - L を -1 にうまく分配するという問題になる． これはいわゆる重複組合せというやつ．高校数学でも頻出． という…

問題文 http://codeforces.com/contest/679/problem/B 問題概要 整数 m があたえられる．m 以下の整数 X で，以下を満たす (n, X) を求める． X を超えない最大の a^3 （立方数）を選び，X = X - a^3 と更新する． X に対して上記の操作を繰り返す． 上記の…

問題文 http://agc004.contest.atcoder.jp/tasks/agc004_d 解法 首都が自己辺でなければならないのは，すぐ分かる．（ぱっとわからなくても実験すればわかるようになってる．） あとは制約から，与えられたグラフが首都を根とする木になっていることがわかる…

問題文 http://codeforces.com/contest/698/problem/C 解法 10^100なので実質無限大の時間がたったと考えて良い． 正規マルコフだし，十分大きな時間が経過したあとは定常状態に落ち着く． この時，過渡状態にいる確率はほぼ0で，キャッシュは（できるかぎり…

問題文 http://codeforces.com/contest/587/problem/E 問題概要 n 個の数からなる数列 {a_n} が与えられる． また，q 個のクエリが投げられるものとする．クエリは以下の2種類． ただし，以降は + を XOR, * を AND とする． 1. l 2. a_l, ..., a_r からいく…

問題文 http://arc006.contest.atcoder.jp/tasks/arc006_3 解法 貪欲解で解くひとが多いと思うので，それ以外の解法を． この問題は，よく考えると「与えられたDAGの最小パス被覆を求めよ」と言い換えられる． 実際，x が y の上に積める，を y -> x という…