SRM670 div.1 450 / div.2 1050 Treestrat
解法
- 木の隣接行列から、全点対最短距離を求めたものD[i][j]と置く。
- まず、A[i](0 <= i < |A|)が最終的に重なって負ける場合、重なる頂点を決めると、他の各Bはそこから最短距離でその頂点に向かう場合が最適である。よって、A[i]が重なって負ける頂点をlastとすると、A[i]が負けるターン数はmin(D[B[j]][last])(0 <= j < |B|)である。ただし、D[B[j]][last] <= D[A[i]][last]となるB[j]が1つでもある場合は、そのlastはA[i]が重なって負ける頂点となり得ない。(つまり別のlastで、より少ないターン数で負ける)
- ここでAは、A[i]について、全てのlastとなりうる頂点について最小ターン数が決まったとき、各A[i]は、その中でターン数が最大となるlastを選んで移動するのが最適である。
- このときBは、上で述べた各A[i]で最大となるターン数のうちターン数が最小となる頂点を選んで追い詰めるのが最適であるので、そのようなA[i]を選んで、ターン数を出力すれば良い。
計算量
全点対最短距離を求めるのにWarshall-Floydを用いた場合O(N^3+N|A||B|)。木なので、DFSを用いた場合はO(N^2+N|A||B|)
コード
感想
ゲームの問題だ→距離を求めればいい、ということに気がつくのが(少なくとも僕にとっては)難しい感じた
