ARC045 B - ドキドキデート大作戦高橋君

いもす法の問題を初めて解いたのでメモ。

問題

B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder

1からNまでの整数列(教室の番号を表す)に対し、M個の閉区間[s,t]が与えられる。

このとき、2つ以上の閉区間に含まれる区間をすべて出力せよ、という問題。

解法

まず各教室がいくつの区間に被覆されているかをカウントするとよい。これにはいもす法を用いる。

いもす法の手順は以下の通り。

配列S[N+2]を0で初期化しておく。*1

各区間[s, t]に対し、S[s]++; S[t+1]--; とする

Sの累積和をとる

こうして得られたS[i]がiの被覆数となる。(1 <= i <= N)

この問題ではさらに被覆数1の要素にのみ注目し再度累積和をとることで、各区間が答えに適するかどうかの判定をO(1)で実現している。

N, M = map(int, input().split())
S = [0 for _ in range(N+2)]
sec = []
for _ in range(M):
    s, t = map(int, input().split())
    sec.append([s, t])
    S[s] += 1; S[t+1] -= 1
for i in range(1, N+1):
    S[i] += S[i-1]

X = [0 for _ in range(N+1)]
for i in range(1, N+1):
    if S[i] == 1:
        X[i] = 1
for i in range(1, N+1):
    X[i] += X[i-1]

ok = []
for j in range(M):
    s, t = sec[j]
    if X[t] - X[s-1] == 0:
        ok.append(j+1)
        
print(len(ok))
for ans in ok:
    print(ans)