PCK2019 本選解説

    解説   競プロ PCK  

本選 1問目 目盛りのないストップウォッチ

問題

目盛りのないストップウォッチがある。このストップウォッチには、0を示す目印と針が一つずつついている。
針は最初目印を指しており、ストップウォッチを起動すると時計回りに回転し始める。
針が目印から$a$度回転した時の経過時間が$t (1 \le t \ le 1000)$秒であると分かっているとき、針の角度が$r$の時の経過時間を求めるプログラムを作成せよ。
ただし、$0 \lt r \lt 360$であるとする。

解法

針の角度が$r$の時の経過時間を$T$とすれば、
$a : t = r : T$が成り立つので、$T = \cfrac{rt}{a}$となる。
したがって、$\cfrac{rt}{a}$を出力すればよい。
時間計算量のオーダーは$O(1)$となる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    long double A, T, R;
    cin >> A >> T >> R;
    cout << setprecision(8) << R*T / A << endl;
}

本選 2問目 ガソリンスタンド

問題

このガソリンスタンドには$1$から$N$の番号が割り当てられた$N (1 \le N \le 10)$個のレーンがある。
ガソリンスタンドに入場した車は、並んでいる車が最も少ないレーンを選び列の末尾に並ぶ。 もし、そのようなレーンが複数ある場合は最も番号が小さいレーンの末尾に並ぶ。
レーンの先頭の車から給油を行い、給油が終わると車はレーンから出ていく。
一度レーンを選んだら車は他のレーンに移ることはなく、並び順が変わることもない。
レーンの数、入場した車と給油が終了したレーンの情報が与えられたとき、給油が終了した車のナンバーを順番に出力するプログラムを作成せよ。 ただし、情報の数$M$は$2 \le M \le 10000$であるとする。

解法

各レーンはキュー構造になっているので、$N$本のキューを用いてシミュレーションをすればよい。
時間計算量のオーダーは$O(M)$となる。$M$の上限は$10000$なので十分高速である。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;

    vector<queue<int>> lanes(N);
    for(int i = 0; i < M; i++){
        int b, n;
        cin >> b >> n;
        if(b == 0){
            n--;
            cout << lanes[n].front() << endl;
            lanes[n].pop();
        } else {
            int lane = 0;
            int len = 1e9;
            for(int l = 0; l < N; l++) {
                if(len > lanes[l].size()){
                    lane = l;
                    len = lanes[l].size();
                }
            }
            lanes[lane].push(n);
        }
    } 
}

本選 3問目 海苔

問題

二枚の長方形の海苔があります。
二枚の海苔それぞれの左端の座標の幅と高さが与えられたとき、重なっていない部分の海苔の面積を出力するプログラムを作成せよ。
ただし、海苔の左端の座標$x,y$、幅$w$、高さ$h$は$(0 \le x, y, w, h \le 1000)$の範囲で与えられる。

解法

全体の面積から重なっている部分の面積を引けばよい。
簡単のために、より左側にある海苔を一枚目の海苔とする。 　　 重なっている幅は$x+w - X$と$W$の小さい方か、その小さい方が負になる場合は$0$になる。 重なっている幅と高さはそれぞれ独立に求められるので、それぞれ独立に求めて重なっている面積を計算すれば良い。
時間計算量のオーダーは$O(1)$になる。

コード

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main(){
    i64 x, y, w, h;
    i64 X, Y, W, H;
    cin >> x >> y >> w >> h;
    cin >> X >> Y >> W >> H;

    if(x > X) { swap(x ,X), swap(y, Y), swap(w, W), swap(h, H); }
    i64 width = max(min(x+w - X, W), 0ll);
    if(y > Y) { swap(x ,X), swap(y, Y), swap(w, W), swap(h, H); }
    i64 height = max(min(y+h - Y, H), 0ll);

    cout << (w*h + W*H) - 2*(width*height) << endl; 
}

本選 4問目 へびの脱皮

問題

頭から尾にかけて一列にならんだマル(o)とバツ(x)からなる模様のへびが発見された。
このへびは脱皮のときに、2つのマルが並んだ部分の間すべてが伸びることで成長する。新たに加わった箇所にはマル、バツ、マルが並んだ模様がつく。
へびの模様と脱皮の回数が与えられたとき、この回数だけ脱皮した後のへびの長さを求めるプログラムを作成せよ。
ただし、へびの長さ$L$は$1 \le L \ le 100$、脱皮の回数$N$は$1 \le N \le 50$であるとする。

解法

マルがとなりあっている個数を$A$とすると$A$は脱皮の度に2倍になる。すると、 $A_{i+1} = 2A_{i}$という漸化式が成り立つ。この漸化式の一般項は$A_N = A_0(2^N - 1)$で与えられる。
へびの長さの増加量はその3倍なので$N$回の脱皮で伸びる長さは$3A_N$となる。
したがって、最初のへびの長さを$L_0$とすれば$N$回脱皮した後のへびの長さ$L_N$は$L_N = L_0 + 3A_0(2^N-1)$となる。 最初にマルがとなりあっている個数を数えるのに$O(L)$時間かかるので、全体の時間計算量オーダーは$O(L)$となる。

コード

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

i64 POW(i64 x, i64 n){
    i64 res = 1;
    while(n){
        if(n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int main(){
    i64 L, N;
    string snake;
    cin >> L >> N >> snake;

    i64 A = 0;
    for(int i = 1; i < L; i++) {
        if(snake[i-1] == snake[i] && snake[i] == 'o') A++;
    }

    cout << L + 3ll*A*(POW(2, N) - 1ll) << endl;
}