この記事は 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』 のサンプルです。
【その他のサンプル】
ABC201 A：https://qiita.com/sano192/items/3258c39988187759f756
ABC225 B：https://qiita.com/sano192/items/10133eeb6abc64f1441e
ABC213 C：https://qiita.com/sano192/items/9cd14b2cefd8bafa5615
ARC122 B：https://qiita.com/sano192/items/1f314701f2d5b18c8816
「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC119~128の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
【キーワード】
なし
【どう考える？】
単純に一日毎に何人ログインしていたか記録していく方法では間に合わない。管理すべき情報はログインしている人数であり、それはAi,Biのタイミングでしか変動しない。で、あれば増減が起こる日に絞ってログイン人数を確認し、それが次の増減が起こるまで何日続くかを確認していくだけでよい。
【解説】
ログインしている人数が増減するタイミングはログインまたはログアウトが起こった日のみ。
よって増減のタイミングで人数を計算し、それが次の増減が起こるまで何日続くかを確認して記録していく。
以下の手順で解く。
(1)ログイン開始日(login)、ログアウト日(logout)の一覧を作る
(2)ログイン開始、またはログアウトがある日の一覧(event)を作る
(3)(1),(2)で作った一覧をソートする
(4)eventの各日付について人数の増減が何人あるかを確認してログイン人数を計算し、次のeventの日付まで何日続くかを計算して記録していく。
(5)答えを出力する
～例～
N：6
A1 B1：1 9
A2 B2：6 1
A3 B3：20 10
A4 B4：10 20
A5 B5：6 4
A6 B6：20 10
(1)ログイン開始日、ログアウト日の一覧を作る
ログイン開始日はAi、ログアウト日は(Ai+Bi)となる。
login：1 6 20 10 6 20
logout：10 7 30 30 10 30
(2)ログイン開始、またはログアウトがある日の一覧(event)を作る
ログイン開始、またはログアウトがある日はつまりプレイヤーの増減が発生する日。
(1)で得られたログイン開始日、ログアウト日を合わせて重複を消す。
event：1 6 7 10 20 30
(3)(1),(2)で作った一覧をソートする
login：1 6 6 10 20 20
logout：7 10 10 30 30 30
event：1 6 7 10 20 30
(4)eventの各日付について人数の増減が何人あるかを確認してログイン人数を計算し、次のeventの日付まで何日続くかを計算して記録していく。
ログインしている人数をplayersとする。
「event[0]：1日目」
players：0
1日目は
login[0]=1 なのでログイン者が1人増える。
logout[0]=7 なのでログアウト者はいない。
よって1日目にはログイン者が1人ということがわかる。
players：1
これは次の増減が起こる日、つまりevent[1]=6日目まで続く。
よってログイン人数が1人である日数は
「次の増減が起こる日」-「今の日付」
=6-1
＝5日
つまりログイン人数が1人である日が5日間続く。
「event[1]：6日目」
players：1
6日目は
login[1]=6 なのでログイン者が1人増える。
更にlogin[2]=6 なのでもうひとり増える。
このようにlogin[i]が今の日付と同じ間はiを進めていくことでログイン者の増加数が確認できる。
logout[0]=7 なので減るログイン者はいない。
6日目にはログイン者が2人増えて3人ということがわかる。
players：3
同様に何日続くか計算する。
「次の増減が起こる日」-「今の日付」
=7-6
＝1日
ログイン人数が3人である日が1日間続く。
「event[2]：7日目」
players：3
7日目は
login[3]=10 なのでログイン者は増えない。
logout[0]=7 なので1人ログアウトする。つまり1人減る。
7日目にはログイン者が1人減って2人となる。
players：2
「次の増減が起こる日」-「今の日付」
=10-7
＝3日
ログイン人数が2人である日が3日間続く。
「event[3]：10日目」
players：2
10日目は
login[3]=10 なのでログイン者が1人増える。
logout[1],logout[2]=10 なので2人減る。
6日目にはログイン者が1人増え、2人減るので1-2=-1となり、1人になるということがわかる。
players：1
「次の増減が起こる日」-「今の日付」
=20-10
＝10日
ログイン人数が1人である日が10日間続く。
ただしログイン者が1人の期間は1日目~6日目の5日間あったので、合計で15日間となる。
「event[4]：20日目」
players：1
20日目は
login[4],login[5]=20 なのでログイン者が2人増える。
logout[3]=30 なのでログアウトはいない。
20日目にはログイン者が2人増えて2人ということがわかる。
players：3
「次の増減が起こる日」-「今の日付」
=30-20
＝10日
ログイン人数が3人である日が10日間続く。
ログイン者が3人の期間は6日目~7日目の1日間と合算して11日間となる。
「event[5]：30日目」
最後の日は全員がログアウトする。つまり0人になるだけなので考慮しなくて良い。
(5)答えを出力する
(4)の情報を整理して以下が答えとなる。
1人：15日間
2人：3日間
3人：11日間
4人：0日間
5人：0日間
【実装のコツ】
＜変数名の付け方＞
本問のように管理する情報が「プレイヤーの増減が発生する日」「ログイン開始日」「ログアウト日」と多い場合、競プロ上位者や公式解説はx,y,zやa,aa,aaaなどのような変数名をつけている事が多い。
しかし競プロに慣れていない人が同じことをやるとバグが起こったり余計な時間がかかったりする。灰色や茶色の間は「event」「login」「logout」等パット見で何を格納している変数かわかるよう、できるだけ単純でわかりやすい変数名を心がけると良い。
＜リストのカッコを外して出力＞
print(*リスト)とすることでリストの内容を[]なしで出力できる。
A=[1,2,3,4,5]の場合
print(A)
→[1,2,3,4,5]
print(*A)
→1 2 3 4 5
【提出】
# 入力の受け取り
N=int(input())
# ログイン開始日
login=[]
# ログアウト日
logout=[]
# 開始または終了が起こる日(重複除去のためリスト)
event=set()
# N回受け取り
for i in range(N):
# A,Bの受け取り
A,B=map(int, input().split())
# プレイヤーiのログイン開始日
login.append(A)
# プレイヤーiのログアウト日(ログインをやめた日)
logout.append(A+B)
# ログイン開始日を追加
event.add(A)
# ログアウト日を追加
event.add(A+B)
# ログイン開始日,ログアウト日をソート
login.sort()
logout.sort()
# リストへ変換
event_list=list(event)
# ソート
event_list.sort()
# ログインしている人数
players=0
# 答えの格納リスト
ans=[0]*(N+1)
# ログイン開始日の確認用
a=0
# ログアウト日の確認用
b=0
# i=0~(eventの長さ-2)
for i in range(len(event_list)-1):
# 今何日目か
now=event_list[i]
# now=ログイン開始日ならば
while a<len(login) and login[a]==now:
# プレイヤーがひとり増える
players+=1
# 次のログイン開始日を確認
a+=1
# now=ログアウト日ならば
while b<len(logout) and logout[b]==now:
# プレイヤーがひとり減る
players-=1
# 次のログアウト日を確認
b+=1
# ans[プレイヤー人数]に次の(「開始または終了が起こる日」-「今の日数」)をプラス
ans[players]+=event_list[i+1]-now
# 答えの出力
print(*ans[1:])