読者です 読者をやめる 読者になる 読者になる

AOJ 0613 Treasures

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613 問題概要 N 個の財宝が与えられ,それぞれ市場価値 w(i)と貴重度 v(i) が決まっている. この財宝をAとBで分け合う.どちらも獲得しない財宝があってもよい. 分け合った後のAとBの財…

AOJ 0145 Cards

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145 問題概要 n 個のカードの山がある.カードには数字がかかれている. それぞれの山の一番上と下のカードの数字は a(i) と b(i) である. 2つの山を重ねる操作を繰り返して,一つの山に…

AOJ 0098 Maximum Sum Sequence II

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098 問題概要 n次正方行列(a_ij)が与えられる.(a_ij) の部分行列の要素の和の最大値を求めよ.・制約 1 解法 まず,要素の横方向について累積和を取る. その後,横方向のある区間[i, j]…

TopCoder SRM 711 Div2 Hard TreeMovingDiv2

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

TopCoder SRM 709 Div2 Med Permatchd2

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

Codeforces Round #406 (div.2) C

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

AOJ 1337 Count the Regions

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

AOJ 2302 On or Off

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

AOJ 2156 Magic Slayer

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

TopCoder SRM 710 Div2 Hard MinMaxMax

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

AOJ 2442 Convex-Cut

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

AOJ 2303 Marathon Match

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

AOJ 2157 Dial Lock

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

AOJ 2182 Eleven Lover

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

ARC070 D - No Need

arc070.contest.atcoder.jp 解法(証明?) を降順にソートする. 今, が不必要かどうかを判定したいとする.この時, とおく. また, から までの和で表現できる 未満の数がわかっているとする.(dpで保存) その中の任意の数 について, であるならば,…