競プロ典型：Sign Up Requests

またもや間が空いてしまった。
一応前回の続き。

N = int(input())

list = []

for day_num in range(N):
    user = str(input())
    if not user in list:
        list.append(user)
        print(day_num + 1)

結果はTLE。うーん。
コード自体はかなりシンプルでfor文を重ねて回しているわけでもないが実行時間が長いらしい。
他の人がどのように書いているか見てみることにした。

その1

def main():
    import sys
    sys.setrecursionlimit(10 ** 9)
    input = sys.stdin.readline
 
    N = int(input())
    names = set()
    ans = []
 
    for i in range(N):
        s = input()[:-1]
        if s in names:  # 既に名前が登録済みの場合は登録しない
            continue
        else:  # 新規の名前の場合
            names.add(s)  # 申請された名前を登録
            ans.append(i+1)  # 申請日を答えの配列に格納
 
    print(*ans, sep='\n')
 
 
if __name__ == '__main__':
    main()

Submission #43069942 - 競プロ典型 90 問

その２

n= int(input())
user_list = [input() for i in range(n)]
meibo = set()
 
for i in range(n):
    if user_list[i] not in meibo:
        meibo.add(user_list[i])
        print(i+1)

その1を見る前にその２について。ほぼ自分の回答と同じだが重複しないuser名を格納するmeiboがsetによって用意されている。
従って自分のコードにもそれを適用することにした。

N = int(input())
 
list = set()
 
for day_num in range(N):
    user = str(input())
    if not user in list:
        list.add(user)
        print(day_num + 1)

これによりTLEを解消することが出来た。ただ実行時間はやや長め。その２で示したコードが219msなのに対して上の改良したコードは393ms。このことから理解したことは
・listよりsetとして用意してappendでなくaddを用いたほうが実行時間は短い
ということだ。だが理解できないこととして
・その２では内包表記含めて2回for文が回っているにもかかわらず自分で書き改良したfor一回しか回っていないコードより実行時間が短いのはなぜか
少し調べてみることとしたい。