接着剤の精進日記

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

AtCoder Beginner Contest 143 (ABC143)

ABC参加記事すごく久しぶり
4完超遅解きで冷え!悲しいね前回ABCで水タッチ出来ててよかった(?)

A - Curtain

これちょっと難しくない?問題文理解に時間かかっちゃった
最大で2B覆えるのでAから引くと答えなのでmax(0,A - 2B)
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    cout << max(0, A - 2 * B) << endl;
}

B - TAKOYAKI FESTIVAL 2019

問題文にちょっと威圧されますが、制約が小さいので全通り足します
[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> d(N);
    REP(i,N) cin >> d[i];
    ll ans = 0;
    REP(i,N){
        for(int j=i+1;j<N;j++) ans += d[i] * d[j];
    }
    cout << ans << endl;
}

C - Slimes

脳死でランレングス圧縮を貼りました。ランレングス最近結構使うのでライブラリにしてます。
ライブラリ使わなくてもs[i] != s[i+1]になる数を数えたりでもいけます。
提出コード

vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.size();

    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    for(int i=1;i<n;i++) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }

    res.push_back({ pre, cnt });
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >>  S;
    auto res = runLengthEncoding(S);
    cout << res.size() << endl;
}

D - Triangles

愚直にやるとN^3なので頑張ってN^2logNに落とす。
こういう典型として2つを固定して残り1つを上手く探す考え方がある。
Lをソートすると条件を満たすものはa + b = L[i] + L[j]より小さいかつインデックスがjより大きいものになる。
なのでにぶたんを使うとcをlogNで計算できるので全計算量はN^2logNになる。やったね。
本番中はにぶたんすぐ思いついたけどサンプルなかなか合わなくて沼にハマってた。反省。
愚直でも通るらしい。本番は通せば正義だけど復習ではちゃんと計算量落とそうね。
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> L(N);
    REP(i,N) cin >> L[i];
    sort(L.begin(),L.end());
    ll ans = 0;
    int cnt = 0;
    REP(i,N) for(int j=i+1;j<N;j++){
        int cand = lower_bound(L.begin(),L.end(), L[i] + L[j]) - L.begin();
        cand -= (j + 1);
        if(cand > 0) ans+=cand;
    }
    cout << ans << endl;
}

E - Travel by Car

本番でD全然解けなくてちょっとだけ見た。
制約がいかにもワーシャルフロイドをしてくださいと言っているので、とりあえずワーシャルフロイドで最短距離を求めてみる。
次にいくつ補給出来るかを知りたいので、最短距離でどれだけ街を通るかが知りたくなる。
本番ではここまで考えた時点でわからん!wでDに戻っちゃったけど、もう一回ワーシャルフロイドをすればOK。
言われるとそれはそうだけど、全然思いつかなかった。
途中で燃料が切れるとだめなので最初に求めた最短距離でL以下で行けるなら距離1みたいにしてもう一回ワーシャルフロイドをする。
後は各クエリに対して、補給しながら行けるなら補給の回数-1、行けないなら-1を出力する。
DもそうだけどEも面白くて良問。
提出コード

ll dist[333][333];
ll hokyu[333][333];
ll A[101010], B[101010], C[101010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, L, Q;
    cin >> N >> M >> L;
    REP(i,N){
        REP(j,N){
            dist[i][j] = LINF;
            hokyu[i][j] = LINF;
        }
        dist[i][i] = 0;
        hokyu[i][i] = 0;
    }
    REP(i,M){
        cin >> A[i] >> B[i] >> C[i];
        --A[i], --B[i];
        chmin(dist[A[i]][B[i]], C[i]);
        chmin(dist[B[i]][A[i]], C[i]);
    }
    cin >> Q;
    REP(k,N) REP(i,N) REP(j,N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
    REP(i,N) REP(j,N){
        if(i == j) continue;
        if(dist[i][j] <= L) chmin(hokyu[i][j], 1LL);
    }
    REP(k,N) REP(i,N) REP(j,N) chmin(hokyu[i][j], hokyu[i][k] + hokyu[k][j]);

    REP(i,Q){
        ll t, s;
        cin >> t >> s;
        --t, --s;
        if(hokyu[t][s] < LINF) cout << hokyu[t][s] - 1 << endl;
        else cout << -1 << endl;
    }
}

おわりに

AGCで緑落ちしたのはしょうがないとして、レートが1150くらいにもどちゃったのでとりあえず水色に戻したいね。
一回タッチしてるからまあ、行けるでしょみたいに思ってますがどうなるか乞うご期待。
それはそうと11/2にHTTFの予選があるのでみんな出ようね、マラソン楽しいよ!