結果

問題 No.320 眠れない夜に
ユーザー rpy3cpprpy3cpp
提出日時 2015-12-13 03:06:19
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 2,387 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 11,004 KB
実行使用メモリ 8,428 KB
最終ジャッジ日時 2023-10-13 14:14:27
合計ジャッジ時間 2,105 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
8,396 KB
testcase_01 AC 16 ms
8,364 KB
testcase_02 AC 16 ms
8,320 KB
testcase_03 AC 16 ms
8,348 KB
testcase_04 AC 17 ms
8,392 KB
testcase_05 AC 16 ms
8,404 KB
testcase_06 AC 16 ms
8,252 KB
testcase_07 AC 16 ms
8,308 KB
testcase_08 AC 16 ms
8,368 KB
testcase_09 AC 16 ms
8,312 KB
testcase_10 AC 16 ms
8,356 KB
testcase_11 AC 16 ms
8,352 KB
testcase_12 AC 16 ms
8,296 KB
testcase_13 AC 16 ms
8,320 KB
testcase_14 AC 15 ms
8,428 KB
testcase_15 AC 16 ms
8,392 KB
testcase_16 AC 16 ms
8,356 KB
testcase_17 AC 16 ms
8,348 KB
testcase_18 AC 16 ms
8,348 KB
testcase_19 AC 16 ms
8,196 KB
testcase_20 AC 16 ms
8,328 KB
testcase_21 AC 16 ms
8,252 KB
testcase_22 AC 16 ms
8,364 KB
testcase_23 AC 16 ms
8,248 KB
testcase_24 AC 16 ms
8,264 KB
testcase_25 AC 16 ms
8,308 KB
testcase_26 AC 17 ms
8,264 KB
testcase_27 AC 16 ms
8,348 KB
testcase_28 AC 16 ms
8,212 KB
testcase_29 AC 16 ms
8,248 KB
testcase_30 AC 16 ms
8,428 KB
testcase_31 AC 16 ms
8,220 KB
testcase_32 AC 16 ms
8,316 KB
testcase_33 AC 16 ms
8,404 KB
testcase_34 AC 16 ms
8,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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