【ABC367】AtCoder Beginner Contest 367【C++】

コンテスト名

AtCoder Beginner Contest 367

コンテストURL

https://atcoder.jp/contests/abc367

開催日

2024/08/17 21:00-22:40

---

A: Shout Everyday

解法

• 就寝時間が日をまたぐときとまたがないときで場合分けする

ABC367A.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;

    if(b<c){
        if(a<b || a>c){
            cout << "Yes" << endl;
            return 0;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }else{
        for(int i=b; i<24; i++){
            if(i==a){
                cout << "No" << endl;
                return 0;
            }
        }
        for(int i=0; i<=c; i++){
            if(i==a){
                cout << "No" << endl;
                return 0;
            }
        }

        cout << "Yes" << endl;
    }

    return 0;
}

B: Cut .0

解法

• 入力を文字列として受け取る
• 文字列の末尾が 0 であれば削除することを繰り返したあと、末尾が . であればさらに削除する

ABC367B.cpp

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

int main(){
    string s;
    cin >> s;

    while(s.back()=='0'){
        s.pop_back();
    }

    if(s.back()=='.'){
        s.pop_back();
    }

    cout << s << endl;
    return 0;
}

C: Enumerate Sequences

解法

• 再帰関数
• 数列を辞書順に列挙して判定する

ABC367C.cpp

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

int n, k;
vector<int> R;

void f(string s){
    if(s.size()==n){
        int sum = 0;
        for(int i=0; i<n; i++){
            if((s[i] - '0')>R[i]){
                return;
            }
            sum += (s[i] - '0');
        }

        if(sum%k!=0){
            return;
        }

        for(int i=0; i<n; i++){
            if(i){
                cout << " ";
            }
            cout << s[i];
        }
        cout << endl;

        return;
    }

    for(char c='1'; c<='5'; c++){
        s.push_back(c);
        f(s);
        s.pop_back();
    }
}

int main(){
    cin >> n >> k;

    R.resize(n);
    for(int i=0; i<n; i++){
        cin >> R[i];
    }

    f("");

    return 0;
}

D: Pedometer

解法

• 2 周に伸ばして考える
• 休憩所 $1$ からの歩数を $M$ で割った余りが等しい休憩所同士の移動にかかる歩数は $M$ の倍数になる
• 前から順番に $i + N - 1$ 番目の休憩所までを範囲として、休憩所 $1$ からの歩数を $M$ で割った余りが等しい休憩所の数を求める

ABC367D.cpp

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<int> A(2*n);
    for(int i=0; i<n; i++){
        cin >> A[i];
        A[i+n] = A[i];
    }

    vector<int> S(2*n-1);
    map<int, int> M;
    for(int i=0; i<2*n-2; i++){
        S[i+1] = (S[i] + A[i])%m;
        if(i<n){
            M[S[i]]++;
        }
    }

    long long int ans = 0;
    for(int i=0; i<n; i++){
        M[S[i]]--;
        ans += M[S[i]];
        M[S[i+n]]++;
    }

    cout << ans << endl;
    return 0;
}

E: Permute K times

解法

• ダブリング
• $\text{D} [i][j]$ := $j$ から $2^i$ 回遷移した先
• $j$ から $2^{i+1}$ 回遷移した先 $\text{D} [i+1][j] = \text{D} [i][\text{D} [i][j]]$ で求められる
  • $K \leqq 10^{18} < 2^{60}$ だから、最初に $i = 1, \cdots, 60$ まで初期化する
• 計算量は $O(N \ \log K)$

ABC367E.cpp

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

int main(){
    int n;
    long long int k;
    cin >> n >> k;

    vector<int> X(n), A(n);
    for(int i=0; i<n; i++){
        cin >> X[i];
        X[i]--;
    }
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    vector<vector<int>> D(60, vector<int>(n));
    D[0] = X;
    for(int i=0; i<60-1; i++){
        for(int j=0; j<n; j++){
            D[i+1][j] = D[i][D[i][j]];
        }
    }

    vector<int> ans(n);
    for(int j=0; j<n; j++){
        int tmp = j;
        for(int i=0; i<60; i++){
            if(k&(1LL<<i)){
                tmp = D[i][tmp];
            }
        }
        ans[j] = A[tmp];
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }
        cout << ans[i];
    }

    cout << endl;
    return 0;
}