PCK2019 予選解説

予選 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;
}