AtCoder Beginner Contest 139 （ABC139）

5完11ペナ(!?)でパフォ1483でした
新ABCになってから初5完ですが反省も多かった…

A - Tenki

各文字が一致しているかどうか見ればいいですね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    string T;
    cin >> S >> T;
    cout << (S[0] == T[0]) + (S[1] == T[1]) + (S[2] == T[2]) << endl;
}

B - Power Socket

A〜Dまでで一番難しくないですか（問題文ちゃんと読もうね）
愚直にシミュレートでも数式立てても解けますがB=1のときに注意
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    if(B == 1){
        cout << 0 << endl;
        return 0;
    }
    int cnt = 1;
    int tap = A;
    if(tap >= B){
        cout << 1 << endl;
        return 0;
    }
    while(tap < B){
        tap += A-1;
        cnt++;
    }
    cout << cnt << endl;
}

C - Lower

前から見て愚直にやると $O(N^2)$ になりそう
逆に後ろから見ると一意に決まりそうなので後ろから見ました
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    reverse(a.begin(),a.end());
    a.push_back(0);
    int cnt = 0, ans = 0;
    REP(i,n){
        if(a[i] <= a[i+1]) cnt++;
        else chmax(ans,cnt), cnt = 0;
    }
    cout << ans << endl;
}

D - ModSum

競プロに慣れてる人はサンプルからエスパーできそう
エスパーすると1~N-1までの総和になりそう
一応ちゃんと証明すると
N，1，2，…のように数列を並べていくとそのmodを取った数列は
0，1，2，...，N-1になりそれが最大になるのでこれが答え
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    cout << N * (N-1) / 2 << endl;
}

~~ごめんなさいテストケースエスパーしました~~
愚直にシミュレートすると $O(N^3)$ になる
キューなどを上手く使うと $O(N^2)$ になるみたいです
もしくは各試合を頂点とみなしDAGとして扱うと $O(N^2)$ で解けるみたいですね（閉路があった時-1）
ぼくの場合愚直にシミュレートすると1ケースだけTLE
→最大ケースは1日に1試合しか行われない(N*(N-1)/2)
→ $O(N^3)$ でTLEしているので最大ケースしかなさそう？
→時間計算をしてTLEしそうなら最大ケース出力するとAC(ごめんなさい)
N=1000のとき最大ケース以外でTLEするケースあるんですかね？
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> player(N,vector<int>(N));
    REP(i,N) REP(j,N-1){
        cin >> player[i][j];
        player[i][j]--;
    }
    int ans = 0;
    vector<int> cnt(N);
    int sum = 0;
    int step = 0;
    while(sum < N*(N-1)){
        ans++;
        int tmp = sum;
        vector<bool> done(N);
        REP(i,N){
            step++;
            if(cnt[i] > ans) continue;
            if(cnt[i] >= N-1) continue;
            int outside = player[i][cnt[i]];
            if(cnt[outside] < ans){
                if(i == player[outside][cnt[outside]] && !done[i] && !done[outside]){
                    cnt[i]++;
                    cnt[outside]++;
                    done[i] = true;
                    done[outside] = true;
                    sum += 2;
                }
            }
            else continue;
        }
        if(sum == tmp){
            cout << -1 << endl;
            return 0;

        }
        if(sum >= N*(N-1)) break;
        if(step >= 1e8){
            cout << N*(N-1)/2 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

おわりに

今回はBでペナ出したり，Eで計算量削減出来ずにエスパーしたりと反省が多い回でした
とりあえずEは想定解でACし直したいですね
ところで今回はAのAC数が5,800超えてて大分参加者が増えたなあという印象です
DのAC数も4,000近く居て人類競プロ強くないかというお気持ち
今回のDは証明まで含めたら400でも良さそうだけどこんなに解ける？というお気持ちです
水になるにはやっぱりEの打率上げるのが一番の近道かな？

接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。