Codeforces Round #574(Div.2) A～D2解説

たのん

Codeforces Round #574 (Div.2)のA～D2までの解説です。
コンテスト中にはA～D1までの4完(Aは考察ミスでSystem Test Failed)、その後20分ほどかけてD2も解きました(D2の考察は済んでいたものの実装で手間取り5完を逃したうえ、Aで考察ミスをやらかしたために水レに逆戻りしました…)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1195
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/68471

A問題:

ある種類の飲み物を偶数杯配っても、好みの飲み物を受け取る人数の最大値は変化しません。
したがって、すべての種類の飲み物について、元の数を越えない最大の偶数杯を先に配ってしまっても問題ありません。
この操作によって、すべての種類の飲み物について、その飲み物が好きな人数の残りは0または1人になります。
その飲み物が好きな人数の残りが1人の飲み物の数をkとすると、飲み物は2杯で1セットになっているため、少なくともk/2(小数点以下は切り捨て)種類の飲み物は、その飲み物が好きな人に配ることができません。
したがって答えは、(元の人数n)-k/2(小数点以下は切り捨て)となります。
この答えは、すべての種類の飲み物について、その飲み物が好きな人数が奇数であるような飲み物の数を数え、その数をkとすることで、O(N)で求めることができます。

B問題:

i回目のキャンディの追加ではi個のキャンディが追加されることから、k回キャンディを追加する操作を行ったとき、追加されるキャンディは全部でk(k+1)/2個になります。
操作終了時に残っているキャンディは制約より10^9個以下なので、k<=10^5までのすべてのkについて、追加したキャンディの数k(k+1)/2から食べたキャンディの数(n-k)を引いた値k(k+1)/2-(n-k)が、操作終了時に残っているキャンディの個数に一致しているかどうかを調べ、一致していればn-kを答えとして出力すればよいです。
この計算量はO(K)<=10^5より、この問題を解くことができました。

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

n,k=map(int,input().split())
for i in range(10**5):
 if (i*(i+1))//2-(n-i)==k:
   print(n-i)

C問題:

各列について、チームに入れられるのは1人までであること、同じ行について、連続して同じ行からチームに入れることはできないことに注意します。
問題は適切にチームメンバーを選んだときのチームメンバーの身長の総和の最大値を求めるもので、いかにもDPで解けそうな雰囲気があるので、DPで解くことを考えます。
各列iについて、2列前までで1行目を選んだときに取りうる最大の値をDP[i][0][0]、2列前までで2行目を選んだときに取りうる最大の値をDP[i][0][0]、1列前までで1行目を選んだときに取りうる最大の値をDP[i][1][0]、1列前までで2行目を選んだときに取りうる最大の値をDP[i][1][1]、列iで1行目を選んだときに取りうる最大の値をDP[i][2][0]、列iで2行目を選んだときに取りうる最大の値をDP[i][2][1]とします。
2列前までに取りうる値は、今見ている列でどちらの行を取るかに関わらず選ぶことができ、一方、1列前までに取りうる値は、今見ている列でどちらの行を取るかによって選ぶことができるかどうかが変わります。
これを踏まえると、列iでのDPは以下のように更新できます。
DP[i][0][0]=DP[i-1][1][0]、DP[i][0][1]=DP[i-1][1][1]、DP[i][1][0]=DP[i-1][2][0]、DP[i][1][1]=DP[i-1][2][1]、DP[i][2][0]=max(DP[i-1][0][0]+(列iの1行目の値),DP[i-1][0][1]+(列iの1行目の値),DP[i-1][1][1]+(列iの1行目の値))、DP[i][2][1]=max(DP[i-1][0][0]+(列iの2行目の値),DP[i-1][0][1]+(列iの2行目の値),DP[i-1][1][0]+(列iの2行目の値))
答えは、n列目まで見たときのDPの値DP[n-1][2][0]とDP[n-1][2][1]の最大値となります。
サンプルコード(Python):
https://codeforces.com/contest/1195/submission/57222000

n=int(input())
arr1=list(map(int,input().split())) #1行目の値
arr2=list(map(int,input().split())) #2行目の値
dp=[[[0]*2 for _ in range(3)] for _ in range(n)]
dp[0][2][0]=arr1[0] #初期値の設定(1行目の値の設定)
dp[0][2][1]=arr2[0]
for i in range(1,n):
 #DPの更新
 dp[i][0][0]=dp[i-1][1][0]
 dp[i][0][1]=dp[i-1][1][1]
 dp[i][1][0]=dp[i-1][2][0]
 dp[i][1][1]=dp[i-1][2][1]
 dp[i][2][0]=max(arr1[i]+dp[i][0][0],arr1[i]+dp[i][0][1],arr1[i]+dp[i][1][1])
 dp[i][2][1]=max(arr2[i]+dp[i][0][0],arr2[i]+dp[i][0][1],arr2[i]+dp[i][1][0])
print(max(dp[n-1][2][0],dp[n-1][2][1]))

D1問題:

すべての組み合わせを試す方法を考えると、計算量がO(N^2)となりN<=10^5より制限時間に間に合いません。
したがって、より効率的な方法を考える必要があります。
D1では制約としてすべての数の桁数が等しいという条件が与えられているので、ちいさなケースで実験して、どのような性質を持っているかを推測します。
2
12 34
について考えると、関数fによって生成される数は、
1122
1324
3142
3344
の4つになります。
このとき、生成された数の各桁に注目すると、元の数のi桁目の数字は、生成された数の2*i桁目と2*i-1桁目に現れることが分かります。
また、生成された数の各桁には、元の数の個数n個の数が現れることが分かります。
したがって、与えられた数のそれぞれについて、各桁の数を見て、各桁の数*(元の数の個数)*(10^(2*i-1)+10^(2*i-2))を計算すればよいです。
これより、全体でO(N)でこの問題を解くことができます(定数倍は高々10倍(各入力の数の桁数の値)で済むので、制限時間に間に合うことが分かります)。
サンプルコード(Python):
https://codeforces.com/contest/1195/submission/57226026

n=int(input())
arr=list(map(str,input().split()))
l=len(arr[0]) #入力された数の桁数の取得
mod=998244353
ans=0
modarr=[0]*(2*l)
for i in range(2*l):
 modarr[i]=((10**i)%mod)%mod #10^iのmodの前処理
for s in arr:
 for i in range(1,l+1): #入力された数の各桁について計算   
   tmp=int(s[-i])
   ans+=(n*tmp*modarr[2*i-1])%mod
   ans+=(n*tmp*modarr[2*i-2])%mod
print(ans%mod)

D2問題:

D1から、入力される数の桁数がすべて等しいという制約をなくした問題です。
この問題も、D1と似たような流れで解くことができます。
ちいさなケースで実験すると、元の数でi桁目の数は、関数fで生成された数において、i桁目で2*(1桁の数の個数)回、(i+1)桁目で2*(2桁の数の個数)回、(i+2)桁目で2*(3桁の数の個数)回、(i*2-3)桁目で2*(i-1桁の数の個数)回、(i*2-1)桁目で(i桁の数の個数)+(i+1桁以上の数の個数)+2*(i-1桁の数の個数)回、(i*2)桁目で(i桁の数の個数)+(i+1桁以上の数の個数)回現れることが分かります。
ただし、元の数が1桁、もしくは2桁の場合は(i*2-1)桁目で(i桁の数の個数)+(i+1桁以上の数の個数)+2*(i-1桁の数の個数)回と、(i*2)桁目で(i桁の数の個数)+(i+1桁以上の数の個数)回のみを考えます。
制約より各入力の数の桁数は10以下なので、事前に1～10桁の数の個数と、1桁～10桁以上の数の個数の両方を求めておくことで、この問題をO(N)で解くことができます(D1と同様にして考えると定数倍は高々50倍程度であることが分かり、制限時間に間に合うことが分かります)。
サンプルコード(Python):
https://codeforces.com/contest/1195/submission/57240609

n=int(input())
arr=list(map(str,input().split()))
cnt=[0]*12
for val in arr:
 cnt[len(val)]+=1 #i桁の数がいくつあるかを計算
acumcnt=[0]*12
acumcnt[10]=cnt[10]
for i in range(9,-1,-1):
 acumcnt[i]=acumcnt[i+1]+cnt[i] #i桁以上の数がいくつあるかを計算
mod=998244353
ans=0
modarr=[0]*(20)
for i in range(20):
 modarr[i]=((10**i)%mod)%mod #10^iのmodの前処理(高速化)
for s in arr:
 for i in range(1,len(s)+1):
   tmp=int(s[-i]) #入力された数を右から見るために-符号で文字を指定しています
   if i==1: #1桁目の場合
     ans+=((acumcnt[2]+cnt[1])*tmp*modarr[1])%mod
     ans+=((acumcnt[2]+cnt[1])*tmp*modarr[0])%mod
   elif i==2: #2桁目の場合
     ans+=((acumcnt[3]+cnt[2])*tmp*modarr[3])%mod
     ans+=((acumcnt[3]+cnt[2]+2*cnt[1])*tmp*modarr[2])%mod
   else: #それ以外の場合
     for j in range(i,2*i):
       if j==2*i-1:
         ans+=((acumcnt[i+1]+cnt[i])*tmp*modarr[j])%mod
       elif j==2*i-2:
         ans+=((acumcnt[i+1]+cnt[i]+2*cnt[i-1])*tmp*modarr[j])%mod
       else:
         ans+=(2*cnt[j-i+1]*tmp*modarr[j])%mod
print(ans%mod)

この記事が気に入ったらサポートをしてみませんか？