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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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