問題文 http://codeforces.com/gym/100459 解法 Standing -> 重心をおろした位置が底面の内部 Unstable -> 重心をおろした位置が底面の周上にある Falling -> 重心をおろした位置が底面の外部重心の座標は (a + b + c + d) / 4 なので，あとは底面の三角形と…

問題文 http://codeforces.com/gym/100459 解法 しゃくとり法で解いた． 条件を満たさないようなペアの数を数えて，全体から引くことで求める． しゃくとりの過程で，今現在の区間が overlap しうるので，その分は足すことで重複して引かないようにしている…

問題文 http://codeforces.com/gym/100459 解法1 行列累乗で解く． 左から順番に見ていった時，状態としては k + 3 種類ある． 最初の second type が来た状態，途中の first type （k個の状態がある），最後の second type が来た状態（受理状態），それ以…

問題文 http://codeforces.com/gym/100453 解法 X, Y, Z のそれぞれについて，巡回するいくつかのグループに分けることができる． 周期 a で巡回する列と，周期 b で巡回する列と，周期 c で巡回する列を考える．これらはそれぞれ X, Y, Z から持ってくると…

問題文 http://codeforces.com/gym/100453 解法 長さを最小化するので，N * (N - 1) / 2 >= K && (N - 1) * (N - 2) / 2 あとは，上から順に，その位置の値を変えなければならないところまで順番に 1 から埋めていく． その場所まで来たら，変えないと行けな…

問題文 http://codeforces.com/gym/100453 解法 ある数 a_i からスタートした時に，それ以上の値で余りをとっても変化はない． したがって，数列をまずソートし，最初にする数字を何にするか全部試すのが良さそうである． これは dp で計算できて， dp[i] :=…

問題文 http://codeforces.com/gym/100453 問題概要 n 個の鎖が与えられ，それぞれのサイズは c_i である． 鎖とは，連結グラフであり，かつ両端点以外の頂点の次数が2であるものである． これらの鎖を，鎖とは別に用意した1つの頂点 X に，その両端をつなげ…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の要素からなる数列 a が与えられる．あなたは以下の操作を k 回行える． ある要素の値を隣接する（どちらかの1方の）要素に加える． k 回の操作の後の，数列に含まれる値の最小値を最大化せよ． また…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の要素からなる数列 a が1つ与えられる． 以下を満たす集合 X のうち，最小の |X| をもとめよ． X = {b_1, ..., b_k} とすると，任意の a の要素は，Xの要素のうちからいくつか選んで足し合わせて作る…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の数列が与えられる． 各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる． 最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなる…

問題文 http://codeforces.com/gym/100448 問題概要 n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする． もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする． こうしてできる四角形のうち，凹四角形で…

問題文 http://codeforces.com/gym/100448 問題概要 n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える． こ…