Codeforces Round #578(Div.2) A～E解説
Codeforces Round #578 (Div.2)のA～Eまでの解説です。
コンテスト中にはA/B/Eの3完+Bの考慮漏れで1WA(CはPythonでの大きい数の扱いの考慮漏れでSystem Test Failedしました…)でした(CでSystem Test Failedしたときはかなり焦りましたが、無事青に復帰することができました)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1200
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/69035
A問題:
来た客をどの客室に案内すればよいかを効率的に求めるのは難しいですが、制約よりN<=10^5、客室の数は10なので、毎回条件を満たす客室を愚直に求めても計算量は高々10^6のオーダーとなりこの問題を解くことができます(CodeforcesのA問題は肝が冷える問題が多く不安になりがちですが、落ち着いて解いていきましょう)。
B問題:
今いる階層のブロック数がmax(次の階層のブロック数-K,0)以上であれば、今いる階層のブロック数がmax(次の階層のブロック数-K,0)に一致するまでブロックを拾い、そうでなければ手持ちのブロックから今いる階層にブロックを積むという操作を行うのが最善です(次の階層のブロック数-Kが0未満のときは今いる階層のブロック数が0になるまでしかブロックを拾うことはできません)。
したがって、各段(i=1 to N-1)において上記の操作が可能かどうかを確かめればよいです。
これはO(N)で判定することができ、キューがT個あるため、トータルでO(TN)でこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1200/submission/58585217
t=int(input())
for _ in range(t): #T個のキューについて判定を行う
n,m,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n-1):
if arr[i]<max(arr[i+1]-k,0): #今の階層のブロック数が次の階層のブロック数-Kに満たない場合は手持ちのブロックからブロックを積む
if m<max(arr[i+1]-k,0)-arr[i]: #手持ちのブロックすべてを積んでも次の階層のブロック数-Kに届かないときクリアできない
print('NO')
break
else:
m-=max(arr[i+1]-k,0)-arr[i]
else: #ブロックを拾えるときは拾えるだけブロックを拾う
m+=arr[i]-max(arr[i+1]-k,0)
else: #最下段まで到達できたらクリアとなる
print('YES')
C問題:
外側の隔壁と内側の隔壁がちょうど重なる回数がいくつかを考えます。
すると、そのような回数はGCD(外側の隔壁の枚数,内側の隔壁の枚数)で求められることが分かります。
これを用いると、外側の各部屋と内側の各部屋をいくつかのグループに分けることができ、2つの部屋が同一のグループに属しているとき部屋間の移動が可能、そうでないとき移動は不可能であると判定できます。
各部屋のグループ分けは、g=GCD(外側の隔壁の枚数,内側の隔壁の枚数)とすると、外側の部屋であれば(部屋番号-1)/(外側の部屋数/g)の小数点を切り捨てた値、内側の部屋であれば(部屋番号-1)/(内側の部屋数/g)の小数点を切り捨てた値として求めることができます。
GCDの計算はO(log(max(n,m)))で行うことができ、上記の判定はO(1)で行うことができるので、キューがQ個あるため全体としてO(log(max(n,m))Q)でこの問題を解くことができました(Pythonの場合、グループを表す数を正確に表すためにDecimalモジュールを使うなどの対策が必要になる気がします)。
サンプルコード(C++):
https://codeforces.com/contest/1200/submission/58622163
サンプルコード(Python):
https://codeforces.com/contest/1200/submission/58621087
from decimal import *
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
n,m,q=map(int,input().split())
g=gcd(n,m)
for _ in range(q):
sx,sy,gx,gy=map(int,input().split())
if sx==1: #内側の部屋の場合
s_group=Decimal((sy-1))//Decimal((n/g))
else: #外側の部屋の場合
s_group=Decimal((sy-1))//Decimal((m/g))
if gx==1: #内側の部屋の場合
g_group=Decimal((gy-1))//Decimal((n/g))
else: #外側の部屋の場合
g_group=Decimal((gy-1))//Decimal((m/g))
if s_group==g_group: #同じグループに属していれば移動可能、そうでなければ移動は不可能
print('YES')
else:
print('NO')
D問題:
愚直に計算するとO(N^4)かかってしまうので、考えるべき要素の個数を減らす方法を考えます。
まず、塗りつぶす際の始点の候補についてですが、塗りつぶす際の始点になり得るすべての点をみる必要があるためO(N^2)かかります(各行、各列についてはじめて黒マスが出てくるような高々2N個の点のみを考えれば十分なように感じますが、これには反例があるため結局すべての点をみる必要があります)。
したがって、各始点を選んだときに、すべてが白マスとなる行または列がいくつ増えるかをO(1)で判定する方法を考える必要があります。
これは、行と列のそれぞれについて、ある点からK個塗ったときに黒マスをすべて白マスにできるような頂点を2次元配列に乗せ、その累積和を取ることでO(1)で判定することができるようになります。
上記の判定方法に使う累積和は、以下のように実装することができます。
まず盤面のi行目についてはじめて黒マスが出てくる点firstと最後に黒マスが出てくる点lastを求め、これらの点の距離がK以下であればその点firstからK-(last-first+1)個さかのぼった点t(t=max(0,last-k+1) to first)についてcolumns[i][t]=1とします。
同様に、盤面のi列目についてもはじめて黒マスが出てくる点firstと最後に黒マスが出てくる点lastを求め、これらの点の距離がK以下であればその点firstからK-(last-first+1)個さかのぼった点t(t=max(0,last-k+1) to first)についてrows[t][i]=1とします。
上記の操作を行う際に、ある行、または列のすべてのマスが白であるような行、列の個数を数えておき、これをwhitesとします。
ついで、columns[i][j]をi列目について連続してK個みたときの1の個数を求めccount[0][i]に代入し、j=1 to n-k+1なるjについて、縦に連続してK個みたときの1の個数を求めccount[j][i]に代入します(j=n-k+1より大きいjについては、n-k+1まで戻ることで真に値を大きくすることができるため考える必要がありません)。
これはまず連続してK個みたときの1の個数を持っておき、その後1歩進むごとにcolumns[i][j+k-1]を足し、columns[i][j-1]を引くことでO(N)で求めることができます。
同様に、rows[i][j]をi行目について連続してK個みたときの1の個数を求めccount[i][0]に代入し、j=1 to n-k+1なるjについて、縦に連続してK個みたときの1の個数を求めrcount[i][j]に代入します。
以上の操作はO(N^2)で行うことができ、またこの操作を行っておくことで、各始点を選んだときにすべてが白マスとなる行または列がいくつ増えるかをccount[i][j]+rcount[i][j]としてO(1)で判定することができるようになります。
最終的な答えは、各頂点(i,j)についてwhites+ccount[i][j]+rcount[i][j]を求めたときの最大値となります。
以上によりこの問題がO(N^2)で解けることがいえ、制約よりこの問題を制限時間内に解けることが分かります。
サンプルコード(Python):
https://codeforces.com/contest/1200/submission/58628104
n,k=map(int,input().split())
board=[input() for _ in range(n)]
columns=[[0]*n for _ in range(n)]
rows=[[0]*n for _ in range(n)]
whites=0
for i in range(n): #各行について、K個塗ったときに黒マスをすべて白マスにできるような点の位置を求める
first=-1
last=0
flag=False
for pos in range(n):
if flag==False: #黒マスがはじめて出てきたときの位置を求める
if board[i][pos]=='B':
first=pos
flag=True
else:
if board[i][pos]=='B': #黒マスが最後に出てきたときの位置を求める
last=pos
if first==-1: #黒マスが一度も出てこなければ、その行のマスは全て白である
whites+=1
continue
if last==0: #黒マスが1回しか出てこないときは、最初の黒マスの位置と最後の黒マスの位置は一致する
last=first
if last-first<k: #最初と最後の黒マスの距離がK以下であれば、最初の黒マスの位置からK-(last-first+1)マスさかのぼった位置までの間で塗りはじめると、その行をすべて白マスにできる
for j in range(max(0,last-k+1),first+1):
columns[i][j]+=1
for i in range(n): #各列について、K個塗ったときに黒マスをすべて白マスにできるような点の位置を求める
first=-1
last=0
flag=False
for pos in range(n):
if flag==False: #黒マスがはじめて出てきたときの位置を求める
if board[pos][i]=='B':
first=pos
flag=True
else:
if board[pos][i]=='B': #黒マスが最後に出てきたときの位置を求める
last=pos
if first==-1: #黒マスが一度も出てこなければ、その列のマスは全て白である
whites+=1
continue
if last==0: #黒マスが1回しか出てこないときは、最初の黒マスの位置と最後の黒マスの位置は一致する
last=first
if last-first<k: #最初と最後の黒マスの距離がK以下であれば、最初の黒マスの位置からK-(last-first+1)マスさかのぼった位置までの間で塗りはじめると、その行をすべて白マスにできる
for j in range(max(0,last-k+1),first+1):
rows[j][i]+=1
ccounts=[[0]*n for _ in range(n)]
rcounts=[[0]*n for _ in range(n)]
for i in range(n): #各行の塗りはじめの点の位置を表す2次元配列を、各列についてみていく(あるx座標を選んだときに、いくつの行をすべて白で塗れるかを数える)
tmp=0
for j in range(k): #一番上からK個みたときの1の個数を数える
tmp+=columns[j][i]
ccounts[0][i]=tmp
for j in range(1,n-k+1): #1歩進むごとに、今いるマスの値を1の個数に加え、最初にいたマスの値を1の個数から引く(j=n-k+1以降のjについては考える必要はない)
tmp+=columns[j+k-1][i]
tmp-=columns[j-1][i]
ccounts[j][i]=tmp
for i in range(n): #各行の塗りはじめの点の位置を表す2次元配列を、各行についてみていく(あるy座標を選んだときに、いくつの列をすべて白で塗れるかを数える)
tmp=0
for j in range(k): #一番上からK個みたときの1の個数を数える
tmp+=rows[i][j]
rcounts[i][0]=tmp
for j in range(1,n-k+1): #1歩進むごとに、今いるマスの値を1の個数に加え、最初にいたマスの値を1の個数から引く(j=n-k+1以降のjについては考える必要はない)
tmp+=rows[i][j+k-1]
tmp-=rows[i][j-1]
rcounts[i][j]=tmp
ans=whites
for x in range(n): #各頂点について、すべてのマスが白になっている行と列の個数の最大値を求める
for y in range(n):
tmp=whites
tmp+=ccounts[x][y]
tmp+=rcounts[x][y]
ans=max(ans,tmp)
print(ans)E問題:
愚直に判定を行うと、文字列Sの末尾i文字と文字列Tの先頭i文字が一致する最長の長さを求めるのにO(min(|S|,|T|)^2)かかってしまいます。
そのため、この判定を高速化することを考えます。
これは、文字列Sの末尾i文字と文字列Tの先頭i文字についてハッシュ値を求めることで判定でき、ローリングハッシュ法を用いることでO(|S|+|T|)で判定を行うことができます。
制約より、この方法で制限時間内にこの問題を解くことができることがいえます(実際にはハッシュ値が衝突する可能性があるので、複数の基数とmodについてハッシュ値を求めるなどの対策を考えるべきですが、ハッシュ値が衝突する確率は非常に小さいのであまり気にしなくてよいと思います)。
サンプルコード(C++)
https://codeforces.com/contest/1200/submission/58612279
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string arr[n];
for(int i=0;i<n;i++){
cin >> arr[i];
}
long long b=1e7+7; //ハッシュ計算時の基数
long long h=1e11+7; //ハッシュ計算時のmod
long long al=arr[0].size();
int ans;
long long bl,ah,bh,t;
for(int i=1;i<n;i++){ //1番目の文字列を固定し、2番目以降の文字列についてみる
bl=arr[i].size();
ans=0;
ah=0;
bh=0;
t=1;
for(int j=1;j<min(al,bl)+1;j++){ //ローリングハッシュ法
ah=ah+arr[0][al-j]*t; //末尾j文字のハッシュ値なので1回前のハッシュ値にj文字目の値にb^kを掛けた値を付け加える
ah%=h;
bh=bh*b+arr[i][j-1]; //先頭j文字のハッシュ値なので1回前のハッシュ値にbを掛けて左にずらしj文字目の値を加える
bh%=h;
if(ah==bh){ //ハッシュ値が一致していれば、i番目までの文字列どうしが一致していると判定する
ans=j;
}
t*=b;
t%=h;
}
al+=bl-ans; //1番目の文字列の長さを伸ばす
arr[0]+=arr[i].substr(ans); //1番目の文字列の末尾にi番目の文字列の被っていない部分を付け加える
}
cout << arr[0] << endl; //
return 0;
}
この記事が気に入ったらサポートをしてみませんか？