ABC054 C One-stroke Path

頑張って実装したやつは記事にしようという試み。

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

問題概要

自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるので、頂点1を始点として、全ての頂点を1度だけ訪れるパスは何通りあるかを求める。

制約

再帰を使った解法

コンテスト中に解いた解法はこれ。とりあえずDFSで探索して、行った頂点を記憶しておく。頂点1からN-1回移動したときにすべての頂点に行っていれば、一つの経路として数える。「DFSで行ったところを記憶する」のがとても面倒だった(引き返すときにマイナスしないといけないので)。

Submission #1105966 - AtCoder Beginner Contest 054 | AtCoder

next_permutationを使った解法

すべての頂点を1回しか通らないなら、1からNまでの数字からなる数列の並ぶ順番と頂点をたどる経路を同一視して考えられるよね。ってとこまでわかったけど、N桁の数列の並び替えとかがわからなかった。
next_permutationという関数があるらしいので(知らなかった)、調べて実装してみた(ニコニコ動画とかに実装してみたとかいうジャンルありそう)。
next_permutationは、受け取った配列を、辞書順で次の並べ方に並べ替える関数。最初は配列を昇順になるようにしておかないと、うまく全部まわってくれないので注意が必要。次の順列が存在する場合はtrueを返し、存在しない場合はfalseを返す。

配列の要素をi番目にいる頂点とすると、毎回頂点iと頂点i+1の間に辺が張られているかを調べ、辺がすべて張られている並べ方の数を出力する。
N頂点の並べ替えと隣り合う頂点間に辺が張られているかそれぞれ調べるので、計算量は 。Nが小さいから間に合う。

Submission #1113580 - AtCoder Beginner Contest 054 | AtCoder

next_permutation関数は辞書順で次の並べ方を表示するので、配列のはじめの要素が1以上のときにnext_permutation関数に配列を渡しても、配列のはじめの要素が0になることはない。よって、配列のはじめの要素が0でなくなったときには今後始点が0になることがないのでdo-while文を抜けても大丈夫。

感想

next_permutaion関数すごすぎる。なにこの便利な関数。
実はコンテスト中は、Cの実装&&バグ取りに50分くらいかけてて(コンテストの前にsetとか使ってたせいで余計なことを考えてた)、next_permutationの解法書くのに10分くらいしかかかってないから、コンテストで使えてたらもっと順位が良かったのになと思った。まあレートには関係ないけど。
りんごさんが解説放送で余裕があればnext_permutationを自作してみてね！と言っていたけど私には無理だった。