https://beta.atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_bニコ生の公式解説でちらっと触れていた解法が凄くスマートだったので復習を兼ねて書いておきます。 解法 与えられた[v_1, v_2, ..., v_n]を(K+1)倍に拡張した次のような配…

No.643 Two Operations No.2 - yukicoder 考察 xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。 （ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無い…

No.642 Two Operations No.1 - yukicoder 考察 とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。頂点数はNで辺の数は2Nなので、N 最短距離（最小操作回数）が求められますが、今回はN 頂点iへの最短距離をdist(i)と書く…