ABC370 B問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが開催している、競技プログラミングコンテストのことです。

今回はABC370のB問題を解説していきます。

ABC370　B – Binary Alchemy

問題

問題

N種類の元素 1, 2, …, N があります。

元素iと元素jを合成すると、\(i \geqq j\) のときは元素 \(A_{i,j} \) に、\(i < j\) のときは元素 \(A_{j,i} \) に変化します。

元素1に対し、元素 1, 2, …, N をこの順に合成したとき、最終的に得られる元素を求める問題です。

制約

• \(1 \leqq N \leqq 100\)
• \(1 \leqq A_{i,j} \leqq N\)

思考の筋道

元素を順番に合成していく処理を素直に書くことで解ける問題です。

合成する際の左の元素をl、右の元素をrと呼ぶことにします。lとrの値はどのように推移するかを考えましょう。

出力例1を見るとわかりやすいです。

元素rは 1, 2, 3, 4 と値が変わっていきます。一方、元素lは初期値を1とし、それ以降は、前回の合成結果の値となります。

あとは合成についてですが、 \(i \geqq j\) のときと \(i < j\) のときで得られる結果が異なりますので、分岐処理を使うか、または下のコードのようにmax、minを使いましょう。

lとrの値を推移させていき、最終的に得られるlの値が答えとなります。

コード

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

l = 1
for r in range(1, N + 1):
    l = A[max(l - 1, r - 1)][min(l - 1, r - 1)]

print(l)

リンク