いがメモ

プログラミング関連についてやったことの記録を書いていきます。

TopCoder SRM 620 Div1 Easy PairGame [1人競技プログラミング Advent Calendar 2016 19日目]

遅れを取り戻した…。
この記事は1人競技プログラミング Advent Calendar 2016 19日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

解いた方法：
逆から戻していき、一致する初期座標を探す。

#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 PairGame {
    public:
    int a;
    int b;
    int c;
    int d;
    int maxSum(int _aa, int _bb, int _cc, int _dd) {
        a = _aa, b = _bb, c = _cc, d = _dd;

        if(a == b && b == c && c == d) return a*2;
        if(a == b && c == d) return -1;


        vector<PII> ab;
        while(0 < a && 0 < b){
            ab.PB(MP(a, b));
            if(a < b){
                b -= a;
            }else{
                a -= b;
            }
        }

        set<PII> cd;
        while(0 < c && 0 < d){
            cd.insert(MP(c, d));
            if(c < d){
                d -= c;
            }else{
                c -= d;
            }
        }

        REP(i, ab.size()){
            if(cd.count(ab[i]) == 0) continue;
            return ab[i].first + ab[i].second;
        }

        return -1;
    }
};

TopCoder SRM 619 Div1 Easy SplitStoneGame [1人競技プログラミング Advent Calendar 2016 18日目]

こういうサクッと解けるゲーム系は得意かも。
この記事は1人競技プログラミング Advent Calendar 2016 18日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

解いた方法：
全部1の時とサイズが2の時は必ず負ける。
それ以外の時は、全ての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 SplitStoneGame {
    public:
    vector<int> number;
    string winOrLose(vector<int> _number) {
        number = _number;

        bool flag = false;
        REP(i, number.size()){
            if(number[i] != 1) flag = true;
        }
        if(!flag) return "LOSE";
        if(number.size() <= 2) return "LOSE";

        return number.size() % 2 == 0 ? "LOSE" : "WIN";
    }
};

TopCoder SRM 618 Div1 Easy Family [1人競技プログラミング Advent Calendar 2016 17日目]

色々あって時間が取れなかったのと今日も時間が無いので手短に…。

この記事は1人競技プログラミング Advent Calendar 2016 17日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement

解いた方法：
親同士に辺を貼ったグラフが2色で塗れるかどうかをDFS

#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};

vector<VI> G;
VI color;

void add_edge(int from, int to){
    G[from].PB(to);
    G[to].PB(from);
}

bool dfs(int now, int c){
    if(color[now] != c && color[now] != 0) return false;
    if(color[now] != 0) return true;

    color[now] = c;
    REP(i, G[now].size()){
        if(!dfs(G[now][i], c*-1)){
            return false;
        }
    }

    return true;
}

class Family {
    public:
    vector<int> parent1;
    vector<int> parent2;
    string isFamily(vector<int> _parent1, vector<int> _parent2) {
        parent1 = _parent1, parent2 = _parent2;

        G.clear();
        color.clear();
        REP(i, parent1.size()){
            VI tmp;
            G.PB(tmp);
            color.PB(0);
        }

        REP(i, parent1.size()){
            if(parent1[i] == -1) continue;

            add_edge(parent1[i], parent2[i]);
        }

        REP(i, parent1.size()){
            if(color[i] == 0){
                if(!dfs(i,1)){
                    return "Impossible";
                }
            }
        }

        return "Possible";
    }
};

TopCoder SRM 617 Div1 Easy MyLongCake [1人競技プログラミング Advent Calendar 2016 16日目]

この記事は1人競技プログラミング Advent Calendar 2016 16日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
長さn(2<=n<=100,000)のケーキがある。
これから来る友人全員に同じサイズのケーキを渡したい。
来る人数はnの約数の人数のいずれかの人数である。

どの人数が来てもいいように予めケーキをカットしておきたい。
例えばn=6の時は1,2,3人が来るので、[2,1,1,2]とケーキをカットしておくと、1人来たときは全部、2人来たときは[2,1]と[1,2]のケーキを渡し、3人来たときは[2],[1,1],[2]のケーキを渡せば同じサイズのケーキを渡すことが出来る。
渡すケーキは連続である必要があるので、上記の例では[2,1,2,1]とカットしておくことは許されない。(3人来た時に渡せなくなる為)
あらかじめケーキを分けて置く個数を答えよ。

解いた方法：
どの人数が来たときも、(n/人数)のサイズのケーキを渡せばよい。
ということは、あらかじめ約数の個数毎に切り込みを入れておけばよい。(対応する約数があるので)

#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 MyLongCake {
    public:
    int n;
    int cut(int _n) {
        n = _n;
        set<int> used;
        REP2(i, 2, n){
            if(n % i == 0){
                int tmp = i;
                while(tmp != n){
                    used.insert(tmp);
                    tmp += i;
                }
            }
        }

        return used.size()+1;
    }
};

TopCoder SRM 615 Div1 Easy AmebaDiv1 [1人競技プログラミング Advent Calendar 2016 15日目]

この記事は1人競技プログラミング Advent Calendar 2016 15日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
アメーバは自分と同じサイズのゲルのみを食べることが出来る。
N(1<=N<=200)匹のゲルのサイズの配列X(1<=X[i]<=1,000,000,000)が与えられる。
アメーバは0番目からN-1番目まで順番にゲルを食べれたら食べていく。

アメーバの初期サイズが任意に決められる際に存在しない最終的なアメーバのサイズは何通りあるかを答えよ。

解いた方法：
初期サイズがゲルのいずれかの値と一致しない場合は1度もアメーバはゲルを食べることが出来ないので、最終的なサイズはそのままになる。
ということは、調べる必要があるアメーバの初期サイズは1度以上ゲルを食べるサイズのみで良い。

そうすると高々初期サイズ200通りを調べるだけで良いので、全通り試して適当にsetにぶち込めば終わる。

#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 AmebaDiv1 {
    public:
    vector<int> X;
    int count(vector<int> _XX) {
        X = _XX;
        set<int> X_set;
        set<int> goal;

        REP(i, X.size()){
            X_set.insert(X[i]);
            int now = X[i];
            REP(j, X.size()){
                if(X[j] == now) now *= 2;
            }

            REP(j, X.size()){
                if(X[j] == now){
                    goal.insert(now);
                    break;
                }
            }
        }

        return X_set.size()-goal.size();
    }
};

ルシアン・バレエ [1人おうちカクテル Advent Calendar 2016 15日目]

この記事は 1人おうちカクテル Advent Calendar 15日目の記事です。

f:id:iga_c:20161216002938j:plain

名前：ルシアン・バレエ
材料：ウオッカ 40ml、クレーム・ド・カシス 10ml、レモンジュース 10ml
技法：ステア

ルビーレッド色(が近い表現かな？)の綺麗な見た目のカクテル！初めて作りました。
味はカシスとレモンの味がよく出ており甘酸っぱく、良い感じ👏

ウオッカが多めに入っており度数が高いので、強めのカクテルや酔いたい時に良さそうですね！

ギムレット [1人おうちカクテル Advent Calendar 2016 14日目]

この記事は 1人おうちカクテル Advent Calendar 14日目の記事です。

f:id:iga_c:20161215004019j:plain

名前：ギムレット
材料：ドライ・ジン 45ml、ライムジュース 15ml
技法：シェーク

ジンとライムをシェークして作るシンプルなカクテルです。名前を聞いたことがある人は結構いるのではないでしょうか？
ジンライムよりはしっかり混ざって冷えており飲みやすいが、個人的にはちょっとあわないかな？といった感じです。
居酒屋でジンライム好きで飲む人は試してほしい🍸ですね！