Pythonで競プロに挑む日誌 vol.23 ~計算量つづき~

現在の目標

• 2018年内に茶色になる←イマココ
• ABC の A, B 問題を全部解く
• 2018年度内に緑色を取得する
• ABC の C 問題を全部解く
• (水色になったら, APG4b で C++ にも手を出す)

今日のおはなし

結論

標準入力の受け取り方ひとつで, 計算量を減らすことができる.

解いた問題

B - Trained?

標準入力の受け取り方で実行時間に大きな差が出た

naswer1.py

# coding: utf-8
import sys

N = int(input())
lst = [int(input()) for _ in range(N)]

btn = 1
cnt = 0
for a in lst:
    btn = lst[btn-1]
    cnt += 1
    if btn == 2:
        print(cnt)
        sys.exit()
print(-1)

# 実行時間：195ms
# メモリ　：7084 KB

naswer2.py

# coding: utf-8
import sys

N = int(input())
lst = [int(i) for i in sys.stdin]

btn = 1
cnt = 0
for a in lst:
    btn = lst[btn-1]
    cnt += 1
    if btn == 2:
        print(cnt)
        sys.exit()
print(-1)

# 実行時間：68ms
# メモリ　：7084 KB

一回ずつ標準入力から値を取ってちびちびメモリを確保するよりは, 一気にメモリを確保したほうが早いということなのでしょうか.

むすび

制約が大きい時, sys.stdin は役立ちそう.