67097


> 問題文
>
> 高橋キングダムには、高橋諸島という、N 個の島からなる諸島があります。 便宜上、これらの島を島 1、島 2、 ...、島 N
>
> と呼ぶことにします。
>
> これらの諸島の間では、船の定期便が M 種類運行されています。 定期便はそれぞれ 2 つの島の間を行き来しており、i  
>  種類目の定期便を使うと、 島 ai と島 bi
>
> の間を行き来する事ができます。
>
> すぬけくんは今島 1 にいて、島 N に行きたいと思っています。 しかし、島 1 から島 N への定期便は存在しないことがわかりました。  
>  なので、定期便を 2 つ使うことで、島 N
>
> に行けるか調べたいと思っています。
>
> これを代わりに調べてあげてください。

問題文の詳細はコチラ  
<https://atcoder.jp/contests/abc068/tasks/arc079_a>

基本的には正しい答えが得られるのですが、いくつかのケースでTLEが発生してしまいACすることができません。  
どの箇所が原因でTLEが発生しているのでしょうか？

## 自身の回答

[code]

    class Ship:
      def __init__(self, land_from, land_to):
        self.land_from = land_from - 1
        self.land_to = land_to - 1
    
    N, M = map(int, input().split())
    
    ships = []
    for _ in range(M):
      f, t = map(int, input().split())
      ships.append(Ship(f, t))
    
    # 到達可能島リスト
    reachable_islands = [float('inf') for _ in range(N)]
    # 初期位置は到達可能なのでTrue
    reachable_islands[0] = 0
    # 探索予定島
    search_list = [0]
    
    # 新たな島に移動できたなら次も探索する
    while len(search_list):
      now_island = search_list.pop(0)
      # 各到達可能な島ごとに移動シミュレーション
      if reachable_islands[now_island] == float('inf'):
          continue
      # 全ての船についてシミュレート
      for ship in ships:
        # 現在地の島発の船かつ目標島への移動コストが割安なら移動シミュレート実行
        if now_island == ship.land_from \
           and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
          # 到達済の印をつける
          reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
          # 到着島を探索予定リストに追加
          search_list.append(ship.land_to)
    
    # 最後の島が到達可能であるかを判定
    if reachable_islands[N - 1] == 2:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')
    
[/code]


CC BY-SA 4.0
2020-05-28T14:56:53.133
67091
2020-05-30T04:50:45.650
2020-05-29T11:59:12.970
9616
9616
question
python python3
AtCoder Beginner Contest 068 C問題でTLE発生


まず単純に `while len(search_list):` がN回ループして、`for ship in ships:`
がM回ループするならそれだけでTLEです。

`if reachable_islands[now_island] == float('inf'):`
このガード節がうまく働けば内側のループが減ると期待してるのかもしれませんが、search_listに追加される時点でreachable_islandsは更新されてるのでこのガードは働きません。

さらに言えばsearch_listをスタックとして使っているので、同じ島が何度も追加される可能性があります。

[code]

    # 新たな島に移動できたなら次も探索する
    while len(search_list):
      now_island = search_list.pop(0)
      # 各到達可能な島ごとに移動シミュレーション
      if reachable_islands[now_island] == float('inf'):
          continue
      # 全ての船についてシミュレート
      for ship in ships:
        # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
        if now_island == ship.land_from \
           and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
          # 到達済の印をつける
          reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
          # 到着島を探索予定リストに追加
          search_list.append(ship.land_to)
    
[/code]


CC BY-SA 4.0
2020-05-28T17:45:52.690
67096
2020-05-29T00:15:02.140
2020-05-29T00:15:02.140
3060
33033
67091
answer


上記の回答では ダイクストラ法を使って 到達目的の島の最短距離を求めて  
最終的に その距離が 2 であれば OK というロジックになっていると思います。

Python が詳しくないので C# で 上記コードと同じアルゴリズムを実行した結果 2つの問題で  
`TLE` が発生する事を確認しました。

何パターンかアルゴリズムの改善を試してみましたが、

[code]

    for ship in ships
    
[/code]

とする部分が 船の数が多い時に ループの回数が多くて遅くなっているようです。

島を特定して その島から 次の島を判定するために 200,000 も 定期便があった場合に  
処理速度が遅くなっているのだと思います。

最初の 読み込み時に 島から 定期便1本で行ける 次の島の情報を リストに保管しておくことで  
無駄なループが減り `TLE` にはならずに すべて 0.5 秒以内に回答できるようになりました。

また、 ちょっと気になったのですが、  
定期便は 双方向なので from -> to と 逆の to -> from の経路も考慮しておかないと  
正しい答えにはならない気がします。

ダイクストラ法で 解くのもありかもしれませんが、  
『定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。』  
というように書かれているので、

わざわざすべての経路の最短経路を求める ダイクストラ法を使うのは時間の無駄な気がします。

出発の島 -> 中間の島 → 到達の島

となる 中間の島 を探すのが目的なので

出発の島 から の定期便のある 中間の島 の集合 A

到達の島 に行くことができる 定期便のある 中間の島の集合 B

を調べて A と B を両方満たす島を見つける。

という単純な 回答が一番ふさわしい気がします。


CC BY-SA 4.0
2020-05-28T19:13:56.040
67097
2020-05-28T19:13:56.040
18851
67091
answer


アルゴリズムの改善ではありませんが、コードの改善でも、ある程度の効果が期待できます。  
あらかじめ使用予定数のリストを用意しておき、`append`を使わないコードでプロファイルをとってみました。  
私の環境では200000回のappend版との差は0.187秒でした。

変更例

[code]

    ships = [0] * M
    for i in range(M):
      f, t = map(int, input().split())
      ships[i] = Ship(f, t)
    
[/code]


CC BY-SA 4.0
2020-05-29T01:39:06.400
67108
2020-05-30T04:50:45.650
2020-05-30T04:50:45.650
35558
35558
67091
answer