🦁
【競技プログラミング】AtCoder Beginner Contest 167_D問題
問題
要約
-
高橋王国には N 個の町があり、1 から N まで番号が振られています。
-
各町にはテレポーターが1台ずつあります。
-
町 i (1 ≤ i ≤ N) のテレポーターの転送先は町 A_i です。
-
高橋王は町1から出発し、テレポーターをちょうど K 回使います。
-
K 回テレポーターを使った後、どの町に到着するかを求める必要があります。
- N: 町の数
- A_i: 町 i のテレポーターの転送先の町番号 (1 ≤ i ≤ N)
- K: テレポーターを使用する回数
既存投稿一覧ページへのリンク
アプローチ
テレポーターの使用パターンを追跡し、周期性を見つけ出す方法を用いる。
解法手順
-
入力値N（町の数）、K（テレポーター使用回数）、各町のテレポーター転送先を受け取る。
-
町1から開始し、テレポーターの使用を順次シミュレートする。
-
各町の訪問状況を記録するリストを用意する。
-
テレポーターの使用順序（訪れた町の順序）を記録するリストを作成する。
-
同じ町に2回目に到達するまでシミュレーションを続ける。
-
周期の開始地点（同じ町に2回目に到達した地点）を特定する。
-
周期の長さを計算する。
-
指定された使用回数Kと周期の情報を用いて、最終的な到着地点を計算する。
-
K回のテレポーター使用後の最終到着地点（町の番号）を出力する。
ACコード
ac.py
def io_func():
# 入力値N（町の数）とK（テレポーター使用回数）を受け取る
n, k = map(int, input().split())
# 各町のテレポーター転送先を受け取る
teleporters = list(map(int, input().split()))
return n, k, teleporters
def solve(n, k, teleporters):
# 各町の訪問状況を記録するリスト
visited_towns = [0] * n
# テレポーターの使用順序（訪れた町の順序）を記録するリスト
town_sequence = [1] # 町1から開始
current_pos = 1 # 現在の位置（町1から開始）
# 同じ町に2回目に到達するまでシミュレーション
while True:
if visited_towns[current_pos - 1] == 0:
# 未訪問の町の場合
visited_towns[current_pos - 1] = 1 # 訪問済みにマーク
current_pos = teleporters[current_pos - 1] # 次の町へ移動
town_sequence.append(current_pos) # 訪問順序に追加
else:
# 既に訪問済みの町に到達した場合
break
# 周期の開始地点を特定
cycle_start = town_sequence.index(current_pos)
# 周期の長さを計算
cycle_length = len(town_sequence) - cycle_start - 1
# 最終的な到着地点を計算
if k > cycle_start:
remaining_steps = (k - cycle_start) % cycle_length
else:
remaining_steps = k - cycle_start
# K回のテレポーター使用後の最終到着地点を計算
final_position = town_sequence[cycle_start + remaining_steps]
return final_position
if __name__=="__main__":
# メイン処理
n, k, teleporters = io_func()
result = solve(n, k, teleporters)
print(result)
###
# n: 町の数
# k: テレポーター使用回数
# teleporters: 各町のテレポーター転送先リスト
# visited_towns: 各町の訪問状況を記録するリスト
# town_sequence: テレポーターの使用順序（訪れた町の順序）を記録するリスト
# current_pos: 現在の位置（町の番号）
# cycle_start: 周期の開始地点（インデックス）
# cycle_length: 周期の長さ
# remaining_steps: 周期内での残りのステップ数
# final_position: K回のテレポーター使用後の最終到着地点
#
# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
# 2.1 各町の訪問状況と訪問順序を記録するリストを初期化
# 2.2 同じ町に2回目に到達するまでシミュレーション
# 2.3 周期の開始地点と長さを計算
# 2.4 指定された使用回数Kと周期情報を用いて最終到着地点を計算
# 3. 結果を出力する
超ざっくり概要図
n = 11
k = 23
teleporters = [6, 3, 11, 7, 4, 10, 9, 1, 8, 5, 2]
の場合、8が解答
Discussion