エイシング プログラミングコンテスト 2020に参加してみた
初めに
レーティングがABC相当のようだったので企業コンに参加しました。
結果はABC完でしたので、ぼちぼちって感じですね。
今回はD問題について書きますが、解き方うんぬんって話では無く
解説を聞いていて今まで書いた事が無いようなテクニックがあったので
そこにフォーカスして次に似たような問題が出た際に活用できるように
メモとして書いて行きます。
https://atcoder.jp/contests/aising2020/
D - Anything Goes to Zero
この問題はf(n)を「n を popcount(n) で割ったあまりに置き換える」という操作を繰り返した際に
nが0になるまでの操作回数として、与えられたN桁の2進数Xの1桁目のビットを反転した値をX1、
2桁目のビットを反転した値をX2、・・・n桁目のビットを反転した値をXnとして、
それぞれの桁数を反転させた場合の数値でのf(n)を求める問題です。
(X=101の場合は、X1=001,X2=111,X3=100になります。)
計算例) n = 7 の場合はf(7) = 2となります。(2回の操作でnが0となるため)
popcount(7)=3 なので、7を3で割ったあまりである 1に置き換えます。
popcount(1)=1 なので、1を1で割ったあまりである 0に置き換えます。
解説で記載されていたコードにコメントを追記したもの
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int pcnt(int x) {
//⑤popcountの計算を行うビルトイン関数
return __builtin_popcount(x);
}
int f(int x) {
//xの値が0の場合は0を返す
if (x == 0) return 0;
//操作回数を計算
return f(x%pcnt(x))+1;
}
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> x(n);
// ①配列xに数値として1と0を格納する。'1'-'0'= 1,'0'-'0' = 0
rep(i,n) x[i] = s[i]-'0';
// popcountを計算する。配列xに1or0が入っているので順番に足すだけで良い。
int pc = 0;
rep(i,n) pc += x[i];
//答えの格納用の配列ans
vector<int> ans(n);
//popcountが入力が反転して1増えるた場合と1減った場合を試す
rep(b,2) {
//popcountをnpcに格納する。
int npc = pc;
// 入力が反転してpopcountが1増えるパターン
if (b == 0) npc++;
// 入力が反転してpopcountが1減ったパターン
else npc--;
// npcが0以下になったらスキップ
if (npc <= 0) continue;
// 元の割った余りを求めていくための変数
int r0 = 0;
//元の数をnpc(pc+1 or pc-1)で割った数をr0としている。(掛け算・足し算・引き算の最中なら余りを求めても結果は変わらない)
//npc(pc+1 or pc-1)の2パターンでこれを行う。入力が011とかの場合は、101(5)や111(7)が考えられる
rep(i,n) {
// ②2進数Xの先頭桁から、桁が変わる毎に2を掛けていきXの値を計算し、その値をnpcで割っている
r0 = (r0*2)%npc;
r0 += x[i];
}
cout << "r0 = " << r0 << endl;
int k = 1;
for (int i = n-1; i >= 0; --i) {
//bが0のパターンと1のパターンで処理を分ける
if (x[i] == b) {
//元の数をnpc(pc+1 or pc-1)で割った数をr0としている。
//入力が011とかの場合は、101(5)や111(7)が考えられる
int r = r0;
//0が1に反転したと考えて、i桁目の値kを足す
if (b == 0) r = (r+k)%npc;
//③1が0に反転したと考えて、i桁目の値kを引く
else r = (r-k+npc)%npc;
ans[i] = f(r)+1;
}
//④i桁の目値をkに代入する。
k = (k*2)%npc;
}
}
rep(i,n) cout << ans[i] << endl;
return 0;
}
まずは①についてですね。(数字はソースコード内のコメントに記載されています。)
// ①配列xに数値として1と0を格納する。'1'-'0'= 1,'0'-'0' = 0 rep(i,n) x[i] = s[i]-'0';
入力された2進数文字列をint型配列に格納している処理ですが、
文字列sに格納されている各配列の値より文字列'0'を引いて数値を格納しています。
入力される文字列は'0'か'1'のみです。文字コード上の'0'と'1'は値が1しか差が無いので
文字列'0'を引くことで0 or 1をint型配列に格納することが出来ます。
解説聞くとなるほどと思いますけどやっている時には浮かばないんですよね。
お次は②についてです。
// 元の割った余りを求めていくための変数
int r0 = 0;
rep(i,n) {
// ②2進数Xの先頭桁から、桁が変わる毎に2を掛けていきXの値を計算し、その値をnpcで割っている
r0 = (r0*2)%npc;
r0 += x[i];
}
2進数の先頭ビットの値から変数に格納していき、次の桁数に移る際に現在の値に2を掛け、
移ったビットの値を足していく操作を繰り返していくと2進数の文字列の値を求める事が可能です。
※下記イメージのような感じ
これは、2進数に限らず10進数等でも同じように文字列から数字に変換することが可能です。
最初は解説を聞いた時にはピンと来なかったんですが、実際に書いてみたり10進数の場合で考えて
見たら理解出来ました。
③と④は関連しているのでまとめて書きます。
//③1が0に反転したと考えて、i桁目の値kを引く
else r = (r-k+npc)%npc;
//④i桁の目値をkに代入する。
k = (k*2)%npc;
④については、ループが回る毎にkに2を掛け1(20),2(21),4(22),8(23),16(24)・・・という形で
2進数の各桁の値をkで表す事が可能です。
③については、条件分岐によりrからkを引く際にマイナスになる可能性があるので、npcを足しています。
kについてもnpcで毎回割っているため、npcで余りを求めても問題ありません。
これは、掛け算・足し算・引き算の最中なら余りを求めても
結果は変わらないということがポイントですね。
※詳細については下記の記事を見てもらえると理解が深まると思います。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
最後は⑤についてです。
int pcnt(int x) {
//⑤popcountの計算を行うビルトイン関数
return __builtin_popcount(x);
}
まぁこれはgccのビルトイン関数でint型の数値のポップカウントを求める方法が
ある事が解説を見て分かったので、忘れないようにメモしておこうって感じですね。
最後に
今回はABC完出来たので個人的には良かったのですが、まだD問題には全然歯が立たないですね。
解説聞けば解けそうと思うような問題もあるんですが、まだまだですねぇ。
まぁとりあえずはABC完をキープしてまずは茶色になりましょ！
