AOJ

AOJ 2702 Alternate Escape

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2702 解法 後退解析で解く. ゲームの探索なので,最初は始点からDFSしたくなるかもしれないが,普通に状態が自分に戻ってくるような遷移があるので困る. こういうときは確定しているとこ…

AOJ 0324 Downhill Race

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く. 与えられるグラフはDAGになっていて,この上で2回違う条件で最短経路を求めたい.しかし依存関係にあるので独立にはできない. こういうときは1回目と2回…

AOJ 0322 Slates

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける. 左が欠けているやつを考えるときは末尾から比べたいので,各文字を反転した文字列集合も別に持っておく. 与えられた石版に ? がある場合は26文字全通り試す…

AOJ 0321 Investigation of Club Activities

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽? union find の各集合がどのクラブに属するかを別に vector で持っておく. a と b が同じ部活に所属している場合,マージするのだが違うクラブに属し…

AOJ 2693 JAG-channel II

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2693 解法 いかにもな bitDP 感がある. しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える. うまくやれば状態に順列持てたりしないかな~と制約を読むと N -…

AOJ 2390 AYBABTU

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390 解法 感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう. そして投げたら通った(終了)…だと困るので厳密じゃないけど一応それっぽいのだけ.木なので基地…

AOJ 1342 Don't Burst the Balloon

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1342 解法 3次元幾何に見せかけた2次元幾何. 球の半径Rを決めた時,上から見て中心をどこにおけるかをイメージする. すると針と球の条件は,ある円があってその外側に中心を置く,という…

AOJ 2558 Medical Inspection

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2558 解法 最小点被覆は多項式時間で解けない. この時点で,グラフにある良い性質を用いるか,頑張って枝刈りしかない. しかし与えられたグラフは単純グラフであるだけで他にいい感じの…

AOJ 2541 Magical Bridges

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2541 解法 特別な辺のコストを定めた時,それぞれの最短経路長がすぐに求まってくれないと困る. そこで特別な辺は100個しか無いことを利用し,とりあえず以下のダイクストラをやる.d[i][…

AOJ 2434 Audition

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434 解法 他のそれぞれのアイドルの得点の期待値は,3種類の要素の得点の確率変数をX, Y, Z とすると E[X + Y + Z] だが,これは期待値の線形性から E[X] + E[Y] + E[Z] と等しい. した…

AOJ 1324 Round Trip

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 解法 最短経路(それはそう). 同じ高さの街が高々10しかないので,どの街に行ったか 2 ^ 10 で表現したい. どの街に行ったかを保存しつつ最短経路をやりたいね,となる. それには…

AOJ 2703 Dice Stamp

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703 解法 明らかに全てのサイコロを使うのが最適. あとは,後ろから見るbitDPで解く. これは,最後に使うサイコロから決めていくと,その直前に使うサイコロによる得点が,今まで使った…

AOJ 2572 Venn Diagram

問題文 Venn Diagram | Aizu Online Judge 解法 頑張って実装するだけ. 円の半径は入力からすぐわかる. 2つの円の距離を二分探索で求めたら,でかい方を左下隅に配置. 小さいほうは [0, pi/2] でどの角度に置くとよいかを判定.計算したくないので二分探…

AOJ 1252 Confusing Login Names

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1252 解法 以下の4パターン全部試すだけ. swap しない(単に編集距離の問題) 1回swapしたあと編集距離 2回swap 消した後 swap 最悪 200(200-1)/2 * 16 * (16 * 16) なので,まあ適当にや…

AOJ 1371 Infallibly Crack Perplexing Cryptarithm

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1371 解法 現れうる文字は高々8種類しかない. なので各文字に対して何を割り当てるか全探索して構文解析するだけ. ソースコード #include <bits/stdc++.h> using namespace std; using ret_type = doubl</bits/stdc++.h>…

AOJ 1351 Flipping Parentheses

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351 解法 StarrySkyTree + 二分探索で通した.( を +1, ) を -1 として累積和をStarrySkyTree上で管理する. 文字列が balanced であることと,累積和上の最小値が 0 以上であり,かつ末…

AOJ 1333 Beautiful Spacing

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 解法 二分探索+しゃくとり法. 二分探索は,普通に「スペースの隙間を X にして条件をクリアできるか」でやる.次にしゃくとり部分.二分探索の過程で与えられた,空けていい間隔を …

AOJ 0597 Xiao Long Bao

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0597 解法 汁が飛び散る範囲が小さいので,それを利用します. ある連続する8個の区間を考えると,そのなかで各小籠包がどの順で食べられるかさえわかれば,答えを求めることができます. …

AOJ 1386 Starting a Scenic Railroad Service

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1386 解法 一方はいもす法やるだけなのはすぐわかると思います. もう一方が問題ですが,これも累積和で簡単に求まります. じつは,乗客 i のデータの区間 [a[i], b[i]] に対して,端点以…

AOJ1133 Water Tank

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1133&lang=jp 方針1 いわゆるやるだけ問題ですが,頑張って通して満足するだけで終わると得られるものがなさそうな問題. こういうので実装方針を詰める練習をしなければいけないと思う(…

AOJ 0537 Bingo

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537 解説 言い換えると $1 \leq a_1 $a_1 + a_2 + \ldots + a_n = S$ をみたす $a_n$ の作り方を求める問題で,O(NMS) の解法はすぐわかると思いますが,実は O(NS) で解けます. 分割数…

AOJ 1281 The Morning after Halloween

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1281 解法 この問題はやるだけなんですが,TLEとMLEをうまく回避するのが大切な問題です.定数倍遅くなりそうな部分はできるだけ排除していく必要があります. 基本BFSをやっていくだけな…

AOJ 1238 True Liars

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1238 解法 人をノードと見て,x y a を辺と考えると良い.ある人を仮に divine あるいは delivish と定めると,その人と関係のある人間の性質が一意に定まる. よって,関係のあるグループ…

AOJ 2731 Shifting a Matrix

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2731 解説 シフト操作 F について,F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば,あとはこれらを結合するだけです.操作 F, G に対し,これらをこの順に結合した操作 H は…

AOJ 1361 Deadlock Detection

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1361 解法 求めるものは unavoidable になる境界なので二分探索できそうです. ある時刻からデットロックを避ける最良の方法は,当然 terminate できるプロセスを順に殺していくことです.…

AOJ 1362 Do Geese See God?

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1362 問題概要 文字列 S を部分列(部分文字列ではない)に持つような最小の長さの回文の集合の中で,辞書順 k 番目のものを求めよ. ・制約 1 1 解法 区間DPをやります.作れる文字列の数…

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つのパスまたは閉路になっていることがわかります. 各連結成分において計算して,最後にま…