読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #359 (Div. 1) A. Robbers' watch

http://codeforces.com/contest/685/problem/A

問題

0..n-1 時 0..m-1 分まで 7 進表記で表示できる時計がある。どの桁も異なる表記は何通りあるか。

  • 1≦n,m≦109

解法

7進表記で 0..n を表現するのに必要な桁数を L(n) とする。このとき L(n-1)+L(m-1)≧8 だと必ずどこかの桁が重複してしまう。 L(n-1)+L(m-1)≦7 の場合は 0..6 の順列すべてを生成して確かめればいい。


nPk を生成するなら next_permutation が使える。n! を生成して先頭 k 個を見ればいい。ただし (n-k)! 回重複するので注意。

gist.github.com

こういう全探索は精神がすり減らないので良い。