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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.411 昇順昇順ソート

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

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

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

条件をみたすような昇順昇順列をとる
a_j\geq 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\geq\min (\{1,...,N\}\setminus A)  (∵\max A=a_j\geq a_{j+1}=\min (\{1,...,N\}\setminus A)
逆に(i)(ii)を満たすような集合Aを取れば、a_1=Kなる昇順昇順列がそれぞれ一意に定まる
\min\emptyset=\inftyであることに注意する)
(i)を満たすような集合Aは2^{N-K}個ある
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