はじめに

時間におわれて、切羽詰まった状態で回答している、AtCoder初心者です。
ABC305のD問題が、時間内に解けませんでした。

人のプログラムを見たときに、その人の頭の中がどれくらい整理されているかわかる。と常々おもっていました。
私の書いたABC305のDが、それを証明するかのような、混沌としたもので、WAを解消をあきらめるレベルでした。
頭の中を整理して、書き直してみたら、すんなりACとり頭の中を整理する事の大切さを再確認しました。

頭の中が整理できてないバージョン

こんな、イメージの処理方法をプログラムにしてみました。

def solve(N,A,Q,lr):
    ss = []
    s = 0
    for i in range((N-1)//2):
        s = s + A[i*2+2] - A[i*2+1]
        ss.append(s)

    for [l,r] in lr:
        x = bisect(A,l)
        if x % 2 == 0:
            # 睡眠中
            offset = A[x] -l
            s = x //2
        else:
            offset = 0
            s = x //2
        y = bisect(A,r)
        if y % 2 == 0:
            # 睡眠中
            offset += r - A[y-1]
            e = (y-1) //2
        else:
            e = y //2
        ans = offset
        if s == 0:
            ans += ss[e-1]
        else:
            ans += ss[e-1] - ss[s-1]
            
        print(ans)

図に書いたような方法でもできると思いますが、次のような疑問点があります。

疑問点

s,eの値の算出が、例題のテストケースではOKだが完全かわからない。
r,lの値が、A[i]の値と一致した場合の扱いが正しいかわからない。
条件によって、e = (y-1) //2 とe = y //2の場合分けがあるけどこれ何？
bisectかbisect_leftどっちにするのか正しいかわかってない。

改良版

改良点

時刻0から時刻tまでの睡眠時間を求めるf(t)を作り、f(r)-f(l)を求める方法にする
bの導入（b[i]は、iまでの睡眠時間の合計値）
Aからbを算出する処理は明確。
b[i]は、A[i]同じ長さNの配列。
b[i]は、bisect()で調べた値をそのまま使える（2で割るとか境界をきにしなくてよい）
r=l=0の場合の扱いを注意する

図にするとこんな感じ

def solve(N,A,Q,lr):

    def f(t):
        x = bisect_left(A,t)
        if x == 0:
            return 0
        if x % 2 == 0:
            # 睡眠中
            return b[x-1] + t - A[x-1]
        else:
            return b[x]
    
    b = [0] * N
    for i in range(1,N):
        if i % 2 == 1:
            b[i] = b[i-1]
        else:
            b[i] = b[i-1] +(A[i]-A[i-1])

    for [l,r] in lr:
        print(f(r)-f(l))

まとめ

算出方法を思いついてもすぐにコーディングしない。実装しやすい工夫をする。
if文が多かったり、不明な+1や-1が各所にでてくる場合は、方針を考え直す。
bisect_leftとbisect_rightの違いは理解しておくこと。

【abc305 D】1時間かけてもWAが解消できないレベルの酷いプログラムを捨てて、書き直したら５分でACした話

はじめに

頭の中が整理できてないバージョン

改良版

まとめ