問題:https://atcoder.jp/contests/code-festival-2014-quala/tasks/code_festival_qualA_c
うるう年かどうかの判定は、4の倍数であればうるう年、ただし100の倍数はうるう年ではない、でも400の倍数はうるう年、というもの。単純に考えると一つずつ割り算を試して倍数判定する方法が思いつきますが、今回は問題の制約条件が厳しく最大値が2*10^9まであります。このため愚直に全探索していては間に合いません。工夫して実装する必要があります。
やり方はいくつかありますが、そのうちの一つを紹介します。ある整数の集合のうち、4の倍数は下図のような集合です。この青の領域は整数の集合をNとしたときにN//4で求めることができます。
同様に100の倍数はN//100で求めることができます。これを先ほどの4の倍数から除きます。
さらに400の倍数の数をN//400で求めて先ほどの集合に追加します。最終的に得られた青の領域がうるう年の数に相当します。
以上の方法で、1からNまでの数のなかにある「うるう年」の数を高速に求めることができます。ところで、この問題で求めなくてはならないのは、ある数A-B間にある「うるう年」の数です。このままでは上記の考え方で求めることはできません。
ここは下記の図のように考えれば解決できます。A~Bまでのうるう年の数は、「１～B」までのうるう年の数から、「1~A-1」までのうるう年の数を引くことで求めることができます。
なお、このエレガントな解法は職場の後輩から教えてもらいました。１～Nまでのうるう年の数を求めるところは自力でできたのですが、A-B間のうるう年を求める工夫はできず。。。
コード例
def uruu(a):
uru=a//4-a//100+a//400
return(uru)
A,B=map(int,input().split())
print(uruu(B)-uruu(A-1))以上の解法を実装するとこのようにシンプルなコードとなります。