バイオレット・フィズ [1人おうちカクテル Advent Calendar 2016 6日目]
この記事は 1人おうちカクテル Advent Calendar 6日目の記事です。
名前：バイオレット・フィズ
材料：クレーム・ド・バイオレット 45ml、レモンジュース 20ml、シュガーシロップ 1tsp、ソーダ 適量
技法：シェーク
綺麗な紫色のリキュールを使ったカクテルです。仄かに香るニオイスミレの香りとレモンの味がマッチしてとてもGOOD！
作るのには色々材料が必要で面倒なので、バーに行く機会とかあったら是非飲んでみてください！
グリーン・ハット [1人おうちカクテル Advent Calendar 2016 5日目]
この記事は 1人おうちカクテル Advent Calendar 5日目の記事です。
名前：グリーン・ハット
材料：ドライ・ジン 25ml、クレーム・ド・ミント(グリーン) 25ml、ソーダ 適量
技法：ビルド
1日目に作ったエリンと似ている(+ソーダ)カクテルです。グリーン・ハットは度数がかなり控えめで飲みやすいです！
こちらは材料さえあればシェーカー要らずで作れるので、シェーカー買うまではあれだけどちょっとお洒落で美味しいカクテルを作ってみたいという方にはオススメの一品です！
ミントリキュールはいいぞ！(宣伝)
(ここまでジン系やミント系のカクテルが多くなってしまっているので明日からは違う方面で攻めていきます…！
TopCoder SRM 604 Div1 Easy PowerOfThree [1人競技プログラミング Advent Calendar 2016 5日目]
この記事は1人競技プログラミング Advent Calendar 2016 5日目の記事です。
問題概要：
TopCoder Statistics - Problem Statement
ロボットが初期座標(0,0)に存在する。
このロボットを座標(x,y) (-1,000,000,000 <= x,y <= 1,000,000,000)に移動させたい。
ロボットはkステップ目(0から)には、3k分上下左右の何方かに移動することが出来る。
つまり、1,3,9,27…と移動することが出来る量が変化していく。どのステップでも必ず上下左右の何処かには移動しなければならない。
xとyが与えられた際に、このロボットが目的地まで辿り着けるかどうかを判定せよ。
解いた方法：
ゴールに辿り着けるかという問題を考えると非常に難しいので、逆にゴールから目的地に辿り着けるかという問題を考える。
このゲームでは、x座標でもy座標でも必ずスタート地点から遠い方を優先して動かさなければならない。
sum(30..3k-1) より 3kの方が大きくなる為、距離が遠い方を動かさないと後々必ずステップ数が足りなくなる。(もしくはそもそもスタート地点に辿り着けない)
ロボットが移動するステップ数は一意に求めることができ、(x=0,y=0を除いて)3k - sum(30..3k-1) <= max(abs(x), abs(y)) <= sum(30..3k)を満たすkがステップ数となる。
後は上記の手法を使い、座標(x,y)からkステップを逆に辿っていき座標(0,0)に戻る事が出来たかどうかで求めることができる。
この手の問題の逆から考えるをすっかり頭から抜けてて解くのに時間掛けたり、最初のmax_num = max(abs(x), abs(y))でabsを付け忘れて1WAを出してしまった…。反省。
#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}; LL create_3k(int k){ LL res = 1; REP(i, k) res *= 3; return res; } class PowerOfThree { public: LL x; LL y; string ableToGet(int _xxx, int _yyy) { x = _xxx, y = _yyy; LL max_num = max(abs(x), abs(y)); LL tmp = 0; int k = 0; while(true){ if(max_num <= tmp) break; k++; tmp += create_3k(k-1); } while(k != 0){ if(abs(x) < abs(y)) swap(x, y); k--; if(x < 0){ x += create_3k(k); }else{ x -= create_3k(k); } } return (x==0 && y==0) ? "Possible" : "Impossible"; } };
ブルー・マンデー [1人おうちカクテル Advent Calendar 2016 4日目]
この記事は 1人おうちカクテル Advent Calendar 4日目の記事です。
名前：ブルー・マンデー
材料：ウオッカ 45ml、ホワイトキュラソー 15ml、ブルーキュラソー 1tsp
技法：ステア
ネガティブな名前とは裏腹に、透き通った青が綺麗なカクテルです。
憂鬱な月曜日と言った意味を持っており、今日が最適だなと思い作りました…。(お仕事…)
味も飲みやすく見た目もよく出来ており素敵なカクテルなのですが、全て酒しか混ざってないので度数が非常に高くなっています。
飲みすぎには気を付けて飲みましょう！
TopCoder SRM 603 Div1 Easy MaxMinTreeGame [1人競技プログラミング Advent Calendar 2016 4日目]
この記事は1人競技プログラミング Advent Calendar 2016 4日目の記事です。
問題概要：
TopCoder Statistics - Problem Statement
ノードにコストがある木が与えられる。
2人のプレイヤーがノード数1になるまで下記の行動を順番に取ることが出来る。
・1個のエッジを選んで消す
・上記の手順後、2個になった木の内片方を消す
先手プレイヤーは最終的に残ったノードのコストを出来る限り大きく、後手プレイヤーは出来る限りコストを小さくしたい。
お互い最適にプレイした際の答えを出力せよ。
解いた方法：
例えば先手プレイヤーが最終的に残したいノードの木を残したとしても後手プレイヤーが消すことが出来る。(逆も成り立つ)
なので、先手プレイヤーが最初の1手でノード数1になるような最もコストの高いノード(要するに葉ノード)を1手目で残すのが最適戦略となる。
#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 MaxMinTreeGame { public: vector<int> edges; vector<int> costs; int findend(vector<int> _edges, vector<int> _costs) { edges = _edges, costs = _costs; VI counts; REP(i, costs.size()) counts.PB(0); int res = 0; REP(i, edges.size()){ counts[i+1]++; counts[edges[i]]++; } REP(i, costs.size()){ if(counts[i] == 1) res = max(res, costs[i]); } return res; } };
TopCoder SRM 602 Div1 Easy TypoCoderDiv1 [1人競技プログラミング Advent Calendar 2016 3日目]
この記事は1人競技プログラミング Advent Calendar 2016 3日目の記事です。
問題概要：
TopCoder Statistics - Problem Statement
TypoCoderというコンテストがあり、レーティング2200以上がbrown coder、2200未満がciel coderである。
Cat Lowerの現在のレーティングXとコンテスト毎のレーティング変動配列Dが与えられる。
i番目のコンテストでベストを尽くした場合はD[i]分レーティングが上がる。
i番目のコンテストで何もしなかった場合はD[i]分レーティングが下がる。0以下にはならない。
Cat Lowerはciel coderが好きなので、i番目のコンテストでbrown coderになった際にi+1番目のコンテストではciel coderに戻らなければならない。
最大でbrown coderとciel coderの入れ替わる事が出来る回数は何回かを答えよ。
解いた方法：
DP。dp[ 終了したコンテスト ][ 現在のレート ] = 変動回数 でやりました。
遷移する際に、必ずi+1番目では元のciel coderに戻らなければならないという条件があるので、2つ先のコンテストではレートがciel coderの取り得る値になっている。
その為、オーダーがO(len(D)*2200)回程度にまで落ちて間に合う。
vectorのsizeと負の数の比較でfalseを返しハマっていた…。泣きたい。 とりあえず遅すぎたけどWAは出さずに一発ACは達成。
#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}; int dp[51][2201]; class TypoCoderDiv1 { public: vector<int> D; int X; int getmax(vector<int> _D, int _XX) { D = _D, X = _XX; REP(i, 51) REP(j, 2201) dp[i][j] = -1; dp[0][X] = 0; REP(i, D.size()){ REP(j, 2200){ if(dp[i][j] == -1) continue; if(j + D[i] >= 2200){ if( i-2 < (int)D.size() && ((j + D[i] - D[i+1]) < 2200)){ dp[i+2][max(0, j + D[i] - D[i+1])] = max(dp[i][j] + 2, dp[i+2][max(0, j + D[i] - D[i+1])]); } if( i+1 == D.size() ){ dp[i+1][2200] = max(dp[i][j] + 1, dp[i+1][2200]); } }else{ dp[i+1][j + D[i]] = max(dp[i][j], dp[i+1][j+D[i]]); } if(j - D[i] > 0){ dp[i+1][ j - D[i] ] = max(dp[i][j], dp[i+1][j-D[i]]); }else{ dp[i+1][0] = max(dp[i][j], dp[i+1][0]); } } } int ans = 0; REP(i, 2201){ ans = max(ans, dp[D.size()][i]); } return ans; } };
