D - Crossing
はじめに
競技プログラミング、Tenka1 Programmer Beginner Contest
D - Crossing
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
整数 Nが与えられます。
{1,2,...N}の部分集合の組 (S1,S2,...,Sk)であって、
以下の条件を満たすものが存在するか判定し、
存在する場合はひとつ構成してください。
・1,2,...,Nのうちどの整数も、S1,S2,...,Skのうちちょうど 2つに含まれる
・S1,S2,...,Skのうちどの 2つの集合をとっても、それらに共通して含まれる要素はちょうど 1つである
制約
1≤N≤10^5 Nは整数である
入力 入力は以下の形式で標準入力から与えられる。
N
出力 条件を満たす部分集合の組が存在しない場合、No を出力せよ。 存在する場合、まず Yes を出力し、次いで以下の形式で部分集合の情報を出力せよ。 ただし、 Si={Si,1,Si,2,...,Si,|Si|} とする。 条件を満たすものが複数ある場合、どれを出力しても構わない。
k |S1| S1,1 S1,2 ... S1,|S1| : |Sk| Sk,1 Sk,2 ... Sk,|Sk|
解き方
※Tenka1 Programmer Contest 2018 解説放送の解き方で解いています。
以下の条件から問題を解いていく。
・1,2,...,Nのうちどの整数も、S1,S2,...,Skのうちちょうど 2つに含まれる ・S1,S2,...,Skのうちどの 2つの集合をとっても、それらに共通して含まれる要素はちょうど 1つである
例題1を見てみると
S1 {1,2}
S2 {3,1}
S3 {2,3}
という集合を作ることができる。
これを
二番目の条件と同じ形にしてみる。
{S1,S2}=1
{S1,S3}=2
{S2,S3}=3
上を見てみると
集合で重複している数字に
綺麗に1～3までの数字が
各一回ずつ出現していることが分かる。
これを記号に置き換えると以下のようにすることができる。
（大文字アルファベットは共通して含まれる要素）
{S1,S2}=A
{S1,S3}=B
{S2,S3}=C
集合で重複している数字が
各一回ずつしか
2つの集合をとったときに共通して含まれる要素として
現れないということは
問題文の条件に合うかどうかは
集合で重複する数字の数がNと合致するkが存在するかどうか
で判断できるということである。
上の例の場合、
集合はS1～S3まであるのでk=3である。
つまり、
k=3のとき数字はA,B,Cの3つが必要なので
N=3のとき条件に合う。
少し分かりにくいので、さらに例をあげる。
k=4のとき
{S1,S2}=A
{S1,S3}=B
{S1,S4}=C
{S2,S3}=D
{S2,S4}=E
{S3,S4}=F
数字はA,B,C,D,E,Fの6つがないと成り立たないので、N=6のとき条件に沿う
k=5のとき
{S1,S2}=A
{S1,S3}=B
{S1,S4}=C
{S1,S5}=D
{S2,S3}=E
{S2,S4}=F
{S2,S5}=G
{S3,S4}=H
{S3,S5}=I
{S4,S5}=J
数字はA,B,C,D,E,F,G,H,I,Jの10個ないと成り立たないので、N=10のとき条件に沿う
k=6のとき
{S1,S2}=A
{S1,S3}=B
{S1,S4}=C
{S1,S5}=D
{S1,S6}=E
{S2,S3}=F
{S2,S4}=G
{S2,S5}=H
{S2,S6}=I
{S3,S4}=J
{S3,S5}=K
{S3,S6}=L
{S4,S5}=M
{S4,S6}=N
{S5,S6}=O
数字はA,B,C,D,E,F,G,H,I,J,K,L,M,N,Oの15個ないと成り立たないので、N=15のとき条件に沿う
つまり、この問題はkを起点に考えていく。
kがいくつのとき、数字がいくつ必要であるかを
ループで回しながら見ていき
もし、Nがその数に合わなければ
問題の条件に合うNは存在しないということになる。
次に、
Nが条件に合うか判別するコードを書くために
問題の条件に合うものに規則性があるかどうかを見ていく。
上の例にk=2を加えると
k=2のとき、N=1 k=3のとき、N=3 k=4のとき、N=6 k=5のとき、N=10 k=6のとき、N=15
となっていることが分かる。
（k=1は
どの 2つの集合をとっても、それらに共通して含まれる要素はちょうど 1つである
という問題の条件に合わせることができないので省く。）
上の数列をよく見ると
階差数列になっていることが分かる。
この数列を記号で表すと
k(k-1)/2＝N
となるので
var N = Int32.Parse(Console.ReadLine());
var k = 0;
for(int i = 1; i <= N+1; ++i) if (i * (i - 1) == 2 * N) k = i;
if (k == 0)
{
Console.WriteLine("No");
return;
}
とすれば、条件を満たせるかどうかを判別できる。
(下のコードでは、i=0から数えているので上のものとは、ずれています。)
さらに、最終的に出力したいものは
集合であり、それにはkの値が必要になるので
保存しておく。
次にそれぞれの集合の出し方を考えていく。
今、分かっていることは
kの値、そして二つの集合において重なる数字である。
まず、集合の要素の数について考える。
1,2,...,Nのうちどの整数も、S1,S2,...,Skのうちちょうど 2つに含まれる
という問題文の条件から
要素の数は2*N/kであると言える。
試しに、
k=4のときを
問題文の条件を踏まえて、書き出してみると以下のようになる。
N=6なので要素の数字は1～6である。
S1={1,2,3}
S2={1,4,5}
S3={2,4,6}
S4={3,5,6}
書き出してみると、
要素の数は3となり
2*N/kが合っていることが分かる。
しかし、
k=3のとき要素の数が2
k=4のとき要素の数が3
だったので
ここで要素の数はk-1でも出るのではないかという疑問が起こる。
試しに、
k=5のときを
問題文の条件を踏まえて、書き出してみると以下のようになる。
N=10なので要素の数字は1～10である。
S1={1,2,3,4}
S2={1,5,6,7}
S3={2,5,8,9}
S4={3,6,8,10}
S5={4,7,9,10}
要素の数は4なので
ここでも
要素の数=k-1
が成り立っていることが分かり、
要素の数はk-1でも出せるということが分かる。
次に
要素の数字について考えていく。
上で列挙されたものを見ていくと
ある規則性があることが分かる。
k=5のとき（N=10）
S1={1,2,3,4}
S2={1,5,6,7}
S3={2,5,8,9}
S4={3,6,8,10}
S5={4,7,9,10}
まず、S1は単純に1から数字を列挙する
S1={1,2,3,4}
問題文の条件から
S2はS1と一つしか要素が重なれないので
1だけをS1と重複させる。
S1={1,2,3,4}
S2={1,5,6,7}
問題文の条件から
S3はS1,S2と一つずつしか要素が重なれない
かつ
要素として使われる数字は
2回しか全体の要素の中に現れられないので
1は使用することができない。
そのため、
2だけをS1と、5だけをS2と重複させる。
S1={1,2,3,4}
S2={1,5,6,7}
S3={2,5,8,9}
こうして考えていくと
以下のようになっていることが分かる。
つまり、
上の行と一つずつ数字を重複させていき
足りない要素は
まだ、どこにも入っていない数字の要素を入れるということである。
また、
集合を行と列でとらえると
k行、(k-1)列となるので
これをループで回しながら出力させていけば
集合を一つずつ出力させていくことができる。
コード
using System;
using System.Linq;
using System.Collections.Generic;
class Dmondai
{
static void Main()
{
//入力を保存
var N = Int32.Parse(Console.ReadLine());
//問題文の条件に当てはまっているかを判別する
var k = 0;
//条件に当てはまったらkを保存
for (int i = 0; i <= N; ++i) if (i * (i + 1) == 2 * N) k = i + 1;
//条件に当てはまらないものはここではじく
if (k == 0)
{
Console.WriteLine("No");
return;
}
Console.WriteLine("Yes");
//集合の数kを出力
Console.WriteLine(k);
//ここから集合の中身を列挙していく
//集合を保存できるように二重配列を用意する（要素の重なりに対応）
var array = new int[k, k - 1];
//配列に-1を入れておく
for (int i = 0; i < k; ++i) for (int j = 0; j < k - 1; ++j) array[i, j] = -1;
//集合を一つずつ出力したいので
//外側のループは集合の数ぶん回す
for (int i = 0; i < k; ++i)
{
//要素の数を出力
Console.Write(k - 1);
//後に出力する要素を用意
var num = 0;
//要素のインデックスを用意（重なりに対応）
var index = 1;
//内側のループ
//要素数のk-1回回す
for (int j = 0; j < k - 1; ++j)
{
//空白を出力
Console.Write(" ");
//i=0のとき、すなわちS1
//1から単純に数字を列挙する
if (i == 0) num = j + 1;
//i=1のとき、すなわちS2
else if (i == 1)
{
//S1と「1」のみ重なるので初めの要素は「1」
if (j == 0) num = j + 1;
//それ以降はS1で列挙されていない要素
else num = array[i - 1, k - 2] + j;
}
//S1でもS2でもないとき
else
{
//iよりjが大きい、すなわち
//現在の集合が上の集合と重なる部分がないとき
if (i <= j)
{
//一つ上の集合の一番大きいかずよりも大きい数を列挙していく
num = array[i - 1, k - 2] + index;
index++;
}
//iよりjが小さい、すなわち
//現在の集合が上の集合と重なる部分があるとき
//過去に列挙した集合の要素から取り出す
else num = array[j, i - 1];
}
//要素を保存
array[i, j] = num;
//要素を出力
Console.Write(num);
}
//開業して、次の集合を出力できるようにする
Console.WriteLine();
}
}
}
