http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3552 問題 半径Rの円盤に半径rのドリルでn個の穴を開ける。重心を求めよ。 0 解法 穴がかぶることが無ければ普通に重心の公式で求めれば良い。穴がかぶってしまうので穴の形を考えて厳密に面…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3559 問題 矩形の毒沼がn個ある所でスタートからゴールまで行きたい。毒沼に入らず(境界含む)にゴールまで行くには最低何回曲がらないといけないか答えよ。 0 座標 解法 座標圧縮してダイクス…

問題 B進数を16segで表示する。180度回転して一致するK番目の数値を答えよ。 1 1 解法 反転して一致するものが0のみでK!=1のときは解が無い。他の場合は適当に反転して一致しない物が存在しない数をスキップしながら1ずつ足して順番に見つけていく。

問題 数列がN個ある。また数列に関してという制約がM個ある。この制約をすべて満たす数列は存在するか？存在する場合は辞書順最小の数列を求めよ。 N M 0 解法 強連結成分分解しグラフを縮約する。制約を満たすためには同じ強連結成分に含まれるもの同士の間…

問題 長さNの数列Aがある。Aのsubsequenceで単調増加でも単調減少でもない物の数は何個？ 1 解法 O(n^2)のDPをするだけ。無駄にTLEがきつい。

問題 のサイズを求めよ。 1 1 解法 やるだけ。

問題 andoroidとかのロックで押した順番が与えられる。同じ番号を押していて、線の形が同じになる押し方の数を答えよ。 解法 やるだけ。