東京海上日動 プログラミングコンテスト2020

atcoder.jp

C時間かかっちゃった

Bondo416さんの東京海上日動　プログラミングコンテスト2020での成績：971位
パフォーマンス：1576相当
レーティング：1241→1279 (+38) :)#AtCoder #東京海上日動　プログラミングコンテスト2020 https://t.co/7rAeY22pOf

— ボンド@競プロ (@bond_cmprog) June 13, 2020

A - Nickname

連続した3文字のどこかを出力すればいいので
S[0] S[1] S[2] を出力する
提出コード

void solve(){
    string S;
    cin >> S;
    cout << S[0] << S[1] << S[2] << endl;
}

B - Tag

のときは差が広がるだけなので"NO"
それ以外の場合は鬼が詰めないといけない距離はであるので
秒間でこの差を詰めれるかを考える
1秒間に詰めれる距離がなので、T秒間ではの距離を詰めることが出来る
したがって、であれば"YES"、そうでなければ"NO"
提出コード

void solve(){
    ll A, V, B, W, T;
    cin >> A >> V >> B >> W >> T;
    if(V <= W){
        cout << "NO" << endl;
        return;
    }
    ll dist = abs(A - B);
    if(dist <= T * (V - W)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

C - Lamps

明るさ0の電球iが座標iを照らすことを見落としてて時間溶かしちゃった
愚直にやるとになって間に合わないのでどっちかをlogとかに落とせないかなーって考える
考えるんだけどよくわからないので、愚直にシミュレーションしてみる
そうすると結構早く全ての電球の明るさがになることがわかる
でもシミュレーションしてみると40回で操作が終わることを確認できる
そのため、最大でも50回くらいで打ち切ればシミュレーションでも通ることがわかる
区間にはimos法などを使えばいい（セグ木とかだと実装によっては落ちるらしい）
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    // int N = 2e5;
    // int K = 2e5;
    vector<int> A(N+10);
    vector<int> imos(N+10);
    REP(i,N){
        cin >> A[i];
        // A[i] = 0;
        imos[max(1, i+1-A[i])]++;
        imos[min(N+1, i+1+A[i]+1)]--;
    }
    REP(k,min(K,50)){
        vector<int> tmp(N+10);
        for(int i=2;i<=N+5;i++) imos[i] += imos[i-1];
        REP(i,N){
            A[i] = imos[i+1];
            // cout << A[i] << " ";
            tmp[max(1, i+1-A[i])]++;
            tmp[min(N+1, i+1+A[i]+1)]--;
        }
        imos = tmp;
    }
    REP(i,N) cout << A[i] << " ";
    cout << endl;
}