2018-09-02

ARC102-E Stop. Otherwise...

勉強になったのと，解説があまり丁寧でないのでまとめのため。
問題概要: $1$ から $K$ までの目が出るサイコロを $N$ 個振る。このとき， $2\leq i \leq 2K$ をみたす各 $i$ について，次の問題に答えよ。

・どの異なる2つの出目の和も $i$ にならないような出目の組の場合の数はいくつか？ただし，サイコロ同士は区別しない。

解法が2つあるので，どちらも紹介する。解法2の方が簡潔である。

解法1(解説解)

$i$ を固定したときの問題を考える。 $a+b=i$ を満たす $(a,b)(1\leqq a\leqq b \leqq K)$ のペアの個数を $n$ とする(具体的な $n$ の値はコード参照)。求める出目の総数は， $m$ 個のペアについては $a$ もしくは $b$ の片方のみの数が出現し， $n-m$ 個のペアについてはどちらの数字も現れないような出目の総数を $S(m)$ とすると， $\sum_{m=0}^{m=n}S(m)$ である。
$S(m)$ を求めよう。戦略は以下のようになる。まず，(1) $m$ 個のペアを使うと決めたときに，使用できる数の個数を求める。その次に，(2)それらの数を使った出目が何通りあるかを求める。最後に，(3)使用できる数の選び方が何通りあるか求める。これらをすべてかけ合わせた値が $S(m)$ である。
注意する必要があるのは， $i$ が奇数と偶数のときは少しだけ事情が変わってくるということである。 $i$ が偶数のとき，上のペアのうち， $a=b=\frac{i}{2}$ となるものが混入するためである。まずは， $i$ が奇数のときを考えよう。

(1) $m$ 個のペアの片方の数を必ず使うと決めたので，まず $m$ 個の数が手に入る(このとき， $a,b$ どちらを使うかは問題にならない)。他のペアの数は使わないと決めたので，残りは， $n$ 個のペアに入らない $K-2n$ 個の数たちを使う。よって，使用できる数の個数は $K-2n+m$ 個である。

(2) $K-2n+m$ 個の数のうちから $N$ 個を重複して選ぶ組合せの数なのだが， $m$ 個のペアの片方の数を必ず使うと決めたので， $N$ 個のうち $m$ 個はもう埋まっていると考えよう。すると，残りの $N-m$ 個を $K-2n+m$ 個の数で埋めてやればよい。重複組合せの記号 ${}_n \mathrm{H} _r={}_{n+r-1} \mathrm{C} _r$ を用いれば， ${}_{K-2n+m} \mathrm{H} _{N-m}$ 個である。

(3) まず， $n$ 個のペアから $m$ 個のペアを求める組合せの数は ${}_n \mathrm{C} _m$ である。さらに $m$ 個のペアにそれぞれついて， $a$ と $b$ どちらを選ぶかが2通りあるから， $2^m$ が掛け算される。

以上より， $i$ が奇数のとき， $S(m)$ は
$S(m)={}_{K-2n+m} \mathrm{H} _{N-m}\times {}_n \mathrm{C} _m \times 2^m$
とわかった。これを $0\leqq m \leqq n$ について足し合わせれば，過不足なく数えることができる。

$i$ が偶数のときは， $\frac{i}{2}$ を使うか使わないかで別々に数えるが，別々になるのは(2)の部分のみである。
・まず，奇数のときと同様に考えるため，ペアの数 $n$ は $n-1$ に置き換える。
・次に，(1)での使える数の個数は $K-2(n-1)-1+m$ としておく。 $-1$ というのは $\frac{i}{2}$ を差し引いたものである。((1)で求めたのは，重複を許して使うのことのできる数だったという言い方がわかりやすいだろうか。)
・(2)について， $\frac{i}{2}$ を使うとき，埋めるべき枠は $N-m-1$ 個，使わないときに埋めるべき枠は $N-m$ 個である。
・(3)は $n$ が $n-1$ に変わるだけである。
以上より， $i$ が偶数のときは
$S(m)=\left({}_{K-2(n-1)+m-1} \mathrm{H} _{N-m-1}+{}_{K-2(n-1)+m-1} \mathrm{H} _{N-m}\right)\times {}_{n-1} \mathrm{C} _m \times 2^m$
であり，これを $0\leqq m \leqq n-1$ について足し合わせれば，過不足なく数えることができる。

提出
Submission #3125501 - AtCoder Regular Contest 102

解法2(包除原理)

包除原理がそもそもなにかということについては包除原理 - Wikipediaを参照。
解法1と同様に， $a+b=i$ を満たす $(a,b)(1\leqq a\leqq b \leqq K)$ のペアの個数を $n$ とし，各ペアに1から $n$ までの番号をつけておく。集合 $A_k (1\leqq k \leqq n)$ を「出目の組み合わせのうち， $k$ 番目のペアが少なくとも1つあるようなものの集合」と定義する。すると，求める組合せの総数は，集合
$\bigcap_{k=1}^{n}\overline{A_k}=\overline{\bigcup_{k=1}^{n}A_k}$
の要素の数である(ド・モルガンの法則を用いていることに注意)。よって，包除原理を用いて $\bigcup_{k=1}^{n}A_k$ の要素の個数を求め，全体の出目の組み合わせの数 ${}_K \mathrm{H} _N$ から引けばよい。

$m (1\leqq m \leqq n)$ 個の $A_k$ たちの共通部分の要素の大きさを求めよう。 $m$ 個のペアの数は使うと決めたから， $N$ 個のサイコロのうち $2m$ 個の出目は決まっている。あとは，残りの $N-2m$ 個の枠を， $K$ 個の数で埋めると考えてよい。 $m$ 個の $A_k$ たちの選び方は ${}_n \mathrm{C} _m$ であるから，結局
${}_n \mathrm{C} _m\times {}_K \mathrm{H} _{N-2m}$
を， $m (1\leqq m \leqq n)$ の偶奇に対応して足し引きすればよい。

なんと，この解法は $i$ の偶奇に依存していない。包除原理最高である。

提出
Submission #3126896 - AtCoder Regular Contest 102

こういうのが時間内に解けるようになりたいですね。

参考
包除原理 - Wikipedia
E - Stop. Otherwise...
包除原理の解がもう少し丁寧に書いてあります。本記事と表現がちょっと違いますが、基本的な考え方は同じです。
ARC102 参加記録 - ARMERIA

2018-08-09

codeforces #502 C ~The Phone Number~

codeforces

背景が面白い問題だったのでつい投稿。嘘を書いていたら教えてください。
問題要約
長さ $n$ のpermutationのうち，最長増加部分列(LIS)の長さと最長減少部分列(LDS)の長さの和が最小になるものを1つ出力せよ。
https://codeforces.com/contest/1017/problem/C

本番はエスパーして解いたので，解説を見たところこう書いてあった。

You can use [Dilworth's theorem]https://en.wikipedia.org/wiki/Dilworth So assume we've already known that $LIS=L$ ,then we can achieve $LDS=\lceil \frac{n}{L} \rceil$ .

なんでや。

ということで詳しく調べてみた。
まず，いくつか準備。
定義(最小被覆パス)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の最小被覆パスとは，パスの集合の組 $P_1,\dots P_k$ であって，これらが $V$ の分割になっているようなもの(すべての頂点 $v\in V$ に対して，ある $P_i$ がただ1つあって， $v\in P_i$ )のうち， $k$ が最小のものである。

定義(反鎖)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の反鎖(antichain)とは， $V$ の部分集合 $P$ であって， $P$ の任意の2要素の間にパスがないもののことである。
本来この語は半順序集合に定義されるもののようだが，閉路をもたない有向グラフは半順序集合とみなせる(と思う)ので，ここではグラフで定義をしても差し支えない。

Dilworthの定理とは以下のようなものらしい。
定理(Dilworth)
閉路をもたない有向グラフ $G(V,E)$ における最小被覆パスの大きさ(上の定義でいうところの $k$ )と， $G$ の最大の反鎖の大きさは等しい。
証明は(https://en.wikipedia.org/wiki/Dilworth%27s_theorem)を参照。こちらは半順序集合の言葉で話を進めているので注意。

LISとLDSに話を戻そう。長さ $n$ のpermutationを $p_1,p_2,\dots,p_n$ とする。このとき，頂点集合を $\{p_1,p_2,\dots,p_n\}$ として，グラフを作る。 $p_i,p_j (1\leq i.j\leq n)$ について， $p_i\lt p_j$ かつ $i\lt j$ のときに $p_i$ から $p_j$ に辺を張る。このグラフを $G(V,E)$ とすると，LISの長さ $L$ は $G$ の最長のパスの長さであり，LDSの長さ $K$ は最大の反鎖の大きさになる。これが肝である。
こんな感じ。
f:id:sigma1113:20180809202306j:plain

LISの長さが $L$ のとき， $K=\lceil \frac{n}{L} \rceil$ が最小であることを示そう。Dilworthの定理より， $K$ は $G(V,E)$ の最小被覆パスの大きさに等しい。ここで，LISの長さが $L$ であることから，最小被覆パスを構成するパスたち $P_1,P_2,\dots,P_K$ のそれぞれの大きさは高々 $L$ である。すると， $KL\geq n$ ，つまり $K\geq \lceil \frac{n}{L} \rceil$ が成り立つ。この下界は達成できる。実際， $L(K-1)+1,L(K-1)+2,\dots,n,L(K-2)+1,L(K-2)+2,\dots,L(K-1),\dots\dots,L+1,L+2,\dots,2L,1,2,\dots,L$ がそうなっている。

本番中に証明までして通した人どれくらいいるんだろう。

参考:
codeforces https://codeforces.com/contest/1017/problem/C
https://codeforces.com/blog/entry/61081

Dilworth's theorem https://en.wikipedia.org/wiki/Dilworth%27s_theorem

Erdős–Szekeres theorem https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Divisor https://www.slideshare.net/oupc/divisor

順序集合 https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88