AOJ

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 を一つ求める.…

AOJ 1330 Never Wait for Weights

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330 解法 基本は union-find をいじるだけ. 各ノードは,親からの相対重さを持つ. クエリで a, b, w が与えられたとする. a と b の代表元が異なる場合は,それぞれの集合の根を r1, r2…

AOJ 1318 Long Distance Taxi

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318 解法 単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので,少し違う方針で. まず,ガソリンスタンドについたら満タンにしてしまっていいので,ガソリンスタンドから cap …

AOJ 2726 Black Company

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2726 問題概要 N 人の従業員がいて,それぞれ成果を c(i) あげたとする.成果に応じて,報酬 p(i) を分配する. ただし,それぞれの従業員には親しい人が何人か存在する. 従業員 i が j と…

AOJ 2680 LR

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2680 解法 メモ化再帰.memo[l][r] で,s[l..r]の取りうる最大値,もし無ければ "invalid" を入れていく. 完全に数字に置き換えられるならそうして(当然それが最適),そうじゃないならLかR…

AOJ 2710 An Equation in a Mine

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710 解法 区間DP(メモ化再帰). ある演算子に注目して,左と右に分けて,再帰的に処理していくとよい. 演算子が + であれば,左も右も最大値を取るようにすればよい.-であれば,左を…

AOJ 2741 Invisible

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741 解法 メモ化再帰で解ける. memo[si][sj][i][j][turn][pass] := a(si)からa(i-1),b(sj)からb(j-1)までスタックに積まれていて,手番がturnかつパスの状態がpassであるときの最大値.(p…

AOJ 0575 Festivals in JOI Kingdom

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575 解法 実装できなかったので,eagletmt さんの解法を参考にした. AOJ 0575 - Festivals in JOI Kingdom - プログラミングコンテストの記録使うアルゴリズムとしては,DijkstraとKruskal…

AOJ 0519 Worst Reporter

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519 解法 a が b に勝利したことを,a -> b と有向辺で表現することにすれば,この問題はトポロジカル順序を求める問題になる. トポロジカル順序が求まったら,その頂点列のなかで隣り合っ…

AOJ 0526 Boat Travel

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526 解法 基本はワーシャルフロイドだが,それだと間に合わないので工夫する. 仮に島a, b間の船舶が更新された時,グラフ上の異なる2つの島u, vの最短経路は, u -> a -> b -> v つまり d[…

AOJ 0562 Shopping in JOI Kingdom

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562 解法 まず,各頂点がショッピングモールからどれだけ離れているかを求める. これは,ショッピングモールの頂点をあらかじめ全てpriority_queueに突っ込んでおいたダイクストラを解けば…

AOJ 0623 Zombie Island

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0623 解法 危険な街を列挙さえすれば,あとはただの単一始点最短路問題. 危険な街を列挙するには,ゾンビに支配された街を全て,最初にqueueにプッシュしておくだけで十分である.計算量…

AOJ 0616 JOI Park

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0616 解法 まず,0を始点としてダイクストラで,各点への最短路重みを求めておく. そして,その重みで頂点をソートしておく.また,あらかじめ辺全体の重みの総和を求めておく. Xの候補…

AOJ 0600 Baumkuchen

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0600 解法 累積和と二分探索. まず,バウムクーヘンの累積和を二周分求めておく. その後,左端を適当に定め,そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める.…

AOJ 0509 Sheets

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509 問題概要 平面座標に n 個の長方形がある.重なっていることもある. それらがつくる図形の面積と,周の長さを求めよ.・制約 1 長方形の左下,右上の座標の x, y 座標は,共に 0 以…

AOJ 0517 Longest Steps

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0517 解法 しゃくとり法でやった. 与えられた k 枚のカードをソートしておく. 0が含まれていれば1つだけ飛ばせるので,それは場合分けで処理. 行けるところまでいったら,左端をカード…

AOJ 0302 Star Watching

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0302 解法 星を輝度でソートする. 輝度の最小(つまり左端)を決めて,しゃくとり法でできる. 座標の最大最小は,priority_queueでもmapでもmultisetでもなんでもよい. 自分は最初 priori…

AOJ 0299 Railroad II

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0299 解法 d(i) をソートし,かつ p が 0 となるようにずらしておく. ちょっと考えると,解の候補としては d(1) まで反時計回りで一周する d(M) まで時計回りで一周する d(i) まで時計回り…

AOJ 0254 Scone

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0254 問題概要 数列 {a_n} と整数 M が与えられる. 適当な i ・制約 1 1 0 解法 累積和と二分探索. mod を取った累積和を sum(i) で表すことにする. 右端 j を固定すると,j までの累積和…

AOJ 0613 Treasures

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613 問題概要 N 個の財宝が与えられ,それぞれ市場価値 w(i)と貴重度 v(i) が決まっている. この財宝をAとBで分け合う.どちらも獲得しない財宝があってもよい. 分け合った後のAとBの財…

AOJ 0145 Cards

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145 問題概要 n 個のカードの山がある.カードには数字がかかれている. それぞれの山の一番上と下のカードの数字は a(i) と b(i) である. 2つの山を重ねる操作を繰り返して,一つの山に…

AOJ 0098 Maximum Sum Sequence II

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098 問題概要 n次正方行列(a_ij)が与えられる.(a_ij) の部分行列の要素の和の最大値を求めよ.・制約 1 解法 まず,要素の横方向について累積和を取る. その後,横方向のある区間[i, j]…

AOJ 1337 Count the Regions

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337 問題概要 xy 平面に長方形が N 個与えられる.長方形によっていくつの領域に分かれるか求めよ.・制約 1 長方形がある x, y 座標は 0 解法 N が小さいので座標圧縮と確信できる. 与え…

AOJ 2302 On or Off

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2302 問題概要 R * C のグリッドが与えられる.各マスは,部屋または壁を表している. さらに,M 個の仕事が与えられて,それぞれの仕事をする部屋は決められている.仕事は与えられた順番に…

AOJ 2156 Magic Slayer

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2156 問題概要 N 体のモンスターがいる.それぞれの体力は HP_i である. 自分が使える単体魔法と全体魔法がM個与えられる.それぞれの魔法には消費MPとダメージ量が決まっている. この時,…

AOJ 2442 Convex-Cut

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2442&lang=jp 問題概要 N 個の頂点からなる凸多角形が与えられる.このとき,ある点があって,その点を通る任意の直線がこの多角形を二等分することができるだろうか?できる場合は,その点…

AOJ 2303 Marathon Match

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2303 問題概要 N 人のランナーがマラソンをする.コースの長さは L で,休憩所が途中に M 箇所存在する.i 人目のランナーは,どの休憩所でも全く同じ Pi パーセントの確率で休憩を取る.一…

AOJ 2157 Dial Lock

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2157 問題概要 数列の連続した区間に同じ数を足し引きする操作によって,ある数列を目的に数列に一致させたい.このとき,目的を達成する最小の操作回数を求めよ.制約 : 数列の長さは10以下…

AOJ 2182 Eleven Lover

問題のリンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182 問題概要 ある自然数 N が与えられる.その連続部分文字列(0から始まるものを除く)で,11の倍数となるものはいくつあるか?制約: N の桁数は 80000 以下. 解法 DP で解くこ…