接着剤の精進日記

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

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

atcoder.jp

C時間かかっちゃった

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

 V \leq Wのときは差が広がるだけなので"NO"
それ以外の場合は鬼が詰めないといけない距離は|A - B|であるので
T秒間でこの差を詰めれるかを考える
1秒間に詰めれる距離がV - Wなので、T秒間ではT(V-W)の距離を詰めることが出来る
したがって、|A - B| \leq T(V-W)であれば"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を照らすことを見落としてて時間溶かしちゃった
愚直にやると\mathcal{O}(NK)になって間に合わないのでどっちかをlogとかに落とせないかなーって考える
考えるんだけどよくわからないので、愚直にシミュレーションしてみる
そうすると結構早く全ての電球の明るさがNになることがわかる
N = 2 \times 10^5でもシミュレーションしてみると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;
}