こんばんは、医学部5年の淡田です。

自粛につぐ自粛でどうぶつの森で魚ばっか釣ってる日々であんま話すことがなかったのでちょっと競プロの話

競プロって？

競技プログラミングの略で、問題が与えられてそれをプログラミングで解決していくコンテスト。

問題によって縛りがあって 「○○時間内に解けよ」 って制約がある。 なので愚直に解こうとすると 「あなたの書いたコードは終わるのに5秒も掛かっちゃってます！遅すぎ！」 ってなる。 よって問題によっては工夫が必要になる。

アルゴリズム

他にも単純に問題むずくて工夫しないと汗、パターンもあるので難易度が上がると手の込んだ手法・手順が必要となる。

それがアルゴリズム（ざっくりしすぎ・・・？）

今回はその中で幅優先探索というやり方を説明する。 といってもそんなに難しくないので気軽に聞いてくださいまし。

実際の問題

https://atcoder.jp/contests/abc168/tasks/abc168_d

↑問題はこれ。 詳しい説明は省きますが、ざっくり言うと

「上記のような感じで部屋と部屋とが繋がってるぞ (入力のところでどの部屋と部屋が繋がってるかが与えられる。 上のはそれを図にした) 。 それぞれの部屋から最短で①に行く方法を探せ (３→４→２→１みたいな) 。 探したら最短経路を辿るためには、例えばaの部屋は次にどこに向かえばいいかを出力しろ。 複数あったら一個でいいぞ」

って問題。 なんとなくやることはわかるけど実際にプログラミングじゃどう書くのだろうってなる。

幅優先探索について

結論からいうとこれは幅優先探索を使えば簡単に解ける。

はじめの状態→最短1回の遷移 (移動) でたどり着ける状態を探す→最短2回の遷移 (移動) でたどり着ける状態探す・・・

を上の例で行けば「①から1回で移動できるのは②、⑤→②、⑤から1回で移動できるのは④・・・という風に探索していく。

イメージ数学の問題で出てきた「点Aから点Bへの最短で行くのは何通りか？」みたいなのと似ている。

実装

実際にコードを書いてみる (初めて書いたからスマートでないところはあるかも・・・。 悪しからず)

n,m=map(int,input().split())

まずは入力される n, m をget。

今回はゴールである①の部屋にはどうすればいけるか？ というのが問題。 すると繰り返し上の例でいくと①の部屋には②と⑤が隣り合ってるから②と⑤は最短1回。 ②と⑤と隣り合っているのは④だから・・・という風に探索していくと、「どの部屋とどの部屋が隣り合っているか」が重要になる。

list_tonari=[[] for i in range(n+1)]

ここで空の [] が n 個あるリストを作る。 1個目の [] には①と隣り合った部屋の番号を、2個目には②と隣り合った部屋の番号を入れていく。

for i in range(m):
  a,b=map(int,input().split())
  list_tonari[a].append(b)
  list_tonari[b].append(a)

以上で隣り合うリスト完成。

ans=[0 for i in range(n+1)]

ここで答え用のリストを作る。 たとえば「5の部屋から最短で1に向かうには次に3の部屋いけばいいんやで」となったら ans の5番目の 0 を 3 に変える、という風にしていく。

temp=list()
temp.append(1)

今現在どこの部屋にいるかのリストをつくる。 上の例だと最初は 1、次は 2、5 みたいな。

temp2=list()

temp を随時更新するので臨時の別のリストもつくる。

while True:
  temp2=temp
  temp=[]

  while len(temp2):
    get=temp2.pop()

    for n in list_tonari[get]:
      if ans[n] ==0:
        ans[n]=get
        list_tonari[n].remove(get)
        temp.append(n)

  if len(temp)==0:
    break

まず今どの部屋にいるか temp2 にいれて temp を一旦空に。

pop() で temp2 の先頭の数字を取ってくる ( get のこと) 。 その部屋と隣り合っている部屋全てに対して以下の処理を行う。 まだその部屋に訪れていない ( ans のリストでその部屋の値が 0 ) なら、その部屋からは get に向かえば最小経路を辿るので get の部屋番号を入れる。 部屋を行ったり来たりしないので get の部屋と隣り合っている部屋の隣り合っている部屋のリストから get を削除。 そして temp を改めて更新していく。

もう行ってない部屋ないよってなったら break で処理終了。 以上でOK

まとめ

なんか言葉で説明するとグダってしまった感がある・・・。 申し訳ねぇ。

こういうのって習うより慣れろなんでしょうかね？

ただ一回自力で書けば2回目以降はそんな苦労しないんじゃないでしょうか？

同じアルゴリズムで解ける問題と、本記事は蟻本と呼ばれる本を参考にしました。 ただC++で書かれているので、pythonで説明してくれてるサイトも載っけときます。 よければどうぞ。

という訳でもっと競プロ、勉強します。

(編集注記)

発展的な話となりますが、今回の本文コードで使われている

list_tonari[n].remove(get)

の部分は実は少しだけ危険で、時間切れの恐れがあります。

リストからの要素削除は、リストの長さに比例した時間がかかります。 よって意地悪な入力では、トータルでほぼ頂点数の2乗に比例する時間がかかる可能性があります。 AtCoderのテストデータでは実際に本文のコードで正解と判定されるのですが、時間切れになる (正解に数時間程度かかる) 入力は問題制約の範囲で作れると思います。

ではどうすればいいか。 最初に list_tonari を作る部分を、

list_tonari=[set() for i in range(n+1)]

と、リスト [] でなく集合 set() を使うように変更します。 これに伴い、その下の append() は add() に変更します。
それだけです。 (remove() の行自体はそのままでOKです。)

同じ remove() でも、集合では要素数の対数に比例した時間しかかかりません。 したがって全体の計算量が頂点数の2乗で爆発する可能性もなく、どんな入力でも確実に時間内で正解することができます。

また set() に変更するかわりに、上記の remove() の行だけを削除してもいいです。 削除しなかったものはいずれ呼ばれますが、ans[] に値が入っているので if でスキップされます。 これは事前に削除しておくより高速です。 逆に remove() がある場合、if 判定は実はなくても構いません。

(注記担当：小川)