結論

何も考えずに float("inf") で初期化するのは止めよう。

最初の考え

ABC286_E

全ての都市間の移動についての解を用意する必要があるのでワーシャルフロイドを用いればよい。
都市間の移動に用いた直行便の本数と、購入可能なお土産の価値の 2 つの情報を保持してワーシャルフロイドを実行すれば解けるはず。

この考え方は合っていましたが、pyhton で高速なプログラムを記述できず、コンテスト中に c++ で実装しなおし、時間を浪費しました。

提出コード

提出した python コードでは、 TLE でした。

提出コード

import sys

sys.setrecursionlimit(10 ** 8)


def main():
    N = int(input())
    A = list(map(int, sys.stdin.readline().strip().split()))

    S = []
    for _ in range(N):
        S.append(sys.stdin.readline().strip())

    # ワーシャルフロイド
    ans = [[[float("inf"), 0]] * N for _ in range(N)]
    for n in range(N):
        for i, s in enumerate(S[n]):
            if s == "N":
                continue
            ans[n][i] = [1, A[n] + A[i]]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                cost = ans[i][k][0] + ans[k][j][0]
                gain = ans[i][k][1] + ans[k][j][1] - A[k]

                if cost > ans[i][j][0]:
                    continue

                if cost < ans[i][j][0]:
                    ans[i][j] = [cost, gain]
                else:
                    ans[i][j][1] = max(ans[i][j][1], gain)

    Q = int(input())
    for _ in range(Q):
        U, V = map(int, sys.stdin.readline().strip().split())
        U -= 1
        V -= 1

        cost = ans[U][V][0]
        gain = ans[U][V][1]

        if cost == float("inf"):
            print("Impossible ")
        else:
            print(f"{cost} {gain}")

    return


if __name__ == "__main__":
    main()

提出コード問題点

提出コードの問題点は以下の 2 つです。

1. 価値と直行便の個数を 1 つの配列で保持していること
2. ワーシャルフロイドに用いる配列をfloat("inf") で初期化していること

問題点 1.

価値と直行便の個数を

• 3 次元配列 1 つで保持するか
• 2 次元配列 2 つで保持するか

によって微妙に実行速度が異なるようです。
複数回実行して確認したところ、実行速度は異なるものの差異は小さく、こちらの問題が TLE の主要因ではないようです。

# float("inf") 由来の低速化
from datetime import datetime

N = 300

time_start = datetime.now()
slow = [[[N, 0]] * N for _ in range(N)]
time_end = datetime.now()
print(f"初期化にかかる時間: {time_end - time_start}")

time_start = datetime.now()
for i in range(N):
    for j in range(N):
        for _ in range(N):
            val = slow[i][j][1]
            path = slow[i][j][0]
time_end = datetime.now()
print(f"値の取り出しにかかる時間: {time_end - time_start}")


time_start = datetime.now()
fast_path = [[N] * N for _ in range(N)]
fast_val = [[0] * N for _ in range(N)]
time_end = datetime.now()
print(f"初期化にかかる時間: {time_end - time_start}")

time_start = datetime.now()
for i in range(N):
    for j in range(N):
        for _ in range(N):
            val = fast_val[i][j]
            path = fast_path[i][j]
time_end = datetime.now()
print(f"値の取り出しにかかる時間: {time_end - time_start}")

"""
初期化にかかる時間: 0:00:00.001000
比較にかかる時間: 0:00:04.135120
初期化にかかる時間: 0:00:00.002001
比較にかかる時間: 0:00:03.370627
"""

問題点 2.

こちらは float("inf") で初期化したことが問題と言うよりも、 float("inf") で比較演算を行うことが問題となるようです。
以下は参考コードです、

# float("inf") 由来の低速化
from datetime import datetime

N = 300

time_start = datetime.now()
slow = [[float("inf")] * N for _ in range(N)]
time_end = datetime.now()
print(f"初期化にかかる時間: {time_end - time_start}")

time_start = datetime.now()
for i in range(N):
    for j in range(N):
        for _ in range(N):
            if slow[i][j] == float("inf"):
                continue
time_end = datetime.now()
print(f"比較にかかる時間: {time_end - time_start}")


time_start = datetime.now()
fast = [[N] * N for _ in range(N)]
time_end = datetime.now()
print(f"初期化にかかる時間: {time_end - time_start}")

time_start = datetime.now()
for i in range(N):
    for j in range(N):
        for _ in range(N):
            if fast[i][j] == N:
                continue
time_end = datetime.now()
print(f"比較にかかる時間: {time_end - time_start}")

"""
初期化にかかる時間: 0:00:00.001000
比較にかかる時間: 0:00:06.286245
初期化にかかる時間: 0:00:00.001000
比較にかかる時間: 0:00:02.020000
"""

ABC286 E の問題の条件下では、 float("inf") で比較を行った場合 3 倍程度の実行時間がかかっており、TLE することが確認できます。

正解コード

python での AC コードはこちらです。 AC コード

float("inf") を用いたために低速になったのは 2 度目です。
float("inf") 何も考えずに大きな数字を用意する際に非常に楽なので、つい使ってしまいます。
同じ轍を踏んだことを反省