【今日の精進】CF17-FINALF - Distribute Numbers

毎日格上の問題を倒すやつの78日目です。

問題リンク

atcoder.jp

問題概要

枚の紙があって、 個ずつ数字を書くよ。

このとき、 が 個ずつ出現したうえで、各紙に共通する数字はただ一つにする必要があるよ。

は自由に、 は1000から2000の範囲で自由に決められるとき、これを実際にやって見せてね。

解法

とりあえず、 にする必要はあります。

そうしたら、 を書く紙を固定し、それらにすべての数を書いたうえで、それ以外はうまくスライドしていくとうまく数字を書けます。

ただし、 は素数+1である必要があります。

提出コード

from collections import deque

#N=1057,K=33
K=38
N=K*(K-1)+1
print(N,K)
ans=[[] for i in range(N)]
ans[0]=list(range(1,K+1))
for i in range(N-1):
    ans[i+1].append(i//(K-1)+1)
cnt=K+1
for i in range(1,K):
    sw=deque(range(cnt,cnt+K-1))
    for j in range(K-1):
        ans[i].append(cnt)
        cnt+=1
    now=K
    for j in range(K-1):
        for k in sw:
            ans[now].append(k)
            now+=1
        for k in range(i-1):
            sw.append(sw.popleft())
for i in ans:
    print(*i)

感想

こういう構築いいね