アルゴリズムと数学 062

https://atcoder.jp/contests/math-and-algorithm/tasks/abc167_d

全く予期していなかったのですが、この問題の解法は問題59と完全に同じです。この問題も、ある状態から一意に次の状態に進むことができますが、後ろに一意に戻れるかわかりません。
このため、前に進むことができるProceedableというTraitを定義して、これを実装していれば問題が解ける関数を作りました。問題59はu64がこのTraitを次のように実装するだけです。

impl Proceedable for u64 {
    fn proceed(&self) -> Self {
        self * 2 % 10
    }
}

// Teleporter
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Proceedable ////////////////////

trait Proceedable {
    fn proceed(&self) -> Self;
}

fn proceed_length<T: Proceedable>(e: T, n: usize) -> T {
    let mut s = e;
    for _ in 0..n {
        s = s.proceed()
    }
    s
}

fn find_period<T: Proceedable + PartialEq + Copy>(init: T) -> usize {
    let mut e1 = init;
    let mut e2 = init;
    for i in 1..  {
        e1 = proceed_length(e1, 1);
        e2 = proceed_length(e2, 2);
        if e1 == e2 {
            return i
        }
    }
    0
}

fn proceed_long<T: Proceedable + PartialEq + Copy>(init: T, n: usize) -> T {
    let period = find_period(init);
    let length = min(n, n % period + period);
    proceed_length(init, length)
}


//////////////////// State ////////////////////

type City = usize;

#[derive(Clone, Copy, PartialEq)]
struct State<'a> {
    city: usize,
    A: &'a Vec<City>
}

impl Proceedable for State<'_> {
    fn proceed(&self) -> Self {
        State { city: self.A[self.city-1], A: self.A }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<City>) {
    let v = read_vec();
    let K = v[1];
    let A: Vec<City> = read_vec();
    (K, A)
}

fn f(K: usize, A: Vec<City>) -> City {
    let init = State { city: 1, A: &A };
    let state = proceed_long(init, K);
    state.city
}

fn main() {
    let (K, A) = read_input();
    println!("{}", f(K, A))
}