CODE FESTIVAL 2014 予選A C - 2月29日

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B = il()
    A -= 1
    print((B//4 - B//100 + B//400) - (A//4 - A//100 + A//400))


if __name__ == '__main__':
    main()

考え方

ループによって、うるう年の判定を行うと実行時間超過となります。
そのため、効率的な求め方を考える必要があります。

• 回答概要
  • AからB年までに訪れるうるう年は、B年までのうるう年の数 - A-1年までのうるう年の数
  • X年までに訪れるうるう年はX // 4 - X // 100 + X // 400

---

まず、素直な実装について考えます。
単純にA年からB年までの範囲で、 毎回うるう年か否かの判定を行うことで、1 <= A <= B <= 3000のテストケースは正解することが出来ます。

    ret = 0
    for year in range(A, B+1):
        if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
            ret += 1
    print(ret)

または

    import calendar
    ret = 0
    for year in range(A, B+1):
        if calendar.isleap(year):
            ret += 1
    print(ret)

ただし、上記の回答は計算量が最大O(2 * 10**9)となるため、全て回答することが出来ません。

今回の問題では、ある年がうるう年か否かの判定ではなく、
X年までのうるう年の数を求められています。
そのため、判定式year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)を毎回行う必要はありません。

X年までのうるう年の数はX // 4 - X // 100 + X // 400になります。
ただし、求める範囲はA年も含めることに注意が必要です。