TopCoder SRM 624 Div1 Easy BuildingHeights [1人競技プログラミング Advent Calendar 2016 21日目]
この記事は1人競技プログラミング Advent Calendar 2016 21日目の記事です。
問題概要：
TopCoder Statistics - Problem Statement
N(2<=N<=4000)個i番目の建物の高さがheights[i]で与えられる。
建物の高さを自由に追加することが出来る。
x個の建物の高さを同じ高さにする際に追加する必要な高さの最小をA[x]とする。
A[2] xor A[3] xor ... xor A[N]の値を答えよ。
解いた方法：
建物の高さをソートしてしゃくとりっぽく計算する。累積和を取っておくと速くなる。(取らないと多分TLEする？
#include<bits/stdc++.h> #define MP make_pair #define PB push_back #define ALL(x) (x).begin(),(x).end() #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<(n);i++) #define REP2(i,d,n) for(int i=(d);i<(n);i++) #define RREP(i,n) for(int i=(n);i>=0;i--) #define CLR(a) memset((a),0,sizeof(a)) #define MCLR(a) memset((a),-1,sizeof(a)) #define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef vector<LL> VLL; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const LL INFL = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-9; const int DX[]={1,0,-1,0},DY[]={0,-1,0,1}; class BuildingHeights { public: vector<int> heights; int minimum(vector<int> _heights) { heights = _heights; int res = 0; sort(ALL(heights)); int memo[4001] = {0}; REP(i, heights.size()){ memo[i+1] = memo[i] + heights[i]; } REP1(i, heights.size()){ int ans = INF; int cnt = 0; REP(j, heights.size()){ if(i+j == heights.size()) break; int cost = heights[i+j] * i - (memo[i+j] - memo[j]); ans = min(ans, cost); } res = res ^ ans; } return res; } };
グレープバイン [1人おうちカクテル Advent Calendar 2016 19日目]
1日分足りていない事に今更気づいた…！
この記事は 1人おうちカクテル Advent Calendar 19日目の記事です。
名前：グレープバイン
材料：ドライ・ジン 30ml、グレープフルーツジュース 15ml、レモンジュース 15ml、グレナデンシロップ 1tsp
技法：シェーク
綺麗な赤色のカクテル！レシピを見ていた時にどんな感じになるんだろう？と凄いワクワクしていました。(今回初めて作りました)
個人的にはちょっと味が合わなかったのが残念でした…。材料的にはそんな外れないだろうと思っていたのに…！
ダイキリ [1人おうちカクテル Advent Calendar 2016 18日目]
この記事は 1人おうちカクテル Advent Calendar 18日目の記事です。
名前：ダイキリ
材料：ホワイト・ラム 45ml、ライムジュース 15ml、砂糖 1tsp
技法：シェーク
ラムとライムジュースに砂糖を若干加えたカクテル。ちょっと度数が高めです。
シェーカーがあれば結構お手軽に作れるのではないでしょうか！ライム好きな人はぜひ！
チャイナ・グリーン [1人おうちカクテル Advent Calendar 2016 17日目]
この記事は 1人おうちカクテル Advent Calendar 17日目の記事です。
名前：チャイナ・グリーン
材料：ライチリキュール 30ml、グレープフルーツジュース 20ml、メロンリキュール 10ml
技法：シェーク
メロンリキュールを使ってグリーンに！メロン大好きな僕としてはオススメなカクテルです:bow: ショートカクテルだけど度数もかなり低めで甘くてオススメです！
チャイナ・ブルー [1人おうちカクテル Advent Calendar 2016 16日目]
こっちの遅れを取り戻します…！ この記事は 1人おうちカクテル Advent Calendar 16日目の記事です。
名前：チャイナ・ブルー
材料：ライチリキュール 30ml、ブルーキュラソー 10ml、グレープフルーツジュース 20ml、トニックウオーター 適量
技法：ビルド
度数が非常に低く甘くて飲みやすいし見た目もいい感じの色々と良さを感じるカクテルです！
おうちカクテルで作ろうとすると色々と揃えないと作れなくて面倒ですが、シェーカー要らずでお手軽に作れるので持ってない人も是非…！
TopCoder SRM 621 Div1 Easy RadioRange [1人競技プログラミング Advent Calendar 2016 20日目]
ここまで続けてきて初の275点問題。今まで全部250点問題でした。
この記事は1人競技プログラミング Advent Calendar 2016 20日目の記事です。
問題概要：
TopCoder Statistics - Problem Statement
N(1<=N<=100)個の町があり、i番目の町の中心が(X[i],Y[i])(-109 <= X[i],Y[i] <= 109)で与えられる。
i番目の町の範囲はi番目の町の中心から半径Ri以内のエリアで与えられる。
座標(0,0)にラジオ塔を建て、半径Z(1<=Z<=109)以内のエリアにラジオが届く。
全てのそれぞれの町において、ラジオが町の全てのエリアに届かないか、全てのエリアに届いている状態が良い状態である。
半径Zの内、良い状態の部分の割合を誤差1^-6以内で答えよ。
解いた方法：
全ての町において、悪い状態になる最小値と最大値を列挙する。
町の中心とラジオ塔の中心(0,0)で線を引き、町側の円と線が隣接している部分が最小値と最大値になる。
後は悪い部分が重複しているエリアをうまく計算して悪い部分がどのぐらいあるのかの合計値を求めれば答えが出てくる。
オーバーフローには要注意。(サンプルが優しいので救ってくれる)
#include<bits/stdc++.h> #define MP make_pair #define PB push_back #define ALL(x) (x).begin(),(x).end() #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<(n);i++) #define REP2(i,d,n) for(int i=(d);i<(n);i++) #define RREP(i,n) for(int i=(n);i>=0;i--) #define CLR(a) memset((a),0,sizeof(a)) #define MCLR(a) memset((a),-1,sizeof(a)) #define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef vector<LL> VLL; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const LL INFL = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-9; const int DX[]={1,0,-1,0},DY[]={0,-1,0,1}; class RadioRange { public: vector<int> X; vector<int> Y; vector<int> R; int Z; double RadiusProbability(vector<int> _XX, vector<int> _YY, vector<int> _RR, int _ZZ) { X = _XX, Y = _YY, R = _RR, Z = _ZZ; vector<pair<double, double> > lens; bool used[100]; REP(i, X.size()){ used[i] = false; double dis = sqrt((double)X[i]*X[i] + (double)Y[i]*Y[i]); double mn = max(0.0, dis - R[i]); double mx = min((double)Z, dis + R[i]); lens.PB(MP(mn, mx)); } sort(ALL(lens)); double del_size = 0.0; REP(i, lens.size()){ if(used[i]) continue; used[i] = true; REP2(j, i+1, lens.size()){ if(lens[j].first <= lens[i].second){ used[j] = true; lens[i].second = max(lens[i].second, lens[j].second); } } if((double)Z <= lens[i].first) continue; del_size += lens[i].second - lens[i].first; } return (double)(Z - del_size) / Z; } };
