結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー LyricalMaestro
提出日時 2026-06-30 01:42:04
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,208 ms / 5,000 ms
コード長 1,435 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 243 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 83,112 KB
最終ジャッジ日時 2026-06-30 01:42:14
合計ジャッジ時間 8,232 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/294

def combination(k, n):
    ans = 1
    for j in range(n):
        ans *= (k - j)
        ans //= (j + 1)
    return ans

def main():
    N = int(input())

    cache = {}
    def combination(k, n):
        if (k, n) in cache:
            return cache[(k, n)]
        
        if k == n or n == 0:
            ans = 1
        else:
            ans = combination(k - 1, n) + combination(k - 1, n - 1)
        cache[(k, n)] = ans
        return ans


    def calc(k):
        answer = 0
        n = 3
        while n <= k:
            answer += combination(k - 1, n - 1)
            n += 3
        return answer

    total_num = 0
    k = 1
    while N > total_num + calc(k):
        total_num += calc(k)
        k += 1

    N -= total_num

    def dfs(array, k, five_num, N_map):
        if len(array) == k - 1:
            if (five_num + 1) % 3 == 0:
                N_map[0] -= 1
                if N_map[0] == 0:
                    array.append("5")
                    return True
            return False
                
        array.append("3")
        if dfs(array, k, five_num, N_map):
            return True

        array[-1] = "5"
        if dfs(array, k, five_num + 1, N_map):
            return True
        array.pop()
        return False

    array = []    
    dfs(array, k, 0, [N])
    print("".join(array))

        
        
 

    



if __name__ == "__main__":
    main()
0