2011-12-01から1ヶ月間の記事一覧

SRM528 div1

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

Searching the String (ZOJ Problem Set - 3228)

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

Conference Call (ZOJ Problem Set - 3396)

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

Counting Factor Trees (ZOJ Problem Set - 3405)

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

いけるかな? (AOJ 2107)

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

White Bird (AOJ 2308)

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

夏への扉 (AOJ 2193)

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

天使の階段 (AOJ 2190)

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

足し算ゲーム (AOJ 2189)

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

Boxes (SPOJ 371)

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

よくわかる二重魔法 (AOJ 2338)

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

問題文担当者は働かない! (AOJ 2339)

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

スプリング・タイル (AOJ 2336)

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

10歳の動的計画 (AOJ 2335)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335 問題 略 解法 右方向に寄り道する回数をi回とする。この時左右方向の進み方はカタラン数の計算方法を応用して計算するとCombination(n+2*i,i) - Combination(n+2*i,i-1)になる。上下方向も同…

ねこ鍋改造計画(仮) (AOJ 2237)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337 問題 略 解法 DP+尺取メソッドで解く。まずオス、メスを考慮せずにcuteが低い順にソートする。次にcuteの上界と下界を固定してDPを計算する。DPは2*Wの大きさで、各性別について重さwのねこ…

街を駆ける道 (AOJ 2334)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334 問題 略 解法 街ABか街CDのどちらかは直接道を作ったほうが良い。なので両方試してダイクストラとかで最短距離を計算すれば良い。

僕の友達は小さい (AOJ 2333)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333 問題 略 解法 まず重さの低い順にソートをしておく。次にindex番目の友達以降を使って作れる重さを計算しておく。あとはindex番目の友達をリュックに入れない友達の中で最も軽い友達とした時…

時空のスゴロク・ロード (AOJ 2332)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332 問題 略 解法 BFSするだけ。pマス進めの命令は経路圧縮しながらdfsする。

友だちの誘い方 (AOJ 2331)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331 問題 略 解法 FenwickTreeを使って、それぞれの人について[a,b]の範囲に+1しておく(aで+1、b+1番目で-1する)。あとはi番目の和がi以上になるかどうかチェックするだけ。

雅先生の地球侵略日誌 (AOJ 2330)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330 問題 略 解法 答えはになる。

ソウルジェムゲーム (AOJ 2319)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2319 問題 略 解法 片方の経路をfixし、もう一方の経路で最短路を見つける。validな経路はそこまで多くないので枝刈りをすれば間に合う。難しすぎるので詳しいことは略。

舞台装置の魔女 (AOJ 2318)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2318 問題 略 解法 解説参照。

委員長の魔女 (AOJ 2317)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 問題 略 解法 紐をまとめて切るだけ。

人魚の魔女 (AOJ 2316)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2316 問題 略 解法 やるだけ。鋭く凹んでる場合に今の軸の反対側の頂点が次の軸になることがあるので注意。

影の魔女 (AOJ 2315)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2315 問題 略 解法 解説参照。

落書きの魔女 (AOJ 2314)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2314 問題 略 解法 解説参照。

ハコの魔女 (AOJ 2313)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 問題 略 解法 解説参照。

魔法少女さやかちゃん (AOJ 2312)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2312 問題 略 解法 DPで解く。大きい数値は隣接して置いた方が良いので、一番大きい数値を置いた後に、残りの数値を大きい順に左端か右端に順々に置いていけば良い。

お菓子の魔女 (AOJ 2311)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311 問題 略 解法 やるだけ。

薔薇園の魔女 (AOJ 2310)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2310 問題 略 解法 レーザーを出す角度を使った平面走査で解く。答えが変わる角度はセルの右下の頂点を通る時であるのでそこをイベント点に突っ込む。各イベント点では同じ角度のイベント点を全て…