CADDi 2018 for Beginnersに参加しました - プログラミング初心者の勉強日記

CADDi 2018 for Beginnersに参加したので記録を残したいと思います.

今回のコンテストは、キャディ株式会社主催のABC/ARC形式のプログラミングコンテストで、レートが~1199までの人が参加できる初級者向けコンテストに参加しました。要はいつものABC形式ですね。

問題のタイトルは以下のようになっています. 詳しい問題文は下のリンクから、公式のコンテストページでご確認ください.

A - 12/22
- 問題の概要
- 解法
B - AtCoder Alloy
- 問題の概要
- 解法
C - Product and GCD
- 問題の概要
- 解法
D - Harlequin
- 問題の概要
- 解法
感想

A - 12/22

問題の概要

十進法表記でちょうど4桁の整数 $N$ が与えられる. $N$ の十進法表記に何個の「２」が現れるかを求める.

解法

$N$ を文字列として受け取り、先頭から2があるかどうかをfor文で確認すれば良いです.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string N;
    cin >> N;
    int rsl = 0;
    rep(i, 0, N.size()) {
        if(N[i] == '2') rsl++;
    }

    cout << rsl << endl;
}

B - AtCoder Alloy

問題の概要

長方形の板状の素材が $N$ 枚ある. $i$ 番目の素材の縦の長さ、横の長さはそれぞれ $A_i , B_i$ で与えられる. 縦の長さが $H$ 、横の長さが $W$ の長方形の板を作りたい. 板を長方形の変に平行に切断することで、欲しい板を作ることができる素材は $N$ 枚中何枚あるかを求める. ただし、素材は向きが決まっているため回転することができない.

解法

$i$ 番目の素材を適切に切断することによって、縦の長さが $H$ 、横の長さが $W$ の板を作ることができるとは、 $A_i \geq H$ かつ $B_i \geq W$ を満たすときです. したがって、この条件を満たす素材の個数をカウントしてあげればよいことになります.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, H, W;
    cin >> N >> H >> W;
    int A[N], B[N];
    rep(i, 0, N) cin >> A[i] >> B[i];

    int rsl = 0;
    rep(i, 0, N) {
        if(A[i] >= H and B[i] >= W) rsl++;
    }

    cout << rsl << endl;

}

C - Product and GCD

問題の概要

$a_1, a_2, \cdots a_N$ がある. $a_1, a_2, \cdots a_N$ の値はわからないが、 $a_1 \times a_2 \times \cdots \times a_N = P$ はわかっている.

このとき、 $a_1, a_2, \cdots a_N$ の最大公約数として考えられるもののうち、最大値を求める.

解法

$N$ 個の数列の積 $P$ が与えられているので、 $P$ を素因数分解します. 素因数分解した結果を、 $i$ 番目の素因数を $p_i$ としたとき、

$$ P = p_1^{b_1} \times p_2^{b_2} \times \cdots \times p_m^{b_m} $$

と表せたとします. $n$ が $N$ 個の数列の公約数になるのは、数列の各項が素因数の積で $n$ を作れるときです. 最大公約数はそのうち最大のものなので、共通の素因数を全て使って掛け合わせたものになります.

例えば、 $20 = 2^{2} \times 5$ と $8 = 2^{3}$ の最大公約数は共通の素因数 $2$ が2つなので、それらの積で表される、 $2 \times 2 = 4$ が最大公約数になります.

したがって、Pの各素因数を先頭から順に $N$ 個の数列の項に振り分けてあげれば良いことになります.

$a_1 \times a_2 \times a_3 = 3240 = 2^{3} \times 3^{4} \times 5$ のとき、素因数2を $a_1, a_2, a_3$ にそれぞれ一つずつ、3もそれぞれ1つずつ振り分けることができます. 5は1つしかなく、3つの項に振り分けることができません. したがって、 $a_1 = a_2 = a_3 = 2 \times 3 = 6$ を作ることができ、最大公約数は6になります. (残った素因数5を適当に $a_1$ とかに振り分けても共通の素因数を他の項が持たないので最大公約数に影響を与えません.)

したがって、 $b_i \geq N$ のとき、 $p_i$ を各項に $b_i / N$ 個振り分けていけば良いことになります.

素因数分解の部分は蟻本を参考にしました. 計算量は $\mathcal{O}(\sqrt{n})$ なので、間に合います.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)

typedef long long ll;

map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, P;
    cin >> N >> P;

    map<ll, ll> m = prime_factor(P);
    
    ll rsl = 1;
    for(map<ll, ll>::iterator itr = m.begin(); itr != m.end(); itr++ ){
        if(itr->second >= N) rsl *= (pow(itr->first, itr->second / N));
    }
    cout << rsl << endl;

}

D - Harlequin

問題の概要

$N$ 色のりんごがあり、 $i$ 番目の色のりんごは $a_i$ 個ある. このとき、先攻、後攻にわかれて以下の行動を交互に行う.

1個以上のリンゴを選んで食べる. ただし、一度に選ぶリンゴは全て異なる色でなければならない.

最後のリンゴを食べた人を勝者とする. 先攻と後攻が最善を尽くすとき、どちらが勝つかを求める

解法

入力例1を例に考察してみます.

1番目のリンゴが1個、2番目のリンゴが2個あるとき、先攻は1番目のリンゴを1個食べれば、2番目のリンゴが2個残ります. このとき、後攻は2番目のリンゴを1個食べることしか選択肢がありません. 後攻が2番目のリンゴを一個食べた後は2番目のリンゴが1 個だけ残り、それを先攻が食べることで、先攻が勝利することができます.

毎ターン、各リンゴは最大でも1つしか減らないので、自分のターンにリンゴが奇数個ある場合、交互に1つずつ食べていくと最終的に自分が最後の一個を食べることができます. 逆に偶数個のときは、自分が最初にそのリンゴに手を出すと相手に最後の一個を食べられてしまいます.

1つでも奇数個のリンゴが存在すれば、そのリンゴだけを食べることで、全色のリンゴの個数を偶数個にすることができます. 全て偶数個になってしまったら、上で述べた理由から最後のリンゴを相手に食べられてしまうので、相手にその状況を作れた方が勝者となります.

したがって、各リンゴの個数のうち奇数のものが一つでも存在したら先攻が勝利します.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)

typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    int a[N];
    int cnt_even = 0;
    rep(i, 0, N) {
        cin >> a[i];
        if(a[i] % 2 == 0) cnt_even++;
    }

    if(cnt_even == N) cout << "second" << endl;
    else cout << "first" << endl;

}

感想

パフォーマンス1600の順位26位という私にしては信じられないぐらいの結果でかなり嬉しいです.

C問題でWAを出さずにいたら1桁順位も狙え賞金をもらえたと思うと少し悔しいですが、久しぶりの全完で満足しています.

少し水色に近づいたので、これからも精進していき、一日でも早く「水色になるまでにやったこと」という記事をかけるように頑張っていきます.