【今日の精進】AGC008D - K-th K

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

問題リンク

atcoder.jp

問題概要

すべての数が 回ずつ出る長さ の数列のうち、以下のようなものを見つけるか、そんなものはないと宣言してね。

• 番目の は全体で の位置にある

解法

非常に単純明快です。

の小さい順に、その前に必要な数だけその数を置くようにします。

その後、同じようにして余った数を置きます。

そしてそれが正当か判定して終わりです。

提出コード

N=int(input())
x=list(map(int,input().split()))
bef=x[:]
ser={}
for i in range(N):
    ser[x[i]-1]=i+1
    x[i]=(x[i],i+1)
x.sort()
ans=[]
for i in range(N):
    ans=ans+[x[i][1]]*(x[i][1]-1)
for i in range(N):
    ans=ans+[x[i][1]]*(N-x[i][1])
aft=[]
for i in range(N*(N-1)):
    while len(aft) in ser:
        aft.append(ser[len(aft)])
    aft.append(ans[i])
while len(aft) in ser:
    aft.append(ser[len(aft)])
cnt=[0]*N
for i in range(N*N):
    cnt[aft[i]-1]+=1
    if cnt[aft[i]-1]==aft[i]:
        if bef[aft[i]-1]!=i+1:
            print("No")
            exit()
print("Yes")
print(*aft)

Submission #47628171 - AtCoder Grand Contest 008

感想

めっちゃ簡単だった