AOJ

AOJ 2850 Endless BFS

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2850 解法 01BFSで解いた。 まず、2部グラフだと永遠に終わらないことはわかる。 2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は…

AOJ 2847 Ninja Map

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2847 解法 まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。 一行目が埋まると、下の行の数は一…

AOJ 2858 Prime-Factor Prime

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858 解法 区間篩の要領で解ける。 [1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。 今回の場合は、素数 p が検出できたら、[L, R] …

AOJ 2593 Square in Circles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2593 解法 辺の長さをまず決め打つと、それぞれの円と交わる部分が区間として求まる。 得られた区間の連結な部分の総長さで、決めうった値よりも長い所があれば、そのような正方形を配置す…

AOJ 1620 Boolean Expression Compressor

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1620 解法 前もってすべての式を生成してしまえばOK。 真理値表は 16bit 分の情報があればよく、bitDP 的な要領で生成していけば良い。 つまり、キーが真理値表で、値がその最小長さである…

AOJ 2373 HullMarathon

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 解法 自分は数式で捉えて、ラグランジュの未定乗数法で解いた。 ラグランジュの未定乗数法については以下のサイトがわかりやすい(ただし厳密な証明はない)。 mathtrain.jp与えられ…

AOJ 0353 Sort

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0353 解法 とりあえず観察しないとよくわからない。 僕は観察してもよくわからなかったので、確実に言えることを探すことにした。 まず、一番小さい数は、左端に到達したら以降はもう動か…

AOJ 0323 Ruins

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0323 解法 二分探索するとよい。 海岸からの距離を y とすると、半円 i との交点の x 座標は、x[i] ± sqrt(r[i] * r[i] - y * y) となる。 これを区間と見て、すべての半円に対応する区間…

AOJ 1383 Pizza Delivery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1383 解法 始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺…

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) で解けます. 分割数…