AOJ

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

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 度とすると,長針,短針,秒針…