AtCoder Beginner Contest 161（ABC161）

前回に引き続き今回も青パフォ〜
E解けなかったのは反省点

E解けなかったけど伸びたのでよし！ｗ
Bondo416さんのAtCoder Beginner Contest 161での成績：497位
パフォーマンス：1848相当
レーティング：1347→1408 (+61) :)
Highestを更新し、3 級になりました！#AtCoder https://t.co/74OChIBg6F pic.twitter.com/YwfHMVbljx
— ボンド@競プロ (@bond_cmprog) 2020年4月4日

A - ABC Swap

配列に入れてswapでもいいけど Z X Yの順に出力すればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y << endl;
}

B - Popular Vote

総和を求めてから愚直に全部チェックしていけばいい
整数で扱いたいので $sum \leq 4 M A_i$ を満たす個数が $M$ 以上になるかどうか
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    int sum = 0;
    REP(i,N){
        cin >> A[i];
        sum += A[i];
    }
    int cnt = 0;
    REP(i,N){
        if(sum <= 4 * M * A[i]) cnt++;
    }
    if(cnt >= M) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Replacing Integer

$N$ を $N-K$ で置き換える操作はmodを考えてあげるといい
この問題の場合、差の絶対値で求めるのでmodを取った後に $|N-K|$ と比較して小さい方を出力すればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    N %= K;
    cout << min(N, abs(N - K)) << endl;
}

条件を満たす文字列の列挙はdfsとかで出来る
最初dfsで出来た順でK個目を出力するみたいなことしててこれ辞書順じゃんになったのでbfsで書き直してAC
1桁目は1~9をqueueに入れて、2桁目からは0~9の順に条件を満たすものをくっつけたものを同様にqueueに入れていきK番目に出来た文字列が答え
コンテスト後にTLで知ったけどdfsでも10桁しかないから全列挙してからソートするとかでも出来るんだね（サンプルに最大ケースありますが…）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    queue<string> q;
    string t = "";
    q.push(t);
    while(!q.empty() && K > 0){
        string cur = q.front();
        q.pop();
        if(cur == ""){
            for(char c='1';c<='9';c++){
                string tmp = cur + c;
                K--;
                if(K == 0){
                    cout << tmp << endl;
                    break;
                }
                q.push(tmp);
            }
        }
        else{
            for(char c='0';c<='9';c++){
                if(abs((cur.back() - '0') - (c - '0')) > 1) continue;
                string tmp = cur;
                tmp += c;
                K--;
                if(K == 0){
                    cout << tmp << endl;
                    break;
                }
                q.push(tmp);
            }
        }
    }
}

E - Yutori

これ難しい
貪欲っぽいけどわからなかった
グラフっぽく考えて出来ないかなーとかも考えてたけど愚直に辺貼ったら死にそう、とか考えてたら終わった
左右からの貪欲とかでいいっぽい？ちゃんと通しておかないと

F - Division or Substraction

D解いた時にEが20人Fが60人くらい通してたのでEチラ見してFから解いた
制約的にも、操作的にも約数は絶対使うのでまず約数を列挙して、愚直にシミュレートする（1は使えないので注意）
これだけだとサンプルの答えよりも少なくなるので、サンプルを睨むと $N-1$ が答えになっているのでこれを考える
割り算の操作をしないと考えると $N mod K = 1$ ならば条件を満たすので、 $N - 1$ の約数で条件を満たすものを数えればいい（解説見ると1以外の全部の約数で大丈夫っぽい）

提出コード

vector<ll> divisor(ll n){
    vector<ll> res;
    for(ll i=1; i*i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    int ans = 0;
    auto res = divisor(N);
    auto res2 = divisor(N-1);
    REP(i,res.size()){
        if(res[i] == 1) continue;
        ll tmp = N;
        while(tmp > 1){
            if(tmp % res[i] == 0) tmp /= res[i];
            else{
                tmp %= res[i];
                if(tmp < res[i]) break;
            }
        }
        if(tmp == 1) ans++;
    }
    REP(i,res2.size()){
        if(res2[i] == 1) continue;
        ll tmp = N;
        while(tmp > 1){
            if(tmp % res2[i] == 0) tmp /= res2[i];
            else{
                tmp %= res2[i];
                if(tmp < res2[i]) break;
            }
        }
        if(tmp == 1) ans++;
    }
    cout << ans << endl;
}