問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2556 解法 やり方は色々あると思うんですが，僕は桁DPっぽくやりました（正直実装方針かなりミスっていると思う．）まず，[0..N] までの答え f(N) を求めることができれば，f(B) - f(A - 1…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2614 解法 ローリングハッシュでやります．同じ長さの文字列 S, T に対して，「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます． も…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2605 解法 制約をよく読むと，（使えない辺を含める）与えられたグラフにおける各連結成分は，1つのパスまたは閉路になっていることがわかります． 各連結成分において計算して，最後にま…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449 解法 これは典型問題です． $i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは，$i$ 行目の $1$ から $j - 1$ 列目と，$i - 1$ 行目の $j$ から $C$ 列目だけです…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 解法 石取りゲームだからいい感じにわかるんでは？と思ったけどよくわかんなかったのでメモ化再帰で解きます．勝ちが決まるタイミングはは，連結成分の数が2であり，かつ自分の手番で…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 解法 ちゃんとフローがわかってるなら解ける問題． まず辺の追加クエリは簡単で，単純に辺を増やすだけ． 問題は辺の削除クエリです．与えられた辺を $\{a, b\}$ とします． 今流れて…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2344 解法 木DPで解きます． まず部分木に注目しましょう． 冷静に考えると，この部分木のすべての葉を回収するのには，以下の3通りだけしかありません．この部分木の根を $v$，左右の子を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2598 解法 移動に時間がかからないので，各強連結成分においては，好きな広告を（制限以内なら）好きな回数だけ見ることが出来ます．これは典型的な個数制限付きナップザック問題です．あ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1338 解法 まず，それぞれの針がなす角を求めましょう．短針が1周するのに$H$時間かかるとします． 今時刻が $h:m:s$ である時，針が上を向いている状態を 0 度とすると，長針，短針，秒針…

問題文 http://arc057.contest.atcoder.jp/tasks/arc057_d 解法 メモ化再帰で解きます． $rec(C) := $連結成分の状態が $C$ であるような状態から始めたときに，条件を満たすような辺の張り方の総数$A[i]$ を小さい方から張って順に張っていくとき，$A[i]$に…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2436 解法 カードの数字同士を足すわけではなくそのまま並べるので，桁に注目したいなーという気持ちになります． しかも $a[i]$ は高々4桁なので嬉しいです．こういう問題は，すべての数…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725 問題概要 催し物を時間 $T$ だけ開催することになった． そこで歌う歌の候補が $N$ 個あり，それぞれの歌はパラメーター $t[i], p[i], f[i]$ を持つ．$t[i]$ は歌の長さ，$p[i]$ は歌…

問題文 http://codeforces.com/problemset/problem/311/B 問題概要 N個の地点があり，順に 0 から N-1 とする．地点 i と i + 1 の間の距離は d[i] である． また，猫が m 匹いて，猫 j は時刻 t[j] に地点 h[j] にあらわれるものとする．それぞれの猫は，餌…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2606 解法 まず，制約を読むと，ある項についてたかだか40回の遷移で元に戻ることがわかるので，愚直にこれを求めます． このとき，それぞれの項が c[i] 回 で元に戻るとします． すると，…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2617 解法 この問題を解く上でポイントとなるのは，大気を循環させたときに，(p[i-1], p[i], p[i+1]) の累積和が不変であるということです．今大気の状態が (a, b, c, d) であるとしましょ…

問題文 http://arc058.contest.atcoder.jp/tasks/arc058_c 解法 X, Y, Z が小さいので bitDP でやります． dp[i][S] := i 番目まで見たときに，直前の和が X + Y + Z 以下になるところまでの状態が S であるような場合の数 とします． たとえば，X = 5, Y = …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301 解法 まず，一つの円を決め打ちします． すると，残りの2円の位置は，二分探索などをして求めることが出来ます． ここで，残りの2円が離れすぎている場合，最初に決め打ちした円が小…

問題文 http://arc067.contest.atcoder.jp/tasks/arc067_c 解法 dp[i + 1][j] := i 人以下のグループのみを用いて，あと j 人グループ分けされてない人がいるときの場合の数 という dp で解けます． 遷移は，use == 0 または C $$\displaystyle dp[i + 1][j …

問題文 まず問題読解が難しかった． http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2309 問題概要 N次元のベクトルが M 個与えられる．これを v[1], ..., v[M] とする． M 個のベクトルを好きな順番に並べ替え，その順に記録していく．記録する…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446&lang=jp 解法 簡単のために，試しに2つの数字 a, b を用意して考えてみます．a, b が選ばれる確率をそれぞれ p, q とします． まず，a のみを選んだ場合の期待値は， (m / a) * p * (…

問題文 http://codeforces.com/contest/392/problem/B 問題概要 ハノイの塔のパズルの最小手数は 2^n - 1 であることは有名な事実であるが，今回は以下の問題を考えるとする． ある段を位置 i から位置 j に移すのにコストが t[i][j] かかるとするとき( 1 ・…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2611&lang=jp 解法 問題文を丁寧に読まなければならない問題です． 「それぞれの塔は自分自身よりも大きな塔とは高々1回しか比較されていない」とあるので，与えられた関係 (a, b) を有向…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day2&pid=I 解法 WaveletMatrixで殴ると通ります． 具体的には，区間の何番目の値が D との大小関係の境界になっているか quantile で二分探索するだけです． ソースコード #inc…

問題文 http://codeforces.com/contest/853/problem/B 問題概要 街が n + 1 あり，それぞれナンバリングされている．また人が n 人いて，人 i は街 i に存在する．0番目の街は首都であり，人はいない． ここで，飛行機のスケジュールが m 個与えられる．スケ…