パソコン甲子園2019に参加して来ました。
弊学で行われた成果報告会の為に解説を書かされたのでここに公開しておきます。
僕が実際に参加したときに解いた問題しか解説は書いていません。ご容赦ください。

ここに書いた内容はすべてここにあります
GitHub - ugis70194/PCK
ジャッジを通したい方はこちらから
AOJ-PCK(パソコン甲子園過去問)

予選問題

予選 1問目柴犬の数

問題

公園に4種類の柴犬がいます。柴犬の数はそれぞれ、 $R, B, W, G$ で与えられる。このとき、柴犬の総数を求めるプログラムを作成せよ。
ただし、 $1 \le R,B,W,G \le 100$ を満たす。

解説

$R, B, W, G$ すべてを足したものを出力すればよい。
時間計算量のオーダーは $O(1)$ となる。

コード

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

int main(){
    int R, B, W, G;
    cin >> R >> B >> W >> G;
    cout << R + B + W + G << endl;
}

予選 2問目アスキー文字

問題

コンピューター内部ではアルファベットの大文字'A'から'Z' に連続してそれぞれ数値の65から90が割り当てられており、同様に、小文字'a'から'z'にそれぞれ数値の97から122が割り当てられている。
数値 $N$ が与えられたとき、アルファベットの大文字であれば1を、小文字であれば2を、それ以外であれば0を出力するプログラムを作成せよ。ただし $N$ は $1 \le N \le 127$ を満たす。

解説

if文を用いて、 $N$ が大文字の範囲内なら1を、小文字の範囲内なら2をそれ以外なら0を出力するようにする。
時間計算量のオーダーは $O(1)$ となる。

コード

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

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

    if(65 <= N && N <= 90) cout << 1 << endl;
    else if(97 <= N && N <= 122) cout << 2 << endl;
    else cout << 0 << endl;
}

予選 3問目２の累乗

問題

数値 $N$ が与えられる。
$N$ 以下の数の中で最大の2の累乗を求めるプログラムを作成せよ。ただし、 $N$ は $1 \le N \le 10^{6}$ を満たす。

解説

数値のbit表現を利用する。
bit表現においてbitが一つだけ立っているときは、10進数では2の累乗になる。
したがって、立っているbitを左にずらしたときに与えられた数より大きくならなければ、bitを左にずらし続ければよい。時間計算量のオーダーは $O(\log_2 N)$ となる。

コード

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

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

    int ans = 1;
    while(N >= (ans << 1)) ans <<= 1;
    cout << ans << endl;
}

予選 4問目集会所

問題

東西に一直線に伸びる道路に沿った村がある。
最も西の地点を0番目として、等間隔に東に向かって順に地区番号が与えられている。ある時刻に一斉にすべての村人が自分の家から集会所に向かったとき、全員が集まるのに必要な時間が最小になるような場所に集会所を建てることにした。
家の立っている地点の番号が与えられたとき、最適な場所に集会所と建てた場合に、すべての村人が集会所に集まるのに必要な時間の最小値を求めるプログラムを作成せよ。
ただし、家の数 $N$ は $1 \le N \le 1000$ を、家が立っている地区番号 $x_i$ は $0 \le x_i \le 2000$ を満たす。
集会所はすで家が立っている地区に建ててもよい。また、すべての村人は隣の地区まで1分で移動できるものとする。

解説

集会所にたどり着くのに最も時間がかかるのは西の端か、東の端の家に住んでいる村人なので、そこだけ考えればよい。
そして、集会所がこれら2つの地区のちょうど真ん中に建っているとき、村人全員が集会所に集まるまでにかかる時間が最小になる。
したがって、西の端の家から集会所までの距離と東の端から集会所までの距離のより大きい方が最小の時間になる。
時間計算量のオーダーは $O(N)$ となる。

コード

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

int main(){
    int N;
    cin >> N;
    vector<int> X(N);
    for(int i = 0;i < N; i++) cin >> X[i];
    int MIN = *min_element(begin(X), end(X));
    int MAX = *max_element(begin(X), end(X));
    int m = (MIN + MAX) / 2;
    cout << max(abs(MIN - m), abs(MAX - m)) << endl;
}

予選 5問目ねこのあな

問題

中が行き止まりになっている横穴がある。この横穴は猫がちょうど一匹入れるくらいの横幅で、奥行きは100匹の猫が入るのに十分である。横穴に出入りした猫のリストが与えられるので、リストの先頭から順に見ていったとき、それより後ろを見なくても誤りと判定できる最初の位置を求めるプログラムを作成せよ。ただし、猫は100匹いて、1から100までの番号が与えられているものとする。 $i$ 番目に横穴に入った猫の番号が $a_i$ 、出た猫の番号が $-a_i$ で与えられる。
また、リストの長さ $L$ は $1 \le L \le 10000$ の範囲で与えられる。

解説

明らかに誤りなのは、リスト上で

既に横穴に入っている猫が横穴に入ったとき
一匹も横穴に入っていないのに猫が出てきたとき
一番最後に入った猫でない猫が出てきたとき
横穴に入っていない猫が出てきたとき

の4つの状況が起こった場合である。
横穴はスタック構造になっているのでスタックと配列を用いてシミュレーションをすればよい。配列は今その番号の猫が横穴に入っているかどうかのフラグを管理するために用いる。
上記4つをスタックと配列の操作に直せば以下のようになる。

今見ている値に横穴に入っているフラグが立っている
スタックのサイズが0なのに今見ている値が負
スタックの一番上の値といま見ている値に-1をかけたものが異なる
今見ている値に-1をかけたものに横穴に入っているフラグが立っていない

したがって、これらのパターンを検知するようにアルゴリズムを組めばよい。リストを最後まで見る必要がある場合があるので、時間計算量は $O(L)$

コード

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

int main(){
    int L;
    cin >> L;
    vector<int> C(L);
    for(int i = 0; i < L; i++) cin >> C[i];
    vector<int> in(L+1,0);
    stack<int> s;

    int ans = 1e9;
    for(int i = 0; i< L; i++){
        if(C[i] > 0){
            if(in[C[i]]) ans = min(ans, i+1);
            else in[C[i]] = 1, s.push(C[i]);
        } 
        if(C[i] < 0){
            if(s.size() == 0) ans = min(ans, i+1);
            else if(in[-C[i]] && s.top() != -C[i]) ans = min(ans, i+1);
            else if(!in[-C[i]]) ans = min(ans, i+1);
            else in[-C[i]] = 0, s.pop();
        }
    }

    if(ans == 1e9) cout << "OK" << endl;
    else cout << ans << endl;
}

予選 6問目床

問題

博士の家の床には正方形のタイルが敷きつめられている。はじめに部屋の適当なタイルをひとつ選び、以下の方法で色を塗っていく。

タイルを塗る色を、赤、黄、青の順に変えていき、青の次はまた赤から始める。
すでに色を塗った領域の隣に正方形を追加し、そこに色を塗る。それらを合わせた領域が長方形になるようにする。正方形を追加する方向は、東、北、西、南の順に変えていき、南の次はまた東から始める。

最初に赤く塗ったタイルから東を $x$ の正の方向、北を $y$ の正の方向として、東西方向に $x$ 個,南北方向に $y$ 個移動したところにあるタイルの色を求めるプログラムを作成せよ。
ただし、 $x, y$ は $-10^{6} \le x, y \le 10^{6}$ の範囲で与えられる。

解説

正方形の大きさはかなりの速さで増加していくことが分かる。
正方形の一辺の長さは1, 1, 2, 3, 5 ...となっている。
これはフィボナッチ数列であるので、 $i$ 個目の正方形の一辺の長さは動的計画法を用いて高速に求められる。最初に赤く塗ったタイルの左下端を原点(0,0)として、 $i$ 個目の正方形の左下端の座標と右上端の座標をもっておけば、座標(x,y)の位置のタイルが何個目の正方形に属しているかがわかる。
したがって、 $i$ 個目の正方形の左下端の座標と右上端の座標、面積、色を最初に赤く塗ったタイルから順に求めていって、座標(x, y)が正方形の中に入っているか逐次判定すればよい。
フィボナッチ数列は2の累乗よりもすこし増加量が小さいので時間計算量はおおまかに $\log (max(|x|, |y|))$ 程度となる。

コード

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

struct coor{
    pair<i64, i64> x, y;
};

int main(){
    i64 X,Y;
    cin >> X >> Y;
    vector<i64> fib(500);
    fib[0] = fib[1] = 1;
    for(int i = 2; i < 500; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    coor now = {{0, 1}, {0, 1}};
    i64 way = 0;
    i64 color = 0;
    int i = 1;
    while(i < 500){

        //cout << color << " -----" << endl;
        //cout << now.x.first << " " << now.x.second << endl;
        //cout << now.y.first << " " << now.y.second << endl;

        if(now.x.first <= X && X < now.x.second 
        && now.y.first <= Y && Y < now.y.second){
            cout << color+1 << endl;
            return 0;
        }
        
        coor next;
        if(way == 0) {
            next.x.first = now.x.second;
            next.x.second = next.x.first + fib[i];
            next.y.first = now.y.first;
            next.y.second = next.y.first + fib[i];
        }
        if(way == 1){
            next.x.second = now.x.second;
            next.x.first = next.x.second - fib[i];
            next.y.first = now.y.second;
            next.y.second = next.y.first + fib[i];
        }
        if(way == 2){
            next.x.second = now.x.first;
            next.x.first = next.x.second - fib[i];
            next.y.second = now.y.second;
            next.y.first = now.y.second - fib[i]; 
        }
        if(way == 3){
            next.x.first = now.x.first;
            next.x.second = next.x.first + fib[i];
            next.y.second = now.y.first;
            next.y.first = next.y.second - fib[i];
        }

        now = next;
        i++, way++, color++;
        way %= 4;
        color %= 3;
    }

    cout << 0 << endl;
}

本選問題

本選 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)$ の範囲で与えられる。

解説

全体の面積から重なっている部分の面積を引けばよい。
簡単のために、より左側にある海苔を一枚目の海苔とする。
そうすれば、海苔の重なり方は3通りになる。　　重なっている幅は $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$ であるとする。

解説

たとえば、長さ３のへびoooが１回脱皮すると、左から1番目と2番目、2番目と3番目のマルの間にマル、バツ、マルが並んだ模様が加わるので、
脱皮後のへびはooxoooxooとなる。
もう一回脱皮するとooxooxooxoooxooxooxoo となり、へびの長さは21となる。
ここで長さを増加する箇所(マルが隣り合っている箇所)の増え方に注目する。
マルがとなりあっている個数を $A$ とすると $A$ は脱皮の度に2倍になる。すると、 [tex: A{i+1} = 2A{i}]という漸化式が成り立つ。この漸化式の一般項は[tex: A_N = A_0(2^N - 1)]で与えられる。
へびの長さの増加量はその3倍なので $N$ 回の脱皮で伸びる長さは $3A_N$ となる。
したがって、最初のへびの長さを $L_0$ とすれば $N$ 回脱皮した後のへびの長さ $L_N$ は[tex: 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;
}

最後に

ugisの活動記録

PCK2019予選・本選解説

予選問題

予選 1問目柴犬の数

予選 2問目アスキー文字

予選 3問目２の累乗

予選 4問目集会所

予選 5問目ねこのあな

予選 6問目床

本選問題

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

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

本選 3問目海苔

本選 4問目へびの脱皮

予選問題

予選 1問目 柴犬の数

予選 2問目 アスキー文字

予選 3問目 ２の累乗

予選 4問目 集会所

予選 5問目 ねこのあな

予選 6問目 床

本選問題

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

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

本選 3問目 海苔

本選 4問目 へびの脱皮

予選 1問目柴犬の数

予選 2問目アスキー文字

予選 3問目２の累乗

予選 4問目集会所

予選 5問目ねこのあな

予選 6問目床

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

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

本選 3問目海苔

本選 4問目へびの脱皮