結果

問題 No.3554 Rurumaru Function Problem 2
コンテスト
ユーザー Kude
提出日時 2026-05-23 02:10:49
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 111 ms / 2,000 ms
コード長 1,284 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 251 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 82,148 KB
最終ジャッジ日時 2026-05-23 02:10:53
合計ジャッジ時間 3,203 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def count(n, v):
    n = bin(n)[2:][::-1]
    v = bin(v)[2:][::-1]
    mx = max(len(n), len(v))
    n += '0' * (mx - len(n))
    v += '0' * (mx - len(v))
    dp = [[0] * 2 for _ in range(2)]
    dp[0][0] = 1
    for b in range(mx)[::-1]:
        ub = int(n[b])
        tgt = int(v[b])
        ndp = [[0] * 2 for _ in range(2)]
        for i in range(2):
            for j in range(2):
                for x in range(2):
                    for y in range(2):
                        if i == 0 and x > ub: continue
                        if j == 0 and y > ub: continue
                        z = x & y if b % 2 == 0 else x | y
                        if z != tgt: continue
                        ndp[i | (x < ub)][j | (y < ub)] += dp[i][j]
        dp = ndp
    return dp[1][1]

vals = [0]
for i in range(16):
    vals.append(vals[-1] | 1 << (2 * i + 1))

memo = [0]
for i in range(16):
    l = 0
    r = 1
    while count(r, vals[i]) >= count(r, vals[i+1]):
        l = r
        r *= 2
    while r - l > 1:
        c = (l + r) // 2
        if count(c, vals[i]) >= count(c, vals[i+1]):
            l = c
        else:
            r = c
    memo.append(r)

n = int(input()) + 1
ans = 0
for i in range(16):
    ans += (max(memo[i], min(n, memo[i+1])) - memo[i]) * vals[i]

print(ans)
0