Codeforces Round #638(Div.2) A～D解説

Codeforces Round #638 (Div.2)のA～Dまでの解説です。
今回も無事にA～Dまでの4完を達成し、ついに紫レートに到達することができました！
Codeforcesの紫はAtCoderの黄色に相当するという意見もあり、今後はまずAtCoderで青になれるよう頑張りたいです＊
問題のアドレスは以下になります↓
https://codeforces.com/contest/1348
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/76555

A問題:

任意の整数a(>=2)について、sum[i=1 to n-1](a^i)<a^nが成り立ちます。
このことから、2^Nに小さいほうから(N/2)-1個を足し、残ったN/2個を引くことで答えを求めることができます。

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

t=int(input())
for _ in range(t):
   n=int(input())
   arr1=[2**n]
   arr2=[]
   for i in range(1,n): #2^Nと2^1,2^2,…,2^(N/2-1)の組と、残りの組を作る
       if i<n//2:
           arr1.append(2**i)
       else:
           arr2.append(2**i)
   print(abs(sum(arr1)-sum(arr2))) #それぞれ組の総和の差が答えとなる

B問題:

まず、(数列{ai}の種類数)>kのとき答えは存在しません。
以下これを示します。
すべての要素aiが1<=ai<=nを満たす長さkの数列を考えます。
このとき、この数列の右隣に置けるのはa1のみ(∵長さkの連続部分列の和はすべて等しい)、その右隣に置けるのはa2のみ…となり、数列にはa1,a2,…,akまでの高々k種類の要素しか登場することができません。
一方、与えられた数列の種類数はkより大きいので、これは上記の議論に矛盾します。
これより(数列{ai}の種類数)>kのとき答えが存在しないことが示せました。
逆に、(数列{ai}の種類数)<=kのとき上記の議論により必ず答えを構成することが分かります。
具体的には、数列{ai}の相異なる要素にそれらとは異なるいくつかの要素を加えてk個の新たな数列を作り、これをk個並べることで、どの長さkの区間の和も等しく、また元の数列{ai}の要素はk個並べた列の部分列になることが分かります。
以上によりこの問題を解くことができました。

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

import collections

t=int(input())
for _ in range(t):
   n,k=map(int,input().split())
   arr=list(map(int,input().split()))
   if len(collections.Counter(arr))>k: #元の数列の種類数がKより大きいとき、そのような数列は構成できない
       print(-1)
   else:
       cand=list(collections.Counter(arr).keys())
       cnt=len(cand)
       for i in range(1,n+1): #元の数列の異なる要素をすべて含んだ長さKの数列を作る
           if cnt>=k:
               break
           else:
               if i not in cand:
                   cand.append(i)
                   cnt+=1
       print(cnt*n)
       print(*(cand*n)) #上記の数列をN回繰り返した数列は条件を満たす

C問題:

まず、文字列Sの各文字をアルファベット昇順に並び替え、k個の箱にSの先頭からk文字を1文字ずつ入れる操作を行います。
このとき、k個の箱に入っている文字の種類数が2以上であれば、辞書式順序で最大である文字が入った箱について、残ったn-k文字をどのように入れてもその箱の文字を真に小さくすることはできません。
一方、残ったn-k文字を辞書式順序で最大である箱以外に入れることで、k個の箱に入った文字の辞書式順序での最小値を辞書式順序で最大である文字が入った箱の文字にすることができます。
これより、k個の箱に入っている文字の種類数が2以上である場合の最小値を求めることができました。
また、k個の箱に入っている文字の種類数が1のとき、残るn-k文字の種類数で改めて場合分けします。
残るn-k文字の種類数が2種類以上のとき、辞書式順序の定義より、1つの箱に残った文字をすべて詰め込むのが最善であることが分かります。
また残るn-k文字の種類数が1種類のとき、同様に辞書式順序の定義より、すべての箱に残った文字を均等に詰め込むのが最善であることが分かります。
以上によりこの問題を解くことができました。

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

t=int(input())
for _ in range(t):
   n,k=map(int,input().split())
   s=list(input())
   s=sorted(s)
   if k==1: #箱が1つしかなければ、そこにすべての文字を詰め込むしかない
       print(''.join(map(str,s)))
   elif len(set(s))==1: #Sのすべての文字の種類数が1なら、すべての文字を均等に配るのが最善
       print(s[0]*((n+k-1)//k))
   else:
       if len(set(s[:k]))!=1: #先頭のK文字の種類数が2以上なら、先頭のK文字のうち最大のものが最小値となる
           print(s[k-1])
       else:
           tmp=s[0]
           s=s[k:]
           if len(set(s))!=1: #残ったN-K文字の種類数が2以上なら、1つの箱にすべての文字を詰め込むのが最善
               print(tmp+''.join(map(str,s)))
           else: #種類数が1のとき、残った文字を均等に配るのが最善
               print(tmp+s[0]*((n-k+k-1)//k))

D問題:

i日目の昼の開始時点(分裂する数を選ぶ前)のバクテリアの個数をk、各バクテリアのサイズの総数をmとおくと、m+2k<=n<=2+6kを満たすとき、(i+1)日後の夜に各バクテリアのサイズの総数をnにすることができます。
以下これを示します。
i日目の昼に分裂させるバクテリアの数をdとおくと、i日目の夜の各バクテリアのサイズの総数はm+(k+d)となります。
また、(i+1)日目の昼に分裂させることのバクテリアの数は0からk+dの間の任意の数で、これより(i+1)日目の各バクテリアのサイズの総数は、m+2(k+d)からm+3(k+d)の間の任意の値を取ります。
dは0からkの間の任意の整数を取り、[m+2(k+d),m+3(k+d)]が重ならないことはないので、結局(i+1)日目の夜に実現できる各バクテリアのサイズの総数はm+2kからm+6kまでの任意の値であることが分かりました。
また、dが分かっているとき、i日目の昼にはd体のバクテリアを分裂させ、k=k+d,m=m+kと更新し、(i+1)日目の昼にはn-m-k体のバクテリアを分裂させることで、(i+1)日目の夜に各バクテリアのサイズの総数がnに一致します。
また、上記の条件を満たさないとき、k=k*2,m=m+kと更新すればよいです(このように更新したとき、k日目の夜に実現できる各バクテリアのサイズの総数の区間が4以上のすべての整数を覆うことが分かります)。
m+2k<=n<=2+6kを満たすとき、m+2(k+d)<=n<=m+3(k+d)を満たすdを愚直に求めると、最悪の場合O(N)かかってしまい制限時間に間に合いませんが、dを2分探索により求めることができるので、この問題をO(logN)で解くことができました。
ただし、コーナーケースとしてバクテリアのサイズの総数をnにするのに1ステップしかかからない場合、具体的にはn=2とn=3の場合があり、これについては個別に解を記述する必要があります。

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

t=int(input())
for _ in range(t):
   n=int(input())
   if n==2: #N=2とN=3のときは具体的に答えを書く
       print(1)
       print(0)
   elif n==3:
       print(1)
       print(1)
   else: #そうでないときは上記の方法で答えを求められる
       k=1
       m=1
       ans=[]
       for _ in range(1000):
           if m+2*k<=n<=m+6*k: #1日後の夜に総数をNにできるとき、そのような操作を具体的に求める
               break
           else: #そうでないときkを2倍にして総数をk増やす
               ans.append(k)
               k*=2
               m+=k
       l=-1
       r=k+1
       while 1: #0<=d<=kの範囲で1日後の夜に総数をNにできるようなdを2分探索で求める
           mid=(l+r)//2
           if m+2*(k+mid)<=n<=m+3*(k+mid):
               ans.append(mid)
               k+=mid
               m+=k
               ans.append(n-m-k)
               break
           elif n<m+2*(k+mid):
               r=mid
           elif n>m+3*(k+mid):
               l=mid
       print(len(ans))
       print(*ans)