問題 https://community.topcoder.com/stat?c=problem_statement&pm=14556 問題概要 与えられた引数にしたがって， 頂点数が n の m 個の木を構築します． それぞれの木を T(i) とします． 各 i = 0, 1, ..., m-1 について，辺 e(i) ∈ T(i) を一つ選びます．…

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14539 問題概要 「グラフが "pretty" である」を，「グラフに含まれる任意の連結成分 S に対して，|E(S)| が偶数である」と定義する． ここで，単純グラフが1つ与えられる．このグラフを "…

問題 http://codeforces.com/contest/787/problem/C 問題概要 円上に n 個のマスがある．それぞれ 0 から n-1 まで番号が振られている． 0 番目はブラックホールである． また，どこかのマスに一匹のモンスターがいる． これらを使って2人でゲームをする．2…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337 問題概要 xy 平面に長方形が N 個与えられる．長方形によっていくつの領域に分かれるか求めよ．・制約 1 長方形がある x, y 座標は 0 解法 N が小さいので座標圧縮と確信できる． 与え…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2302 問題概要 R * C のグリッドが与えられる．各マスは，部屋または壁を表している． さらに，M 個の仕事が与えられて，それぞれの仕事をする部屋は決められている．仕事は与えられた順番に…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2156 問題概要 N 体のモンスターがいる．それぞれの体力は HP_i である． 自分が使える単体魔法と全体魔法がM個与えられる．それぞれの魔法には消費MPとダメージ量が決まっている． この時，…

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14545 問題概要 頂点数 N, 辺の数がM の連結グラフが与えられる． それぞれの頂点と辺には重みがつけられていて，i 番目の頂点の重みは vi, i 番目の頂点の重みは wi である． 異なる2つの…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2442&lang=jp 問題概要 N 個の頂点からなる凸多角形が与えられる．このとき，ある点があって，その点を通る任意の直線がこの多角形を二等分することができるだろうか？できる場合は，その点…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2303 問題概要 N 人のランナーがマラソンをする．コースの長さは L で，休憩所が途中に M 箇所存在する．i 人目のランナーは，どの休憩所でも全く同じ Pi パーセントの確率で休憩を取る．一…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2157 問題概要 数列の連続した区間に同じ数を足し引きする操作によって，ある数列を目的に数列に一致させたい．このとき，目的を達成する最小の操作回数を求めよ．制約 : 数列の長さは10以下…

問題のリンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182 問題概要 ある自然数 N が与えられる．その連続部分文字列（0から始まるものを除く）で，11の倍数となるものはいくつあるか？制約: N の桁数は 80000 以下． 解法 DP で解くこ…

arc070.contest.atcoder.jp 解法（証明？） a[i] を降順にソートする． 今，a[i] が不必要かどうかを判定したいとする．この時，Si := a[1] + a[2] + ... + a_[i] とおく． また，a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする．…