問題文 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://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか，という問題． まず，n * m （n, m はただの自然数）のような表現は完全に不利． 例えば 99 * 99 を考えてみるとわかりやすいが，そのまま出力したほうが短い…

問題文 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][…

問題文 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] と等しい． した…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 解法 最短経路（それはそう）． 同じ高さの街が高々10しかないので，どの街に行ったか 2 ^ 10 で表現したい． どの街に行ったかを保存しつつ最短経路をやりたいね，となる． それには…