接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 196（ABC196）

AtCoder Beginner Contest 196（ABC196）

AtCoderBeginnerContest AtCoderBeginnerContest196 ABC ABC196

atcoder.jp

A - Difference Max

$ \mathcal{O}(1) $ でできそうだけど全探索できるのでする
提出コード

void solve(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = -INF;
    for(int x = a;x<=b;x++){
        for(int y=c;y<=d;y++){
            chmax(ans, x - y);
        }
    }
    cout << ans << endl;
}

B - Round Down

.が出てくるまで出力すればいい
提出コード

void solve(){
    string S;
    cin >> S;
    REP(i,S.size()){
        if(S[i] == '.') break;
        cout << S[i];
    }
    cout << endl;
}

C - Doubled

同じ文字列を連結したものを考えると6桁の文字列のとき12桁の文字列になるので $ 10^6 $ 程度まで見れば十分
今見ている値を $ i, i $ の桁数を $ cnt $ とすると $ i \times 10^{cnt} + i \leq N $ を満たしていれば答えに加算していく
提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = 0;
    for(ll i=1;i<=1e6;i++){
        ll cnt = 1;
        ll tmp = i;
        while(tmp > 0){
            cnt *= 10;
            tmp /= 10;
        }
        ll num = i * cnt + i;
        if(num <= N) ans++;
    }
    cout << ans << endl;
}

D - Hanjo

$ HW \leq 16 $ なのでbit全探索などで全探索ができそうなので全探索を考える
マス $ (i, j) $ の番号を $ i \times W + j $ とすると、$ (i, j) $ に $ 2 \times 1 $ の畳を縦に置く、横に置く、置かないの3通り考えられる
そのため、愚直に上記を全探索しても $ \mathcal{O}(3^{HW} HW) $ で間に合う
すでに置いてあるところに置こうとする、最下段や右端のときに縦・横に置いたりなどは出来ないので注意
提出コード

void solve(){
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    ll ans = 0;
    int n = H * W;
    auto dfs = [&](auto self, vector<int> &a) -> void{
        if(a.size() == n){
            int cnt = 0;
            REP(i,n) if(a[i] > 0) cnt++;
            if(cnt != A) return;
            vector<bool> used(n);
            REP(i,n){
                if(a[i] == 0) continue;
                else if(a[i] == 1){ // 縦
                    if(i >= (H - 1) * W) return;
                    if(used[i] or used[i+W]) return;
                    used[i] = true;
                    used[i+W] = true;
                }
                else{ // 横
                    if(i % W == W - 1) return;
                    if(used[i] or used[i+1]) return;
                    used[i] = true;
                    used[i+1] = true;
                }
            }
            ans++;
        }
        else{
            REP(i,3){
                a.push_back(i);
                self(self, a);
                a.pop_back();
            }
        }
    };
    vector<int> a;
    dfs(dfs, a);
    cout << ans << endl;
}

E - Filters

beatsで殴れる
関数を合成していくと、最終的には解説の図のようになる
https://img.atcoder.jp/ghi/f0bde453251ed936cbc861c1a9878e4c.png
最終的にある下限 $ mi $ 以下はすべて $ mi, $ ある上限 $ ma $ 以上はすべて $ ma, $ それ以外の場合 $ x ( mi \lt x \lt ma ) $ となる
そのため、$ f(-INF), f(INF) $ の値を実際に求めておき、$ t_i = 1 $ で加算される総和を $ sum $ として求めておくと各クエリの答えはclamp(x+sum, f(-INF), f(INF) として求められる
提出コード

void solve(){
    int N;
    cin >> N;
    ll mi = -LINF;
    ll ma = LINF;
    ll sum = 0;
    REP(i,N){
        ll a, t;
        cin >> a >> t;
        if(t == 1){
            sum += a;
            mi += a;
            ma += a;
        }
        else if(t == 2){
            chmax(ma, a);
            chmax(mi, a);
        }
        else{
            chmin(ma, a);
            chmin(mi, a);
        }
    }
    int Q;
    cin >> Q;
    while(Q--){
        ll x;
        cin >> x;
        cout << clamp(x + sum, mi, ma) << endl;
    }
}