AOJ

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, …

AOJ 1348 Space Golf

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1348 解法 完全にやるだけ.多少無駄なことをしても入力サイズが小さいので余裕で通る. ご丁寧に式が書かれているので,それに従って候補を全部列挙し,それらが条件をみたすか(つまり接触…

AOJ 2334 Roads on Towns

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334 解法 実は,A->B と C->D の少なくともどちらか一方は,直接結んでしまって良いことがわかる.そうすればあとは最短経路問題.以下は自分のイメージ. 例えば図のように,(解が存在し…

AOJ 2592 Flowers

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2592 解法 3分探索.(自分は黄金比探索を持ってたのでそれを貼り付けた.) 使う水の量が決まれば,使う肥料の量は一位に定まる.つまり,コスト関数はWのみを引数とする関数である. グラ…

AOJ 2595 Cookie Counter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2595 解法 1枚も食べない日を考えるとややこしい(し,Dがでかいのでそのまま求められない)ので,D 日のうち一枚も食べない日はあとで決めることにすればよい. つまり,まずは一日に最低…

AOJ 2570 Shipura

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570 解法 > が >> なのか S の > なのかは,数字またはSの直前かどうかで判定ができる. なので最初に式を後ろから見ていって,どれがシフト演算なのか確定させておく. それができればあと…

AOJ 2512 Ononokomachi's Edit War

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2512 解法 適当に置換 or 削除でminimax法だと明らかに間に合わないので,すこし考える必要がある. 冷静に考えると,N が偶数のときは2ターン,N が奇数のときは1ターンやるのと変わらない…

AOJ 2255 6/2(1+2)

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255 解法 BNFどおりに実装する必要はなくて,区間DPをすればよい. その区間で取りうる値の集合を持たせておく. 区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける. …

AOJ 1350 There is No Alternative

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1350 問題概要 連結グラフ G が与えられる.一般に G の最小全域木は複数存在しうる.G のすべての最小全域木に必ず含まれている辺を求めよ.・制約 3 N-1 解法 最小全域木 T を一つ求める.…