Educational Codeforces Round 68(Rated for Div.2) A～D解説

Educational Codeforces Round 68(Rated for Div.2)のA～Dまでの解説です。
コンテスト中にはA～Dまでの4完しました(Codeforces初の4完+初青レートに到達したので嬉しかったです＊)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1194
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/68405

A問題:

サンプルケースを見ると、与えられた値を2倍した値を返せばよさそうな雰囲気が漂っていますが、実験してアイデアが正しいかを確かめてみましょう。
1 2 3 4 5 6 7 8という数列を考えます。
最初の操作では、左から1番目の数が消えるので数列は2 3 4 5 6 7 8という形になります。
次の操作では、左から2番目の数が消えるので数列は2 4 5 6 7 8という形になります。
その次の操作では、左から3番目の数が消えるので数列は2 4 6 7 8という形になります。
これを一般化すると、n番目の操作を行う時点では数列の左端にn-1個の偶数があることが分かり、これからn番目の操作で奇数が消えることが分かります。
したがって、最終的な数列はすべて偶数になるので、与えられた値を2倍した値を返せばよいことが分かります(サンプルケースから何となく解法が推察できる問題はそれなりにあるので、困ったときはサンプルケースの気持ちになってみるのもひとつの手だと思います)。

B問題:

クロスとは、すくなくとも1つの縦列と1つの横列が、どちらもすべて黒マスになっている状態のことを指します。
このことを踏まえると、クロスを構成する縦列の選び方と横列の選び方は独立であることが分かります(∵ある縦列とある横列を選んだとき、それらの列が交わるのはただ1マスだけなので、縦列と横列のそれぞれについて、操作回数が最小になるような列のみを考えればよいです)。
したがって、まずすべての縦列とすべての横列に対し、操作回数が最小になるようなものの候補を2重ループにより調べ、もしも縦列と横列のうち少なくともどちらか一方の操作回数が0になる場合は、(縦列の操作回数)と(横列の操作回数)の和が答えになります(∵どちらかの操作回数が0であるとき、操作回数が0である列ともう一方の列の交わるマスが必ず黒マスであることからいえます)。
縦列と横列の両方の操作回数が1以上の場合は、操作回数が最小になるような縦列の候補と横列の候補に対し、それらの列が交わるマスが白マスとなるような組み合わせがあれば、(縦列の操作回数)と(横列の操作回数)の和-1が答えとなり、そのような組み合わせがなければ、(縦列の操作回数)と(横列の操作回数)の和が答えとなります。
以上の操作は1回あたりO(HW)で行うことができ、制約よりこの解法は制限時間に間に合うことが分かります。

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

q=int(input())
for _ in range(q):
 n,m=map(int,input().split())
 board=[input() for _ in range(n)]
 cn=10**10
 candn=[]
 cm=10**10
 candm=[]
 for i in range(n):
   tmp=0
   for j in range(m):
     if board[i][j]=='.':
       tmp+=1
   if tmp<cn:
     cn=tmp
     candn=[i]
   elif tmp==cn:
     candn.append(i)
 for i in range(m):
   tmp=0
   for j in range(n):
     if board[j][i]=='.':
       tmp+=1
   if tmp<cm:
     cm=tmp
     candm=[i]
   elif tmp==cm:
     candm.append(i)
 if cn==0 or cm==0:
   print(cn+cm)
 else:
   flag=False
   for i in candn:
     for j in range(m):
       if board[i][j]=='.':
         if j in candm:
           flag=True
   if flag==False:
     print(cn+cm)
   else:
     print(cn+cm-1)

C問題:

元の文字列から目標の文字列を作るためには、少なくとも元の文字列が目標の文字列の(連続とはかぎらない)部分文字列になっている必要があります(∵この問題では文字の削除を行うことができないので、元の文字列が目標の文字列の部分文字列になっていないとき、「はみでた部分」を一致させることができません)。
したがって、まず元の文字列が目標の文字列の部分文字列になっているかどうかを判定します。
これは目標の文字列を左からみていき、元の文字列のk番目の文字と一致していればkを1つすすめ、最終的にkが元の文字列の長さまで到達しているかどうかで判定することができます。
kが元の文字列の長さまで到達していれば元の文字列は目標の文字列の部分文字列となっていて、そうでなければ元の文字列は部分文字列にはなっていないといえます。
次に、元の文字列が目標の文字列の部分文字列になっているとき、実際に目標の文字列を作ることができるかを判定します。
これは各アルファベットに対して、(元の文字列に現れる各アルファベットの数)+(追加できる文字列に現れる各アルファベットの数)>=(目標の文字列に現れる各アルファベットの数)を満たすかどうかを確かめることで判定できます。
すべてのアルファベットについてこの不等式を満たせば目標の文字列を作ることができ、そうでないとき、目標の文字列を作ることはできません。
以上の操作は1回あたりO(T+S+P)で行うことができ、制約よりこの解法は制限時間に間に合うことが分かります。

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

q=int(input())
for _ in range(q):
 s=input()
 ls=len(s)
 t=input()
 lt=len(t)
 p=input()
 nt=''
 pos=0
 for i in range(len(t)):
   if pos==ls:
     nt+=t[i:]
     break
   if t[i]==s[pos]:
     pos+=1
   else:
     nt+=t[i]
 if pos!=ls:
   print('NO')
 else:
   cnt=[0]*26
   check='abcdefghijklmnopqrstuvwxyz'
   flag=True
   for char in p:
     for i in range(26):
       if char==check[i]:
         cnt[i]+=1
   for char in nt:
     for i in range(26):
       if char==check[i]:
         cnt[i]-=1
         if cnt[i]<0:
           flag=False
   if flag==True:
     print('YES')
   else:
     print('NO')

D問題:

このゲームは、N番目のマスからスタートし、自分の手番では1または2またはK歩左に移動することができ、自分の手番で0番目のマスに到達したプレイヤーが負けになる、というゲーム(以下1-2-Kゲームと呼びます)になっています。
K歩左に動くことがゲームの勝敗にどのような影響を与えるのかを考えるのは難しいので、まずは自分の手番では1または2歩左に移動することができるゲーム(以下1-2ゲームと呼びます)について考えてみることにしましょう。
このゲームは非常に有名なので、スタートするマスの番号によって勝敗を決める方法を知っている方もいると思います。
実はこのゲームでは、相手が何歩移動したかにかかわらず、2手で合計3歩移動することができます。
これより、スタートするマスの番号が3の倍数であれば後攻の勝ち、そうでなければ先攻の勝ちになることが分かります。
この勝敗条件はDPによって求めることができます。
具体的には、Trueを先攻の勝ち、Falseを先攻の負けに割り振るとき、初期値としてDP[0]=False、DP[1]=[2]=Trueを与えると、DP[n](n>=3)の値を、if DP[n-1] == True and DP[n-2] == True then DP[n]=False else DP[n]=Trueとして更新することで、N番目のマスでどちらが勝つかを判定することができます。
1-2ゲームについて、DPによって勝敗条件を求められるということが分かったので、元の1-2-KゲームについてもDPによって勝敗条件を求められないかを考えてみます。
1-2-KゲームのDPの更新は、初期値としてDP[0]=False、DP[1]=[2]=Trueを与えると、DP[n](n>=3)の値を、if DP[n-1] == True and DP[n-2] == True and DP[n-k] == True then DP[n]=False else DP[n]=Trueとして更新できることが分かります。
ここで、Kが3の倍数でないとき、DP[n-k] == Falseとなるようなnについて、DP[n-1] == FalseまたはDP[n-2] == Falseを満たすことが分かります(∵Kは3の倍数でないので、n-k ≡ 1(mod 3)またはn-k ≡ 2(mod 3)が成り立ちます)。
したがって、Kが3の倍数でないときは、1-2-Kゲームの勝敗と1-2ゲームの勝敗は一致することになります。
Kが3の倍数のとき、DP[n-k] == Falseとなるようなnについて、DP[n-1] == TrueかつDP[n-2] == Trueを満たすnが存在することが分かります(∵n-k ≡ n(mod3)より、nが3の倍数のときDP[n-1] == TrueかつDP[n-2] == Trueを満たします)。
DP[n-k] == Falseとなる最小のnはn=kのときで、このとき上記の議論より、DP[n] == True、DP[n+1] == Falseとなります。
したがって、Kが3の倍数のときは、ゲームの勝敗の周期がK+1になることがいえます。
このとき、NをK+1で割ったあまりMについて見て、これが3の倍数であれば後攻の勝ち、そうでなければ先攻の勝ちとなります。
ただし、DPの更新から明らかですが、NをK+1で割ったあまりMがKに等しいときは先攻の勝ちとなります。
以上より、Kが3の倍数でないときは、Nが3の倍数であれば後攻の勝ち、そうでなければ先攻の勝ち、Kが3の倍数のときは、NをK+1で割ったあまりMについて、Mが3の倍数かつMとKが等しくないのであれば後攻の勝ち、そうでなければ先攻の勝ちとなることが分かります(ちいさなケースについて実験することでも周期性を発見することができます)。

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

q=int(input())
for _ in range(q):
 n,k=map(int,input().split())
 if n==0:
   print('Bob')
 elif n==1 or n==2:
   print('Alice')
 else:
   if n==k:
     print('Alice')
   else:
     if k==1 or k==2 or k>n:
       if n%3==0:
         print('Bob')
       else:
         print('Alice')
     else:
       if k%3!=0:
         if n%3==0:
           print('Bob')
         else:
           print('Alice')
       else:
         m=n%(k+1)
         if m%3==0 and m!=k:
           print('Bob')
         else:
           print('Alice')