AtCoderをPythonで取り組んだ振り返り(ABC403 A,B)

どうもこんにちは！

今週もAtCoderのコンテストに参加しましたので記録します。
今回はBまで完答。Cは計算量を最後まで落としきれず。残念。

問題

問題は以下のリンクから。完答できたA,Bと途中までやったCを振り返ります。

A - Odd Position Sum -

与えられた長さNの正整数列から、奇数個目の要素の総和を出力する問題。
素直に、数列を配列に入れて奇数個目の値だけを変数に足しあわせていくとしました。なお与えられた数列は最初を1個目と指定されています。

n = int(input())
s = [int(x) for x in input().split()]

ans = 0
for i in range(len(s)):
    if (i+1) % 2 == 1:
        ans += s[i]

print(ans)    

B - Four Hidden -

英小文字と?で構成する文字列Tと英小文字からなる文字列Uが与えられ、Tの中にUが含まれるケースがあるかを判定するという問題。なお、?は任意の1文字に置き換えることができます。(いわゆるワイルドカードですね)
解くにあたって、Tの文字列の起点を１文字ずつずらしながら１文字ずつ一致するかをチェックするとしました。例えばTの5文字目とUの1文字目が一致すれば、次はTの6文字目とUの2文字目が一致するかを判定していくという感じです。Tの文字が?のときも一致する扱いです。
このときに、Tの文字列より長い位置を判定しないようにする必要があります(これを忘れて2ミス)

s = input()
u = input()
ans = "No"

i,j,k = 0,0,0
for i in range(len(s)):
    for j in range(i,i+len(u)):
        if j < len(s) and (s[j] == u[k] or s[j] == '?'):
            k += 1
            if k == len(u):
                ans = "Yes"
                break
        else:
            k = 0
            break
    if ans == "Yes":
        break
    
print(ans)

C - 403 Forbidden -

N人のユーザーとM個のページがあるとして、Q個のクエリを処理した結果を出力する問題。クエリは以下の3種類。
1. ユーザXにページYの閲覧権限を与える
2. ユーザXにすべてのページの閲覧権限を与える
3. ユーザXがページYの閲覧権限があるかを出力する

ユーザもページもクエリも最大数は$2 × 10^5$個です。計算量を考えないといけないC問題の定番ですね。
解くにあたって、まずユーザーごとの閲覧権限を保存する2次元配列に保存したところ、以下の2点で計算量をオーバーするケースがありました。

• すべてのページの閲覧権限を与えるときに、ユーザXの配列に1からMの数字を格納する(for文)
• ユーザXの配列にYの数字が入っているかを判定する(y in xの配列)
  クエリを１つずつ処理するだけでもQ回ですが、for文にしてもy in 配列にしても、O(n)なので制限オーバーとなりました。
  このうち、すべてのページの閲覧権限については、すべてのページの権限があるか無いかの2値で保存するとして独立させたのでよいのですが、一部のページしか権限がない場合の判定の計算量の落とし方がわかりませんでした。集合を使えばよさそうとは思っていたのですが、実装のしかたがわからず。
  で、これを踏まえて書いたコードが以下です。
  解説を見ると、配列の中にset()を入れて集合にしていました。配列の要素に集合を使えるという知識や発想がなかったです。残念。

計算量が多くてTLE

n,m,q = map(int,input().split())
allow_part = [[] for _ in range(n)] # 解説では [set() for _ in range(n)]とされていた。
allow = {}

for _ in range(q):
    query = list(map(int,input().split()))
    x = query[1]-1
    if query[0] == 1: # XにYの閲覧権限を付与
        y = query[2]-1
        allow_part[x].append(y)
    elif query[0] == 2: # Xにすべてのページの閲覧権限を付与
        allow[x] = 1
    elif query[0] == 3: # XにYの閲覧権限の有無を出力
        y = query[2]-1
        if x in allow and allow[x] == 1:
            print("Yes")
        elif y in allow_part[x]: # ここの計算量を減らす必要がある
            print("Yes")
        else:
            print("No")

おわりに

C問題の完答には計算量の落とし方を色々知りたいところです。
ところで、いつもは1万人くらい参加していますが今日は7900人程度だったみたいですね。珍しく日曜日に開催だったからでしょうか。GWで不在の方も多いのかもしれませんね。
来週はGWまっただなかなので、不参加になるかもしれませんが、参加したら振り返りしたいと思います。

ではでは。