CADDi 2018 for Beginners - zeronosu77108’s blog

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（間違い）になってしまった．

全然間違っている理由が分からなくて，
いろいろ変えて提出したので間違いだらけになってしまった．
（int を long 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分ほど遅れてスタートした割りには良い方なんじゃないだろうか．