AtCoderをPythonで取り組んだ振り返り(ABC411 A~C,Dも途中まで)

どうもこんにちは！

今週のコンテストはCまで完答。Dは計算量とメモリ使用量を落としきれませんでした。メモリオーバーは初遭遇。

# 問題

問題は以下のリンクから。Dは作ったところまでを振り返ります。

https://atcoder.jp/contests/abc411/tasks

https://atcoder.jp/contests/abc411/editorial

## A - Required Length -
与えられた文字列の長さが指定の文字数以上かどうかを判定する問題。
シンプルに受け取った文字列の長さでif文で判定しました。
~~~Python
p = input()
l = int(input())
print('Yes' if len(p) >= l else 'No')
~~~

## B - Distance Table -
与えられた一直線に並ぶ駅の個数と隣り合う駅間の距離から、各駅ごとの距離を出力するという問題。例えば3駅あるとすると駅1と駅2、駅2と駅3の距離が与えられます。これをもとに駅1と駅2、駅1と駅3、駅2と駅3の距離をそれぞれ計算して出力することになります。
駅の個数としては最大50個程度なので、2重ループで基準の駅を固定して距離を足し合わせれば解けました。
~~~Python
n = int(input())
d = [int(x) for x in input().split()]

for i in range(n-1):
    dist = []
    sum = 0
    for j in range(i,n-1):
        sum += d[j]
        dist.append(sum)
    print(*dist)
~~~

## C - Black Intervals -
最初白色のマスがN個並んでいてQ個のクエリが与えられます。1つのクエリでマスが指定されて、そのマスの色が反転します。(白なら黒に、黒なら白に変化)
このクエリを1個処理するごとに、黒色の塊の個数を出力するという問題。例えば、最初のクエリを処理すると黒マスが1個になるので1を出力します。次に黒いマスの隣が黒色になるなら1のまま、離れたマスが黒色になったら合計で2として出力となります。
マスの個数やクエリの数は最大$5×10^5$です。また、マスが1個というケースもあります。

マスの色を管理するリストを作るとして、クエリを1個処理するごとにリストを走査して個数を数えるのは多分TLEだろうなということで、どういう場合に個数が変化するかを考えました。これを整理すると以下の場合があります。
* マスの総数が1個
    1. マスが白に変化→塊は0
    1. マスが黒に変化→塊は1
* 隣接するマスが1個で、かつ隣のマスが白色の場合(両端のマス)
    1. 指定のマスが白に変化→塊の数が-1 (飛び石が無くなる)
    1. 指定のマスが黒に変化→塊の数が+1 (飛び石ができる)
* 隣接するマスが2個で、かつ両隣のマスがどちらも白色の場合
    1. 指定のマスが白に変化→塊の数が-1
    1. 指定のマスが黒に変化→塊の数が+1
* 隣接するマスが2個で、かつ両隣のマスがどちらも黒色の場合
    1. 指定のマスが白に変化→塊の数が+1
    1. 指定のマスが黒に変化→塊の数が-1

※ これ以外の条件では増減なし。(黒色の塊の長さが変わるだけのため)

これならfor文1つで実装でき、ACとなりました。
~~~Python:ACだけどコードの整理はもう少しできそう
n,q = map(int,input().split())
a = [int(x) for x in input().split()]

count = 0
color = ['w' for _ in range(n)]
for i in a:
    color[i-1] = 'b' if color[i-1] == 'w' else 'w'
    if i-1 == 0 and (n == 1 or color[i] == 'w'):
        if color[i-1] == 'b':
            count += 1
        else:
            count -= 1
    elif i-1 == n-1 and color[i-2] == 'w':
        if color[i-1] == 'b':
            count += 1
        else:
            count -= 1
    elif 0 < i-1 < n-1 and color[i-2] == 'w' and color[i] == 'w':
        if color[i-1] == 'b':
            count += 1
        else:
            count -= 1
    elif 0 < i-1 < n-1 and color[i-2] == 'b' and color[i] == 'b':
        if color[i-1] == 'b':
            count -= 1
        else:
            count += 1

    print(count)
~~~

## D - Conflict 2 -
1台のサーバとN台のPCがあり、それぞれが文字列を1つ持つとします。(最初は空)
与えられたQ個のクエリを処理したあとのサーバの文字列を出力するという問題。クエリで実行する処理は以下です。
 * 指定されたPCの文字列を削除し、サーバの文字列に差し替える
 * 指定されたPCの文字列の末尾に与えられた文字列を追加する
 * サーバの文字列を削除し、指定されたPCの文字列に差し替える

PCの数とクエリの数の最大は$2×10^5$です。
1クエリごとに処理するとして以下のように実装しましたが、TLEとMLEになりました。MLEはメモリの制限オーバーですね、初めて見ました。
最初はPCの文字列をリストで保管しようとしたんですが文字列が無いPCの分もメモリを確保するので、辞書にするなどしたんですが解消されませんでした。加えてfor文1つでもTLEになっているので、小手先の工夫でどうにかできる問題ではなかったようです。
なお、解説によると、クエリを反対から処理すればよかったようです。
~~~Python:WAにはならなかったけどTLEとかMLEになる
n,q = map(int,input().split())
word_s = None
word_pc = {}

for _ in range(q):
    query = [x for x in input().split()]
    work = int(query[0])
    num = int(query[1])

    if work == 1:
        if word_s != None:
            word_pc[num] = word_s
        elif word_s == None and num in word_pc:
            word_pc.pop(num)
    elif work == 2:
        word_pc[num] = word_pc[num] + query[2] if num in word_pc else query[2] 
    elif work == 3:
        word_s = word_pc[num] if num in word_pc else None

if word_s != None:
    print(word_s)
~~~

ではでは。