接着剤の精進日記

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

AtCoder Beginner Contest 165(ABC165)

atcoder.jp

ちょい伸び

A - We Love Golf

A \leq i \leq Bを全探索すればいい
提出コード

void solve(){
    int K, A, B;
    cin >> K >> A >> B;
    for(int i=A;i<=B;i++){
        if(i % K == 0){
            cout << "OK" << endl;
            return;
        }
    }
    cout << "NG" << endl;
}

B - 1%

愚直にシミュレートする
サンプルに最大ケースあるの優しいね
後はオーバーフローに注意?
提出コード

void solve(){
    ll X;
    cin >> X;
    ll cur = 100;
    int ans = 0;
    while(cur < X){
        cur += cur / 100;
        ans++;
    }
    cout << ans << endl;
}

C - Many Requirements

読解が難しかった
 1 \leq A_1 \leq A_2 \leq ... \leq ... \leq A_N \leq Mを満たす場合の数は
重複組合せを考えると _{N + M - 1} C _Nで最大ケースでも十分に間に合う
そのため、dfsなどで全探索をすればいい
コンテスト中はこれを思い出してた
atcoder.jp

提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> a(Q), b(Q), c(Q), d(Q);
    REP(i,Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i],--b[i];
    }
    ll ans = 0;
    auto dfs = [&](auto && dfs, vector<int> v) -> void{
        if(v.size() == N){
            ll tmp = 0;
            REP(i,Q){
                if(v[b[i]] - v[a[i]] == c[i]){
                    tmp += d[i];
                }
            }
            chmax(ans, tmp);
        }
        else{
            if(v.empty()){
                for(int i=1;i<=M;i++){
                    auto tmp = v;
                    tmp.push_back(i);
                    dfs(dfs, tmp);
                }
            }
            else{
                for(int i=v.back();i<=M;i++){
                    auto tmp = v;
                    tmp.push_back(i);
                    dfs(dfs, tmp);
                }
            }
        }
    };
    vector<int> v;
    dfs(dfs, v);
    cout << ans << endl;
}

D - Floor Function

これ難しい
手元で実験してみると、周期性があって、B-1のときに最大になっていることがわかる
なので、 min(B - 1, N)のときの答えを出力する
提出コード

void solve(){
    ll A, B, N;
    cin >> A >> B >> N;
    ll mi = min(B-1, N);
    cout << (A * mi) / B << endl;
}

E - Rotation Matching

こういうパズルっぽいの解けるようになる気がしないなあ
端同士の点と、真ん中の2点を取る
端 -> 真ん中 -> 端 -> ...の順に交互に取っていき、端は真ん中に、真ん中は端に寄せていく
2点(i, j)の差分の mod Nが重複しないようにするってことを考えるのが良いのかな
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    int a = 1, b = N - 1, c = N / 2, d = N / 2 + 1;
    REP(i,M){
        if(i & 1) cout << a++ << " " << b-- << endl;
        else cout << c-- << " " << d++ << endl;
    }
}

F - LIS on Tree

言われてみるとそれはそうなんだけど通す人々が多くて強いなーってなった
まず、パスで考えると普通のLISを解けばいい
木上で考えると、ある葉までのパス上の頂点はLISを更新していけばいい
後は、帰りがけのときにDPの更新を戻してあげればいい
これは行きがけのときにDPの値をメモっておいて、帰りがけのときにロールバックをしてあげると、\mathcal{O}(NlogN)で解くことが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<vector<int>> G(N);
    REP(i,N-1){
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    vector<int> ans(N, INF);
    vector<int> dp(N+1, INF);
    dp[0] = -INF;

    auto dfs = [&](auto && self, int cur, int par) -> void{
        int idx = lower_bound(dp.begin(), dp.end(), a[cur]) - dp.begin();
        int tmp = dp[idx];
        dp[idx] = a[cur];
        ans[cur] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin() - 1;
        for(auto nv : G[cur]){
            if(nv == par) continue;
            self(self, nv, cur);
        }
        dp[idx] = tmp;
    };

    dfs(dfs, 0, -1);
    for(auto x : ans) cout << x << endl;
}

おわりに

青difficulty解けないなあ精進しないと