AtCoder Regular Contest 127 A,C問題メモ

AtCoder Regular Contest 127

8時開始なら8時開始って言ってよねもぉ～（大遅刻）（※言われてました）

A - Leading 1s

• 整数 $x$ に対し、$f(x)$ を「10進数表記で先頭に'1'が連続する個数」とする
  • 例: $f(1112311)=3, f(2)=0$
• $N$ が与えられるので、$f(1)～f(N)$ の総和を求めよ
• $1 \le N \le 10^{15}$

桁DPっぽいけど、なんか上手く当てはめきれなくて手間取った。

「10進数表記にしたときの桁数」と「何桁目か」ごとに、答えへの寄与を求める。

       N = 1113012

7桁 1桁目  1xxxxxx  ... 1000000 ～ 1113012 の (1113012 - 1000000 + 1) 個
7桁 2桁目  11xxxxx  ... 1100000 ～ 1113012 の (1113012 - 1100000 + 1) 個
7桁 3桁目  111xxxx  ... 1110000 ～ 1113012 の (1113012 - 1110000 + 1) 個
7桁 4桁目  1111xxx  ... 1111000 ～ 1111999 の (1112000 - 1111000) 個
7桁 5桁目  11111xx  ... 1111100 ～ 1111199 の (1111200 - 1111100) 個
...
6桁 1桁目   1xxxxx  ...  100000 ～  199999 の ( 200000 -  100000) 個
6桁 2桁目   11xxxx  ...  110000 ～  119999 の ( 120000 -  110000) 個
...

※xで表された箇所は、Nを超えない限り何でもよい

このように、$k$ 桁目を考えるときは先頭 $k$ 個を $1$、残りを $0$ にした数を $X$ とし、
「$N+1$」と「$X$ の最後の $1$ を $2$ にしたやつ」の小さい方から $X$ を引いた個数だけ、答えに寄与する。

ただし、$N=11103$ のように $1$ が連続した次に $0$ が来るケースは、 4桁目の $X=11110$ を考慮する際に個数が負になってしまうので、$N \lt X$ となったらその桁数はそこで打ちきる。

Python3

C - Binary Strings

• $1～2^N-1$ の数を2進数表記にして、それら全てを文字列とみなして辞書順にソートした
• $X$ 番目の数を2進数表記で答えよ
• ただし $X$ は2進数表記で与えられる
• $1 \le N \le 10^6$

$X$ 番目を高速に見つける方法を発見するのが1点、2進数で与えられる $X$ を上手く処理するのが1点。

とりあえず実験してみると、先頭は'1'なのは全て共通として、後は自己相似形っぽくなっている。

N=4
          桁は下から数えるとして、
1---      3桁目に着目すると、'-' が1つ、'0' が7つ、'1' が7つ
10--  |
100-  |-- 3桁目が'0'である7つの 2桁目に着目すると
1000  |     '-' が1つ、'0' が3つ、'1' が3つ
1001  |   （これは3桁目が'1'の7つでも同じ）
101-  | |
1010  | |-3桁目が'0'、2桁目が'1'の3つの1桁目に着目すると、
1011  | |   '-' が1つ、'0' が1つ、'1' が1つ
11--      （これは3桁目、2桁目が同じ他のグループでも同じ）
110-
1100
1101
111-
1110
1111

従って、以下のようにすると答えが求められる。

• ans = 1 とする（文字列として扱う）
• 上の桁から順に処理して、$d$ 桁目の処理では
  • $X=1$ なら、今の ans が答え
  • $X \le 2^{d-1}$ なら、ans 末尾に '0' を加え、$X←X-1$ とする
  • $X \gt 2^{d-1}$ なら、ans 末尾に '1' を加え、$X←X-2^{d-1}$ とする

よっしゃ、Pythonなら多倍長も扱えるしこれをそのまま実装すれば勝ったな。ガハハ。

だが、いくら多倍長が扱えるといってもさすがに $2^{1000000}$ に近い数を $10^6$ 回演算するのはTLEとなる（なった）。

$X$ が2進数で与えられること、また各桁で'0'と'1'のどちらを追加するかは $2^{d-1}$ 以下か超過かで判定できることから、

• $X$ を0埋めして $N$ 桁にした上で 0,1の配列で表す
• 最初に1を引いて、0-indexedにする

X = 1100110    N=9
  ↓
X = [0, 0, 1, 1, 0, 0, 1, 0, 1]

とした上で、以下の3種類の演算を実装すればよい。

• $X$ が $2^{d-1}$ 未満か以上か判定する
  • それに相当する箇所が 0 か 1 か見る
• $X$ から $2^{d-1}$ を引く
  • それに相当する箇所を 1 → 0 にする
• $X$ から $1$ を引く
  • 下の桁から最初に '1' が見つかるまで遡り、そこを'0'、それまでの'0'を'1'にする

で、最後が1個ずつ見ていくので計算量的に不安になるが、実はこれは大丈夫。

1回、なかなか '1' が見つからないでたくさん遡った後は、下の桁は '1' で埋められる。
そしたらしばらくは、再びたくさん遡ることは無い。

A問題をひっくり返した感じで、 下から $k$ 桁目まで遡られる期待値を $k$ 毎に考えると、$2^{k-1}$ 回に1回なので、 $1+\dfrac{1}{2}+\dfrac{1}{4}+...=2$ に収束する。1回あたり均し $O(1)$ で済む。

（今回は1を引く演算しか無いのでこれが言えるが、足したり、他の演算も絡んでくる場合はそうとは限らないので注意）

Python3