競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 24/25/26

- 24 数当てゲーム

  • 問題概要

0から9までの数字に一つだけあたりの数字があります。
4つの数字が与えられ,その中に当たりの数字が含まれていないならNO,含まれているならYESが与えられます。
これが複数回与えられ、答えが特定できるような入力が与えられるので当たりの数字を求めてくださいという問題です。

  • 解説

YESなら4つの数字以外は外れ,NOなら4つの数字の外れを確定します。
当たりの候補を限定していけば解が求まります。

#include<iostream>
#include<string>
using namespace std;

bool num[10];
int main(void){
    int N;
    int input[10];
    int n;
    for (int i = 0; i < 10; i++){
        num[i] = true;
        input[i] = -1;
    }
    cin >> N;

    string str;
    for (int j = 0; j < N; j++){
        for (int i = 0; i < 4; i++){
            cin >> n;
            input[n] = j;
        }
        cin >> str;
        if (str == "YES")
            for (int i = 0; i < 10; i++){
                num[i] &= (input[i] == j);
            }
        else
            for(int i = 0; i < 10; i++){
                num[i] &= (input[i] != j);
        }
    }
    for (int i = 0; i < 10; i++){
        if (num[i])cout << i << endl;
    }
    return 0;
}

- 25 有限小数

  • 問題概要

N/Mが有限小数であるかを求める問題です。

  • 解説

"10進数の"有限小数であるかを求めます。
言い換えると,N*10^p \equiv 0 (mod M)であるようなpが存在するかを求めます。
これを求めるにあたり、Mに2と5以外のNが持たない素因数を持っている場合,どんな10^pを掛けてもMで割り切れないため無限小数となります。
N/Mを先に約分するために,gcd(N,M)で両方を割っておきます。(ソースコードでは何故かしていない)
次に,NとMをできる限り2と5で割り,それぞれいくつずつ因数としてもっていたかをカウントします。
この時点で,有限小数ならばNはMで割り切れます。Mで割り切れない場合はMにNが持たない2と5以外の素因数が含まれるからです。
あとは必要な回数だけ2と5を掛けます。
このとき1の位の計算だけで良いのでmod10を使えばオーバーフローを気にしなくて良いです。

初期状態でN/Mが割り切れるときはそこだけ調整が必要です。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define LL long long
int main(void){
    LL N, M;
    cin >> N >> M;
    if (N%M == 0){
        string str = to_string(N / M);
        for (int i = (int)str.size() - 1; i >= 0; i--){
            if (str[i] != '0'){
                cout << str[i];
                break;
            }
        }
    }
    else{
        int nx, ny;
        nx = ny = 0;
        while (N % 2 == 0)N /= 2, nx++;

        while (N % 5 == 0)N /= 5, ny++;

        while (M % 2 == 0)M /= 2, nx--;

        while (M % 5 == 0)M /= 5, ny--;
    //	cout << nx << " " << ny << endl;
        if (N%M){
            cout << -1 << endl;
            return 0;
        }
        while (nx < 0 || ny < 0)nx++, ny++;
        LL res = N / M;
        res %= 10;
        LL tmp = 1;
        while (nx--){
            tmp = (tmp * 2) % 10;
        }
        if (ny>0)tmp *= 5;
        res = (res*tmp) % 10;
        cout << res << endl;
    }
    return 0;
}

- 26 シャッフルゲーム

  • 問題概要

3個のカップが一列に並んでいます。
当たりのカップの初期位置が与えられます。
どのカップの場所を入れ替えたかという情報がM回順に与えられるので最終的な当たりのカップの位置を答えてくださいという問題です。

  • 解説

配列を用意してスワップしてやるだけです。

#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
    bool c[4] = { false };
    int n, m, l;
    cin >> n;
    c[n] = true;
    cin >> n;
    while (n--){
        cin >> m >> l;
        swap(c[m], c[l]);
    }
    for (int i = 0; i < 4; i++){
        if (c[i])cout << i << endl;
    }
    return 0;
}