AtCoderをPythonで取り組んだ振り返り(ABC426 A~B,C追加)

どうもこんにちは！

今週のコンテストはBまで完答、振り返りもBまで。
Cを解く時間が1時間半あったのに解けませんでした。。くやしい。
解説見たらめちゃ素直にfor文の2重ループで作ってますね。。
考えなしにfor文の2重ループは計算量間に合わないと思い込んでました。計算量を見積もれるようにならねば。

問題と公式の解説のリンク

問題は以下のリンクから。

A - OS Versions -

問題

文字列X,Yが与えられます。与えられる文字列は "Ocelot", "Serval", "Lynx" のいずれかで、左ほど古いとします。
このとき、XがYより新しいかを回答する問題。

考え方とコード

文字列のリストを用意して、与えられた文字列のインデックスの大小で判定しました。

x,y = map(str,input().split())
os = ['Ocelot','Serval','Lynx']
print("Yes" if os.index(x) >= os.index(y) else "No")

B - The Odd One Out -

問題

3文字以上の文字列が与えられ、これは2種類の文字で構成されています。その文字のうち、文字列の中に1文字しかない文字を出力する問題。

考え方とコード

文字列を集合にして、文字列から数を数えて1の方を出力するとしました。

s = input()
sc = set(s)
for i in sc:
    if s.count(i) == 1:
        print(i)

C - Upgrade Required -

問題

OSのバージョンが1からNまでのPCが各1台あります。バージョンX以前のOSをバージョンYに更新しろという指示がくるたびに、バージョンアップするPCの台数を出力するという問題。
パソコン台数の最大は$10^6$、1つのテストケースでの指示の最大回数は$2×10^5$です。

考え方とコード

最初はバージョンごとの数で累積和を作って更新しつつ答えるようにしたんですがTLE。2重ループの計算量がやはりと思って2重ループの解消に四苦八苦していました。
解説を見たところ、素直に各バージョンの数を保持して、指示のたびに各バージョンの数を更新しても間に合うようでした。ということで作成したコードが以下でACとなりました。2重ループで問題ありませんでした。くやしい。

n,m = map(int,input().split())
osnum = [1 for _ in range(n+1)]
oldest = 1
for _ in range(m):
    x,y = map(int,input().split())
    if x < oldest:
        print(0)
        continue

    ans = 0
    for i in range(oldest,x+1):
        ans += osnum[i]
        osnum[y] += osnum[i]
    
    oldest = x+1
    print(ans)

ではでは。