Codeforces Round #581(Div.2) A～C解説

Codeforces Round #581 (Div.2)のA～Cまでの解説です。
コンテスト中はA～Cの3完でした(D以降が難しい回で、Cでかなり詰まったものの何とかレート微増でとどまることができました)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1204
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/69244

A問題:

(コンテスト中はsが0の場合に気付かなかったため、sを具体的に求めて解いていました)
|S|が奇数のとき、|S|が表す値の範囲は、4^(|S|//2)～4^(|S|//2+1)-1となります。
したがって、|S|の最上位ビットが1、それ以外が0という形でなければ、|S|//2+1本の電車を見送ることになり、|S|の最上位ビットが1、それ以外が0という形であれば、|S|//2+1-1=|S|//2本の電車を見送ることになります(∵|S|が表す数よりも小さいもののみを数えるため)。
|S|が偶数のとき、値の範囲は、2*4^(|S|//2-1)～2*4^(|S|//2)-1となります。
よって、この場合は|S|の形によらず、|S|//2-1+1=|S|//2本の電車を見送ることになります。
ただし、s=0のときは0が答えとなります。
以上により、この問題をO(|S|)で解くことができました(s=0は露骨なコーナーケースなのですが、最上位ビットが1だと思い込んでいると見過ごしてしまうのでかなり怖いです)。

B問題:

条件より、和が最小となる列は、少なくともl種類の数を含まなければなりません。
条件にしたがってl種類の数を取ることを考えると、求める列は少なくとも1,2,…,2^(l-1)を含むことになります。
この列に対して、和が最小になるように残りの要素を加えることを考えると、1をn-l個加えればよいことが分かります。
1,2,…,2^(l-1)の和は、初項1、公比2の等比数列であることより、2^l-1と表せます。
したがって、最小値は2^l-1+1*(n-l)で求めることができます(もちろん1+2+…2^(l-1)を普通に計算してもよいです)。
同様に、和が最大となる列は、少なくともr種類の数を含まなければなりません。
条件にしたがってr種類の数を取ることを考えると、求める列は少なくとも1,2,…,2^(r-1)を含むことになります。
この列に対して、和が最大になるように残りの要素を加えることを考えると、2^(r-1)をn-r個加えればよいことが分かります(∵2^(r-1)より大きい数を取ることはr種類の数からなることに矛盾します)。
1,2,…,2^(r-1)の和は、初項1、公比2の等比数列であることより、2^r-1と表せます。
したがって、最大値は2^r-1+2^(r-1)*(n-r)で求めることができます。
以上より、この問題をO(1)で解くことができました。

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

n,l,r=map(int,input().split())
min=2**l-1+1*(n-l) #最小値の計算
max=2**r-1+(2**(r-1))*(n-r) #最大値の計算
print(min,max)

C問題:

この問題は、元の列の部分列を取ったときに、その部分列での隣り合う2頂点u,v間の任意の最短経路のいずれかに、u,vに元の列で対応する2要素の間にある要素がすべて含まれるような部分列を取るという問題であると言い換えることができます。
これは、部分列での隣り合う2頂点u,vと、u,vに元の列で対応する2要素の間の要素wについて、u,v間の距離とu,w間の距離+w,v間の距離が一致することを意味します。
したがって、まず全点間の距離d(u,v)をワーシャルフロイド法などによって求めておくと、中間地点wについて、d(u,w)+d(w,v)=d(u,v)となるのであれば、そのようなwはu,v間の任意の最短距離のいずれかに含まれるため、wを部分列に含める必要はありません。
一方、d(u,w)+d(w,v)>d(u,v)となるのであれば、そのようなwはu,v間の任意の最短距離に含まれないため、wを取り除くことはできず、このwを部分列に含める必要があります(全点間の最短距離をすでに求めているため、d(u,w)+d(w,v)<d(u,v)となることはありません)。
ただし、u=vとなるときはかならずwを追加する必要があります。
上記の判定を、元の列の要素について、先頭から行っていくことを考えます。
ここで、各整数がpの添字を表すこととすると、u,w,vの取り方として、まずu,w,v=0,1,2としておき、もしd(u,w)+d(w,v)>d(u,v)となるのであれば、wを部分列に加える必要はないため、w+=1,v+=1として始点を変更せずに見る位置を一つ進め、d(u,w)+d(w,v)=d(u,v)となるのであれば、wを部分列に加える必要があるため、wを新たな始点として定め、u=w,w=u+1,v=u+2と更新すればよいです。
答えは、元の列の始点+部分列に加える必要のあるwの列+元の列の終点となります。
この解法の計算量は、ワ―シャルフロイド法がO(V^3)、部分列に加えるかどうかの判定がO(M)となるため、トータルでO(V^3+M)でこの問題を解くことができました。

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

def warshall_floyd(d):
   for k in range(n):
       for i in range(n):
           for j in range(n):
               d[i][j] = min(d[i][j],d[i][k] + d[k][j])
   return d

n=int(input())
g=[list(input()) for _ in range(n)]
d=[[float('inf')]*n for _ in range(n)]
for i in range(n):
 for j in range(n):
   if g[i][j]=='1':
     d[i][j]=1
warshall_floyd(d) #ワーシャルフロイド法により全点間の距離を求める
m=int(input())
arr=list(map(int,input().split()))
for i in range(m):
 arr[i]-=1
ans=[arr[0]] #元の列の始点はかならず部分列に含まれる
pos1=0 #初期位置をp0,p1,p2として上記の判定を行う
pos2=1
pos3=2
for i in range(m-2):
 u,w,v=arr[pos1],arr[pos2],arr[pos3] #始点u,中間地点w,終点vを取る
 if u==v or d[u][w]+d[w][v]>d[u][v]: #u=vまたはd(u,w)+d(w,v)>d(u,v)が成り立つとき
  ans.append(w) #部分列に中間地点wを加える
  pos1=pos2 #wを新たな始点として定め、その1つ先、2つ先の要素を見る
  pos2=pos1+1
  pos3=pos2+1
 else:
  pos2+=1 #始点は変更せず、中間地点、終点を1つ進める
  pos3+=1
ans.append(arr[-1]) #元の列の終点はかならず部分列に含まれる
l=len(ans)
for i in range(l):
 ans[i]+=1
print(l)
print(*ans)