SHIINBLOG

CADDi 2018 for Beginners

CADDi 2018 for Beginners に参加しました.

またもや気付いたら始まっていた…
まぁ,言い訳は置いといて,



結果的には全部解けました.
A → B → D → C の順で解いた.

A - 12/22

問題文はこちら

4桁の整数が与えられて, '2' が何個現れるか求めるもの.

C++ で解いたので, string で受けて,単純に'2'の数を数えた.

#include <iostream>
#include <string>

using namespace std;

int count_char(string s,char x) {
    int count;
    for (auto c : s) {
        if ( c == x ) {
            count++;
        }
    }
    return count;
}

int main(){
    string s;
    cin >> s;
    cout << count_char(s,'2') << endl;
}



B - AtCoder Alloy

問題文
hight と width が与えられて,それ以上の金属板はいくつあるかみたいな問題.

これもすぐに書き終わったかな.

#include <iostream>

using namespace std;

int main(void) {
    int n,h,w;
    int count;

    cin >> n;  cin >> h;  cin >> w;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a; cin >> b;
        if( h <= a && w <= b ) {
            count++;
        }
    }
    cout << count << endl;
}



D - Harlequin

一応解いた順番にD問題から.
問題文

交互にリンゴを食べていって,最後のリンゴを食べるのはどちらかっていう問題.


問題を眺めながら紙に書いてたら何か神が降りてきて,

2 で割った余りが全部 0 なら second の人が勝つのでは?
と思って実装してみたら合ってた.

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int n;
    string winner = "second";
    cin >> n;
    

    for(int i=0; i<n; i++) {
        int a;
        cin >> a;
        if ( a % 2 != 0 ) {
            winner = "first";
        }
    }
    cout << winner << endl;
} 

よく見たら, winner = "first" としている部分で break した方が良いのでは…?



C - Product and GCD

問題文

D 問題解く前に1度見て,ぱっと見思いつかなかったので,一旦放置した問題.

なんとなく素因数分解使えそうだな〜と考えていて,

n個に分解するんだから,素因数分解したときの素数がn個以上あれば,それが最大公約数に含まれるじゃん!
と気付いた.


それで,最初書いたのだけれど,
2*n個以上ある場合を考えていなかったので,
問題によっては,WA(間違い)になってしまった.

全然間違っている理由が分からなくて,
いろいろ変えて提出したので間違いだらけになってしまった.
intlong long にしてみたりとか)

#include <iostream>
#include <unordered_map> 

using namespace std;

std::unordered_map<long long,long long> c;

void decompositPrime(long long n)
{
    long long a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            n /= a;
            c[a] += 1;
        } else {
            a++;
        }
    }
    c[n]++;
}

int main(void) {
    long long n;
    long long p;
    long long ans=1;
    cin >> n;  cin >> p;
    decompositPrime(p);
    
    for (auto itr = c.begin(); itr != c.end(); itr++) {
        // if ( itr->second >= n ) {
        while ( itr->second >= n ) {
            itr->second -= n;
            ans *= itr->first;
        }
    }
    cout << ans << endl;
}



今回は, Beginners だけど, 267位だったので,
40分ほど遅れてスタートした割りには良い方なんじゃないだろうか.