250 うなぎ コーナーケース多そうなので気をつけて書いた。 いろいろテストしてからsubmit。 500 文字列の問題 2分割されるから2^20*20*20くらいではできるな。 そもそもコレって解は常に同じ文字列になるんじゃないの？ naiveなもの実装したらそうっぽい。 …

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3228 問題 文字列Aとクエリがn個与えられる。クエリには2つのタイプがあり、1つ目のタイプのクエリは文字列siが文字列Aの中に何回出ているかを数える物で、2つ目はoverlapを考えない場合の数…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3396 問題 3頂点シュタイナー木のコストを求めよ。 解法 3頂点シュタイナー木なので分岐する箇所を全通り試せば良い。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3405 問題 整数Nを素因数分解したい。図のようにNを素因数分解する時に2つの数値ずつに分けることを繰り返して計算を行う。分解の仕方は何通りか？ 2 答えは64bit signed integerに収まる。 …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107 問題 略 解法 辺の数が50と少ないので、最後に使った辺+どちらの頂点に行ったかで状態を保存し、その遷移行列を作る。この行列をz乗すればちょうどz歩でn-1の頂点に辿りつけるかどうか分かる…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2308 問題 Angry Birdというゲームがある。このゲームは鳥を初速度vで投げ飛ばし、豚にむかって卵爆弾を落とすゲームである。鳥は投げ飛ばすと放物線運動をし障害物にぶつかるまで移動する。豚に…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2193 問題 略 解法 実質的に3頂点のシュタイナー木を求める問題になる。なのでレノンのいる場所から頂点vまで行き、なつめのいる場所により、また元の位置vまで戻ってきて、夏への扉へ向かえば良…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2190 問題 略 解法 後ろから見ていけば最後に踏む段でしか分岐しないのでシミュレートすれば良い。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2189 問題 略 解法 どんな順序でやっても手番の数は変わらないのでシミュレートすれば良い。

http://www.spoj.pl/problems/BOXES/ 問題 n個の箱が円形にならんでいる。各箱にはki個のボールが入っている。ボールを箱から一つ取り出して隣の箱に入れる操作のみが行える。全ての箱に1個以下のボールが入っている状態にするためには何回操作を行わないと…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2338 問題 略 解法 二重連結成分内では閉路を作ることによって全ての呪文を唱えることが出きるようになる。なので二重連結成分を縮約し、重み付き木にする。この木にたいしていくらの重みが入り出…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2339 問題 略 解法 Grundy Number + Nimらしい。詳しくは解説参照。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2336 問題 略 解法 各マスからゴール・バネまでの距離を計算しておいて、バネに乗った後のゴールまでの距離の期待値を2分探索で求める。答えはかなり大きくなるので注意。あと誤差が厳しいのでlong…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335 問題 略 解法 右方向に寄り道する回数をi回とする。この時左右方向の進み方はカタラン数の計算方法を応用して計算するとCombination(n+2*i,i) - Combination(n+2*i,i-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 問題 略 解法 レーザーを出す角度を使った平面走査で解く。答えが変わる角度はセルの右下の頂点を通る時であるのでそこをイベント点に突っ込む。各イベント点では同じ角度のイベント点を全て…