2023-07-09

G - Distance Queries on a Tree

以下の問題の解説を理解するための知識をまとめてみました。

繰り返し二乗法

繰り返し二乗法とは、x¹, x², x⁴, x⁸, x¹⁶, ... を組み合わせて、xⁿを高速で計算するアルゴリズムです。

x¹, x², x⁴, x⁸, x¹⁶ は、二乗していけば、簡単に求めていくことができます。

nを1, 2, 4, 8, 16, ... の組み合わせで表すことができます。例えば、n=7 の場合、7 = 1 + 2 + 4 で表すことができます。もう少し表し直すと 7 = 2⁰ + 2¹ + 2² となり、やっていることは２進数の変換です。

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x; // n & 1で、1ビット目を見る
        x *= x; // x^1, x^2, x^4, x^8, ... を計算していく
        n >>= 1; // nを1bit右にずらして、1bit目に各桁のbitが来るようにする
    }
    return ret;
}

参考

algo-logic.info

ダブリング

繰り返し二乗法は、ダブリングの一種です。

ダンブリングは、「2^k 先の要素は何か」を求めます。以下の変数を考えます。

doubling[k][i] : i番目の要素から2^k先の要素は何か

初期化は、2⁰=1個先を記録します。これをもとに2^k先の要素を求めていきます。求め方は、以下のとおりです。

doubling[k+1][i] = doubling[k][doubling[k][i]]

doubling[k][doubling[k][i]] は、「i番目の要素から2^k先の要素から、さらに2^k先の要素」という意味になります。

クエリとして、「K個先の要素を求める」を考えます。 Kのk桁目が1ならば now = doubling[k][now]とします。

algo-logic.info

最近共通祖先（LCA：Lowest Common Ancestor）

LCAでは、ダブリングを使います。

DFSなどで、すべての頂点について、根からの距離と親を求め(ダブリングの初期化)、ダブリングによって2^k先の祖先を求めます。

algo-logic.info

2023-05-14

037 - Don't Leave the Spice（★5）

atcoder.jp

DPをしつつ、セグメント木で高速化する。普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。

dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。セグメント木の更新は、dp[i]の値を一通り一気にapplyメソッドで更新していく。

2023-05-14

036 - Max Manhattan Distance（★5）

アルゴリズム競技プログラミング

atcoder.jp

2、3回解いているが、なかなか覚えられないのでメモ。マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。

45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすくなる。

45度回転後のマンハッタン距離は max(|x1 - x2|, |y1 - y2|) になる。なぜか？これは チェビシェフ距離 と言うらしい。下記の記事で紹介されている式変形を眺めると、そうなることが分かってくる。

naoyat.hatenablog.jp

回転後の解法としては、

参考

kagglenote.com

2023-05-13

B - Gift Tax

アルゴリズム競技プログラミング

atcoder.jp

ソートして、最小値と最大値に対して、操作を繰り返せば良いかなと思ったが、うまくいかずにTLE。

答えに上限があることは分かったが、２分探索する発想はできなかった。典型問題の「答えで２分探索する」は思いつきたかった。そのあとの判定問題を考えつくのも難しそうだった。解説もイメージが付きづらかったので、以下の解説記事で理解した。

note.com

2023-05-13

A - Trailing Zeros

アルゴリズム競技プログラミング

atcoder.jp

末尾がT[i]個の0になっている整数を作っていけば良いことは分かったが、作り方の方針が誤っていた。「2^T[i] で割り切れて、2^T[i]+1で割り切れない整数」と言い換えられるところは典型っぽい考え方か？上記の条件に加えて、「A[i-1]より大きい整数」も考慮する必要がある。

解説動画では、シフト演算で計算する考え方になっている。基本的な考えとしては、

A[i-1] を T[i] だけ右シフトし(2^T[i]で割っている)
1を足し(左から(T[i]+1)番目を1とするため)
T[i]だけ左シフトする (2^T[i]で掛けている)

以上で、下T[i]桁が0となる。

ただし、2. を行った際に注意が必要で、繰り上がって末尾の 0 が増えてしまう場合がある。

例えば 1011 に 1 を足すと 1100 となってしまい、3. の操作をすると 110000 となって 0 が増えてしまう。この場合は、 1 をもう一度足して 1101 とする必要がある。上記の手順に加えて、

2.1. 一番左の桁が 0 の場合は、1を足す

が必要となる。

以上の手順を、テキスト解説で行っている計算にマッピングしてみる。

atcoder.jp

y1 の計算は、手順 1. と 2. と 3. の計算と同様。 y2 の計算は、手順 2.1 の計算を無条件に行っている。最後に、y1 と y2 の一方のみが 2^T[i]+1 で割り切れないようになっているので、割り切れない方を選んで A[i] とする。

どうすれば解けていたかの考察

2進数での計算の性質に関する理解が少なかったことが要因。

「2^T[i] で割り切れるかつ 2^T[i]+1 で割り切れない整数を求める」という言い換え力
A[i-1] から算出するためのビット計算方法の考案力

あたりが不足していたと考えられる。

2023-05-12

C - Multiplication 3

アルゴリズム競技プログラミング

atcoder.jp

浮動小数点の理解があまかったせいでACできなかった。 100倍して計算結果を100で割るところまでは思いついたが、キャストの部分でも誤差が出ることを理解していなかった。

例えば 0.79の場合、２進数で表すと 0 .11001010001111010111000010100011110101110000101000111101... のように無限に繰り返される形になる。これを10進数に表すと 0.789999999999999... といった数値になる。これを 100 倍して小数部を切り捨てし、100で割ると 0.78 となる。

これを避けるために、四捨五入する必要があるため、切り捨てる際は 0.5 を足せば良い。

double A = 0.79;
long long a = (A * 100 + 0.5) / 100;

2023-05-11

B - A^B^C

アルゴリズム競技プログラミング

atcoder.jp

1の位の周期性を考える。 B^Cは繰り返し二乗法で求めて、周期の長さで割れば良い。周期の中でどの位置にあるのかを求めるのが少し苦戦してしまった。

例えば、3 の周期は「3 9 7 1」の長さ4であり、3⁹ の場合は周期により、1となる。単純に 9 % 3 すると 0 になるので、インデックスがズレてしまう。算出するにはどうすればよいのか分かるのに時間がかかった。最終的には (n % len + len-1) % len とすれば良いことがわかった。

解説では、単純に周期は4になること、繰り返し二乗法で乗数が十分小さくなるので単純に掛けても良いので、もう少しシンプルに回答できることを知った。これに周期が4であると考えれば良いことに気がつくのは結構難しそうだが、繰り返し二乗法で十分小さくなることには気づきたかった。

long long power_mod(long long n, long long k, long long mod) {
    long long result = 1;
    // k を右シフトしつつ n を 2 乗していく
    while (k > 0) {
        // k の最下ビットが 1 なら、今の n を答えに掛ける
        if ((k & 1) == 1) result = (result * n) % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return result;
}


void solve(long long A, long long B, long long C){
    vl cnt;
    map<ll,ll> memo;
    ll wk = 1;
    REP(i, 100) {
        wk *= A;
        wk %= 10;
        if (memo[wk]) break;
        memo[wk] = 1;
        cnt.push_back(wk);
    }

    ll len = memo.size();
    ll n = power_mod(B, C, len);
    ll i = (n % len + len-1) % len;
    cout << cnt[i] << endl;
}

2023-05-08

C - ±1 Operation 1

アルゴリズム競技プログラミング

atcoder.jp

茶diffらしいが、実感としては緑diffくらいに感じる。値の範囲にマイナスが含まれているので、場合分けや反転させる処理が思いつけなかった。値の範囲が正のみ(D>0 && A,X > 0)であれば、特に難しいことはない。負の場合(D<0)、反転するには、初項を(A+(N-1)D)の値にして、D=-1 すれば良い。

if (D<0) {
    A = A + (N-1) * D;
    D *= -1;
}

あとはXに近い項を求める。求め方としては2通り。

項を二分探索するのであれば、0からN-1の範囲で行う。

ll l=0, r=N-1;
while (abs(l-r)>1) {
    ll mid = (l+r)/2;
    ll a = A + mid * D;
    if (a <= X) {
        l = mid;
    } else {
        r = mid;
    }
}

(X-A)/Dの計算で項を求めるのであれば、負になる場合とNになる場合も考慮が必要。

ll n = (X-A)/D;
if (n < 0) {
    cout << abs(A-X) << endl;
    return;
} else if (n > N) {
    cout << abs(A+(N-1)*D-X) << endl;
    return;
}

Xに近い項をiとすると、i か i+1 のそれぞれとXの差分を計算して、小さい方を解とする。

2023-05-02

B - Village of M People

アルゴリズム競技プログラミング

atcoder.jp

結構雰囲気で解いてしまった。まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQueueで管理する。

void solve(long long K, long long N, long long M, std::vector<long long> A){
    vl B(K+9);
    vector<pair<ll,ll>> diff(K+9);
    priority_queue<pair<ll,ll>> que;
    ll s = 0;
    REP(i, K) {
        B[i] = (A[i]*M+N-1)/N;
        s += B[i];
        que.push({B[i]*N-A[i]*M, i});
    }
 
    REP(i, s-M) {
        ll bi = que.top().second;
        que.pop();
        B[bi]--;
        que.push({B[bi]*N-A[bi]*M, i});
    }
 
    REP(i, K) {
        if (i!=0) cout << " ";
        cout << B[i];
    }
    cout << endl;
}

2023-05-02

D - Flip and Adjust

アルゴリズム競技プログラミング

atcoder.jp

表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0

dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1

dp[N][S]が1であればYes、そうでないならNo。

また、Yesの場合は、カードの置き方の一例を求める必要があるので、dpをNから逆順にたどっていく。

dp[N-1][S-a[i]] か dp[N-1][S-b[i]] でどちらかは1なので、前者であれば表を選び、後者であれば裏を選ぶ。

void solve(long long N, long long S, std::vector<long long> a, std::vector<long long> b){
    vvl dp(N+9, vl(S+9, 0));
    dp[0][0] = 1;
    REP(i, N) {
        REP(s, S) {
            if (dp[i][s]==0) continue;
            if (s+a[i]<=S) dp[i+1][s+a[i]] = 1;
            if (s+b[i]<=S) dp[i+1][s+b[i]] = 1;
        }
    }
 
    if (dp[N][S]) {
        cout << YES << endl;
        string ans;
        ll n = N;
        ll s = S;
        while (n > 0) {
            if (s >= a[n-1] && dp[n-1][s-a[n-1]]) {
                s -= a[n-1];
                ans.push_back('H');
            } else if (s >= b[n-1] && dp[n-1][s-b[n-1]]) {
                s -= b[n-1];
                ans.push_back('T');
            }
            n--;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    } else {
        cout << NO << endl;
    }
}