Codeforces Round #639(Div.2) A～E解説
Codeforces Round #639 (Div.2)のA～Eまでの解説です。
今回はDiv.1に参加し、64分でA/Bの2問を解きレート微増(相当)の結果を残すことができました＊(今回はジャッジサーバの不調によりコンテストがunratedになったため実際のレート増減はありませんでした)
Div.1でやっていけるか少し不安だったのですが、今回のDiv.1でレート微増に相当する結果を残すことができたことで少し自信につながりました＊
問題のアドレスは以下になります↓
https://codeforces.com/contest/1344
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/76819
A問題:
明らかに、n=1またはm=1のときそのような並べ方は実現できます。
よってn>=2かつm>=2のときを考える必要がありますが、サンプルケースにある通り、n=2かつm=2のとき最適にピースを組み合わせても周囲にブランクができることはありません。
このことから、n=2かつm=2以外のとき、そのような並べ方は実現できないことが分かります(∵n=2かつm=2のピースの組み合わせにピースを1つ付け加えたものを考えると、nまたはmを1増やすためには付け加えるピースが2つ以上のブランクを必要がありますが、これは問題の条件に矛盾します)。
以上によりこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1345/submission/79253424
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
if n==1 or m==1: #n=1またはm=1であれば構成できる
print('Yes')
elif n==2 and m==2: #そうでないときn=2かつm=2であれば構成可能、それ以外には構成は不可能
print('Yes')
else:
print('No')
B問題:
高さhのピラミッドは、2枚のカードで構成されるパーツをh*(h+1)/2個、1枚のカードで構成されるパーツをh*(h-1)/2個で構成されます。
制約よりn<=10^9なので、0<=h<=10^5までの高さhのピラミッドを作るのに必要な枚数を前計算しておくと、n枚のカードから条件にしたがって作れるピラミッドの個数は、2分探索を用いてn枚以下で作れるピラミッドに必要な枚数の最大値を求め、nをn-(そのピラミッドを作るのに必要な枚数)で更新していくことでO((logN)^2)で求めることができます。
以上によりこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1345/submission/79255384
import bisect
pyramids=[0]
for i in range(1,10**5): #0<=h<=10^5までの高さhのピラミッドを作るのに必要な枚数を前計算する
tmp=(2*i*(i+1))//2+(i*(i-1))//2
pyramids.append(tmp)
t=int(input())
for _ in range(t):
n=int(input())
cnt=0
pos=bisect.bisect_right(pyramids,n)-1
while pos!=0: #ピラミッドが作れなくなるまで、n枚以下で作れる最大のピラミッドの枚数を求め、nをn-(その枚数)で更新していく
cnt+=1
n-=pyramids[pos]
pos=bisect.bisect_right(pyramids,n)-1
print(cnt)
C問題:
問題文に従うと、部屋番号pn+q (0<=q<=n-1)にいる人はpn+q+aqに移動することが分かります。
ここでpn+q+aq mod nを考えると、この値はpによらず、qによってのみ決まります。
したがって、各aiについてai+i mod nを求め、それらの値がすべて異なるかを判定することでこの問題を解くことができます。
これは例えば集合型に計算結果を追加していき、最終的な集合型の要素数がnに一致するかを見ればよく、この問題をO(NlogN)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1344/submission/79158502
import collections
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
for i in range(n): #各aiについてai+i mod nを求める
arr[i]+=i
arr[i]%=n
cnt=collections.Counter(arr) #a0からa(n-1)までの要素の相異なる要素数を求める
if len(cnt)!=n: #すべての要素が異なっていればYes,そうでなければNoとなる
print('No')
else:
print('Yes')
D問題:
まず明らかに、各列・行について白マスで分断された黒マスがあるとき、すなわち黒…白…黒となるとき不可能です(∵いずれかの黒マスにSを置く必要がありますが、このときNは白マスに移動することになり条件に反します)。
また黒マスを1つも含まない列について、すべての行についてすでに黒マスが置かれている場合は不可能、同様に黒マスを1つも含まない行について、すべての列について黒マスが置かれている場合は不可能です(∵黒マスにはすべてSを置くとしてよく、このとき黒マスを1つも含まない列には必ずSを置く必要がありますが、このときその列に重なる行のすべてにすでに黒マスが置かれている場合、上記の議論と同様にNが白マスに移動することになり条件に反します)。
上記の判定により構築が不可能であると判定された場合は答えは-1、不可能でないと判定された場合は黒マスの連結成分の個数が答えとなります。
これは構築が可能であるかの判定にO(NM)、連結成分の個数を数えるのにDFSなどを用いてO(N+M)かかるので、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1344/submission/79186638
import collections
def check(i,j): #BFSを用いてある黒マスから移動できる黒マスすべてを探索する
q=collections.deque()
q.append((i,j))
while len(q)!=0:
i,j=q.popleft()
if i!=0 and checked[i-1][j]==0 and board[i-1][j]=='#':
checked[i-1][j]=1
q.append((i-1,j))
if i!=n-1 and checked[i+1][j]==0 and board[i+1][j]=='#':
checked[i+1][j]=1
q.append((i+1,j))
if j!=0 and checked[i][j-1]==0 and board[i][j-1]=='#':
checked[i][j-1]=1
q.append((i,j-1))
if j!=m-1 and checked[i][j+1]==0 and board[i][j+1]=='#':
checked[i][j+1]=1
q.append((i,j+1))
n,m=map(int,input().split())
board=[list(input()) for _ in range(n)]
tate=set()
yoko=set()
for i in range(n): #各行について、黒…白…黒となる配置があるかを判定する
flag=0
for j in range(m):
if board[i][j]=='#':
yoko.add(i)
tate.add(j)
if flag==0:
flag=1
if flag==2:
print(-1)
exit()
if board[i][j]=='.' and flag==1:
flag=2
for i in range(m): #各列について、黒…白…黒となる配置があるかを判定する
flag=0
for j in range(n):
if board[j][i]=='#':
if flag==0:
flag=1
if flag==2:
print(-1)
exit()
if board[j][i]=='.' and flag==1:
flag=2
for i in range(n): #各行について、黒マスの存在しない列があるかを判定する
if i in yoko:
continue
flag=False
for j in range(m):
if j not in tate:
flag=True
if flag==False:
print(-1)
exit()
for i in range(m): #各列について、黒マスの存在しない行があるかを判定する
if i in tate:
continue
flag=False
for j in range(n):
if j not in yoko:
flag=True
if flag==False:
print(-1)
exit()
cnt=0
checked=[[0]*m for _ in range(n)]
for i in range(n): #黒マスである各マスから探索し連結成分の個数を数える
for j in range(m):
if board[i][j]=='.' or checked[i][j]==1:
continue
else:
cnt+=1
checked[i][j]=1
check(i,j)
print(cnt)
E問題:
与えられた2変数の不等式xi<xjをiからjへの有向辺と捉えて有向グラフを構築すると、不等式すべてが成立するかどうかは、上記の有向グラフに閉路がないかどうかに等しいです(∵不等式が成立することはxi<xjとxj<xiの両方の不等式が現れないことと同値で、不等式が推移律を満たすことを考慮すると、これは上記の有向グラフにiからjまでのパスとjからiまでのパスの両方が存在しないことに等しく、これは有向グラフに閉路がないことと同値であることが分かります)。
以上により、例えばDFSを用いて不等式すべてが成立するかどうかをO(N+M)で判定することができました。
次に論理記号の割り振り方を考えると、問題文の仮定より、不等式xi<xjまたはxj<xiについて、iとjの小さいほうにはAまたはEを置くことができ、大きいほうにはEを置くしかありません。
これが上記の有向グラフにおけるすべてのパスについて成り立つので、頂点番号の小さい順に見て、その頂点から上記の有向グラフで辿れるすべての頂点と、上記の有向グラフの辺の向きを逆にしたグラフで辿れるすべての頂点を探索済みとしていくとき、ある頂点が少なくとも1つのグラフですでに探索されていればその頂点には∃を置くしかなく、どちらのグラフでもまだ探索されていなければその頂点には∀または∃を置くことができるので、∀を置くのが最善です。
これは例えばDFSにより実装できるので、以上によりこの問題をO(N+M)で解く事ができました。
(n,mが大きいとき(Codeforcesの仕様上？)DFSを用いるとREを食らったので、以下のサンプルコードでは上記の有向グラフに閉路があるか、および論理記号の割り振り方をどちらもBFSで求めました、閉路があるかを単純にBFSで求めるのは難しいですが、閉路があることとトポロジカルソートが行えないことは同値なので、BFSによりトポロジカルソートが行えるかどうかを判定しました、トポロジカルソートの判定法については例えばこちらの記事を参照してください→https://qiita.com/drken/items/996d80bcae64649a6580)
サンプルコード(Python):
https://codeforces.com/contest/1344/submission/79250857
import collections
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ans=['']*(n+1)
g1=[[] for _ in range(n+1)] #xi<xjについてiからjに辺を張ったグラフ
g2=[[] for _ in range(n+1)] #xi<xjについてjからiに辺を張ったグラフ
deg=[0]*(n+1) #各頂点の出次数を求める
for _ in range(m):
a,b=map(int,input().split())
g1[a].append(b)
g2[b].append(a)
deg[a]+=1
status=[0]*(n+1) #トポロジカルソートの判定アルゴリズムにおいて各頂点の出次数が0となったか
q=collections.deque()
for i in range(1,n+1):
if deg[i]==0: #元のグラフで出次数が0の頂点からスタートする
q.append(i)
while len(q)!=0:
v=q.pop()
status[v]=1 #出次数が0の頂点を記録する
for u in g2[v]: #出次数が0の頂点を取り除き、その頂点に辺を張っている頂点の出次数を1減らす
deg[u]-=1
if deg[u]==0: #出次数が0となったら頂点候補に追加する
q.append(u)
if status.count(0)>=2: #1度も出次数が0とならない頂点が1つ以上あるとき、トポロジカルソートができない⇔閉路が存在する
print(-1)
else:
status1=[0]*(n+1) #xi<xjについてiからjに辺を張ったグラフ上ですでに辿った頂点を記録する
status2=[0]*(n+1) #xi<xjについてjからiに辺を張ったグラフ上ですでに辿った頂点を記録する
for i in range(1,n+1):
if status1[i]==0 and status2[i]==0: #どちらのグラフでもまだ辿っていない頂点には∀を置く
ans[i]='A'
else: #そうでない頂点には∃を置く
ans[i]='E'
if status1[i]==0:
q=collections.deque()
q.append(i)
while len(q)!=0: #xi<xjについてiからjに辺を張ったグラフ上で探索を行う
v=q.pop()
status1[v]=1
for u in g1[v]:
if status1[u]==0:
status1[u]=1
q.append(u)
if status2[i]==0: #xi<xjについてjからiに辺を張ったグラフ上で探索を行う
q=collections.deque()
q.append(i)
while len(q)!=0:
v=q.pop()
status2[v]=1
for u in g2[v]:
if status2[u]==0:
status2[u]=1
q.append(u)
print(ans.count('A'))
print(''.join(map(str,ans[1:])))
この記事が気に入ったらサポートをしてみませんか？