AtCoder Beginner Contest 145 - giantneco’s blog

今回も A から D まで解いた。

ようやく上の方に青が見えてきたがまだまだ遠い。

A-D までは継続して解けている。

C は全経路のコストに何かしらの値をかければ良さそうだとわかった(すべての組み合わせなので、どの枝も同じ回数だけ出現するはずである)。

全ての枝のコストが 1 だった場合は、明らかに n! が全経路のコストの和になる。

なのでここから計算すると、全枝のコストの和 x (n-2)!/2 が解答になる。

解答に精度の設定がある問題だったが、その設定を忘れていたので、 WA をもらってしまった。

すぐに終わるはずの問題だったが、終了間際になるまで気づかなかった。

入力例 1 で気づいていてもおかしくなかったのだが、急ぐあまり見落としていたようである。

D は本質的に組み合わせの数 = nCr を計算する問題。

頻出の問題なので、こういうのこそ前もって準備しておくべきなんだろうが、それができていなかった。

ただやり方自体は Qiita の次の記事を見た覚えがあったので、時間内に調べてなんとか間に合わせた。

結局時間内に AC は出せたがぎりぎりになってしまい E には進めなかった。

知っていれば簡単に回答できる問題なので、こういうのはしっかり抑えておきたい。