AOJ

AOJ 2172 - Queen's Case

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2172 解法 ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。 これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい(どの問題…

AOJ 2587 - Elevator Hall Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2587 解法 桁DPしようと思ったが、遷移がうまく書けないので困った。 そこでオートマトンをイメージする。 結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。…

AOJ 1317 - Weaker than Planned

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 解法 普通のバックトラックで解ける。 バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。 今回なら、文字の種類数が多い方を先に考え…

AOJ 1307 - Towns along a Highway

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307 解法 こういうのは確定できるところからさせるもの。 とりあえず一番遠いところは unique に定まるので確定させる。 次は、残ってる d の中で最も大きい値を選ぶ。 こいつは、明らか…

AOJ 1322 - ASCII Expression

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322 解法 今の左端と、上下の区間を持ちながら構文解析を書く。 base の位置は左から見ていって、初めて空白以外が現れた行としてよい。 分数表記のときに余計な space がたくさん入るこ…

AOJ 2017 - Karakuri Doll

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017 解法 行きの位置、向き、戻りの位置、向きを同時にもって遷移するだけなんだけど、結構めんどくさい。 一番楽なのは DFS で1マスずつ動かしていくのだと思う。 曲がれるタイミングは…

AOJ 2623 - Optimal alpha beta pruning

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2623 解法 普通にαβ法をメモ化再帰でやるだけ。minimize も maximize も同じ。 dp[v][alpha][beta] := negamax(v, alpha, beta) で最善の選び方をした時の解子供の順番は next_permutation…

AOJ 2646 - Tournament

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646 解法 全探索を考えるところから。 n が小さくで列を愚直に持てるとしたら、次の全探索を考えるはず。 res(l, r, rank) := 区間 [l, r) における勝者の最終順位が rank になるときの最…

AOJ 2786 - Share the Ruins Preservation

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2786 解法 Andrew's Monotone Chain を左右からやっていくだけ。 有名な(?)蟻本の実装だと多角形の表現にするために半時計回りにやっているけど、今回はそんなことせずに、上側も下側も…

AOJ 2690 - Content Delivery

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2690 解法 各頂点について一番遠いところを貪欲に選ぶだけ。 一番遠いところへのパス以外はそこで切って、vector かなんかに突っ込んでおけばよい。 m がでかいけどどう考えても n^2 のオ…

AOJ 2743 - Land Inheritance

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743 解法 全探索をちょっとだけ早くするだけ。 n n == 4 のときは、土地を使い切らない方法で最適なものがありうる。 具体的には螺旋っぽく配置するというもの。真ん中がぽっかり開いてる…

AOJ 2692 - ICPC Teams

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2692 解法 包除原理。 チームにしないといけない組は確定で組ませる。 また、チームにしてはいけない組のすべての部分集合に対して、その集合に含まれる組は確定でチームを組ませるとする…

AOJ 1628 - Floating-Point Numbers

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1628&lang=jp 解説 実装するだけ。 仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。 a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。 それを今の値に足し…

AOJ 2604 - Pattern Language

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2604\ 解法 変数は 10 個しかないので、それぞれの変数を何桁にするか最初に全探索する。 すると、変数の桁ごとに、どの桁と対応するかを決定できる。 対応する集合を union find 木かなに…

AOJ 1388 - Counting Cycles

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1388 解法 m つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。 よく考えると、次数が 2 以下の頂点…

AOJ 2686 - Unfair Game

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2686 解法 自明ケースからちょっとずつ難しくしていくのが良いと思った(実験しても良いかも)。 a == b 同じ条件なので Nim (grundy 数) に帰着可能。 ある山の石の個数を s とすると s %…

AOJ 2250 - Operator

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2250 解法 二分探索やるだけじゃーんとなってサンプルチェックして違うことが判明するやつ。見事に引っかかってしまった。良い性質がないか観察してみると、少なくとも可能かどうかの人数…

AOJ 2861 RPG Maker

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2861 解法 典型構築だと思われる。 4n - 1, 4m - 1 であることが重要で、この制約のためにすべてのマスを回収するようなパスが存在する。 イメージとしては蛇のようにうねうねしながら移動…

AOJ 1382 Black or White

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1382 解法 いかにも DP の高速化をする見た目をしている。 DP を考える前に、操作を観察する。 色々実験などして考えてみると、 ある位置を3回以上塗るのは最適ではなさそう 2つの区間を違…

AOJ 1622 Go around the Labyrinth

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622 解法 右手法かフロー(最大流)で解けるが、今回はフローで解く。 フロー解は割と一発ネタなところがある。まず、各マスを2つの頂点に倍化(入力ノード、出力ノード)し、これら2つの…

AOJ 2785 Escape from the Hell

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2785 解法 とりあえず C[i] については無視して考えてみる。 最終日に使うドリンクを決めたとする。このドリンクを k とする。 すると、L - a[k] をできるだけ早く達成したいということに…

AOJ 2884 Tanka Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2884 解法 二分探索 + 桁DP ……ではなく貪欲に解く。 基本的に上の桁から順番に数字を確定させていって、 n 番目を超えないギリギリを選択する、というよくあるやり方。 当然だが各桁は小さ…

AOJ 2787 Pipe Fitter and the Fierce Dogs

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2787 解法 一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。 それ以外については、一旦 special pipe を使わないとして考え…

AOJ 2432 Sports Days 2.0

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2432 解法 行列累乗で解く。 A[u][v] := u -> v のウォークで最大となるもの と定義すると、A を n 回かけた行列 An は、長さ n のウォークについて考えたものになる。これは超典型。 行列…

AOJ 0389 Dungeon 2

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0389 解法 木DP。つらい。 以下自分の解き方を書くけど、他の人のコード読む限り状態数はまだ減らせそう? すくなくともテーブルでもつ必要のある状態は減らせると思う。まあいいか。まず…

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 的な要領で生成していけば良い。 つまり、キーが真理値表で、値がその最小長さである…