https://atcoder.jp/contests/abc221/tasks/abc221_d
分割統治法で、区間の集まりを[(first, last, num)]で表して、それをマージする、というコードを書いたら意外と長いコードになってしまって、max1462msec。
解説を見ると、ああって感じで、書いてみたら実質8行。でも、1216msecであまり変わりませんでした。最初に書いたコードは、考え方は汎用性があると思います。
以下は、PyPy2のコードです。
# coding: utf-8 # Online games from collections import Counter #################### library #################### def read_int(): return int(raw_input()) def read_tuple(): return tuple(map(int, raw_input().split())) def read_list(): return list(map(int, raw_input().split())) def digits(n): while n: n, d = divmod(n, 10) yield d #################### naive #################### def F_naive(intervals): c = Counter() first = min(A for A, B in intervals) last = max(A+B for A, B in intervals) for d in range(first, last): n = sum(1 for A, B in intervals if A <= d < A+B) c[n] += 1 return [ c[n] for n in range(1, len(intervals) + 1) ] #################### process #################### def read_input(): N = read_int() intervals = [ read_tuple() for _ in range(N) ] return intervals import random def random_intervals(first, last): A = random.randrange(first, last) B = random.randrange(1, last - first) return (A, B) def F(intervals): def g(ints): if len(ints) == 1: A, B = ints[0] yield (A, A+B, 1) return mid = len(ints) / 2 ints1 = list(g(ints[:mid])) ints2 = list(g(ints[mid:])) k, l = 0, 0 while k < len(ints1) and l < len(ints2): A1, B1, n1 = ints1[k] A2, B2, n2 = ints2[l] if B1 == B2: if A1 == A2: yield (A1, B1, n1+n2) elif A1 < A2: yield (A1, A2, n1) yield (A2, B1, n1+n2) else: yield (A2, A1, n2) yield (A1, B1, n1+n2) k += 1 l += 1 elif B1 < B2: if B1 <= A2: yield ints1[k] elif A1 == A2: yield (A1, B1, n1+n2) ints2[l] = (B1, B2, n2) elif A1 < A2: yield (A1, A2, n1) yield (A2, B1, n1+n2) ints2[l] = (B1, B2, n2) else: yield (A2, A1, n2) yield (A1, B1, n1+n2) ints2[l] = (B1, B2, n2) k += 1 else: if B2 <= A1: yield ints2[l] elif A1 == A2: yield (A1, B2, n1+n2) ints1[k] = (B2, B1, n1) elif A1 < A2: yield (A1, A2, n1) yield (A2, B2, n1+n2) ints1[k] = (B2, B1, n1) else: yield (A2, A1, n2) yield (A1, B2, n1+n2) ints1[k] = (B2, B1, n1) l += 1 for int1 in ints1[k:]: yield int1 for int2 in ints2[l:]: yield int2 c = Counter() for first, last, n in g(intervals): c[n] += last - first return [ c[n] for n in range(1, len(intervals) + 1) ] #################### main #################### intervals = read_input() #intervals = [ random_intervals(1, 100) for _ in range(3) ] #print F_naive(intervals) v = F(intervals) print ' '.join(map(str, v))