東京大学 情報理工学研究科 数理情報学 2022年8月実施 第5問
Author
Description
自然数(正の整数)
を満たす整数の列
が成立するものを
(1) 自然数
(2) 任意の自然数
(3) 自然数
(4) 整数の列
が成り立つことを示せ。
(5) 自然数
が成り立つことを示せ。ただし、
Kai
平衡三進法と呼ばれる有名な記法が元ネタ?
(1)
貪欲に 1 を割り当てていくのが最善。
(2)
存在性は (3) より言えるので、一意性のみ言えばよい。
相異なる疎な表現
以上より、示された。
(3)
下位のビットから見ていって、二進数の
油断した実装だと、十進法における
なお、Slack 上では、上位のビットから貪欲に見ていくという方針もあった。 コード 1 において、anotherSolution という関数で実装している。 尤も、二進表現を疎な三進表現に変換せよという問題だったので、あまり想定解ではないかも知れない。
コード 1
import math
from collections import defaultdict
from numba import jit
from tqdm import tqdm
@jit(cache=True)
def toSparseTernaryRepresentation(S: str):
ret = ""
i = 0
while i < len(S):
if S[i] == "0":
ret += "0,"
i += 1
elif S[i] == "1":
cnt = 0
while i < len(S) and S[i] == "1":
cnt += 1
i += 1
if cnt == 1:
ret += "1,"
else:
ret += "-1," + "0," * (cnt - 1)
# originally, the following
# must be inplace operation
# for the sake of efficiency
S = S[:i] + "1" + S[i + 1 :]
return ret[:-1]
def anotherSolution(n: int):
def L(i):
if i <= 0:
return 0
if i % 2 == 1:
return (2 ** (i + 1) - 1) // 3
else:
return 2 * (2**i - 1) // 3
d = []
for i in range(math.ceil(math.log2(n)) + 3)[::-1]:
if abs(n - (2**i)) <= L(i - 1):
n -= 2**i
d.append(1)
elif abs(n + (2**i)) <= L(i - 1):
n += 2**i
d.append(-1)
else:
d.append(0)
d = d[::-1]
while d[-1] == 0:
d.pop()
return ",".join(map(str, d))
def problem5():
maxN = 16
zeroCnt = 0
cntPer3 = defaultdict(int)
for n in tqdm(range(1, (1 << maxN) + 1)):
S = bin(n)[2:][::-1]
T = toSparseTernaryRepresentation(S)
S += "0" * (maxN - len(S))
listT = list(map(int, T.split(",")))
listT += [0] * (maxN - len(listT))
if listT[maxN // 2] == 0:
zeroCnt += 1
cntPer3[tuple(S[maxN // 2 - 1 : maxN // 2 + 2][::-1])] += 1
print(f"result: {zeroCnt/(1<<maxN)}")
print(f"cntPer3: {sorted(cntPer3.items())}")
def main():
maxIntPerDigit = defaultdict(int)
for n in range(1, 1000 + 1):
S = bin(n)[2:][::-1]
# ternary representation
T = toSparseTernaryRepresentation(S)
print(f"binary: {S} | ternary: {T}")
# another solution
T2 = anotherSolution(n)
assert T == T2, f"{T} != {T2}"
# assertion
TasInt = sum([c * (2**i) for i, c in enumerate(list(map(int, T.split(","))))])
assert TasInt == n
# count
maxIntPerDigit[len(T.split(","))] = max(maxIntPerDigit[len(T.split(","))], n)
print(f"maxIntPerDigit: {maxIntPerDigit}")
if __name__ == "__main__":
main()
# problem5()
result
binary: 1 | ternary: 1
binary: 01 | ternary: 0,1
binary: 11 | ternary: -1,0,1
binary: 001 | ternary: 0,0,1
binary: 101 | ternary: 1,0,1
binary: 011 | ternary: 0,-1,0,1
binary: 111 | ternary: -1,0,0,1
binary: 0001 | ternary: 0,0,0,1
binary: 1001 | ternary: 1,0,0,1
binary: 0101 | ternary: 0,1,0,1
binary: 1101 | ternary: -1,0,-1,0,1
binary: 0011 | ternary: 0,0,-1,0,1
binary: 1011 | ternary: 1,0,-1,0,1
binary: 0111 | ternary: 0,-1,0,0,1
binary: 1111 | ternary: -1,0,0,0,1
binary: 00001 | ternary: 0,0,0,0,1
(4)
題意が成立しないと仮定すると、ある自然数
下位ビットから上位ビットに向かって対象としている疎でない表現に対する文字列検索を走査していく。
まず、表現に
次に、表現に
以上の操作を最上位ビットになるまで繰り返す。
これが
以上より、疎な三値表現以外の表現によって、
(5)
あまり想定解な気はしないが、一応
ある桁に注目した際に、その桁が
(3) のアルゴリズムにおける、変換前の 2 進数における状態で場合分けをして考える。 すると、以下のような表が得られる。
変換前の2進数(当該桁+前後) | その桁が0になる確率 |
---|---|
000 | 1 |
001 | 1/2(後続が0) |
010 | 1/4(後続が11) + 1/4(後続が10) |
011 | 1 |
100 | 1 |
101 | 1/2(後続が0) |
110 | 1/4(後続が11) + 1/4(後続が10) |
111 | 1 |
この表における確率を合計すると、
この表の意味を説明する。
まず、前準備として、変換前の 2 進数において、
であるので、
次に、実際に表を埋める。
他も同様。
よって、期待値は