競プロ初中級者100問

Tenka1 Programmer Beginner Contest 2018D Crossing

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d

この問題は深さ優先探索を用いて解くことができます。

方針

Nが、1からiまでの和として表せるような数であれば、要素数iのi+1組の集合で実現できます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
N = int(input())

i = 1
K = []
while(1):
    k = i * (i+1) // 2
    if k > 10**5:
        break
    K.append(k)
    i+=1
if not N in K:
    print ('No')
    exit()
print ('Yes')
S = [[],[]]
i = 0

for n in range(1,N+1):
    S[i].append(n)
    S[-1].append(n)
    i+=1
    if n in K:
        if n==N:
            break
        i = 0
        S.append([])
print(len(S))
for s in S:
    print(str(len(s)) + ' ' + ' '.join(map(str,s)))

記事情報

  • 投稿日：2020年6月3日
  • 最終更新日：2020年6月3日