AtCoder Beginner Contest 179（ABC179）

atcoder.jp

Dに殺されてしまった
Bondo416さんのAtCoder Beginner Contest 179での成績：1919位
パフォーマンス：1181相当
レーティング：1446→1422 (-24) :(#AtCoder #ABC179 https://t.co/Le60l2AZhL

— ボンド@競プロ (@bond_cmprog) September 19, 2020

A - Plural Form

場合分けをして末尾にくっつける
提出コード

void solve(){
    string s;
    cin >> s;
    if(s.back() == 's') s += "es";
    else s += 's';
    cout << s << endl;
}

B - Go to Jail

ゾロ目が続いている個数をcurとして
ゾロ目ならインクリメント、そうでないなら0にする
そのcurのmaxが3以上なら"Yes"そうでないなら"No"
提出コード

void solve(){
    int N;
    cin >> N;
    int cur = 0;
    int ans = 0;
    REP(i,N){
        int d1, d2;
        cin >> d1 >> d2;
        if(d1 == d2) cur++;
        else cur = 0;
        chmax(ans, cur);
    }
    if(ans >= 3) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - A x B + C

何もわからなかったのでosa_k法で愚直に求めた
Cを固定するとがわかるのでABを素因数分解する
その約数の個数は各素因数の個数+1の積になる
提出コード

void solve(){
    int N;
    cin >> N;
    ll ans = 0;
    auto spf = smartPrimeFactors(N);
    for(int c=1;c<=N;c++){
        int ab = N - c;
        if(ab == 0) continue;
        auto res = factorize(ab, spf);
        ll tmp = 1;
        for(auto [num, cnt] : res){
            tmp *= (cnt + 1);
        }
        ans += tmp;
    }
    cout << ans << endl;
}

D - Leaping Tak

愚直しか思いつかなかった
DPの遷移式を見ると、各区間の連続部分の和になるので累積和やimos法で高速化出来る
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> L(N), R(N);
    REP(i,K) cin >> L[i] >> R[i];
    vector<mint> dp(N+10), imos(N+10);
    dp[0] = 1;
    mint add = 0;
    REP(i,N){
        add += imos[i];
        dp[i] += add;
        REP(j,K){
            int l = L[j] + i;
            int r = R[j] + i + 1;
            if(l < N) imos[l] += dp[i];
            if(r < N) imos[r] -= dp[i];
        }
    }
    cout << dp[N-1] << endl;
}

E - Sequence Sum

の値は未満となるのでNが大きくても周期性を持つことがわかる
そのため、ループ検出をする方法やダブリングで解くことが出来る
実装はダブリングのほうが個人的には楽だと思う
ダブリングのテーブルと一緒に和のテーブルも持つと総和も求めることが出来る
ゆきことかにも類題がある
yukicoder.me

提出コード

void solve(){
    ll N, X, M;
    cin >> N >> X >> M;
    vector<vector<ll>> val(40, vector<ll>(M));
    vector<vector<ll>> to(40, vector<ll>(M));
    for(ll i=0;i<M;i++){
        val[0][i] = i;
        to[0][i] = (i * i) % M;
    }
    REP(i,40-1) REP(j,M){
        to[i+1][j] = to[i][to[i][j]];
        val[i+1][j] = (val[i][j] + val[i][to[i][j]]);
    }
    ll cur = X, ans = 0;
    for(ll i=39;i>=0;i--){
        if(N >> i & 1){
            ans += val[i][cur];
            cur = to[i][cur];
        }
    }
    cout << ans << endl;
}