[AtCoder] エイシング プログラミング コンテスト 2020 D – Anything Goes to Zero
問題
方針
ビットカウントのアルゴリズム
アルゴリズムについては上記のサイトを参考にしました。
int count_bits(int n) { n=(n&0x55555555)+(n>>1&0x55555555); n=(n&0x33333333)+(n>>2&0x33333333); n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f); n=(n&0x00ff00ff)+(n>>8&0x00ff00ff); n=(n&0x0000ffff)+(n>>16&0x0000ffff); return n; }
\( 2 \times 10^5 \) 以下の \( f(n) \) の値は、愚直に求めます。
ビット毎に剰余を取る
\( X \) のビットカウントを \( p\) とすると、\( X \) の \( i \) ビット目を反転させたときのビットカウントは、\( p – 1 \) または \( p + 1 \) となります。また、剰余はビット毎に演算しても良いので、\( X \) の \( p – 1 \) と \( p + 1 \) の剰余をあらかじめ計算し、\( i \) ビット目の値によって補正すれば良いです。
ビット毎に剰余を取るには、階乗の剰余のアルゴリズムを使えば良いです。注意として、\( p = 1 \) のとき、\( X_i = 1 \) ならば、答えは \( 0 \) となります。
ビット反転の補正
\( a_1 = X \bmod (p – 1) \) 、\( a_2 = X \bmod (p + 1) \) とします。これらはあらかじめ求めておきます。
\( X_i = 1 \) のとき
このとき、\( X_i = 0 \) としたときの、\( p – 1 \) による剰余は、
\[(a_1 – 2^{N – i – 1} \bmod (p – 1) + p – 1) \bmod (p – 1)\]
となります。
\( X_i = 0 \) のとき
このとき、\( X_i = 1 \) としたときの、\( p + 1 \) による剰余は、
\[(a_2 + 2^{N – i – 1}) \bmod (p + 1)\]
となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int count_bits(int n) { n=(n&0x55555555)+(n>>1&0x55555555); n=(n&0x33333333)+(n>>2&0x33333333); n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f); n=(n&0x00ff00ff)+(n>>8&0x00ff00ff); n=(n&0x0000ffff)+(n>>16&0x0000ffff); return n; } ll modpow(ll a, ll n, ll mod) { if (mod <= 0) return 0; ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int solve(int n) { if (n == 0) return 0; return solve(n % count_bits(n)) + 1; } int main() { int N; string X; cin >> N >> X; ll p = 0; for (int i = 0; i < N; i++) { if (X[i] == '1') p++; } ll a1 = 0; ll a2 = 0; for (int i = 0; i < N; i++) { if (X[i] == '1') { if (p == 1) { a1 = 0; } else { a1 = (a1 + modpow(2, N - i - 1, p - 1)) % (p - 1); } a2 = (a2 + modpow(2, N - i - 1, p + 1)) % (p + 1); } } for (int i = 0; i < N; i++) { if (X[i] == '1') { if (p == 1) { cout << 0 << "\n"; } else { cout << 1 + solve((a1 - modpow(2, N - i - 1, p - 1) + p - 1) % (p - 1)) << "\n"; } } else { cout << 1 + solve((a2 + modpow(2, N - i - 1, p + 1)) % (p + 1)) << "\n"; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません