制約を見ると明らかに座標圧縮なので、座標圧縮して dijkstra 等のアルゴリズムで最短経路を求めると解ける。出題された当時は地力 (実装力) が足りず解けなかったが、今見ると、特に難しいところのない素直な問題に見える。 #define N 150 ll d[N][N]; vect…

実験すると、K=1 のときは、フィボナッチ数列になる。 K>1 のときは、2^K +1 項間漸化式になりそうなので、最初の 2^K +1 項あたりまでを愚直に計算すると、行列を復元することができる。というのを実装したら通った。直感的には正しいことが分かるが、ちゃ…