接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Regular Contest 109(ARC109)

atcoder.jp

A - Hands

算数でも出来そうだけど頭を壊しそうなのでダイクストラとかで最短経路を求める
提出コード

void solve(){
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    --a, --b;
    Dijkstra<int> dijk(2*111, INF);
    for(int i=0;i<100;i++){
        if(i < 99) dijk.make_edge(i, i+1, y);
        if(i < 99) dijk.make_edge(i+1, i, y);
        if(i < 99) dijk.make_edge(i+1, i+100, x);
        if(i < 99) dijk.make_edge(i+100, i+1, x);
        if(i < 99) dijk.make_edge(i+100, i+100+1, y);
        if(i < 99) dijk.make_edge(i+101, i+100, y);
        dijk.make_edge(i, i+100, x);
        dijk.make_edge(i+100, i, x);
    }
    dijk.solve(a);
    cout << dijk.cost[100+b] << endl;
}

B - log

$ n+1 $の丸太で出来るだけ多くの丸太を作ってから残りの丸太を買うのが最適になる
$ n+1 $の丸太で作れるものは$ \frac{x(x+1)}{2} \leq n+1 $を満たす最大の$ x $となる
この$ x $を求めるには二分探索とかで求めればいい(C++なら$ \sqrt n $でも通る)
よって答えは$ n - x + 1 $
提出コード

void solve(){
    ll n;
    cin >> n;
    ll i = 1;
    for(;i*(i+1)<=2*n+2;i++){}
    cout << n - i + 2 << endl;
}

C - Large RPS Tournament

文字列$ s $の対戦結果は周期を持つため、全ての対戦結果をシミュレートする必要がない
そのため $ t = s + s $としてシミュレートを行い、その結果を$ s = t $として$ k $回シミュレートした時の先頭の文字が答えになる
提出コード

vector<vector<char>> win = {{'R', 'R', 'P'},
                            {'R', 'S', 'S'},
                            {'P', 'S', 'P'}};
void solve(){
    int n, k;
    string s;
    cin >> n >> k >> s;
    string t = s;
    map<char, int> mp;
    mp['R'] = 0, mp['S'] = 1, mp['P'] = 2;
    for(int j=k;j>0;j--){
        t = "";
        for(int i=0;i<4*n;i+=2){
            t += win[mp[s[i%n]]][mp[s[(i+1)%n]]];
        }
        s = t.substr(n);
    }
    cout << s[0] << endl;
}