競プロ参加記026 AtCoder Regular Contest 109(ARC109)

Atcoder

はじめに

AtCoder Regular Contest 109 – AtCoder

A,B,Cの3完でした。
1182位でレートは微増(+2)しました。前回、前々回が悲惨な結果だったので何とか踏みとどまった感じです。

A – Hands

A – Hands (atcoder.jp)

A問題(300点)なので、法則さえ分かればO(1)で解けそう…と思いましたが、考慮漏れが少し怖いので逃げました。
Aの1階～100階、Bの1階～100階の200個を頂点に持つグラフを作成し、ダイクストラして最小の時間を求めました。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    vector<pair<int,int>> AB[201];

    int a,b,c,x,y;
    cin>>a>>b>>x>>y;

    for(int i=1;i<=100;i++){
        AB[i].push_back(make_pair(i+100,x));
        AB[i+100].push_back(make_pair(i,x));
    }

    for(int i=1;i<=99;i++){
        AB[i+1].push_back(make_pair(i+100,x));
        AB[i+100].push_back(make_pair(i+1,x));
    }

    for(int i=1;i<=99;i++){
        AB[i].push_back(make_pair(i+1,y));
        AB[i+1].push_back(make_pair(i,y));
        AB[i+100].push_back(make_pair(i+100+1,y));
        AB[i+100+1].push_back(make_pair(i+100,y));
    }

    int dp[201];
    for(int i=0;i<201;i++) dp[i]=-1;
    dp[a]=0;

    queue<int> q;
    q.push(a);
    while(!q.empty()){
        int n=q.front();
        //cout<<n<<endl;
        q.pop();

        for(int i=0;i<AB[n].size();i++){
            int nn=AB[n][i].first;
            int nc=AB[n][i].second;
            //cout<<i<<","<<nn<<","<<nc<<endl;
            if(dp[nn]==-1||dp[nn]>dp[n]+nc){
                dp[nn]=dp[n]+nc;
                q.push(nn);
            }
        }
    }

    cout<<dp[b+100]<<endl;
}

B – log

B – log (atcoder.jp)

N+1の長さの丸太だけ必要のない丸太のため、こいつを買って2本以上に分割することで安くするのが良さそうです。
(N以下の長さを分割するならN+1の長さでも同じことができるし、分割した丸太をN+1の長さの丸太から作る必要があるので、勿体ない)
分割できる数は多いほうが良いので、長さ1,2,3…と小さい順から作る方が良さそうです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    long long n;
    cin>>n;
    long long n2=n+1;
    long long c=0;
    long long i=1;
    n++;

    while(1){
        n2-=i;
        if(n2<0) break;
        i++;
        c++;
    }

    cout<<n-c<<endl;
}

書いた後に、nの最大が10^18なので2分探索しないとヤバそうと感じ、念のためコードテストで10^8を試してみました。

標準入力:1000000000000000000
終了コード:0
実行時間:699 ms
メモリ:440 KB
標準出力:999999998585786440

1s以下で動くっぽいので、ヨシッ！
ACしました。(想定解では二分探索が必要みたいですが、良いでしょう。)

C – Large RPS Tournament

C – Large RPS Tournament (atcoder.jp)

2^100回トーナメントするのは明らかTLEです。

小さい範囲でシミュレーションしてみると、

3 10
RPS

PRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPR
PSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRP
SPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSP
SRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPS
RSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRS
RPSRPSRPSRPSRPSR
PRSPRSPR
PSRP
SP
S

長さnで同じ文字がループしていそうです。
s1,s2の勝者が次のs1に、s3とs4の勝者が次のs2に…と考えると、次のsnはs2n-1とs2nの勝者になります。2*nごとにn人の勝者が決まっていくため、上手いことループしていく感じです。
なので、2^k人全員に対してシミュレーションする必要はなく、ループの範囲内だけでシミュレーションすればOKです。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;
//RPSRPSRP
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;

    for(int i=0;i<k;i++){
        string nx="";
        for(int j=0;j<s.size();j++){
            if(s[(j*2)%s.size()]=='R'&&s[(j*2+1)%s.size()]=='R') nx+='R';
            if(s[(j*2)%s.size()]=='R'&&s[(j*2+1)%s.size()]=='P') nx+='P';
            if(s[(j*2)%s.size()]=='R'&&s[(j*2+1)%s.size()]=='S') nx+='R';
            if(s[(j*2)%s.size()]=='P'&&s[(j*2+1)%s.size()]=='R') nx+='P';
            if(s[(j*2)%s.size()]=='P'&&s[(j*2+1)%s.size()]=='P') nx+='P';
            if(s[(j*2)%s.size()]=='P'&&s[(j*2+1)%s.size()]=='S') nx+='S';
            if(s[(j*2)%s.size()]=='S'&&s[(j*2+1)%s.size()]=='R') nx+='R';
            if(s[(j*2)%s.size()]=='S'&&s[(j*2+1)%s.size()]=='P') nx+='S';
            if(s[(j*2)%s.size()]=='S'&&s[(j*2+1)%s.size()]=='S') nx+='S';
        }
        s=nx;
        //cout<<s<<endl;
    }
    cout<<s[0]<<endl;
}

これ解いたとき、自分天才！と思ったのですがAtcoder Problemsによるとギリギリ緑diffらしいです。Atcoder界ちょっと天才すぎませんか？

おわりに

ARC、AGCに苦手間隔があるのでどうにかしたいですね…。
あと、コンテスト中に多倍長使いたい気持ちになったのでboostを落としていたのですが、思ったより時間がかかりました…。自環境の整備も早く済ませたいです。(未だにマクロ使ってませんしねx x)

コメント

タイトルとURLをコピーしました