問題文 Venn Diagram | Aizu Online Judge 解法 頑張って実装するだけ． 円の半径は入力からすぐわかる． 2つの円の距離を二分探索で求めたら，でかい方を左下隅に配置． 小さいほうは [0, pi/2] でどの角度に置くとよいかを判定．計算したくないので二分探…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1252 解法 以下の4パターン全部試すだけ． swap しない（単に編集距離の問題） 1回swapしたあと編集距離 2回swap 消した後 swap 最悪 200(200-1)/2 * 16 * (16 * 16) なので，まあ適当にや…

問題文 http://codeforces.com/contest/958/problem/E2 解説 わからなかったので上位陣のコードから解法を得た． とりあえずソートして隣接項の差を作ると，以下の問題になる．n - 1 要素からなる数列から，k 個えらんでその和を最小化せよ．ただし，隣接2要…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1371 解法 現れうる文字は高々8種類しかない． なので各文字に対して何を割り当てるか全探索して構文解析するだけ． ソースコード #include <bits/stdc++.h> using namespace std; using ret_type = doubl</bits/stdc++.h>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351 解法 StarrySkyTree + 二分探索で通した．( を +1, ) を -1 として累積和をStarrySkyTree上で管理する． 文字列が balanced であることと，累積和上の最小値が 0 以上であり，かつ末…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 解法 二分探索＋しゃくとり法． 二分探索は，普通に「スペースの隙間を X にして条件をクリアできるか」でやる．次にしゃくとり部分．二分探索の過程で与えられた，空けていい間隔を …

問題文 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| のコストがかかる．この操作は何回でも行える． こ…