ABC355参加後振り返り
前書き
2024/3からAtCoderを始めました。
現職は、2年目の新人インフラSEです。
業務中では、実際に手を動かすとなると時間がかかるという場面が多く、
AtCoderを通して高パフォーマンスを出せるように実装力を磨きます。
使用言語はPython3です。
ABC 355 振り返り
全体を通しての感想
今回はA, B, Cの3完でした。
C問題までは割と順調に解けたのですが、
D問題では、考察不足のまま実装して$${O(N^2)}$$のコードを提出し、
TLEで終わってしまいました。
きちんと振り返って次に生かせればと思います。
A問題 - Who Ate the Cake?
問題
A - Who Ate the Cake? (atcoder.jp)
答案①（AC）
犯人が確定するのは、りんごさんとすぬけくんが別の人を犯人でないと証言したときです。つまり、白確定が2人でない場合かつその場合に限り、犯人は誰であるか特定することができます。
犯人が特定できる場合は、白確定が誰かによって場合分けすればよいです。（約4分）
#input
#りんごさん、すぬけくんの証言をNon-Criminalの集合NCに格納する。
NC =set(list(map(int,input().split())))
#process & output
#場合分けで処理
#犯人が確定しない場合
if len(NC) != 2:
print(-1)
#犯人が確定する場合
else:
if 1 in NC:
if 2 in NC:
print(3)
else:
print(2)
else:
print(1)B問題 - Piano 2
答案（AC）
素直に左から全探索する実装で十分間に合います。（約6分）
#input
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#process
C = sorted(A+B)
#連続するAの要素数をcntとする。
cnt = 0
ans = "No"
#左からCを探索。
for i in C:
if i in A:
cnt += 1
if cnt == 2:
ans = "Yes"
break
else:
cnt = 0
#output
print(ans)C問題 - Bingo 2
答案①（AC）
主な制約は$${2\leq N \leq 2\times 10^3, 2\leq T \leq 2\times 10^5}$$であるため、$${O(T \log T + N^2)}$$程度の処理は制限時間内で実行可能です。
解答の方針は、ビンゴのマスに読み上げられたターン数を書き込むことで、
ビンゴ判定対象の線上の$${\min}$$を取ることでビンゴ判定し、$${\max}$$を取ることで最小ターンを求めることができます。
ビンゴ判定対象は$${2N+2}$$個で、$${\min}$$および$${\max}$$をとる操作は$${O(N)}$$ですので、全体では$${O(N^2+T)}$$で充分高速に動作します。
※この方法は公式解説②で解説されています。（約39分）
個人的な学びは、$${N\times N}$$のリストを初期化する際に、
[[0]*N]*Nのように書くことができないことです。
この記述では、[0]*Nへの参照情報で初期化されたリストをN個複製して格納してしまいますので、一つの行を操作すると同じ操作がすべての行に反映されてしまいます。
これを避けるには、例えばリスト内法表記によって以下のように実装すればよいです。
#input
N,T = map(int,input().split())
A = list(map(int,input().split()))
#process
#配列Turnsにビンゴで読み上げられたターン数を格納（読まれていないものは-1）
#次の行はTurns=[[-1]*N]*Nとは書けないので注意。（同じ配列への参照をN個格納してしまう。）
Turns = [[-1] * N for i in range(N)]
for k in range(len(A)):
a = A[k]
i = (a-1)//N
j = (a-1)%N
Turns[i][j] = k+1
ans = []
#行のビンゴターンを取り出す
for i in range(N):
if min(Turns[i]) != -1:
ans.append(max(Turns[i]))
#列のビンゴターンを取り出す
for j in range(N):
column = [row[j] for row in Turns]
if min(column) != -1:
ans.append(max(column))
#対角線のビンゴターンを取り出す。
diag1 = [Turns[i][N-1-i] for i in range(N)]
if min(diag1) != -1:
ans.append(max(diag1))
diag2 = [Turns[i][i] for i in range(N)]
if min(diag2) != -1:
ans.append(max(diag2))
#output
if len(ans) == 0:
print(-1)
else:
print(min(ans))D問題 - Intersecting Intervals
問題
D - Intersecting Intervals (atcoder.jp)
答案①（TLE）
以下は、リストtempに区間の終端を格納することで、左から共通部分の数を数え上げる実装です。この実装では、$${N}$$回のforループ内でtempを更新するために計算量が$${O(N)}$$のスライス操作を毎回実行するため、forループ部分全体では$${O(N^2)}$$の計算量を要してしまいTLEとなります。
#input
N = int(input())
intervals = []
for _ in range(N):
l, r = map(int, input().split())
intervals.append((l, r))
#process
intervals.sort(key=lambda x: (x[0], x[1]))
K = [x[0] for x in intervals]
temp = []
idx = 0
ans = 0
for k in K:
# kを含まない区間の終端をtempから取り除く。
temp = [i for i in temp if i >= k]
# kを含む区間の終端をtempに加え、自身を除いたkを含む区間との交わりの数をansに加える。
while idx < N and intervals[idx][0] == k:
temp.append(intervals[idx][1])
idx += 1
ans += len(temp) -1
print(ans) 答案②（AC ※コンテスト後）
もう少し考察をして、答案①の太線部分の計算量を減らせないか検討します。
答案①のアルゴリズムでは、区間の終端を一時的に保持するリストtempによって値$${k}$$を含む区間の個数を管理して数え上げをしています。このtempを観察すると、tempから除かれていくデータは、$${r_i}$$で昇順であることがわかります。
よって、$${k}$$を含む区間がいくつあるかを数え上げる際に、$${I_i}$$の終端をtempに格納する代わりに$${r_i}$$を昇順に並べ変えて順番に格納しても、交わりのある区間の組の個数を正しく数え上げることができます。（※ただし、この置き換えによってリストtempが持っていた「$${k}$$を含む区間の個数」の情報は保たれますが、「どの区間$${I_i}$$が$${k}$$を含むか」の情報は失われてしまいます。）
この置き換えによりtempには$${r_i}$$のデータが昇順に加えられるので、答案①で実行速度が遅くなる原因となっていた「$${k}$$以上の条件でスライスを行う」操作は、「加えられた順に（FIFOで）$${k}$$未満のデータをすべて取り出す」操作に置き換えられます。置き換えた後の操作はプログラム全体で$${N}$$回しか行われないため、$${O(1)}$$で実行できるdequeのpopleft()を用いることでforループ部分を$${O(N)}$$に高速化することができます。
以下、上記の内容で答案①を修正して実装したものが以下になります。
#import
#dequeをインポートする
from collections import deque
#input
N = int(input())
L = []
R = []
for _ in range(N):
l, r = map(int, input().split())
L.append(l)
R.append(r)
#process
#L,Rをともにソートする。
#※元の区間の組とは異なるモノに代わる場合があるが、この操作は交わりのある区間の組の個数を保つ。
L.sort()
R.sort(reverse=True) #listは末尾から順に取り出すほうが速いので、降順に並べて末尾から使う。
temp = deque()
idx = 0
ans = 0
#区間の交わりのある組の個数を数え上げる。
for k in L:
while temp and temp[0] < k:
temp.popleft() # k未満の要素をすべてpopleftする。
while idx < N and L[idx] == k:
temp.append(R.pop()) # Rから昇順に取り出してtempに格納する。
idx += 1
ans += len(temp) -1
#output
print(ans) 余談ですが、このコードはCPythonで実行するよりもPyPyの方が2倍以上速いです。CPythonにこだわっているわけではないので次からはPyPyで提出しようかなと思います。