結果

問題 No.2746 Bicolor Pyramid
コンテスト
ユーザー Nzt3
提出日時 2026-05-20 10:14:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,817 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 257 ms
コンパイル使用メモリ 85,760 KB
実行使用メモリ 52,480 KB
最終ジャッジ日時 2026-05-20 10:14:23
合計ジャッジ時間 9,046 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def solve(R, B):
    # 作れない数字の集合 (Sprague の定理より)
    U = {2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 
         43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128}
    
    # 1. S_N <= R + B を満たす最大の N を二分探索で見つける
    total = R + B
    left, right = 0, 1
    while (right * (right + 1) * (2 * right + 1)) // 6 <= total:
        right *= 2
        
    N = 0
    while left <= right:
        mid = (left + right) // 2
        if (mid * (mid + 1) * (2 * mid + 1)) // 6 <= total:
            N = mid
            left = mid + 1
        else:
            right = mid - 1

    # 2. N 段が実現可能か判定する関数 (O(1))
    def is_valid(n):
        S_n = n * (n + 1) * (2 * n + 1) // 6
        L = max(0, S_n - B)
        H = min(S_n, R)
        
        if L > H:
            return False
            
        # N が小さい場合はビット演算を用いた正確なDP (O(1)で完了)
        if n <= 40:
            dp = 1
            for i in range(1, n + 1):
                dp |= (dp << (i * i))
            
            # 区間 [L, H] のいずれかのビットが立っているかチェック
            mask = ((1 << (H - L + 1)) - 1) << L
            return (dp & mask) > 0
            
        # N が大きい場合は Sprague の定理を利用
        else:
            if H - L >= 200:
                return True
            for X in range(L, H + 1):
                if X not in U and (S_n - X) not in U:
                    return True
            return False

    # 3. 実現可能な N を見つけるまで少しずつ下げる (最大でも1〜2回)
    while N > 0:
        if is_valid(N):
            return N
        N -= 1
        
    return 0

R,B=map(int,input().split())
print(solve(R,B))
0