接着剤の精進日記

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

AtCoder Beginner Contest 146 (ABC146)

4完1WAでパフォ1402
Fが思いの外通されてイマイチパフォが伸びなかったね

A - Can't Wait for Holiday

if文全部書いたほうが早い!っていって全部書いちゃった
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(S == "SUN") cout << 7 << endl;
    if(S == "MON") cout << 6 << endl;
    if(S == "TUE") cout << 5 << endl;
    if(S == "WED") cout << 4 << endl;
    if(S == "THU") cout << 3 << endl;
    if(S == "FRI") cout << 2 << endl;
    if(S == "SAT") cout << 1 << endl;
}

B - ROT N

文字列を数値に変換して、N足して26で割る
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    vector<char> alp;
    for(char c='A';c<='Z';c++) alp.push_back(c);
    REP(i,S.size()){
        int idx = S[i] - 'A';
        idx += N;
        idx %= 26;
        cout << alp[idx];
    }
    cout << endl;
}

C - Buy an Integer

脳死にぶたんしました
単調性があるのでこういうときはにぶたんすると早い
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B, X;
    cin >> A >> B >> X;
    ll l = 0, r = INF+1;
    while(r - l > 1){
        ll m = (l + r) / 2;
        int digits = 0;
        ll tmp = m;
        while(tmp > 0){
            digits++;
            tmp /= 10;
        }
        ll sum = A * m + B * digits;
        if(sum <= X) l = m;
        else r = m;
        //cout << m << endl;
    }
    cout << l << endl;
}

D - Coloring Edges on Tree

結構難しめ?
条件として、次数が最大のもの以下の色しか使えないので次数が最大の点を探して、そこからDFSなりBFSなりで色を塗っていく
考察よりも実装のほうが重めなのでAC者数が少なかったっぽい
提出コード

int N;
vector<vector<int>> G;
map<pair<int,int>,int> mp;
int ma = 0;

void dfs(int n, int pre, int col){
    for(auto nv : G[n]){
        if(nv == pre) continue;
        col++;
        col %= ma;
        int a = n, b = nv;
        if(a > b) swap(a,b);
        mp[{a,b}] = col;
        dfs(nv, n, col);
        //cout << pre << endl;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    G.resize(N);
    vector<int> a(N-1),b(N-1);
    REP(i,N-1){
        cin >> a[i] >> b[i];
        --a[i], --b[i];
        if(a[i] > b[i]) swap(a[i], b[i]);
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    int idx = 0;
    REP(i,N){
        if(chmax(ma, (int)G[i].size())) idx = i;
    }

    dfs(idx, -1, 0);
    cout << ma << endl;
    REP(i,N-1) cout << mp[{a[i], b[i]}] + 1 << endl;
}

E - Rem of Sum is Num

本番解けてません
Zero-Sum-Rangesみがあるので、考えますが詰めきれません
modの数列に変換してしゃくとりしましたがsampleが合いませんおしまい
解説見て理解したら追記するかも...
以下追記
A[i]をx個取った和をKで割ったあまりがxになる
これをA[i]-1をx個取った和で考えるとKで割ったあまりが0になるものを数え上げればいい
ここまで落とし込めるとZeroSumRangesの要領で、累積和をKで割った余りが一致するものを数え上げていけばおk
長さがK以上にはならないので、今見ている区間の長さがKを超えたら見ているものの中で一番左端を捨ててあげればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N), cum(N+1);
    map<ll, ll> mp;
    REP(i,N){
        cin >> A[i];
        --A[i];
    }
    REP(i,N) cum[i+1] = (cum[i] + A[i]) % K;
    ll ans = 0;

    REP(i,N+1){
        ans += mp[cum[i]];
        mp[cum[i]]++;
        if(i - K + 1 >= 0) mp[cum[i-K+1]]--;
    }
    cout << ans << endl;
}

F - Sugoroku

無限人が通してたのでE捨てて解きましたが、解けなくて人生の終わり
BFSして最短経路の復元したけど、AC以外のケース全部TLEして、ダイクストラかなーとか言って終わった
正攻法は後ろからDPしてセグ木とかで高速化するみたい
あんまり理解していないけど後ろから貪欲でも通るみたい
お気持ちとしては、ゴールまでの最短経路なのでサイコロを降る回数は固定で後ろに行くほど大きい目が出てほしい
そのため、後ろからスタート地点に向かって大きい目から貪欲に取っていくとそれが辞書順最小のものになる
正当な証明よくわからないけど、最短手数が決まってるから保証されてる感じなのかな?
正攻法を復習でちゃんと勉強しておいたほうが良いね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    string S;
    cin >> S;

    queue<int> q;
    vector<int> ans;
    vector<int> dist(N+1, -1);
    dist[N] = 0;
    q.push(N);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == 0) break;
        for(int i=M;i>=1;i--){
            if(cur - i < 0){
                ans.push_back(cur);
                dist[0] = dist[cur] + 1;
                break;
            }
            if(S[cur-i] == '1' || dist[cur-i] != -1) continue;
            ans.push_back(i);
            q.push(cur-i);
            dist[cur-i] = dist[cur] + 1;
            break;
        }
    }
    if(dist[0] == -1){
        cout << -1 << endl;
        return 0;
    }
    reverse(ans.begin(), ans.end());
    REP(i,ans.size()) cout << ans[i] << " ";
    cout << endl;
}

おわりに

Dが1200人くらいでいい感じだったけどFが結構な人に通されて解けなかったのが痛かった
ABCFとか異常ムーブ多すぎませんかw
EとFしっかり復習すれば強くなれそうな問題なのは良いね頑張るぞ〜