diverta 2019 Programming Contest - 競プロやります。

C - AB Substrings
- 方針
- ソースコード
D - DivRem Number
- 方針
- ソースコード

C - AB Substrings

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

方針

まず各 $s_i$ の中に含まれる 'AB' は文字列の連結の方法に関わらず、最終的な文字列にも残ります。連結により 'AB' の数が減ることは無く、増えるのは 'A' で終わる文字列と 'B' で始まる文字列を連結する場合だけですので、このような文字列をどのように連結するのが最適かを考えればよいです。

'A' で終わる文字列と、'B' で始まる文字列には、合わせて以下のような３つのパターンがあります。これらがそれぞれ $c_0,~c_1,~c_2$ 個あるとします。

B以外で始まり、Aで終わる
Bで始まり、A以外で終わる
Bで始まり、Aで終わる

これらを、以下の手順で組み合わせるのが基本方針です。
(a) (B以外で始まり、Aで終わる文字列) + (Bで始まり、Aで終わる文字列) $\times c_2$ 個 + (Bで始まり、A以外で終わる文字列) と連結させる。
(b) 余った文字列の中で、(B以外で始まり、Aで終わる文字列) + (Bで始まり、A以外で終わる文字列) の連結を出来るだけ多く作る。

(1) $c_2 \neq 0$ のとき
(1-1) $c_0 > 0$ かつ $c_1 > 0$ のとき
上記の基本方針をそのまま適用できるので、'AB'は合わせて $c_2+1 + \min(c_0-1, c_1-1)$ 個増えます。

(1-2) $c_0,~c_1$ の一方が 0 のとき
頭とお尻の一方が抜けますが、(a)だけ行うことが出来ます。例えば $c_1 = 0$ のときは、
　(B以外で始まり、Aで終わる文字列) + (Bで始まり、Aで終わる文字列) $\times c_2$ 個
と連結できます。'AB' は $c_2$ 個増えます。

(1-3) $c_0 = c_1 = 0$ のとき
頭とお尻が抜けますが、(a)だけ行うことが出来ます。'AB' は $c_2 - 1$ 個増えます。

(2) $c_2 = 0$ のとき
(b) の手順だけ行えます。'AB' の数は $\min(c_0, c_1)$ 個増えます。

ソースコード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;  cin >> N;
    vector<string> s(N);

    int ans = 0;
    for(int i=0; i<N; i++){
        cin >> s[i];
        int L = s[i].length();
        // s[i] の中に含まれる 'AB' を数える
        for(int j=0; j<L-1; j++){
            if(s[i][j]=='A' && s[i][j+1]=='B') ans++;
        }
    }

    vector<int> c(3,0);
    // 上記方針の c_0, c_1, c_2 を求める
    for(int i=0; i<N; i++){
        if(s[i][0]!='B' && s[i][s[i].length()-1]=='A') c[0]++;
        if(s[i][0]=='B' && s[i][s[i].length()-1]!='A') c[1]++;
        if(s[i][0]=='B' && s[i][s[i].length()-1]=='A') c[2]++;
    }

    if(c[2]!=0){
        if(c[0]>0 && c[1]>0){
            // (1-1)
            ans += c[2] + 1 + min(c[0]-1, c[1]-1);
        }else if(c[0]==0 && c[1]==0){
            // (1-3)
            ans += c[2]-1;
        }else{
            // (1-2)
            ans += c[2];
        }
    }else{
        // (2)
        ans += min(c[0], c[1]);
    }

    cout << ans << endl;
}

D - DivRem Number

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

方針

$N$ を $m$ で割った商とあまりが等しいとき、 $N = pm + p = p(m+1)$ を満たす $p$ が存在します。
よって、( $N$ の約数 - 1) が $m$ の候補となり、この候補全てについて、実際に $N$ を割った商と余りが等しいかを検証すればよいです。

ソースコード

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ll N;  cin >> N;
    vector<ll> div;

    // div に N の約数を格納する
    for(ll i=1; i*i<=N; i++){
        if(N%i==0){
            div.push_back(i);
            if(i*i!=N){
                // i^2 = N のときに div に i が 2 つ入らないようにする
                div.push_back(N/i);
            }
        }
    }

    ll ans = 0;
    int n = div.size();
    // (Nの約数 - 1)のうち、Nを割った商とあまりが等しいものを ans に加える
    for(int i=0; i<n; i++){
        ll m = div[i] - 1;
        // m = 0 は明らかに不適
        if(m==0) continue;

        if(N/m==N%m){
            ans += m;
        }
    }
    cout << ans << endl;
}