Codeforces Round #573(Div.2) A～E解説
Codeforces Round #573 (Div.2)のA～Eまでの解説です。
コンテスト中にはA～Dまでの4完(Bはコーディングの凡ミスでSystem Test Failed)、その後30分ほどかけてEも解きました(Bの凡ミスがなければ青レートに到達できていたので少し悔しかったです)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1191
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/68314
A問題:
状態が4x3=12通りしかないので手元で実験しましょう。
元のあまりが0～3のそれぞれについて実験すると、
・元のあまりが0のときは"1 A"
・元のあまりが1のときは"0 A"
・元のあまりが2のときは"1 B"
・元のあまりが3のときは"2 A"
と出力すればよいことがわかります(この問題に限らず、状態数が少ない場合で実験してみると法則に気付けることがあります)。
B問題:
文字の種類について場合分けします。
・文字の種類が3種類のとき
文字の種類が違うため与えられた牌を組み合わせることはできず、2回のツモが必要です(同じ牌を2つ引けばよいので最悪でも2回のツモで条件を満たします)。
・文字の種類が2種類のとき
鳩ノ巣原理より同じ種類の文字が2つあるので、これらの牌の数字をnum1,num2とします。
このとき、0<=abs(num1-num2)<=2であれば1回のツモが、そうでなければ2回のツモが必要です(麻雀用語を用いるなら、abs(num1-num2)=0のときは2つの牌がトイツ、abs(num1-num2)=1のときはリャンメンまたはペンチャン、abs(num1-num2)=2のときはカンチャンの状態になります)。
・文字の種類が1種類のとき
もともと数字がすべて同じ(コーツ)、もしくは数字が3連番になっている(シュンツ)とき0回のツモが必要です。
そうでないときは、3つの牌の数字をnum1,num2,num3として、文字の種類が2種類のときの議論と同様にして判定すればよいです。
具体的には、abs(num1-num2),abs(num2-num3),abs(num3-num1)をそれぞれ調べ、どれかが0以上2以下であれば1回のツモ、どれもが0以上2以下を満たさなければ2回のツモが必要です。
サンプルコード(Python):
https://codeforces.com/contest/1191/submission/56938859
arr=list(map(str,input().split()))
num1=int(arr[0][0])
num2=int(arr[1][0])
num3=int(arr[2][0])
str1=arr[0][1]
str2=arr[1][1]
str3=arr[2][1]
if str1==str2 and str2==str3:
if num1==num2 and num2==num3:
print(0)
else:
arr2=[num1,num2,num3]
arr2=sorted(arr2)
if arr2[0]==arr2[1]-1 and arr2[1]==arr2[2]-1:
print(0)
else:
if 0<=abs(num1-num2)<=2:
print(1)
elif 0<=abs(num1-num3)<=2:
print(1)
elif 0<=abs(num2-num3)<=2:
print(1)
else:
print(2)
elif str1==str2:
if abs(num1-num2)==0 or abs(num1-num2)==1 or abs(num1-num2)==2:
print(1)
else:
print(2)
elif str1==str3:
if abs(num1-num3)==0 or abs(num1-num3)==1 or abs(num1-num3)==2:
print(1)
else:
print(2)
elif str2==str3:
if abs(num2-num3)==0 or abs(num2-num3)==1 or abs(num2-num3)==2:
print(1)
else:
print(2)
else:
print(2)
C問題:
削除すべきアイテムの配列を左端から見ていき、今見ている要素からk個先の要素までの要素のうち、同じページに属している要素が何個あるかを数え、次に見る要素の位置を同じページに属している要素の数だけ右に動かし操作回数を+1するという操作を、元の配列の要素をすべてチェックするまで繰り返します。
n個の要素を削除したとき、まだ見ていない要素の位置は、(元の位置)-nで表すことができます。
したがって、各要素が何ページ目に属しているかは、((要素の値)-(削除した要素の数)-1)/kで計算できます。
同じページに含まれている可能性があるのは、今見ている要素からk個先の要素までなので、この範囲を毎回チェックすればよいです。
単純に考えると毎回k個の要素を確認するためO(KM)となり間に合わないように感じますが、各時点で始点となる要素の位置は常に右に移動していくので、しゃくとり法の考え方が適用でき、この問題はO(M)で解けることが分かります。
実装の際は、元の配列にm個の0を番兵として加えておくと実装が楽になります。
サンプルコード(Python):
https://codeforces.com/contest/1191/submission/56909077
n,m,k=map(int,input().split())
arr=list(map(int,input().split()))
arr+=[0]*m #番兵
ans=0 #答えとなる操作回数
pos=0 #今見ている要素の番号(=削除した要素の数)
while arr[pos]!=0:
page=(arr[pos]-pos-1)//k #何ページ目かの判定
tmp=1 #この操作で削除する要素の個数
for i in range(1,k): #k個先までの要素を見る
if pos+i>=2*m-1: #高々m個見れば十分
break
if (arr[pos+i]-pos-1)//k==page: #今見ている要素と同じページに属しているかの判定
tmp+=1
else:
break
pos+=tmp #削除した要素の数を加える
ans+=1 #操作が終わったので操作回数を+1する
print(ans)D問題:
石の数が同じpileを作らないように操作するという条件から、要素の数がn個のとき、最終的に[0,1,2,…n-1]という状態に到達することが分かります(この手の問題はちいさなケースから実験して一般的な形を導くのがよいです)。
このとき、石の数を[0,1,2,…,n-1]にしたプレイヤーが勝利することは明らかです。
この状態に至るまでの操作手順は勝敗に関係がないので、(元々の石の数の配列の和)-n(n-1)/2の偶奇を確かめることで、O(N)で先攻が勝つか後攻が勝つかを判定できます。
(元々の石の数の配列の和)-n(n-1)/2が奇数となるときは先攻の勝利、偶数となるときは後攻の勝利となります。
しかしながら、初期状態がある条件を満たすときには、偶奇に関わらず後攻の勝利となります。
その条件は以下の3つです。
・元々の石の数の配列に0が2つ以上ある
→先攻がどのような操作を行っても0が2つ以上あるため先攻の負けになる
・同じ数が2ペア以上ある、もしくは同じ数が3つ以上ある
→先攻がどのような操作を行っても同じ数のペアが残るため先攻の負けになる
・ペアが1つしかないが、(ペアになっている石の数-1)を満たす要素が1つ以上ある
→先攻がペアを解消しないとそもそも負け、ペアを解消すると(ペアの数-1)個の石のpileが2つ以上あることになるので結局負けになる
以上の条件を元々の石の数の配列について確かめればよいです。
連想配列などを用いることで石の数の種類と出現回数を数えることができ、それらを元に以上の条件を判定することができます。
サンプルコード(Python):
https://codeforces.com/contest/1191/submission/58266989
n=int(input())
arr=list(map(int,input().split()))
dic={}
for val in arr: #石の高さの個数を数える
if val not in dic:
dic[val]=1
else:
dic[val]+=1
flag1=True
if 0 in dic: #上記の条件1
if dic[0]>=2:
flag1=False
cnt=0
for val in dic.keys(): #上記の条件2
if dic[val]>=3:
flag1=False
break
if dic[val]==2:
cnt+=1
if val-1 in dic: #上記の条件3
flag1=False
break
if cnt>=2: #上記の条件2
flag1=False
if flag1==False: #上記の条件のいずれかを満たせば後攻の勝ち
print('cslnb')
else:
flag2=(n*(n-1)//2-sum(arr))%2
if flag2==1: #
print('sjfnb')
else:
print('cslnb')
E問題:
先攻の勝利となるのは、1回の操作ですべてを0または1にできるとき、すなわち1+(右端の0の位置)-(左端の0の位置)<=k、もしくは1+(右端の1の位置)-(左端の1の位置)<=kを満たすときです。
また後攻の勝利となるのは、先攻がどのような区間を選んだとしても、その区間をすべて1にしたとき1+(右端の0の位置)-(左端の0の位置)<=kを、その区間をすべて0にしたとき1+(右端の1の位置)-(左端の1の位置)<=kを、それぞれ満たすときです。
それ以外の場合には、先攻の操作した区間について後攻が逆の操作を行う、もしくは後攻が操作した区間に対して先攻が逆の操作を行うことにより、永遠にゲームが終了しなくなるため、引き分けとなります。
まず、先攻が勝利するかどうかを判定する方法を考えます。
これは文字列の左端の0,1の位置と右端の0,1の位置を求めれば判定できるため、O(N)で行うことができます。
次に、後攻が勝利するかどうかを判定する方法を考えます。
この判定を素直に実装すると、塗りつぶしかたが2種類、区間の数が(N-K+1)種類、区間について操作を行ったあとの文字列について、左端の0,1の位置と右端の0,1の位置を求めるのにO(N)かかるため、トータルでO(N^2)かかり制限時間に間に合いません。
そのため、O(N)もしくはO(NlogN)で判定する方法がないかを考えます。
ある区間を選ぶことは区間の始点を選ぶことと同値ですので、以下始点について見ます。
始点iを選んだとき、その区間の左端lはl=i、右端rはr=i+k-1として表すことができます。
このl,rについて、0が何番目の位置にあるかの配列pos0と、1が何番目の位置にあるかの配列pos1を2分探索すると、その区間をすべて0または1にしたときの文字列の左端の0,1の位置と右端の0,1の位置をO(logN)で判定することができます。
これにより、後攻が勝利するかどうかの判定をO(NlogN)で行うことができるため、この問題を解くことができます。
サンプルコード(Python):
https://codeforces.com/contest/1191/submission/56938895
from bisect import bisect_left
n,k=map(int,input().split())
s=input()
l=len(s)
flag=-1 #初期値は引き分けとしておく
pos0=[-1] #2分探索のための番兵
pos1=[-1]
for i in range(l):
if s[i]=='0':
pos0.append(i)
else:
pos1.append(i)
pos0.append(10**18) #2分探索のための番兵
pos1.append(10**18)
d0=1+(pos0[-2]-pos0[1]) #2つの0の最長の距離
d1=1+(pos1[-2]-pos1[1]) #2つの1の最長の距離
if min(d0,d1)<=k: #0または1について、その距離がk以下であれば先攻の勝ちとなる
flag=1
else:
for i in range(n-k+1): #始点iについて見る
l=i #区間[l,r]について操作を行う
r=i+k-1
#区間[l,r]をすべて0にする操作を考える
tposl=bisect_left(pos1,l)
tposr=bisect_left(pos1,r)
if pos1[tposl-1]==-1: #位置i<=lに1がなければ、左端の1の位置が変化する
tl=-1
else:
tl=pos1[tposl-1]
if pos1[tposr]==r: #位置i>=rに1がなければ、右端の1の位置が変化する
tr=pos1[tposr+1]
if tr==10**18:
tr=-1
else:
tr=pos1[tposr]
if tr==10**18:
tr=-1
td1=0
if tl==-1: #位置i<=lに1がなければ、1の左端はi>=rの範囲での左端の1となる
td1=1+(pos1[-2]-tr)
elif tr==-1: #位置i>=rに1がなければ、1の右端はi<=lの範囲での右端の1となる
td1=1+(tl-pos1[1])
else: #そうでなければ、2つの1の最長距離は元の1の左端と1の右端から変わらない
td1=1+(pos1[-2]-pos1[1])
#区間[l,r]をすべて1にする操作を考える
tposl=bisect_left(pos0,l)
tposr=bisect_left(pos0,r)
if pos0[tposl-1]==-1: #位置i<=lに0がなければ、左端の0の位置が変化する
tl=-1
else:
tl=pos0[tposl-1]
if pos0[tposr]==r: #位置i>=rに0がなければ、右端の0の位置が変化する
tr=pos0[tposr+1]
if tr==10**18:
tr=-1
else:
tr=pos0[tposr]
if tr==10**18:
tr=-1
if tl==-1: #位置i<=lに1がなければ、1の左端はi>=rの範囲での左端の1となる
td2=1+(pos0[-2]-tr)
elif tr==-1: #位置i>=rに1がなければ、1の右端はi<=lの範囲での右端の1となる
td2=1+(tl-pos0[1])
else: #そうでなければ、2つの1の最長距離は元の1の左端と1の右端から変わらない
td2=1+(pos0[-2]-pos0[1])
td=max(td1,td2) #これらの距離の最大値がkより大きければ条件を満たさない
if td>k:
break
else: #すべての距離がk以下であれば後攻の勝利となる
flag=0
if flag==1: #先攻の勝ち
print('tokitsukaze')
elif flag==0: #後攻の勝ち
print('quailty')
elif flag==-1: #それ以外の場合は引き分け(永遠にゲームが終わらない)となる
print('once again')