接着剤の精進日記

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

AtCoder Beginner Contest 172（ABC172）

AtCoderBeginnerContest172 AtCoderBeginnerContest ABC172 ABC

atcoder.jp

A - Calc

問題文の通りa + a^2 + a^3を出力
提出コード

void solve(){
    int a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
}

B - Minor Change

S_i \neq T_iの個数を数える
提出コード

void solve(){
    string S, T;
    cin >> S >> T;
    int cnt = 0;
    REP(i,S.size()) if(S[i] != T[i]) cnt++;
    cout << cnt << endl;
}

C - Tsundoku

いつもより難しめ？
取り敢えず貪欲で考えてみるけど後々得になるパターンがあって駄目そう
片方を幾つ取るかを固定してみると、もう片方は累積和と二分探索を使うことで\mathcal{O}(\log N)で求めることが出来る
実装はC++だとupper_boundを使うのが一番楽そう
提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(N), B(M);
    vector<ll> cum(N+1);
    REP(i,N) cin >> A[i];
    REP(i,M) cin >> B[i];
    for(int i=0;i<N;i++) cum[i+1] = cum[i] + A[i];
    cum.push_back(LINF);
    int ans = 0;
    ll sum = 0;
    REP(i,M+1){
        if(i > 0) sum += B[i-1];
        if(sum > K) break;
        int num = upper_bound(cum.begin(), cum.end(), K - sum) - cum.begin() - 1;
        chmax(ans, num + i);
    }
    cout << ans << endl;
}

D - Sum of Divisors

想定解が綺麗
本番はosa_k法を使って1 \leq i \leq Nに対して素因数分解を行い約数の組み合わせの個数を求めた
これはちょっと無駄があって、素因数分解をしなくてもiごとにその倍数を加算していく方針でも調和級数となって求めることが出来る
さらにこの調和級数部分は等差数列の和として求めることが出来る
これが想定解で\mathcal{O}(N)で解くことが出来る
\mathcal{O}(\sqrt N)でも解けるらしい？
提出コード（osa_k法）

template<typename T>
vector<T> smartPrimeFactors(T n) {
    vector<T> spf(n + 1);
    for (int i = 0; i <= n; i++) spf[i] = i;
    for (T i = 2; i * i <= n; i++) {
        // 素数だったら
        if (spf[i] == i) {
            for (T j = i * i; j <= n; j += i) {
                // iを持つ整数かつまだ素数が決まっていないなら
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
    return spf;
}
 
template<typename T>
map<T, T> factorize(T x, vector<T> &spf) {
    map<T, T> ret;
    while (x > 1) {
        ret[spf[x]]++;
        x /= spf[x];
    }
    //sort(ret.begin(), ret.end());
    return ret;
}
 
void solve(){
    int N;
    cin >> N;
    auto spf = smartPrimeFactors(N);
    ll ans = 0;
    for(int i=1;i<=N;i++){
        auto res = factorize(i, spf);
        ll tmp = 1;
        for(auto [a, b] : res) tmp *= (b + 1);
        ans += (ll)i * tmp;
    }
    cout << ans << endl;
}

提出コード（調和級数）

void solve(){
    int N;
    cin >> N;
    ll ans = 0;
    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j+=i) ans += j;
    }
    cout << ans << endl;
}

提出コード（想定解）

void solve(){
    int N;
    cin >> N;
    ll ans = 0;
    for(int i=1;i<=N;i++){
        ll n = N / i;
        ans += n * (n + 1) / 2 * (ll)i;
    }
    cout << ans << endl;
}

E - NEQ

まず、A_i = B_iとなるような個数kを固定して考えてみる
この時、その選び方はM個の中からA_i = B_iになるものをk個順番に並べるのに _M P _k通り
それ以外の部分をAとBそれぞれM-k個の中からN-k個を順番に並べるのに (_{M-k} P _{N-k})^2通りとなる
また、N個のうちどのk個を選ぶかで _{N} C _k通り出来る
よってkを固定したときの場合の数は _{N} C _k \times {} _{M} P _k \times (_{M-k} P _{N-k})^2となる
問題は、任意のiについてA_i \neq B_iを満たすものを数える必要があるが、これは包除原理によって求めることが出来る
各kについて、 (-1)^k \times {} _{N} C _ k \times {} _{M} P _k \times (_{M-k} P _{N-k})^2を求めてその総和が答えとなる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    mint ans = 0;
    for(int k=0;k<=N;k++){
        mint val = bc.com(N, k) * bc.perm(M, k) * bc.perm(M-k, N-k) * bc.perm(M-k, N-k);
        if(k & 1) ans -= val;
        else ans += val;
    }
    cout << ans << endl;
}

F - Unfair Nim

操作後のA_1, A_2の数をx, yと置くとNimの必勝法から
x \oplus y \oplus A_3 \oplus ... \oplus A_N = 0となれば良いことがわかる
上記のA_3 \oplus ... \oplus A_Nをzとすると
x + y = A_1 + A_2, x \oplus y = zを満たせば良い
また移動の条件として 1 \leq x \leq A_1を満たす必要がある
xorの性質を考えると x + y \lt zの時は不可能なので-1となる
ここで x + y = 2 (x & y) + x \oplus yが成り立つことを考えると
x & y = \frac{x + y - z}{2}となる
この時、x & yが非負整数にならないと不可能
また、x & y とzで共通しているbitがあればその場合も不可能
それ以外の場合、条件を満たす範囲で上位bitから貪欲にx & yにbitを割り振っていけばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    ll z = 0;
    for(int i=2;i<n;i++) z ^= a[i];
    if(a[0] + a[1] < z){
        cout << -1 << endl;
        return;
    }
    ll xy = a[0] + a[1] - z;
    if(xy & 1){
        cout << -1 << endl;
        return;
    }
    xy >>= 1;
    if(xy & z){
        cout << -1 << endl;
        return;
    }
    ll ans = xy;
    for(int i=40;i>=0;i--){
        if((z >> i & 1) && ans + (1LL << i) <= a[0]) ans += (1LL << i);
    }
    if(ans == 0 || ans > a[0]) cout << -1 << endl;
    else cout << a[0] - ans << endl;
}

Educational Codeforces Round 90 (Rated for Div. 2)

Codeforces Educational Codeforces Round 90

codeforces.com

A. Donut Shops

読解が辛い
a \geq cのとき1つ目のお店のほうが小さくなる個数は存在しない
ab \leq cのとき2つ目のお店のほうが小さくなる個数は存在しない
それ以外の時、1つ目のお店では1個買う時必ず小さくなり、2つ目のお店ではb個買う時必ず小さくなる
提出コード

void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    if(a >= c){
        cout << -1 << " " << b << endl;
    }
    else if(a * b <= c){
        cout << 1 << " " << -1 << endl;
    }
    else{
        cout << 1 << " " << b << endl;
    }
}

B. 01 Game

操作回数は操作順によらず一定なのでその偶奇で勝敗が決まる
操作回数はstackなどでシミュレートすればいい
提出コード

void solve(){
    string s;
    cin >> s;
    vector<int> st;
    int cnt = 0;
    REP(i,s.size()){
        if(st.empty()) st.push_back(s[i]-'0');
        else{
            if(st.back() != (s[i] - '0')){
                cnt++;
                st.pop_back();
            }
            else st.push_back(s[i]-'0');
        }
    }
    if(cnt % 2 == 0) cout << "NET" << endl;
    else cout << "DA" << endl;
}

C. Pluses and Minuses

累積和を取ると初期値がiのときどこまで操作が続くかを求めることが出来る
初期値がiだとすると-i-1が最初に出現する場所まで操作が続くのでその長さを加算する
文字列の末尾までたどり着けるときbreakすればいい
提出コード

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> idx(n+10, -1);
    int cur = 0;
    REP(i,n){
        if(s[i] == '-') cur--;
        else cur++;
        if(cur < 0){
            if(idx[abs(cur)] >= 0) continue;
            idx[abs(cur)] = i;
        }
    }

    ll ans = 0;
    for(int i=0;i<=n;i++){
        cur = -i - 1;
        // cout << i << " " << cur << endl;
        if(idx[abs(cur)] == -1){
            ans += n;
            break;
        }
        else ans += idx[abs(cur)] + 1;
        //cout << ans << endl;

    }
    cout << ans << endl;
}

D. Maximum Sum on Even Positions

操作を考えると区間が奇数のときは変化しないので、偶数の場合のみを考える
この時、偶数番目の要素を負として扱うと、連続区間の部分和の最大を求めればよくこれは\mathcal{O}(n)で求めることが出来る
後は、偶数番目からスタートか奇数番目からスタートかの2通りあるのでそれぞれ求めればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    ll sum = 0;
    REP(i,n){
        cin >> a[i];
        if(i % 2 == 0) sum += a[i];
    }
    ll cur = 0, even = INF, odd = 0;
    ll ma = 0;
    REP(i,n){
        cur += (i & 1 ? a[i] : -a[i]);
        if(i % 2 == 0){
            chmax(ma, cur - even);
            chmin(even, cur);
        }
        else{
            chmax(ma, cur - odd);
            chmin(odd, cur);
        }
    }
    cout << sum + ma << endl;
}

AtCoder Beginner Contest 171（ABC171）

AtCoderBeginnerContest171 AtCoderBeginnerContest ABC171 ABC

atcoder.jp

冷えたけど復習してたら楽しくなっちゃった（？）

A - αlphabet

'a'~'z'もしくは'A'~'Z'はASCIIコードでは連続になっているので小文字もしくは大文字かどうかを判定できる
提出コード

void solve(){
    char c;
    cin >> c;
    if('A' <= c && c <= 'Z') cout << "A" << endl;
    else cout << "a" << endl;
}

B - Mix Juice

昇順にソートし、小さい方からK個の合計を出力
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    REP(i,N) cin >> p[i];
    sort(p.begin(), p.end());
    int sum = 0;
    REP(i,K) sum += p[i];
    cout << sum << endl;
}

C - One Quadrillion and One Dalmatians

難しい
26進数っぽいものを求めて出力すればいい
1文字目を考えると'a'が1に対応しているので0-indexedに戻してあげる
次に桁上りした場合、その桁が1から始まるがこの問題だと0(='a')にならないといけない
そのため、各桁ごとに予め1引いた状態で26進数を求めればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    string ans = "";
    while(N > 0){
        N--;
        ans += char('a' + N % 26);
        N /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

D - Replacing

一瞬区間クエリだと思って激ムズでは？となった
数列のある要素を全部書き換えるようなクエリなので、現時点での総和と各値が何個あるかをvectorなどで管理する
そうすると、数列中のB_iをすべてC_iに変えたときの総和はその都度差分を考えることで求めることが出来る
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> cnt(101010);
    ll sum = 0;
    REP(i,N){
        int A;
        cin >> A;
        cnt[A]++;
        sum += A;
    }
    int Q;
    cin >> Q;
    REP(i,Q){
        int B, C;
        cin >> B >> C;
        ll tmp_cnt = cnt[B];
        ll tmp_sum = tmp_cnt * B;
        cnt[B] = 0;
        cnt[C] += tmp_cnt;
        sum -= tmp_sum;
        sum += tmp_cnt * C;
        cout << sum << endl;
    }
}

E - Red Scarf

出力する数列をB_0, B_1, ... , B_{N-1}とする
この時
A_0 = B_1 xor B_2 xor ... xor B_{N-1}
A_1 = B_0 xor B_2 xor ... xor B_{N-1} ... のようになる
B_1 xor B_1 = 0のように同じもののxorは0になるので1個だけ残るようにxor出来ないかを考えてみる
そうすると、B_0 = A_1 xor A_2 xor ... xor A_{N-1}のように自分を除いたもの以外のxorの合計がB_iとなる
これは、左右からの累積xorのようなものを事前に計算しておくと出来る
全体のxorからA_iのxor取るのでも同じ様になるんだけど、その発想出てこなかったな
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<int> left(N), right(N);
    left[0] = a[0], right[N-1] = a[N-1];
    for(int i=1;i<N;i++) left[i] = left[i-1] ^ a[i];
    for(int i=N-2;i>=0;i--) right[i] = right[i+1] ^ a[i];
    REP(i,N){
        if(i == 0) cout << right[i+1] << " ";
        else if(i == N-1) cout << left[i-1] << " ";
        else cout << (left[i-1] ^ right[i+1]) << " ";
    }
    cout << endl;
}

F - Strivore

教えてもらってなんとか理解できた（教えてくれた人ありがとう）
まず、適当に操作を行うと重複が出来てしまうので、操作と結果が1対1になるようにしたい
今回の場合、文字列Sに操作を行って出来たときの文字列をTとする
Tの先頭から貪欲に部分文字列を選んでSにするとき、その選んだindexが必ず辞書順最小となるように操作を行って文字列Tを作ることを考える
そうすると例えば、S="abc"とした時
'a'の左側には'a'以外の25文字、'a'と'b'の間は'b'以外の25文字、'b'と'c'の間は'c'以外の25文字、'c'より右側は好きな26文字すべておける
S_Nより左側にi文字、右側にK-i文字置くかを考え、0 \leq i \leq Kの場合を加算する
iを固定したときは、左側はそれぞれ25^i通りで、 S_1 〜 S_{N-1}をN - 1 + i個の中からどこに置くかで _{N - 1 + i} C _{N - 1}通り、右側は26^{K-i}通りあるので全体で
25^i \times _{N - 1 + i} C _{N - 1} \times 26^{K - i}通りとなる
求めた答えは、実は文字列Sの各文字に依存しないことがわかる、これすごい
提出コード

using mint = Fp<MOD>;
BiCoef<mint> bc(2020202);

void solve(){
    int K;
    string S;
    cin >> K >> S;
    int N = S.size();
    mint ans = 0;
    for(int i=0;i<=K;i++){
        ans +=  modpow(mint(25), i) * bc.com(N-1+i, N-1) * modpow(mint(26), K-i);
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 170（ABC170）

AtCoderBeginnerContest170 AtCoderBeginnerContest ABC170 ABC

atcoder.jp

F通したかったね

A - Five Variables

x_i = 0となるiを出力
提出コード

void solve(){
    int ans = 0;
    for(int i=1;i<=5;i++){
        int x;
        cin >> x;
        if(x == 0) ans = i;
    }
    cout << ans << endl;
}

B - Crane and Turtle

1 \leq X \leq 100なので鶴の数と亀の数を全探索し条件を満たすかどうか調べればいい
提出コード

void solve(){
    int X, Y;
    cin >> X >> Y;
    for(int i=0;i<=X;i++){
        int y = X - i;
        if(i * 2 + 4 * y == Y){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

C - Forbidden List

全探索を考える
pをmapやboolの配列で持っておき0 \leq x \leq 101の範囲で全探索をし、絶対値が一番小さいものを出力する
提出コード

void solve(){
    int X, N;
    cin >> X >> N;
    vector<int> p(N);
    map<int, int> mp;
    REP(i,N){
        cin >> p[i];
        mp[p[i]]++;
    }
    int ans = 0;
    int sa = INF;
    for(int i=-200;i<=200;i++){
        if(mp[i] > 0) continue;
        if(chmin(sa, abs(i - X))){
            ans = i;
        }
    }
    cout << ans << endl;
}

D - Not Divisible

本番は\mathcal{O}(N \sqrt{max(A_i)})で通した（C++を落とせるケースあるのかな）
愚直にA_iの約数列挙を行い、それが各A_jで割り切れるかどうかを調べる
想定解はエラトステネスの篩っぽくやるもの
A_iの倍数をそれぞれcnt_iに加算していく
加算する際には、すでにカウントされているものがあればそこで打ち切る
そうすると、計算量が篩部分と調和級数部分になり十分に間に合う
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> cnt(1010101);
    REP(i,N) cin >> A[i];
    REP(i,N){
        if(cnt[A[i]] > 0){
            cnt[A[i]]++;
            continue;
        }
        for(int k=A[i];k<1010101;k+=A[i]) cnt[k]++;
    }
    int ans = 0;
    REP(i,N) if(cnt[A[i]] == 1) ans++;
    cout << ans << endl;
}

提出コード(愚直)

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> mp(2020202);
    REP(i,N){
        cin >> A[i];
        mp[A[i]]++;
    }
    int ans = 0;
    REP(k,N){
        mp[A[k]]--;
        bool ok = true;
        for(ll i=1; i*i <= A[k]; i++){
            if(A[k] % i == 0){
                if(mp[i] > 0){
                    ok = false;
                }
                if(i != A[i] / i) if(mp[A[k]/i] > 0){
                    ok = false;
                }
            }
            if(!ok) break;
        }
        if(ok){
            // cout << k << endl;
            ans++;
        }
        mp[A[k]]++;
    }
    cout << ans << endl;
}

E - Smart Infants

まず各幼稚園ごとのレートの管理と、各幼稚園のmaxの集合を管理したい
各幼稚園ごとのレートの管理はmapを使えばいい
また、各幼稚園のmaxの集合にはセグ木を使うことで区間minのクエリに答えることができる
転園があるごとに転園前の幼稚園と転園後の幼稚園でレートのmaxが変更されればmapとセグ木の値を更新してあげればいい
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), B(N), C(Q), D(Q);
    vector<map<int, int>> mp(202020);

    SegTree<long long> seg(202020, [](long long a, long long b) {
            return min(a, b);
        },
        2*INF);
    seg.build();
    REP(i, N){
        cin >> A[i] >> B[i];
        A[i], B[i]--;
        mp[B[i]][A[i]]++;
        int val = seg.get(B[i], B[i]+1);
        if((val == 2*INF) || val < A[i]) seg.update(B[i], A[i]);
    }
    REP(i, Q){
        cin >> C[i] >> D[i];
        C[i]--, D[i]--;

        int pre = B[C[i]];
        mp[pre][A[C[i]]]--;
        if(mp[pre][A[C[i]]] == 0) mp[pre].erase(A[C[i]]);
        if(mp[pre].size() > 0){
            int ma = (mp[pre].rbegin() -> first);
            if(pre == 2*INF || ma < A[C[i]]){
                seg.update(pre, ma);
            }
        }
        else seg.update(pre, 2*INF);
        
        mp[D[i]][A[C[i]]]++;
        int ma = (mp[D[i]].rbegin() -> first);
        int val = seg.get(D[i], D[i]+1);
        if(val == 2*INF || ma > val){
            seg.update(D[i], ma);
        }
        cout << seg.get(0, 202020) << endl;
        B[C[i]] = D[i];
    }
}

F - Pond Skater

アルメリアさんの記事がわかりやすい
betrue12.hateblo.jp 愚直に各マスから4方向に1 \leq k \leq Kだけ移動する場合をBFSなどでやると\mathcal{O}(HWK)になる
アルメリアさんの記事でも解説されている通り、無駄になってしまう経路が存在する
具体的には、(h, w) から (nh, nw)への経路を考えたときにdist[nh][nw] \leq dist[h][w]となるときには枝刈りをする
そうすると、各マスへ入ってくる遷移は各方向あたり高々1回となり計算量が\mathcal{O}(HW)に落ちBFSで解くことが出来る
処理自体は簡単だけど、思いつくのかなり難しい

提出コード

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    int sh, sw, gh, gw;
    cin >> sh >> sw >> gh >> gw;
    --sh, --sw, --gh, --gw;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];

    queue<pair<int, int>> q;
    q.emplace(sh, sw);
    vector<vector<int>> dist(H, vector<int>(W, INF));
    dist[sh][sw] = 0;
    while(!q.empty()){
        auto [h, w] = q.front(); q.pop();
        REP(i,4){
            for(int k=1;k<=K;k++){
                int nh = h + k * dx[i], nw = w + k * dy[i];
                if(nh < 0 || nh >= H || nw < 0 || nw >= W) break;
                if(fi[nh][nw] == '@') break;
                if(dist[nh][nw] <= dist[h][w]) break;
                if(dist[nh][nw] > dist[h][w] + 1){
                    dist[nh][nw] = dist[h][w] + 1;
                    q.emplace(nh, nw);
                }
            }
        }
    }

    if(dist[gh][gw] == INF) dist[gh][gw] = -1;
    cout << dist[gh][gw] << endl;
}

東京海上日動 プログラミングコンテスト2020

AtCoder ARC 東京海上日動 プログラミングコンテスト2020

atcoder.jp

C時間かかっちゃった

A - Nickname

連続した3文字のどこかを出力すればいいので
S[0] S[1] S[2] を出力する
提出コード

void solve(){
    string S;
    cin >> S;
    cout << S[0] << S[1] << S[2] << endl;
}

B - Tag

V \leq Wのときは差が広がるだけなので"NO"
それ以外の場合は鬼が詰めないといけない距離は|A - B|であるので
T秒間でこの差を詰めれるかを考える
1秒間に詰めれる距離がV - Wなので、T秒間ではT(V-W)の距離を詰めることが出来る
したがって、|A - B| \leq T(V-W)であれば"YES"、そうでなければ"NO"
提出コード

void solve(){
    ll A, V, B, W, T;
    cin >> A >> V >> B >> W >> T;
    if(V <= W){
        cout << "NO" << endl;
        return;
    }
    ll dist = abs(A - B);
    if(dist <= T * (V - W)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

C - Lamps

明るさ0の電球iが座標iを照らすことを見落としてて時間溶かしちゃった
愚直にやると\mathcal{O}(NK)になって間に合わないのでどっちかをlogとかに落とせないかなーって考える
考えるんだけどよくわからないので、愚直にシミュレーションしてみる
そうすると結構早く全ての電球の明るさがNになることがわかる
N = 2 \times 10^5でもシミュレーションしてみると40回で操作が終わることを確認できる
そのため、最大でも50回くらいで打ち切ればシミュレーションでも通ることがわかる
区間にはimos法などを使えばいい（セグ木とかだと実装によっては落ちるらしい）
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    // int N = 2e5;
    // int K = 2e5;
    vector<int> A(N+10);
    vector<int> imos(N+10);
    REP(i,N){
        cin >> A[i];
        // A[i] = 0;
        imos[max(1, i+1-A[i])]++;
        imos[min(N+1, i+1+A[i]+1)]--;
    }
    REP(k,min(K,50)){
        vector<int> tmp(N+10);
        for(int i=2;i<=N+5;i++) imos[i] += imos[i-1];
        REP(i,N){
            A[i] = imos[i+1];
            // cout << A[i] << " ";
            tmp[max(1, i+1-A[i])]++;
            tmp[min(N+1, i+1+A[i]+1)]--;
        }
        imos = tmp;
    }
    REP(i,N) cout << A[i] << " ";
    cout << endl;
}