接着剤の精進日記

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

AtCoder Beginner Contest 154(ABC154)

atcoder.jp

5完47分で1560パフォ
青パフォがなかなかでないなー

A - Remaining Balls

読解が難しかった
UがSならA--、TならB--して出力
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;
    string U;
    int A, B;
    cin >> S >> T >> A >> B >> U;
    if(S == U) A--;
    else B--;
    cout << A << " " << B << endl;
}

B - I miss you...

Aより簡単かな?
Sの長さ分 x を出力する
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    REP(i,S.size()) cout << "x";
    cout << endl;
}

C - Distinct or Not

setとかで出現したものを管理する
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    set<int> st;
    string ans = "YES";
    REP(i,N){
        int A;
        cin >> A;
        if(st.find(A) != st.end()) ans = "NO";
        st.insert(A);
    }
    cout << ans << endl;
}

D - Dice in Line

サイコロの期待値は\frac{N \times (1 + N)}{2 \times N} = \frac{1 + N}{2}になる
あとはK個の期待値を持ちながら足し引きしていく
しゃくとりっぽくやったけど累積和のほうがシンプルだね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<double> p(N);
    REP(i,N) cin >> p[i];
    double ans = 0;
    double tmp = 0;
    REP(i,K) tmp += (p[i] * (1 + p[i])) / (2 * p[i]);
    chmax(ans, tmp);
    for(int i=K;i<N;i++){
        tmp -= (p[i-K] * (1 + p[i-K])) / (2 * p[i-K]);
        tmp += (p[i] * (1 + p[i])) / (2 * p[i]);
        chmax(ans, tmp);
    }
    printf("%.12lf\n", ans);
}

E - Almost Everywhere Zero

Eは桁dpのE
普通の桁dpに加えて0以外の数字が何個出てきたかの情報を付けてあげる
最初0の個数数えてて、サンプル1で81出てきて逆何だが?をやっていた(あほ)
提出コード

ll dp[111][2][4];
string N;
int K;

ll rec(int k=0, bool tight=true, int non_zero = 0){
    if(non_zero > K) return 0;
    if(k == N.size()){
        return non_zero == K;
    }
    int x = N[k] - '0';
    int r = (tight ? x : 9);
    ll &res = dp[k][tight][non_zero];
    if(!tight && ~res) return res;
    res = 0;
    REP(i,r+1){
        res += rec(k+1, tight && i == r, (i != 0 ? non_zero + 1 : non_zero));
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    memset(dp, -1, sizeof(dp));
    cout << rec() << endl;
}

F - Many Many Paths

制約的に片方を固定して\mathcal{O}(N)もしくは\mathcal{O}(NlogN)で求めたくなる
お絵かきしたら、対角成分に注目すれば上手く計算量収まりそうだなーとか言ってる間にコンテストが終わってしまった
TL眺めたらwolframalpha使っている人が多くて笑ってしまった
wolframalphaの使い方そろそろ覚えないとなあと思いつつ、ちゃんと自分で導出したいお気持ち(コンテスト中は殴れるなら殴れるようにしておきたいね)
[追記]
けんちょんさんの記事を参照
片方を固定するまでは良くて、その後の変形がコンテスト中駄目だったね
経路の場合分けも考えたけど結局式に落とし込めなかったし、二項定理も思いつかなかったので数学力不足だった
drken1215.hatenablog.com

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    mint ans = 0;
    for(int r=r1;r<=r2;r++){
        ans += (bc.com(c2 + r + 1, r + 1) - bc.com(c1 + r, r + 1));
    }
    cout << ans << endl;
}

おわりに

ぼくの青パフォさんはどこですか?ここですか?
1400~1500台は結構出るようになっているので青パフォに飢えています
TLに水コーダーで青パフォ出て無くても突然黄パフォ出るみたいな話もあったので気にせず精進続けようね