AOJ

AOJ 1629 正三角形の柵 (Equilateral Triangular Fence)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1629&lang=ja 解法 底辺の y 座標を決めうったとする.これを \(y_l\) とおく. \(y \geq y_l\) をみたすある点 \((x, y)\) が正三角形の内部にあるための条件は,底辺の左端と右端の x 座…

AOJ 1623 等積変形 (Equivalent Deformation)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1623&lang=jp 解法 点を合わせる順番と対応を全部試して探索するだけで解ける. 点を合わせるときは,直接合わせられる場合は直接合わせればよいし,そうでない場合は残りの2点のどちらか…

AOJ 2559 Minimum Spanning Tree

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559 解法 マージテクだけで解ける. 最初に MST を構成しておく.MST に含まれない辺は自明. 以下MSTに含まれる辺についてコストを求める. MST 上を DFS で探索し,各部分木から外に生…

AOJ 2907 Prefix Suffix Search

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907 解法 \(w_i\) をそれぞれ逆にした文字列集合を \(\{rw_i\}\) とする. 最初にそれぞれをもともとのインデックスが分かるようにソートしておく. 以降は \(w_i, rw_i\) はソート済みで…

AOJ 1387 - String Puzzle

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1387 解法 各分割区間と一致する場所が、「より左にある」という制約が重要で、これにちゃんと気がつけば解ける。 これによって 文字列のある位置の文字と別の位置の文字が、与えられた条…

AOJ 1191 - Rotate and Rewrite

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1191&lang=jp 解法 こういう問題に対する典型的な発想として、一文字ずつ構成していく、というものがある。 つまり、A の先頭位置と B の先頭位置を決めうった後、一文字ずつ作っていって…

AOJ 1158 - ICPC: Intelligent Congruent Partition of Chocolate

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1158 解法 \(_{36}C_{18}\) は流石に間に合わない。 しかし、2つの領域を合同かつ連結になるように選んでいけば、探索空間はそんなに大きくないように思える(実際大きくない)。 なので、…

AOJ 2682 - Polygon Guards

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2682 解法 答えは 9 以下なので全探索で間に合う(えぇ…)。 前処理で、ある点に配置したときにどこが見えるようになるかを bit で管理すると判定が O(1) になる。 視線の線分が多角形内部…

AOJ 2724 - Laser Cutter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2724 解法 結論を言えば、最小重み二部マッチングに帰着できる。線分の交点と端点が頂点になった有向グラフを考えると、考えるべき問題は「いくつか辺を追加することで、最小重みのオイラ…

AOJ 2691 - Cost Performance Flow

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2691 解法 流量1ずつ流していったときの最小費用流のコストのグラフは、下に凸な折れ線グラフになる。 求める値は、このグラフと点 \((M, 0)\) との距離であり、グラフの形からこの距離も…

AOJ 2202 - Canal: Water Going Up and Down

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2202 解法 全長が小さいので DP する。 reach[i][j] := 船 i が位置 j に到達する最短時刻これはあくまでも「到達」時刻であり、その地点を出発できる時刻ではない(門の上下などで停泊す…

AOJ 2385 - Shelter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 解法 こんなの積分するしかないでしょという気分になるので立式する。 とりあえずボロノイ図を考えると、凸多角形領域 \(D\) とその内部の1点に対する問題に帰着できる。 内部の点を …

AOJ 2569 - Putter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2569 解法 線分の通り方を n! 通り全探索する。 ある線分を通る時に、その線分で点を鏡写しにしていけば、直線がそれらの線分を貫くかどうか、という問題になる。 この判定は角度(厳密に…

AOJ 2164 - Revenge of the Round Table

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2164 解法 回転して同じものはとりあえず重複して数える。 というのも、もし周期 s の並べ方があったとしたら、回転して同じとみなせるものは s 通りだとわかるからだ。まず、先頭を A に…

AOJ 2343 - Matrix Operation

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343 解法 操作に必要な情報は、 鏡写しの状態になっているか 何回転しているか どこに何が書き込まれたか (WR, CP) 列 or 行の並びはどうなっているか だけなので、各操作に対し O(1) or …

AOJ 2430 - Longest Increasing Sequence

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2430 解法 やり方は2通りあるんですが、片方はちょっとメモリが厳しかった(通ったけど)。 メモリが厳しいほう dp[i][j] := i 個目までみて最大長さが j であるときの右端の min と定義。…

AOJ 1341 - Longest Chain

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341 解法 動的2次元セグ木とかで解けそうだけど、ICPC でデータ構造の問題はチームメイトに投げるため違う解き方をする。 とりあえずソートができるので3次元 -> 2次元になる。 1次元のと…

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) で求まる。 それを今の値に足し…