C - Upgrade Required
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
1,2,…,NまであるOSのバージョンをクエリの条件に従ってアップグレードしていく問題。
x yのような入力が与えられてx以下のバージョンをyにアップグレードする。
一番古いOSのバージョンを記憶しておくと良く、またもし一番古いバージョンがxより大きければ何もしない。
Nが8の以下のような例を考える。一番古いOSは1。それぞれ１台ずつ存在する
| os_ver | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 台数 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
入力が2 6の場合、2以下のOSのバージョンを6にアップグレードする。
古い方から順に見ていく。この時点で一番古いOSは3。
| os_ver | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 台数 | 0 | 0 | 1 | 1 | 1 | 3 | 1 | 1 |
続いて入力が3 5の場合3以下のバージョンを全て5にする。
| os_ver | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 台数 | 0 | 0 | 0 | 1 | 2 | 3 | 1 | 1 |
この処理を入力の数だけ処理していく。
毎度N（全台）をループする必要はなく、一番古いバージョンから入力のxのバージョンまで処理すれば良いので、計算量が少なくて済む。
以下でACできました。
def i_map():
return map(int, input().split())
def i_list():
return list(map(int, input().split()))
n, q = i_map()
os = [1]*n
mi=0
for i in range(q):
x, y = i_map()
x-=1
y-=1
if x < mi:
print(0)
continue
else:
count = 0
while mi <= x:
count += os[mi]
os[y] += os[mi]
mi += 1
print(count)Code language: Python (python)
コメント