K = 0 のときは、 dijkstra で解ける。 頂点を *1 と拡張すると、K>0 の場合も dijkstra を多少書き換えるだけで解くことができる。 辺の長さが少し特殊なので、k=0..K として順番に dijkstra を行うことで効率よく最短路が求まる。 計算量は、O(K(N+M)logN)…

2次元グリッド上にきつねがN匹いる (N すべてのきつねが辺で連結になるように動かすとき、最小で何ステップでできるか？(きつねは重なることは出来ない)まず、1次元の場合には、中央値に寄せるのが一番効率がよい。 (N が偶数のときは、真ん中の2つの値の平…

グラフ G が与えられる。G が深さ9以下の完全二分木に3本の余計な辺を追加したグラフであるかを判定する問題である。色々な解法が考えられるが、根の候補を小さくしてから、それが正しいか判定するという方針で解いた。 根の候補を小さくする部分は、 全点間…