yukicoder No.411 昇順昇順ソート

問題はこちら
No.411 昇順昇順ソート - yukicoder

$\{a_i\}_{i=1}^n$ が昇順昇順列である $\overset{def}{\iff}\exists j.\forall i.(i = j\Leftrightarrow a_i > a_{i+1})$
定義より $\{a_i\}_{i=1}^j,\{a_i\}_{i=j+1}^n$ はそれぞれ昇順列であることに注意せよ

1～Nの置換である昇順昇順列のうち、 $a_1=K$ であるものの個数を求めよ、という問題である

条件をみたすような昇順昇順列をとる
$a_j> a_{j+1}$ を満たすjをとり、 $A:=\{a_1,...,a_j\}$ とする
このとき明らかに次の(i)(ii)が成立する
(i) $K\in A \subset \{K,...,N\}$ 　　　　　　（∵ $\forall i\leq j.\ \ a_i\geq a_1=K$ ）
(ii) $\max A > \min (\{1,...,N\}\setminus A)$ 　　（∵ $\max A=a_j > a_{j+1}=\min (\{1,...,N\}\setminus A)$ ）
逆に(i)(ii)を満たすような集合Aを取れば、 $a_1=K$ なる昇順昇順列がそれぞれ一意に定まる
（ $\min\emptyset=\infty$ であることに注意する）
(i)を満たすような集合Aは $2^{N-K}$ 個ある。この内(ii)も満たすものの考える
・ $K\neq 1$ のとき
$1\notin A$ なので(i)を満たせば(ii)は必ず成立する。よって $2^{N-K}$ 通り
・ $K=1$ のとき
(i)を満たすようなAであって(ii)を満たさないものは $A=\{i|1\leq i\leq a\}$ という形の時かつその時に限るので、aが1からNのN通り
よって $2^{N-K}-N$ 通り

やるだけ

n;
main(k){
	scanf("%d%d",&n,&k);
	n=!printf("%d",(1<<n-k)-!~-k*n);
}

63B

17/01/24追記
kは1以上なので!-~kは1/kと書き換えられ1B短縮

n;
main(k){
	scanf("%d%d",&n,&k);
	n=!printf("%d",(1<<n-k)-1/k*n);
}

62B

メモ

yukicoderでゆるふわgolf

yukicoder No.411 昇順昇順ソート