2017-08-17から1日間の記事一覧

ARC054 C - たい焼き

問題文 http://arc054.contest.atcoder.jp/tasks/arc054_c 解法 2部グラフの完全マッチングの個数の偶奇性を問う問題. 当然数え上げるのは大変.しかし偶奇だけなら,行列式でわかる.与えられた隣接行列を Aとする. すると,完全マッチングの個数 M は,A…

ARC050 C - LCM 111

問題文 http://arc050.contest.atcoder.jp/tasks/arc050_c 解法 1 が A 桁続いたものと,1 が B 桁続いたものの最大公約数 G は,1 が gcd(A, B) 桁続いたものになる. 例えば 111111 (A = 6) と 1111 (B = 4) の最大公約数は,1 が gcd(6, 4) = 2桁続いたも…

ARC055 B - せんべい

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

Codeforces Round #292 (Div. 1) D. Drazil and Morning Exercise

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