ABC207 C - Many Segments から学んだ

7587 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク




余裕じゃね？
いや、余裕で WA。

恥ずかしい勘違い

区間を未満 とした場合、値そのものを削った。

yarakashita.py
for _ in range(N):
    t,l,r = map(int,input().split())
    if t == 1:
        lis.append([l,r])
    elif t == 2:
        lis.append([l,r-1])
    elif t == 3:
        lis.append([l+1,r])
    else:
        lis.append([l+1,r-1])

だがしかし、問題文には以下の記載がある。
i 以上 j 以下の実数からなる区間で共通部分を持つようなものは幾つありますか？
ふーむ。
実数って何！？

なるほど、とりあえず小数も存在する領域か。
じゃあ、-1 したらダメですね、0.1 くらいかな。

ManySegments_r0.py
N = int(input())
lis = []
for _ in range(N):
    t,l,r = map(int,input().split())
    if t == 1:
        lis.append([l,r])
    elif t == 2:
        lis.append([l,r-0.1])
    elif t == 3:
        lis.append([l+0.1,r])
    else:
        lis.append([l+0.1,r-0.1])
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if lis[i][1] < lis[j][0] or lis[j][1] < lis[i][0]:
            continue
        else:
            ans += 1
print(ans)

問題文に素直に 2<= N <= 2000 と計算量が少なめの
問題は、尚の事、油断禁物のようだ。