結果

問題 No.320 眠れない夜に
コンテスト
ユーザー rpy3cpp
提出日時 2015-12-13 03:06:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 2,387 bytes
コンパイル時間 107 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-09-15 11:01:53
合計ジャッジ時間 2,170 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(N, M):
    ''' i 番目に1つ少なく数えた場合、第 N 項は、本来の値よりも、fib(N-i+1) だけ少なくなる。
    本来の値と M との差を、Q 個のフィボナッチ数の和で表すとして、Q の最小値を求めればよい、、はず。
    '''
    fibs = fib2(N)
    if M > fibs[N]:   # trivial なケースその１
        return -1
    if M == fibs[N]:  # trivial なケースその２
        return 0
    ans = find_min(fibs[N] - M, N, fibs)
    if ans == float('inf'):
        return -1
    else:
        return ans


def fib2(N):
    ''' フィボナッチ数列の第N項までのリストを返す。
    '''
    a = 0
    b = 1
    lst = [a, b]
    for i in range(2, N + 1):
        a, b = b, a + b
        lst.append(b)
    return lst


def find_min(t, n, fs):
    '''整数のリスト fs の部分和として t を表すとき、必要となる最小の個数を返す。
    表せないときは、-1 を返す。
    '''
    idx = n - 2
    return greedy(t, idx, fs)
#    return dfs(t, idx, fs)


def greedy(t, idx, fs):
    if t == 0:
        return 0
    if t >= fs[idx + 2]:
        return float('inf')
    count = 0
    while t:
        while idx and fs[idx] > t:
            idx -= 1
        if idx == 0:
            return float('inf')
        t -= fs[idx]
        count += 1
        idx -= 1
    return count


def dfs(t, idx, fs):
    if t >= fs[idx + 2]:  # 今後すべての fs を使っても t に達しないケース。
        return float('inf')
    while idx and fs[idx] > t:
        idx -= 1
    if idx == 0:         # fs を使い切ったケース。
        return float('inf')
    f = fs[idx]
    if f == t:
        return 1
    a = dfs(t - f, idx - 1, fs) + 1  # fs[idx] を使うケース。
    b = dfs(t, idx -1, fs)           # fs[idx] を使わないケース。
    return min(a, b)

N, M = map(int, input().split())
print(solve(N, M))


#print(solve(7, 9))
#print(solve(67, 17308070087783))

# 貪欲法と深さ優先探索の比較　-> 両者の答えは一致するので、貪欲法で良い模様。
#import random
#ntest = 1000
#N = 40
#fibs = fib2(N)
#for i in range(ntest):
#    t = random.randint(1, fibs[N] - 1)
#    a = greedy(t, N - 2, fibs)
#    b = dfs(t, N - 2, fibs)
#    if a != b:
#        print("Wrong:", i, t, a, b)
#        break
#else:
#    print('all test passed!')
0