AtCoder Beginner Contest 179 ABC179 参加記

A - Plural Form

問題へのリンク

解説

末尾を確認します。

実装

int main() {
    string S;
    cin >> S;
    if(S.back() == 's'){
        S.push_back('e');
    }
    S.push_back('s');
    cout << S << endl;
}

B - Go to Jail

問題へのリンク

解説

連続する3つについて全てゾロ目かどうかをチェックします。

実装

int D[111][2];
int main() {
    int N;
    cin >> N;
    bool ok = false;
    rep(i,N){
        cin >> D[i][0] >> D[i][1];
    }
    rep(i,N-2){
        if(D[i][0] == D[i][1]){
            if(D[i+1][1] == D[i+1][0]){
                if(D[i+2][0] == D[i+2][1]){
                    ok = true;
                }
            }
        }
    }
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - A x B + C

問題へのリンク

解説

を固定します。が正になるようなの個数を割り算で求めます。

実装

int main() {
    ll N;
    cin >> N;

    ll ans = 0;
    for(ll a = 1; a <= N; a++){
        if(N%a == 0){
            ans += N / a - 1;
        }
        else ans += N/a;
    }
    cout << ans << endl;
}

D - Leaping Tak

問題へのリンク

解説

区間addを配らなければならないので計算量が爆発しそうですが、imos法をdpを進めながら使うことで、解決します。 初期状態として、

dp[0] = 1, dp[1] = -1

とするのは、区間[0, 1)に1があることに対応します。

実装

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> l(K), r(K);
    rep(i,K)cin >> l[i] >> r[i];
    vector<mint> dp(N+10, 0);
    dp[0] = 1;
    dp[1] = -1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            int L = min(N, i + l[j]);
            int R = min(N+1, i + r[j])+1;
            dp[L] += dp[i];
            dp[R] -= dp[i];
        }
        dp[i+1] += dp[i];
    }
    cout << dp[N-1] << endl;
}

E - Sequence Sum

問題へのリンク

解説

鳩の巣原理により、項目までにループします。よって、ループを見つけるまで計算し、後はいい感じに和を取ります。実装が大変です。

実装

int main() {
    ll N, X, M;
    cin >> N >> X >> M;
    ll a = X;
    map<ll, int> mp;
    ll sum = a;
    ll cnt = 1;
    vector<ll> cumsum(1, 0);
    cumsum.push_back(a);
    mp[a] = 1;
    while(mp.find((a*a)%M) == mp.end()){
        a *= a;
        a %= M;
        sum += a;
        mp[a] = ++cnt;
        cumsum.push_back(sum);
        if(cnt == N){
            cout << sum << endl;
            return 0;
        }
        dump(a, cnt);
    }
    if(a == 0){
        cout << sum << endl;
        return 0;
    }
    int l_cnt = mp[(a*a)%M]-1;
    int r_cnt = mp[a];
    int len = r_cnt - l_cnt;
    ll ans = cumsum[l_cnt];
    N -= l_cnt;
    ans += N / len * (cumsum[r_cnt] - cumsum[l_cnt]);
    ans += cumsum[l_cnt + N%len] - cumsum[l_cnt];
    cout << ans << endl;
}

F - Simplified Reversi

問題へのリンク

まだわかっていません。