はまやんはまやんはまやん

hamayanhamayan's blog

昇順昇順ソート [yukicoder 411]

問題

http://yukicoder.me/problems/no/411

正の整数 N, K がある。
1~Nが1つずつあるN個の数列はN!通りあるが、その中で以下の条件を満たす組合せを数える

  • 数列の先頭がK
  • 数列について Ai > Ai+1 となるiがただ1つだけある

2 <= N <= 20
1 <= K <= N

考察

1. 最大20なのでbit使う感がある
2. 全探索より計算から求める方法から考え始めてしまった
3. 解説は全探索になってます
4. 計算から求める方法では場合分けの必要があります

5. 今回の問題では昇順数列を2つくっつける
6. 片方の昇順数列が決まればもう片方も一意に決まるので、片方だけ全列挙する方針で考える

7. K != 1のとき
8. 2番目の昇順数列は1から始まる
9. 1番目の昇順数列はK以上の要素のみで構成される
10. Kより大きい数は N - K個 存在するので、この数を選択する組合せは 2^(N - K) 通り

11. K == 1のとき
12. K != 1のとき同様、組合せは 2^(N - K) 通りかなという感じですが、ちょっと違う
13. 1番目の昇順数列が公差1の等差数列になってしまうと、2番目の昇順数列が作れないので、そうなる N 通りを除外する
14. これで答え

実装

http://yukicoder.me/submissions/110378

typedef long long ll;
ll modpow(ll a, ll n) {
	if (a == 0) return 0;
	ll r = 1;
	while (n) r = r*((n % 2) ? a : 1), a = a*a, n >>= 1;
	return r;
}
//-----------------------------------------------------------------
int main() {
	int N, K;
	while (cin >> N >> K)
	{
		if (K == 1)
			cout << modpow(2, N - 1) - N << endl;
		else
			cout << modpow(2, N - K) << endl;
	}
}