金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder ARC #043 B - 最短路問題

B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder

距離が同じもの同士は,ペアの選び方が  {}_nC_2 なので,  2^{{}_nC_2} 通り

距離  i から  i+1 は ,距離  i+1 のそれぞれから 距離  i のそれぞれについてつなぐ・つながない 二通りあって,全部つながないというのを除くので,

距離  i t 通り,距離  i+1 s 通りあるとすると,  (2^t - 1)^s 通り

Rubyで書いていて,2乗 の範囲を間違っていてREになってずっと考えていた.

Python は pow があって楽だった.

AtCoder ARC #044 B - 最短路問題

AtCoder ARC #043 B - 最短路問題