TCO2017 Round1 Easy

SRM精進がしたくなったからArenaを開いたけど広義今夜にTCO2018 Round1があるらしくPractice RoomがこわれていたのでTCO2017の問題をやった.Div1 Easyかとおもったらだいぶ易しかった.

・TCO2017 Round1A Easy PingPongQueue

x人の人がいて,卓球をする.ただし卓球台が1台しかないので同時に対戦できるのは2人だけ.i番目の人の強さはskills[i]で,対戦すると必ず強い方が勝つ(skills[i]は相異なる).はじめ0番目の人と1番目の人が対戦し,のこりの人は順番に列に並んでいる.試合が終わると次のことが行われる.

1.負けた方は列の最後に並ぶ

2.勝った方がすでにN回勝っているなら,その人も列の最後に並ぶ

3.卓球台に残っている人数が2未満の間,列の先頭の人が卓球台に来る

4.卓球台にいる二人で次の試合を行う

これを繰り返したときK回目の試合で負ける人と勝つ人の強さを答えよ.という問題.

ただシミュレーションをしましょうという問題.K≦1000なので十分間に合う.

ソースコード

class PingPongQueue {
    public:
    vector<int> whoPlaysNext(vector<int> skills, int N, int K) {
        deque<int> Q;
        for(int i=0;i<skills.size();i++) Q.push_back(i);
        int win=0;
        int prev=-1;
        for(int i=0;i<K-1;i++) {
            int x=Q.front();Q.pop_front();
            int y=Q.front();Q.pop_front();
            int winner;
            if(skills[x]<skills[y]) {
                Q.push_back(x);
                Q.push_front(y);
                winner=y;
            }else {
                Q.push_back(y);
                Q.push_front(x);
                winner=x;
            }
            if(prev==winner) win++;
            else prev=winner,win=1;
            if(win>=N) {
                x=Q.front();Q.pop_front();
                Q.push_back(x);
            }
        }
        int x=Q.front();Q.pop_front();
        int y=Q.front();Q.pop_front();
        if(skills[x]<skills[y]) {
            return {skills[x],skills[y]};
        }else {
            return {skills[y],skills[x]};
        }
    }
};

・TCO2017 Round1B Easy WaterAndOxygen

あなたは宇宙船の中にいる.宇宙船では1日costH2Oモルの水とcostO2モルの酸素を消費する.現在,宇宙船にのこっている水はremainH2Oモル,酸素はremainO2モルである.あなたは水nモルを消費して酸素n/2モルを作ることが出来る.このとき,あなたは最大何日生き残ることができるだろうか?という問題.

にぶたん.x日生き残れるか,の判定をかんがえると,まず水は作れないのでx*costH2O<remainH2Oが必要.これを満たしているとき,のこりの水を全て使って酸素を作ったとき,酸素が足りるかどうかを計算すればいい.

ソースコード

class WaterAndOxygen {
    public:
    double maxDays(int remainH20, int remainO2, int costH2O, int costO2) {
        double l=0,r=1e10;
        for(int i=0;i<100;i++) {
            double m=(l+r)/2;
            if(costH2O*m<=remainH20 && costO2*m<=remainO2+(remainH20-costH2O*m)/2) {
                l=m;
            }else {
                r=m;
            }
        }
        return l;
    }
};

・TCO2017 Round1C Easy EllysTickets

n+1個の駅が順番に並んでいて,0番目の駅からn番目の駅まで行きたい.i番目の駅からn番目の駅に行くチケットはticketPrice[i]円である.車掌はn個の区間のうちランダムに選んだ一つの区間で乗客のチケットを確認する.もし乗客がチケットをもっていなかった場合,その乗客はfine円を払う必要がある(払えばその後はチケット無しで乗っていても構わない).あなたが払うお金の期待値の最小値を求めよ.という問題.

全探索するだけ.i番目の駅でチケットを購入することにすると,購入する前にチケットを確認される確率はi/n.よってこのとき払うお金の期待値はfine*(i/n)+ticketPrice[i]*(1-i/n)円.

ソースコード

class EllysTickets {
    public:
    double getPrice(vector<int> ticketPrice, int fine) {
        int n=ticketPrice.size();
        double ans=fine;
        for(int i=0;i<n;i++) {
            double r=(double)i/n;
            ans=min(ans,fine*r+ticketPrice[i]*(1-r));
        }
        return ans;
    }
};