up<k を up<=k にした。頂点１に向かって K 階層遡っても、それって１手前にいた頂点だから無駄じゃね？ と思って、移動先を K 階層下、１階層上のち K-1 階層下、２階層上のち K-2 階層下、……、K-1 階層上のち１階層下に限定していたのだけど、まっすぐ K 階層上も移動先に加えるべきだったということ。なぜか。折れ曲がるように移動して到達した頂点からまっすぐ K 階層上というのは、初めて訪れる場合がある。K 階層まっすぐ下るだけが移動じゃないのだから「１手前にいた頂点だから無駄じゃね？」は勘違い。■Crystal で通している人の提出 #67550795 を見ましたが、えー、全然違うー。Ruby で同じことをして通りますか？ だったらだいぶ短く簡潔に解けるということだけど。■■■寝て起きたらフレンズさんのツイート(１、２)や他のブログで読んだことが頭に入ってきた気がする。たぶんだけど BFS をするのかな。頂点ごとに訪問済みフラグを持つわけだけど、追加で K 状態を区別する。これは K 歩の何歩目で訪れたのかを表す。さらに追加で直前の頂点も持つ。直前の頂点へは次の移動ができないのでこれも状態として区別する必要がある。そうすると状態数が NNK になってよろしくないのだけど、直前の頂点が２種類あるとその後の遷移はすべて網羅できているので、３番目以降の直前の頂点フラグはすでに立っているものとして良い。ということが書いてあって、同じことを(もしくは不正確なこと不十分なことを)繰り返しているだけだと思うんだけど、昨日説明を読んだときは何を言っているのかちんぷんかんぷんだったんだよね。何度文字列をなぞっても頭に入って来なかった。脳みその可塑性応答性が低い！■提出 #67610103 (WA×34/AC×19 / 665 ms)。2NK 状態の BFS を書いてみたけど WA だった。サンプルは通るんだけど何が足りないんだろう。■提出 #67610224 (TLE×2)。バグの原因はちょうど K ステップの移動の次の一歩は直前の頂点がどこかに関係なく移動できるということを考え忘れていたこと。これを直して十分に遷移ができるようになったら WA がなくなって TLE が２つ出た。3.3 秒 以下の 3098 ms と 3225 ms だからあとちょっとなんだよなあ。■提出 #67610541 (AC / 2809 ms)。変なことしないで３要素の配列をキューに入れたら良かった。自分で書いたから Crystal の人のスクリプトも読めるようになったけど、N+N の状態数で K ステップを１単位とする BFS をやっているだけに見える。本当に？ それだと K ステップの中間ステップが重複する無駄が生じない？ (K 歩ごとに直前の頂点フラグがリセットされているようだから)