競プロ初中級者100問

AOJ2013 大崎

この記事で使うアルゴリズム

累積和
いもす法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2013

方針

いもす法を用いることで計算量O(N+K)で解くことができます。（ここではK=24*3600）

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from itertools import accumulate

def time_to_seconds(time):
    h, m, s = time.split(':')
    return int(h) * 3600 + int(m) * 60 + int(s)

ans = []
while(1):
    N = int(input())
    if N==0:
        break
    A = [0] * 86400
    for n in range(N):
        begin, end = input().split()
        begin = time_to_seconds(begin)
        end = time_to_seconds(end)
        A[begin] += 1
        A[end] -= 1
    cumsum = accumulate(A)
    ans.append(max(cumsum))

for a in ans:
    print(a)

Kが大きい場合、以下のようにソートを利用することで計算量O(NlogN)で解くこともできます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from itertools import accumulate

def time_to_seconds(time):
    h, m, s = time.split(':')
    return int(h) * 3600 + int(m) * 60 + int(s)

ans = []
while(1):
    N = int(input())
    if N==0:
        break
    A = []
    for n in range(N):
        begin, end = input().split()
        begin = time_to_seconds(begin)
        end = time_to_seconds(end)
        A.append((begin,1))
        A.append((end,-1))
    A.sort()
    mx = 0
    cumsum = 0
    for _, x in A:
        cumsum += x
        mx = max(mx, cumsum)
    ans.append(mx)

for a in ans:
    print(a)

記事情報

  • 投稿日：2020年5月26日
  • 最終更新日：2020年5月26日