AtCoder Beginner Contest (ABC) 183 PythonでC問題解いてみた
前回解いたやつ
こんにちは。めりーです。
今日、「シル・ヴ・プレジデント」を歌っていることで有名な方のYoutubeを見たのですが、歌ってみただけではなく、ショートコント的な動画が大量にあってビビりました。
歌ってみたくらいしか動画あげてないんじゃないかなーって思ってたので、超びっくり。
こりゃ、チャンネル登録者数200万人超えてるのすげえわ・・・。って思いました。
というわけで本日もAtCoder Beginner Contest (abc) 183 C問題解いていきます。
言語はPython、提出はPyPyです。
目次
C問題 解けない（泣）編
Travel
問題文
解けませんでした。
問題はこう。
N個の都市があります。
都市1スタートで、全ての都市を巡るルートのうち、移動の合計時間がちょうどKになるルートはいくつあるでしょうか、という問題。
じゃあ、とりあえず問題文の通りに実装してみよっか！！！と思い、実装を試みた。
そして詰まったのだ。
原因はこの一言に尽きる。
どうやって、巡るルートを全探索するの？？？？
そう、これがわからなかったのだ。
for文でN重ループを回すの？
N重ループってどうやって回すん？？？？
実装しようとしたところでこのように詰まってしまうのであった。
あ、これ、実装する時の根本的な知識がないから無理な奴だ。
そう思い、解答解説を見る決心をするのであった・・・。
いや、ほんとに解き方が思いつかないのは解答見ようね。
数学の問題集で学んだわ。
C問題 解答解説理解編
というわけで解答解説を見ることに。
解答解説(公式)
Editorial - AtCoder Beginner Contest 183
ほうほう。Pythonでは、順列全列挙のライブラリがあるのか。ふむふむ。
というわけでPython公式の説明を見ることに。
itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.10.0b2 ドキュメント
この問題文の場合、permutations(range(2,N+1))を出力すると、2からNまでの都市の行き方を全列挙してくれるのである。
参考までに。N = 4の時(入力例１)、 出力されるのは、 [(2,3,4),(2,4,3),(3,2,4),(3,4,2),(4,2,3),(4,3,2)] 入力例1の全パターンの列挙ができたね！！！
というわけで方針を
1. 全探索で、ルートを全探索する。
2. 各ルートで、移動時間の計算をする。
3. 移動時間がKとなった場合を数える。
4. 3を出力。
というわけでコードを
import itertools
n,k = map(int,input().split())
t = []
for _ in range(n):
T = list(map(int,input().split()))
t.append(T)
ans = 0
for toshi in itertools.permutations(range(1,n)):
time = 0
start = 0
for i in range(n-1):
now = toshi[i]
time += t[start][now]
start = now
time += t[now][0]
if time == k:
ans += 1
print(ans)
コードの解説していきます。
import itertoolsは、permutationsに必要なので。
for _ in range(n):単純にN回くり返すだけのループなので、Pythonではわざわざカウンター用の変数を定義する必要がないので、 _ を使ってます。
for toshi in itertools.permutations(range(1,n)):
time = 0
start = 0
for i in range(n-1):
now = toshi[i]
time += t[start][now]
start = now
time += t[now][0]
if time == k:
ans += 1
この問題の根幹
範囲が1からnになっているのは、問題文の都市(1始まり)を配列のインデックス(0始まり)に合わせたから。
つまり、このコードの中では、都市1が0、都市nがn-1として扱われている。
その方が配列を参照しやすいので・・・。
time、startはそれぞれ移動時間の合計、スタートの都市を表している。
toshiのループが更新される（新しいルートについて調べる）時に初期化します。
初期のスタートが０なのは、問題文に、都市1からスタートするルートって指定されているから。
for i in range(n-1):のループでは、そのルートの合計時間を計算している。
入力例1を参考にすると、
toshiは(1,2,3).(1,3,2) ・・・というようにループを重ねるごとに変化していく。
toshiが(1,2,3)の時の合計移動時間の計算は、
[(0→1の時間) + (1→2の時間) + (2→3の時間)] + (3→0の時間)で表される。
ループで計算しているのは、太文字の部分。
各「→」の左側をstart、右側をnowに更新していき、「start → now」の時間をどんどん足していく。
そして、最後に都市1に戻るので、最後にいた都市(now)から0までの移動時間を最後に足す。
そして、その合計時間がKである場合、ansに1足して、次のルート(1,3,2)について同じことを行っていくのである。
そして、最後にansを出力して終了である。
今回の問題を通して、自分に足りないものがわかった。
問題を解いてる最中にわからない部分を調べる力である。
自分が何がわからないのかを明確にし、その部分をググるのが自分に足りないことだとおもいました。
では。
