接着剤の精進日記

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

AtCoder Beginner Contest 159(ABC159)

atcoder.jp

うーん安定の水パフォ真ん中
Eに時間かけ過ぎちゃった

A - The Number of Even Pairs

Aにしては難しいね
_N C _2 + _M C _2を出力する
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
}

B - String Palindrome

愚直に回文判定していけばいい
for回したけどreverseしたやつが一致するかで判定できるの天才じゃない?
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int N = S.size();
    string T = S.substr(0, (N-1)/2);
    string U = S.substr((N+3)/2-1);
    bool ok = true;
    for(int i=0;i<N/2;i++){
        if(S[i] != S[N-i-1]) ok = false;
    }
    for(int i=0;i<(N-1)/2;i++){
        if(T[i] != T[(N-1)/2 - i - 1]) ok = false;
        if(U[i] != U[(N-1)/2 - i - 1]) ok = false;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Maximum Volume

だいたいこういうのは正方形とか立方体とか同じやつかければ大きくなる
なので(\frac{L}{3})^3を出力すればいい
ちゃんと証明するなら解説の相加相乗平均使えば良いね
ついこの間誤差で殺されたばかりだからビクビクしながら投げたけど大丈夫だった
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double L;
    cin >> L;
    printf("%.12lf\n", (L / 3) * (L / 3) * (L / 3));
}

D - Banned K

これ4800人も解けるのかあというお気持ち
愚直に毎回計算していると間に合わなさそうなので高速化を考える
一先ずN個のときの場合の数baseとして求めておくと
A_iを除いた場合の数は base - _{|A_i|} {} C _2 + {} _{|A_i - 1|} C _ 2
(|A_i|は数列に出てくるA_iの個数)
で求められる
何故かmodを取る使命感に駆られて1WA生やしました(?)
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    map<int, ll> mp;
    REP(i,N){
        cin >> A[i];
        mp[A[i]]++;
    }
    ll base = 0;
    for(auto x : mp) base += x.second * (x.second - 1) / 2;
    REP(i,N){
        ll tmp = mp[A[i]];
        ll ans = base;
        ans -= tmp * (tmp - 1) / 2;
        tmp--;
        ans += tmp * (tmp - 1) / 2;
        cout << ans << endl;
    }
}

E - Dividing Chocolate

これ難しいね
最初区間にどんどん分けられていくから金塊ゲーム思い出して見に行ってた
Hの制約が小さいのでHはbit全探索できる
その状態でWをどこで切るかは貪欲に切っていけばいい
あとはこれを実装するだけなんだけど結構しんどい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> S(H);
    REP(i,H) cin >> S[i];
    vector<vector<int>> cum(H+1, vector<int>(W+1));
    REP(i,H) REP(j,W){
        cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + (S[i][j] == '1');
    }
    int ans = INF;
    REP(i, 1<<(H-1)){
        vector<int> h;
        REP(j,H-1) if((i >> j) & 1) h.push_back(j+1);
        h.push_back(H);
        int cnt = (int)h.size() - 1;
        int preW = 0;
        bool ok = true;
        for(int j=1;j<=W;j++){
            int preH = 0;
            int tmp = 0;
            for(auto x : h){
                chmax(tmp, cum[x][j] - cum[preH][j] - cum[x][preW] + cum[preH][preW]);
                preH = x;
            }
            if(tmp > K){
                if(j == 1){
                    ok = false;
                    break;
                }
                if(preW == W-1 && j == W){
                    ok = false;
                    break;
                }
                preW = j - 1;
                j--;
                cnt++;
            }
        }
        int tmp = 0;
        int preH = 0;
        for(auto x : h){
            chmax(tmp, cum[x][W] - cum[preH][W] - cum[x][preW] + cum[preH][preW]);
            preH = x;
        }
        if(tmp > K) ok = false;

        if(ok){
            chmin(ans, cnt);
        }
    }
    cout << ans << endl;
}

F - Knapsack for All Segments

見た目と制約がDPと言っているんだけどFを見たのが終了10分前なので間に合わず
結構全完している人も多かったからちゃんと通しておきたい

おわりに

Dで謎の1WA生やしたのが本当によくわからない(何が見えていたんだろう)
Eでbit全探索に気づいてからも実装に時間かけ過ぎちゃったのが良くなかったかな