結果

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

ソースコード

diff #
raw source code 

# 前処理.
MAX_BIT = 30
U = [2*(pow(4,k)-1)//3 for k in range(MAX_BIT + 1)]

def h(n, v):
    if n == 0: return 0
    m = n - 1
    memo = {}
    def dfs(d, fx, fy):
        if d == -1: return 1
        st = (d, fx, fy)
        if st in memo: return memo[st]
        res = 0
        bm = (m >> d) & 1
        bv = (v >> d) & 1
        for bx in (0, 1):
            for by in (0, 1):
                if fx == 0 and bx > bm: continue
                if fy == 0 and by > bm: continue
                ok = 0
                if d & 1:
                    if (bx | by) == bv:
                        ok = 1
                else:
                    if (bx & by) == bv:
                        ok = 1
                if ok:
                    res += dfs(d-1, fx or (bx < bm), fy or (by < bm))
        memo[st] = res
        return res
    return dfs(30, 0, 0)

N = int(input())
ans = 0
left = 1
for k in range(1, MAX_BIT + 1):
    l = left
    r = N+1
    # g(n) = U[k]となる境界nを探す.
    while r-l > 1:
        mid = (l+r)//2
        if h(mid, U[k - 1]) >= h(mid, U[k]):
            l = mid
        else:
            r = mid
    ans += (r-left)*U[k-1]
    left = r
print(ans)
0