AOJ

AOJ 2294 Entangled with Lottery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2294 解法 ゴールから見るDPでやります.dp[i][j][k] := 高さ (H から) i まで見た時に,位置 j にいて,それまでに猫が k 本引いているような確率とします. 高さ 1 から i までに,うさ…

AOJ 2556 Integer in Integer

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2556 解法 やり方は色々あると思うんですが,僕は桁DPっぽくやりました(正直実装方針かなりミスっていると思う.)まず,[0..N] までの答え f(N) を求めることができれば,f(B) - f(A - 1…

AOJ 2614 Almost Same Substring

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2614 解法 ローリングハッシュでやります.同じ長さの文字列 S, T に対して,「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます. も…

AOJ 2605 Social Monsters

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2605 解法 制約をよく読むと,(使えない辺を含める)与えられたグラフにおける各連結成分は,1つのパスまたは閉路になっていることがわかります. 各連結成分において計算して,最後にま…

AOJ 2449 Connect

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449 解法 これは典型問題です. $i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは,$i$ 行目の $1$ から $j - 1$ 列目と,$i - 1$ 行目の $j$ から $C$ 列目だけです…

AOJ 2376 Disconnected Game

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 解法 石取りゲームだからいい感じにわかるんでは?と思ったけどよくわかんなかったのでメモ化再帰で解きます.勝ちが決まるタイミングはは,連結成分の数が2であり,かつ自分の手番で…

AOJ 2313 Box Witch

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313 解法 ちゃんとフローがわかってるなら解ける問題. まず辺の追加クエリは簡単で,単純に辺を増やすだけ. 問題は辺の削除クエリです.与えられた辺を $\{a, b\}$ とします. 今流れて…

AOJ 2344 Multi Ending Story

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2344 解法 木DPで解きます. まず部分木に注目しましょう. 冷静に考えると,この部分木のすべての葉を回収するのには,以下の3通りだけしかありません.この部分木の根を $v$,左右の子を…

AOJ 2598 Website Tour

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2598 解法 移動に時間がかからないので,各強連結成分においては,好きな広告を(制限以内なら)好きな回数だけ見ることが出来ます.これは典型的な個数制限付きナップザック問題です.あ…

AOJ 1338 Clock Hands

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1338 解法 まず,それぞれの針がなす角を求めましょう.短針が1周するのに$H$時間かかるとします. 今時刻が $h:m:s$ である時,針が上を向いている状態を 0 度とすると,長針,短針,秒針…

AOJ 2436 Card

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2436 解法 カードの数字同士を足すわけではなくそのまま並べるので,桁に注目したいなーという気持ちになります. しかも $a[i]$ は高々4桁なので嬉しいです.こういう問題は,すべての数…

AOJ 2725 Live Programming

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725 問題概要 催し物を時間 $T$ だけ開催することになった. そこで歌う歌の候補が $N$ 個あり,それぞれの歌はパラメーター $t[i], p[i], f[i]$ を持つ.$t[i]$ は歌の長さ,$p[i]$ は歌…

AOJ 2606 Perm Query

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2606 解法 まず,制約を読むと,ある項についてたかだか40回の遷移で元に戻ることがわかるので,愚直にこれを求めます. このとき,それぞれの項が c[i] 回 で元に戻るとします. すると,…

AOJ 2617 Air Pollution

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2617 解法 この問題を解く上でポイントとなるのは,大気を循環させたときに,(p[i-1], p[i], p[i+1]) の累積和が不変であるということです.今大気の状態が (a, b, c, d) であるとしましょ…

AOJ 1301 Malfatti Circles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301 解法 まず,一つの円を決め打ちします. すると,残りの2円の位置は,二分探索などをして求めることが出来ます. ここで,残りの2円が離れすぎている場合,最初に決め打ちした円が小…

AOJ 2309 Vector Compression

問題文 まず問題読解が難しかった. http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2309 問題概要 N次元のベクトルが M 個与えられる.これを v[1], ..., v[M] とする. M 個のベクトルを好きな順番に並べ替え,その順に記録していく.記録する…

AOJ 2446 Enumeration

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446&lang=jp 解法 簡単のために,試しに2つの数字 a, b を用意して考えてみます.a, b が選ばれる確率をそれぞれ p, q とします. まず,a のみを選んだ場合の期待値は, (m / a) * p * (…

AOJ 2611 Ordering

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2611&lang=jp 解法 問題文を丁寧に読まなければならない問題です. 「それぞれの塔は自分自身よりも大きな塔とは高々1回しか比較されていない」とあるので,与えられた関係 (a, b) を有向…

ACPC2014 Day2 I Hard Beans

問題文 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day2&pid=I 解法 WaveletMatrixで殴ると通ります. 具体的には,区間の何番目の値が D との大小関係の境界になっているか quantile で二分探索するだけです. ソースコード #inc…

AOJ 2372 IkaNumber

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372 解法 問題文を言い換えると,フィボナッチ数同士の積で表される数で K 番目に小さいものは何か?という問題です. 実験すればなんとなく規則性が見えてきます. 自分は fib(n) * fib(…

AOJ 2159 Symmetry

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2159 問題概要 点が N 個与えられる.これらすべての点で,自己交差しないように辺を結ぶことで線対称な多角形を構成できるか判定せよ. ただし,点は多角形の順番(反時計回り or 時計回…

AOJ 2336 Spring Tiles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2336 解法 最適な戦略を取った場合,各マスの移動は確率的に決まるわけではなく,ある基準によってバネに向かうかゴールに直接向かうか定まっているはずです. 問題はなにが基準なのかです…

AOJ 0636 フェーン現象(Foehn Phenomena)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0636&lang=jp 解法 B[i] = A[i] - A[i + 1] という数列 B[i] を考えるのが良いです. すると,A[l] から A[r] の変化が x だとすると,B[l - 1] と B[r] にしか影響を及ぼさないことがわか…

AOJ 0627 Train Fare (鉄道運賃)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0627 解法 まず首都からの最短経路を求めるほかどうしようもないので,BFSで最初に求めておく. このとき,任意の頂点について,すべての最短経路でのその頂点の親と子を求めておく. 経路…

AOJ 2751 BaseBall (野球観戦)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2751 問題概要 2つのチーム(X と Y と呼ぶことにする)が,合計 A + B + C 回試合を行った. A は X が勝利した回数 B は Y が勝利した回数,C は引き分けた回数である. また,X と Y は…

AOJ 1358 Sibling Rivalry

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1358 解法 終点から更新していくベルマンフォードのように解いた. まず,各頂点から a, b, c で行ける頂点を予め求めておく. d[v] := その頂点から終点に必ずたどり着けるなら,その時の…

AOJ 1613 Deciphering Characters

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613&lang=jp 解法 包含関係は,一番背景連結成分を根とした木構造になっていることがわかる. よって,背景連結成分を根として,各再帰段階でBFSをするDFSを行えば,その木構造が得られる…

AOJ 1615 Gift Exchange Party

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615 解法 友人の助けを借りて解いた.この問題は最大流の問題に帰着させることができる.(想定解は違う方法だった.) まず,二部グラフ {V1, V2} をつくる.V1 は n 頂点からなり,各人…

AOJ 2237 The Castle

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2237 解法 bitDP.dp[i][S][j] := i 番目(0-indexed) の敵と j 番目のねこが戦っていて,生き残っている猫が S であるときの勝てる最大確率とする.このDPテーブルを最後の敵から最初の敵…

AOJ 1359 Wall Clocks

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1359 解法 各点から半直線が2本出て,長方形の周上の2点で交わるが,それをそのまま処理すると面倒. なので,(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して,[0, …