@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

【Tenka1 Programmer Contest】D - Crossing

AtCoder Tenka1 構築

問題概要

\{1,2,\cdots ,N\}の部分集合の組(S_1,S_2,\cdots ,S_k)について, 以下の条件を満たすものがあれば構築せよ.

[条件1] 1,2,\cdots ,Nのうちどの整数も, S_1,S_2,\cdots ,S_kのうちちょうど2つに含まれる.
[条件2] S_1,S_2,\cdots ,S_kのうちどの2つの集合をとっても, その共通成分はちょうど1つである.

制約

  • 1\leq N\leq 10^{5}

考察

とりあえず, N=1について考えてみると, S_1=S_2=\{1\}として構築できる.
このS_1,S_2と共通成分を1つずつもつようなS_3を作りたい. ちょっと考えると, S_1=\{1,\underline{2}\},S_2=\{1,\underline{3}\},S_3=\{\underline{2},\underline{3}\}のように, 要素2,3を追加すれば良いと分かる.
このS_1,S_2,S_3と共通成分を1つずつもつようなS_4を作りたい. 同様にして, S_1=\{1,2,\underline{4}\},S_2=\{1,3,\underline{5}\},S_3=\{2,3,\underline{6}\},S_4=\{\underline{4},\underline{5},\underline{6}\}のように, 要素4,5,6を追加すれば良い.
こんな感じで再帰的に構築できそうだという予想がつく. このとき, \displaystyle N = 1+2+\cdots+k=\frac{k(k+1)}{2}より, 三角数でなければならない.

f:id:morio_prog:20181103194020p:plain:w300

ACコード(Python3🐍)

n = int(input())
r = int((n*2)**.5)
if r*(r+1)!=n*2:
    print('No')
    exit()
# nは三角数
res = [[] for i in range(r+1)]
tmp = 0
for i in range(r-1):
    for k in range(tmp,r-i+tmp):
        res[i].append(k+1)
        res[i+k-tmp+1].append(k+1)
    tmp += r - i
res[-2].append(n)
res[-1].append(n)
print('Yes')
print(len(res))
for l in res:
    print(len(l),*l)