2011-12-04から1日間の記事一覧
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337 問題 略 解法 DP+尺取メソッドで解く。まずオス、メスを考慮せずにcuteが低い順にソートする。次にcuteの上界と下界を固定してDPを計算する。DPは2*Wの大きさで、各性別について重さwのねこ…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334 問題 略 解法 街ABか街CDのどちらかは直接道を作ったほうが良い。なので両方試してダイクストラとかで最短距離を計算すれば良い。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333 問題 略 解法 まず重さの低い順にソートをしておく。次にindex番目の友達以降を使って作れる重さを計算しておく。あとはindex番目の友達をリュックに入れない友達の中で最も軽い友達とした時…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332 問題 略 解法 BFSするだけ。pマス進めの命令は経路圧縮しながらdfsする。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331 問題 略 解法 FenwickTreeを使って、それぞれの人について[a,b]の範囲に+1しておく(aで+1、b+1番目で-1する)。あとはi番目の和がi以上になるかどうかチェックするだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330 問題 略 解法 答えはになる。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2319 問題 略 解法 片方の経路をfixし、もう一方の経路で最短路を見つける。validな経路はそこまで多くないので枝刈りをすれば間に合う。難しすぎるので詳しいことは略。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2318 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 問題 略 解法 紐をまとめて切るだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2316 問題 略 解法 やるだけ。鋭く凹んでる場合に今の軸の反対側の頂点が次の軸になることがあるので注意。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2315 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2314 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2312 問題 略 解法 DPで解く。大きい数値は隣接して置いた方が良いので、一番大きい数値を置いた後に、残りの数値を大きい順に左端か右端に順々に置いていけば良い。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311 問題 略 解法 やるだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2310 問題 略 解法 レーザーを出す角度を使った平面走査で解く。答えが変わる角度はセルの右下の頂点を通る時であるのでそこをイベント点に突っ込む。各イベント点では同じ角度のイベント点を全て…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2280 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2279 問題 略 解法 列・行は別々に解いて良い。山を構成できるかどうかはN個のベクトルの半順序を計算し、DAGにした後、ルートが存在するかどうかと、そのDAGが2つのパスで被覆できるかを2部グラ…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2278 問題 略 解法 一番左端のプレート2つを考えるとエネルギーを右側に全力でかけるか、両方のプレートで同じだけの熱を与えるようにエネルギーを掛けるかの効率の良い方を選択すれば良い。これ…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2277 問題 略 解法 1が返ってくるまでランダムな列をクエリに投げる。1が返ってきたら後は2分探索すれば良い。2回目以降は動作していると分かっているビットには0を入れておくこと。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2276 問題 略 解法 まず地点を[0,PI]の区間に直す。次に明らかにいらない区間を全て削除する。後はDPをすれば良い。普通にDPするとO(N^2K)かかるが、その区間を選ぶよりも明らかに良い区間がある…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2275 問題 略。 解法 区間篩 or Fox Numberでない数を全列挙。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274 問題 略 解法 validな列になるまで列をランダムで構成する。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2273 問題 略 解法 解説参照。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2272 問題 略 解法 DPするだけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2271 問題 略 解法 やるだけ。