AtCoder Beginner Contest 221 D – Online games をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 221 D – Online games

解法は思いつきやすいが、ふたつの手法を組み合わせる必要があるので、実装がやや面倒かもしれない。

# AtCoder Beginner Contest 221 D - Online games
# https://atcoder.jp/contests/abc221/tasks/abc221_d
# tag: 座標圧縮 いもす法 典型問題 高橋君

# いもす法と呼ばれる手法で解く。

# A B で表されるプレイヤーがいる場合、人数の変化に着目すると
# A 日目の変化は +1、A+B 日目の変化は -1 となる。

# 日付ごとの変化量を記録するリストを用意しておき、
# 上記の変化をまとめていくことで、日付ごとの
# 人数の変化を作成することが可能。

# 今度は逆に日付ごとに順番に見ていき、現在の人数に
# 人数の変化を加えることで、その日付に何人いるのかを
# 把握することができる。

# 入力例 1 でいうと、作成される変化のリストは
# [0, 1, 1, 0, -1, -1] となり、その累積和
# 0, 1, 2, 2, 1, 0 が、実際の人数となる。

# のだが、日付の制約が緩く、全ての日付分の
# リストを作成すると TLE になってしまう。

# よって、まず日付を座標圧縮した後、いもす法を
# 用いる形で解く

def main():
N = int(input())
players = [list(map(int, input().split())) for _ in range(N)]

# 座標圧縮の準備。全ての座標をリストにする。
day_list = []
for a, b in players:
day_list.append(a)
day_list.append(a + b)

# 重複をなくし、ソートする。
# 圧縮後 → 圧縮前が day_list[i] で求まるようになる。
day_list = list(set(day_list))
day_list.sort()

# 圧縮前 → 圧縮後が comp_dic[day] で求まるよう、辞書を作成。
comp_dic = {day:i for i, day in enumerate(day_list)}

# 圧縮後の座標を利用して、いもす法を行う。
imos = [0] * len(day_list)
for a, b in players:
imos[comp_dic[a]] += 1
imos[comp_dic[a + b]] -= 1

result = [0] * (N+1)

# いもす法で人数と経過した日数を求めていく。
num = 0
prev_day = 0
for i in range(len(day_list)):
now = day_list[i]
result[num] += now - prev_day

num += imos[i]
prev_day = now

print(*result[1:])

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です