問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1359 解法 各点から半直線が2本出て，長方形の周上の2点で交わるが，それをそのまま処理すると面倒． なので，(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して，[0, …

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1348 解法 完全にやるだけ．多少無駄なことをしても入力サイズが小さいので余裕で通る． ご丁寧に式が書かれているので，それに従って候補を全部列挙し，それらが条件をみたすか（つまり接触…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334 解法 実は，A->B と C->D の少なくともどちらか一方は，直接結んでしまって良いことがわかる．そうすればあとは最短経路問題．以下は自分のイメージ． 例えば図のように，（解が存在し…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2592 解法 3分探索．（自分は黄金比探索を持ってたのでそれを貼り付けた．） 使う水の量が決まれば，使う肥料の量は一位に定まる．つまり，コスト関数はWのみを引数とする関数である． グラ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2595 解法 1枚も食べない日を考えるとややこしい（し，Dがでかいのでそのまま求められない）ので，D 日のうち一枚も食べない日はあとで決めることにすればよい． つまり，まずは一日に最低…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570 解法 > が >> なのか S の > なのかは，数字またはSの直前かどうかで判定ができる． なので最初に式を後ろから見ていって，どれがシフト演算なのか確定させておく． それができればあと…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2512 解法 適当に置換 or 削除でminimax法だと明らかに間に合わないので，すこし考える必要がある． 冷静に考えると，N が偶数のときは2ターン，N が奇数のときは1ターンやるのと変わらない…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255 解法 BNFどおりに実装する必要はなくて，区間DPをすればよい． その区間で取りうる値の集合を持たせておく． 区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける． …

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1350 問題概要 連結グラフ G が与えられる．一般に G の最小全域木は複数存在しうる．G のすべての最小全域木に必ず含まれている辺を求めよ．・制約 3 N-1 解法 最小全域木 T を一つ求める．…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330 解法 基本は union-find をいじるだけ． 各ノードは，親からの相対重さを持つ． クエリで a, b, w が与えられたとする． a と b の代表元が異なる場合は，それぞれの集合の根を r1, r2…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318 解法 単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので，少し違う方針で． まず，ガソリンスタンドについたら満タンにしてしまっていいので，ガソリンスタンドから cap …

問題文 http://codeforces.com/contest/689/problem/D 問題概要 長さ N の数列 A, B が与えられる． max{A(l), ..., A(r)} = min{B(l), ... B(r)} となる (l, r) (l ・制約 1 解法 Sparse table を書いてみたのでそのテストに使った．なので Sparse table で…