結果

問題 No.1478 Simple Sugoroku
ユーザー lam6er
提出日時 2025-04-09 21:06:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 369 ms / 2,000 ms
コード長 1,501 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 134,712 KB
最終ジャッジ日時 2025-04-09 21:08:12
合計ジャッジ時間 12,254 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M_orig = int(input[idx])
    idx +=1
    B_orig = list(map(int, input[idx:idx+M_orig]))
    B = sorted(B_orig)
    if B[-1] != N:
        B.append(N)
    B = sorted(list(set(B)))
    M = len(B)
    
    left = 0.0
    right = 1e18
    for _ in range(100):
        mid = (left + right) / 2
        E = [0.0] * M
        sum_cal = 0.0
        E[-1] = 0.0  # since B[-1] is N
        sum_cal = 0.0
        for i in range(M-2, -1, -1):
            B_next = B[i+1]
            move_cost = B_next - B[i] + E[i+1]
            warp_cost = 1 + mid / M_orig  # note: M_orig is the original M, not including N if not present
            e = min(move_cost, warp_cost)
            E[i] = e
            sum_cal += e
        sum_cal += E[-1]
        if sum_cal < mid:
            right = mid
        else:
            left = mid
    final_S = (left + right)/2
    
    # Recompute E with final_S
    E_final = [0.0] * M
    E_final[-1] = 0.0
    for i in range(M-2, -1, -1):
        B_next = B[i+1]
        move_cost = B_next - B[i] + E_final[i+1]
        warp_cost = 1 + final_S / M_orig
        E_final[i] = min(move_cost, warp_cost)
    
    # Find the first B >= 1
    k = bisect.bisect_left(B, 1)
    if k < M and B[k] == 1:
        ans = E_final[k]
    else:
        ans = (B[k] - 1) + E_final[k]
    
    print("{0:.10f}".format(ans))
    
if __name__ == '__main__':
    main()
0