接着剤の精進日記

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

AtCoder Beginner Contest 141 (ABC141)

4完13:28でパフォ1374
Eがそこそこ解かれると4完早解きのパフォが微妙ですね

A - Weather Prediction

ifで3通り書けばいいです
S[0]で判定できるのでそうするとちょっとタイプ数が減ります
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(S[0] == 'S') cout << "Cloudy" << endl;
    else if(S[0] == 'C') cout << "Rainy" << endl;
    else cout << "Sunny" << endl;
}

B - Tap Dance

愚直に調べても出来ますが
偶数にRがある or 奇数にLがある ⇒ No
それ以外はYesで判定するとちょっと楽です
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int N = S.size();
    bool flg = true;
    for(int i=0;i<N;i+=2) if(S[i] == 'L') flg = false;
    for(int i=1;i<N;i+=2) if(S[i] == 'R') flg = false;
    if(flg) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Attack Survival

これパッと見ちょっと混乱しました
正解した分その人の点数は引かれないので参加者ごとに正解数を管理しておけばokです
最後にK - (Q - 正解数) > 0ならYesそうでないならNoですね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A(Q);
    map<ll,ll> mp;
    REP(i,N) mp[i] = 0;
    REP(i,Q){
        cin >> A[i];
        --A[i];
        mp[A[i]]++;
    }
    for(auto x : mp){
        if(K - (Q - x.second) > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

D - Powerful Discount Tickets

これもちょっと難しい
まずどれに割引券を使えば得になるかを考えると、一番大きものに使えば得になる
一度に割引券を使う必要はなくて、一枚ずつ使ってもいい
そうすると今ある一番大きい値を2で割り、割った値をまた候補に入れる
これはpriority_queueを使うと実装できる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    priority_queue<int> pq;
    ll sum = 0;
    REP(i,N){
        ll a;
        cin >> a;
        sum += a;
        pq.push(a);
    }
    REP(i,M){
        ll tmp = pq.top(); pq.pop();
        sum -= tmp;
        tmp /= 2;
        sum += tmp;
        pq.push(tmp);
    }
    cout << sum << endl;
}

E - Who Says a Pun?

本番中に通せず
パッと見たときにローリングハッシュやZ-Algorithmでできそう
LCSだしDPでもできそう→サンプル合わない終了
コンテスト後どれでも出来ることが判明
実装力が足りませんね、精進しましょう

おわりに

4完早解き上手く行ったけどEそこそこ解かれるとあんまりパフォ伸びないのが辛いね
精進してEの打率をあげましょう