ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Tenka1 Programmer Contest　(2018) D - Crossing

構築考察系

問題
 提出コード
今のところ、500点の構築問題は自分と相性がいいみたいで全勝中です(数問しかやったことないですが)

解法

$S$ の個数を $K$ 、そして $S_i$ の個数を $|S_i|$ とすると、
自動的に $|S_i|=K-1$ となります。自分以外の集合と、ちょうど1つずつ共通部分が存在するからです。また、 $1$ ～ $N$ それぞれについて、どこか1組の集合のペアについて、共通部分を作成できます。
これは小さい方から実験していくと規則性が見えてきます。 $K$ を決めたときに、 $N$ は自動的に決まります。

$K = 2$ のとき
これは、 $N=1$ のとき作成できます。
$K=3$ のとき
$N=3$ となります。
これはサンプルに存在する例です。
$K=4$ のとき
$N=6$ となります。
$K=3$ のときのサンプルから、あらたに $S_4$ を用意し、それまでの $S_1$ ～ $S_3$ それぞれと $S_4$ に、同じ数字を入れていけば完了です(例えば、 $S_1$ と $S_4$ に4を、 $S_2$ と $S_4$ に5を、 $S_3$ と $S_4$ に6をいれるとできます)。

これ以降も、 $K=x$ のとき、 $S_x$ を新たに用意し、すでにある集合それぞれと数字のペアを入れていけば条件を満たすことができます。この時、 $N$ の条件は、
$N = \sum_{i=1}^{K-1} i$
となります。
あとは、作成方法に従ってうまいことつくると、答えを導くことができます。次に追加する数字を記録しておき、forの二重ループを利用してやると賢い作成方法になるかと思います(Twitterで見かけたアイデアです、自分のコードはもう少し汚いです)。