結果

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

ソースコード

diff #
raw source code 

import sys

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)

def g(x):
    freq = [(h(x, v), -v) for v in a]
    return -max(freq)[1]

n = int(input())
a = [2 * (4**d - 1) // 3 for d in range(31)]
ans = 0
p = 1
for k in range(1, 31):
    l = p
    r = n + 1
    while r - l > 1:
        m = l + r >> 1
        if g(m) < a[k]:
            l = m
        else:
            r = m
    
    ans += (r - p) * a[k-1]
    p = r

print(ans)
0