Codeforces Round #640(Div.4) A〜G解説

Codeforces Round #640 (Div.4)のA～Gまでの解説です。
試験的に開催された初のDiv.4のコンテストで、難易度としてはDiv.3-DやDiv.2-C程度までの問題(Difficulty1600程度)が出題されました。
ABC-C～E下位程度の問題が7問出る感じのコンテストなので、AtCoder茶～緑の方にとっては非常に練習になるコンテストではないかと思います。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1352
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/77161

A問題:

与えられた文字列について、0でない文字を1つ残してすべてを0にしたような文字列をすべて答えればよく、これは下からi桁目の数が0でないとき、(i桁目の数)*10^iを答えに付け加えることで得られます。
ただし制約がN<=10^4と大きく(i桁目の数)*10^iが64bitを超える場合があるので、実装の際は答えを文字列として求める必要があります。
例えばstr(i桁目の数)+'0'*iを答えに付け加えればよいです。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/79490862

t=int(input())
for _ in range(t):
 s=input()
 l=len(s)
 ans=[]
 for i in range(l):
   if s[i]!='0':
     ans.append(s[i]+'0'*(l-i-1))
 print(len(ans))
 print(*ans)

B問題:

各aiは正数であればどのような数でもよいので、a1,…,a(k-1)をすべて1で埋めたとき、もしくはすべて2で埋めたときに、条件を満たすakが存在するかを判定すれば十分です。
つまり、n-(k-1)>0かつ(n-(k-1))%2==1もしくはn-2(k-1)>0かつ(n-2(k-1))%2==0を満たすかを判定すればよいです。
可能である場合は、1,,…,1,n-(k-1)、もしくは2,…,2,n-2(k-1)を出力すればよいです。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/80896125

t=int(input())
for _ in range(t):
 n,k=map(int,input().split())
 if n-(k-1)>0 and (n-(k-1))%2==1:
   print('Yes')
   ans=[1]*(k-1)+[n-(k-1)]
   print(*ans)
 elif n-2*(k-1)>0 and (n-2*(k-1))%2==0:
   print('Yes')
   ans=[2]*(k-1)+[n-2*(k-1)]
   print(*ans)
 else:
   print('No')

C問題:

nで割れない数の代わりに、nの倍数に着目すると、それぞれの倍数の間には(n-1)個のnで割れない数が存在することが分かります。
このことから、p番目のnの倍数までに、p(n-1)個のnで割れない数が存在することが分かります。
したがって、kがn-1で割り切れるとき、pn-1が求める数となり、kがn-1で割り切れないとき、pn+k%(n-1)が求める数となります。
ただし、ここでpはk//(n-1)を表します。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/79502037

t=int(input())
for _ in range(t):
 n,k=map(int,input().split())
 if k%(n-1)==0:
   print(n*(k//(n-1))-1)
 else:
   print(n*(k//(n-1))+k%(n-1))

D問題:

問題文の通り愚直にシミュレートすれば十分です。
愚直なシミュレートでは、各要素を必ず1回だけチェックすることになるので、計算量はO(N)となることが分かります。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/80896217

t=int(input())
for _ in range(t):
 n=int(input())
 arr=list(map(int,input().split()))
 cnt=0
 pos1=0
 pos2=n-1
 prev1=0
 prev2=0
 a=0
 b=0
 while 1:
   if pos1>pos2:
     break
   if cnt%2==1:
     tmp=0
     while tmp<=prev1 and pos1<=pos2:
       tmp+=arr[pos2]
       pos2-=1
     b+=tmp
     prev2=tmp
   else:
     tmp=0
     while tmp<=prev2 and pos1<=pos2:
       tmp+=arr[pos1]
       pos1+=1
     a+=tmp
     prev1=tmp
   cnt+=1
 print(cnt,a,b)

E問題:

ある要素の値が長さ2以上の連続部分和に等しいとき、その要素が連続部分列に含まれることはありません。
このことを利用すると、O(N^2)で総和がn以下のすべての連続部分和を列挙することで、各要素についてその要素の値に等しい連続部分和があるかどうかを集合型などを用いることでO(logN)で判定することができ、この問題を時間計算量O(N^2)、空間計算量O(N)で解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/79588925

import collections

t=int(input())
for _ in range(t):
 n=int(input())
 arr=list(map(int,input().split()))
 ok=[0]*(n+1)
 for l in range(n-1):
   acum=arr[l]
   for r in range(l+1,n):
     acum+=arr[r]
     if acum>n:
       break
     ok[acum]=1
 ans=0
 for val in arr:
   if ok[val]==1:
     ans+=1
 print(ans)

F問題:

まず0を並べ、次に1を並べ、最後にペア数がn1個になるように0と1を交互に並べることを考えます。
n0とn2の両方が1以上のとき、0と1の切り替えで01が1つ出来ていることに注意して、0と1をペア数がn1個になるように並べればよいです。
n0またはn2の一方が0のとき、上記と異なり切り替えで01が出来ないことに注意し、1と0、もしくは0と1をペア数がn1個になるように並べればよいです。
n0とn2の両方が0のとき、1と0をペア数がn1個になるように並べればよいです。
以上によりこの問題をO(1)で解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/79537059

t=int(input())
for _ in range(t):
 a,b,c=map(int,input().split())
 ans=''
 if a>0:
   ans+='00'+'0'*(a-1)
 if c>0:
   ans+='11'+'1'*(c-1)
 if a>0 and c>0 and b>1:
   ans+='01'*((b-1)//2)+'0'*((b-1)%2)
 else:
   if a==0 and c==0:
     ans+='10'*((b+1)//2)+'1'*((b+1)%2)
   elif a==0 and b>0:
     ans+='01'*(b//2)+'0'*(b%2)
   elif c==0 and b>0:
     ans+='10'*(b//2)+'1'*(b%2)
 print(ans)

G問題:

2<=|ai-(ai+1)|<=4という条件式に注目すると、n→n-3→n-1→n-5→n-7→…という遷移が可能なことが分かります。
また、nから遷移する数はすべてnと偶奇が異なることから、nが偶数のときは2からスタートしてnに2ずつ近づいていき、上記の方法で奇数に移れば条件を満たす列を得ることができ、同様に、nが奇数のときは1からスタートしてnに2ずつ近づいていき、上記の方法で偶数に移れば条件を満たす列を得ることができます。
以上によりこの問題をO(N)で解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1352/submission/79540105

t=int(input())
for _ in range(t):
   n=int(input())
   if n==2 or n==3:
       print(-1)
   else:
       ans=[]
       if n%2==0:
           for i in range(2,n+1,2):
               ans.append(i)
           ans.append(n-3)
           ans.append(n-1)
           for i in range(n-5,0,-2):
               ans.append(i)
       else:
           for i in range(1,n+1,2):
               ans.append(i)
           ans.append(n-3)
           ans.append(n-1)
           
           for i in range(n-5,0,-2):
               ans.append(i)
       print(*ans)