AtCoder Beginner Contest 105 - かつかれーのメモ帳

競プロのカテゴリは、出て気づいたことや解法などメモしていく予定。~~まあABC105は出てないんだけど。~~
コンテストページ: AtCoder Beginner Contest 105 - AtCoder

C: Base -2 Number

「愚直 $O(N^2)$ だけど考察すると $O(N)$ 、ただし今回は必要ありません」とかいうの300点くらいだとよくあるし、考察するよりも適当に当たりをつけて探索書いたほうが速いでしょ→解法1。
実は少しだけ考察すると簡単で速い解法がある→解法2。
どちらも想定解とは違ったようなので記しておく。コンテスト出てたら考察せずに解法1書いてた気がする。

解法1

最下位ビットから数えて偶数番目と奇数番目で符号が違うので、とりあえず分けてみる。

偶数番目: $S_0(-2)^0+S_2(-2)^2+S_4(-2)^4+\dots=\sum S_{2i} 4^i$

奇数番目: $S_1(-2)^1+S_3(-2)^3+S_5(-2)^5+\dots=(-2)\sum S_{2i+1} 4^i$

和を取るiの範囲はいずれも0から最上位まで。ここで、
$m^+=\sum S_{2i} 4^i$
$m^- =\sum S_{2i+1} 4^i$
とする。これらは4進数表記で各ビットに0か1しか立っていない数である*1。

Nは初めの2式の和であるから、 $m^+,m^-$ の満たすべき関係は
$m^+-2m^-=N$

後で述べるように $m^+,m^-$ の候補はさほど多くないので、有り得る組み合わせを順に試せば通る。ただし、候補数( $M$ とする)は $10^5$ のオーダーなので、有り得る $M^2$ 個の組み合わせを全て試しているとTLEする。 $m^+$ を仮決めしてから $\frac{N-m^+}{(-2)}$ を候補から二分探索し、適切な $m^-$ が存在するか判定することで $O(M\log M)$ に改善するなどの工夫が必要。

Submission #3011214 - AtCoder Beginner Contest 105

import bisect


def put(a, b):  # 結果の表示
    l = max(len(a), len(b))  # aとbの長さが違うときに壊れるので以下で十分な長さの0を結合しておく
    a = "0" * l + a
    b = "0" * l + b
    s = ""
    for i in range(-1, -l-1, -1):  # 長さの偶奇を考えたくないので逆順に生成してあとで反転
        s += a[i] + b[i]
    s = s[-1::-1]  # 反転
    print(s[s.find("1"):])  # 頭にたくさんついている0を除いて表示


def quad(i):  # 数値を4進数表記の文字列に直す。16→"100"など。
    s = ""
    while i > 0:
        s += str(i % 4)
        i //= 4
    return s[-1::-1]


l = [0, 1]
for i in range(1, 20):  # 候補の生成。最長で20ビット。
    l += [4 ** i + j for j in l]

n = int(input())
if n == 0:  # n==0は出力が空文字になってしまうので別に扱う
    print("0")
else:
    for i in range(len(l)):
        ind = bisect.bisect_left(l, (l[i] - n) // 2)
        if l[i] - 2 * l[ind] == n:
            put(quad(l[i]), quad(l[ind]))
            break

※ $m^+,m^-$ の候補について
$N$ の-2進数表記での最上位ビットが $2n$ 番目だとする。そのような数は、最小でも $2^{2n}-2^{2n-1}-2^{2n-3}-2^{2n-5}- \dots -2 = 2^{2n}-\frac{2}{3}(2^{2n} - 1)=\frac{2^{2n}+2}{3}>2^{2n-2}$ になる。制約は $10^9<2^{30}$ であるので、32ビット目に1が立っている数が $N$ となることはない。負の数についても同様に考えると、34ビット長まで候補を持っておけば十分である。4進数では17ビット長に相当する。
本番では「 $N$ の-2進数表記のビット数はせいぜい2進数表記+1くらい→とりあえず30ビットより多めに持っておけば良いか」でOK。上のコードではとりあえず40ビット(4進で20ビット)持っている。

解法2

入力例など、いくつかの数字の2進数表記と-2進数表記をそれぞれ計算してみて見比べると、結構似ていることに気づく。そこで、手軽に得られる2進数表記をベースとして、-2進数表記に直していくことを試みる。

まずは解法1と同様偶奇性に目を向ける。

偶数番目のビットは-2進数の負号が消えているので、2進数と変わらない。
奇数番目のビットが0である場合も、両方で0になるので変わらない。
差が出るのは奇数番目のビットが1のときである！

奇数 $i$ について $S_i=1$ である状況を考えてみると、この位が表す数は2進数で $2^i$ 、-2進数で $-2^i$ であるから、この差というのは結局 $2^{i+1}$ であることがわかる。これより、正の数については以下のような手順で答えを求めることができる。

$\tilde{S}=(Nを2進数表記した文字列)$ 　とする。
$i=0$ から始めて、条件「 $i$ 番目以下のビットについては-2進数表記、それより上は2進数表記と思って $\tilde S$ を数値に直した値が $N$ に一致する」を満たし続けるように $\tilde S$ を修正しつつ $i$ をインクリメントすることを繰り返す。
$i$ が最上位ビットに至ったときの $\tilde S$ が求める $S$ である。

途中で行われる $\tilde S$ の修正は、 $i$ が奇数かつ $\tilde{S}_i=1$ でない限り必要なし。そうである場合は、-2進数の方が $2^{i+1}$ だけ損しているので $2^{i+1}$ を足す。これは $\tilde{S}_{i+1}$ に1を足すのと同じことであり、このビット以上は普通の2進数表記であるから、繰り上がり等普通に処理して良い。

文字列に直してから繰り上がり処理とかしたくないので、実装するときは $\tilde{S}$ を作らず数字のまま、2で割りながら最下位ビットを処理していくことになる。入力が負の数だった場合は1行目の処理ができないので、左ビットシフト(-2倍)したものについて答えを求めてから右ビットシフトする必要があることにも注意。

Submission #3011216 - AtCoder Beginner Contest 105

def solve(n):
    ret = ""
    i = 0  # n%2が元の何ビット目にあたるか
    while True:
        if i % 2 == 1 and n % 2 == 1:  # 奇数ビットが1のとき
            n += 2
        ret += str(n % 2)
        n //= 2  # 1ビット右にずらす
        i += 1
        if n == 0:
            break
    return ret[-1::-1]  # 逆順に結合されているので反転


n = int(input())
if n == 0:
    print(0)
elif n < 0:  # 負数は左ビットシフト、一文字落として表示
    n *= -2
    print(solve(n)[:-1])
else:
    print(solve(n))

D: Candy Distribution

これは想定解と同じ。 $B_0=0$ 及び $B_n=\displaystyle \sum_{i=1}^n A_i$ として累積和を計算しておく。 $A_l$ から $A_r$ までの和は $B_r-B_{l-1}$ となる。

これが $M$ の倍数、つまり $(B_r-B_{l-1}) \% M=0$ のとき、 $B_r\% M = B_{l-1}\% M$ が成り立つ( $M$ の剰余は $0$ から $M-1$ であり、 $B_r\% M - B_{l-1}\% M$ が $0$ 以外の $M$ の倍数になることはあり得ないので、 $M$ の倍数ならば必ず $0$ と言える)。

結局、この問題は $B_i\%M=B_j\%M$ なる組 $(i, j)$ が何組取れるか求める問題ということになる。累積和の $M$ 剰余だけが問題なので、はじめから剰余を取りつつ累積和を作れば良い。あとはそれをソートして左から見ていけば、剰余の同じものがいくつあるか調べることができる(もちろん解説の通りハッシュマップでも良い)。剰余の同じものが $n$ 個あったとしたら、組の取り方は ${}_n \mathrm{C}_2$ 通り。これを足し上げていく。

Submission #3011217 - AtCoder Beginner Contest 105

m = int(input().split()[1])

b = [0]
s = input().split()
for c in s:
    b.append((b[-1] + int(c)) % m)
b.sort()

l = []
j = b[0]
cnt = 1
for i in b[1:]:
    if i == j:
        cnt += 1
    else:
        l.append(cnt)
        j = i
        cnt = 1
l.append(cnt)
res = 0
for i in l:
    res += i * (i-1) // 2 # i==1のときは自動的に0になってくれる
print(res)

所感

DよりCが難しかった(こなみ)。C問題あたりまではろくに考察せずに書いちゃえば良いと思っていたけど、今回みたいにバグらせずに書くのが大変なパターンもあるので、少しは考察してみるといいかもしれない。考察をする気さえあれば10分そこそこで解けたはず。一方で、筋力をつけて脳死で書けるようにするのもまた大事っぽい。
tex使えるのは綺麗で良いけど、人が読むと思ってブログの文章書くと無限に時間かかることがわかったのでもう少し手を抜いて書きたい。

*1: $4^k$ をかけながら和を取っていくのは4進数の位取りそのものであり、また、 $S_k$ はすべて0か1であるため。