AtCoder Beginner Contest 138(ABC138) A～E解説

AtCoder Beginner Contest 138(ABC138)のA～Eまでの解説です。
コンテスト中はA～Eまでの4完(53:11)+2WAでした(Eが易しめの回だったため5完しても青パフォを取れずレート微増に終わりました)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc138/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc138/editorial.pdf

A問題:

入力を受け取り、指示通りに条件分岐を書けばよいです(指示通りに条件分岐を書くだけの問題はA問題としても珍しいですが、「以上」と「より大きい」に注意するなど、余計なミスをしないように注意しましょう)。

B問題:

問題文の指示通り、まずは1/A1+…+1/Anを計算し、その後1/(1/A1+…+1/An)を求めればよいです。
C++などの場合は浮動小数点型を用いて計算する必要があります。

C問題:

各時点において、具材の価値が最小である2要素を合成していくことで、最後に残った具材の価値を最大化することができます。
これは、このような操作によって最終的に残る具材の価値が、元の具材の価値を昇順にソートした配列aiを用いてa1/2^(n-1)+a2/2^(n-1)+a3/2^(n-2)+…+an/2^1と表せることと、最終的に残る具材の価値は上記の和の2の指数部分の入れ替えによって表せることおよびa1<=a2<=…<=anが成り立つことからいえます。
以下、これを示します。任意のi,j(i!=j)について、2の指数部分を入れ替えると、総和は(ai/2^ki+aj/2^kj)-(ai/2^kj+aj/2^ki)=(ai-aj)/2^ki+(aj-ai)/2^kjだけ変化し、いまai<=ajかつki>kjから、(ai-aj)/2^ki+2^(ki-kj)(aj-ai)/2^ki=(2^(ki-kj)-1)(aj-ai)/2^ki>=0となるため、入れ替え前の総和の方が入れ替え後の総和よりも大きいことが示せました。
したがって、各時点において具材の価値の配列を昇順にソートし、最小の2要素を合成し、その具材を配列に追加するという操作を配列の要素が1になるまで続けることで、求める答えを得ることができます。
この計算量はO(N*NlogN)となり、制約より制限時間内にこの問題を解くことができることが分かります。

サンプルコード(Python):
https://atcoder.jp/contests/abc138/submissions/7014422

n=int(input())
arr=list(map(int,input().split()))
while len(arr)>1: #最後の1つになるまで操作を続ける
 arr=sorted(arr) #配列を昇順ソート
 v1=arr.pop(0) #最小の2数を取り出し、それらを合成したものを配列に追加する
 v2=arr.pop(0)
 arr.append((v1+v2)/2)
print(arr[0]) #最後に残ったものが答えとなる

D問題:

各操作を愚直に行うと、DFSをQ回行うことになり最大でO((N+M)Q)回の操作が必要になりますが、これでは制限時間に間に合いません。
そのため、各操作を高速に行う方法を考える必要があります。
まず、pi=pj(i!=j)なる操作については、それらをまとめてもよいことが分かります。
したがって、pi=vとなるすべての操作の値の和をcount[v]と定め、これを計算しておくことができます。
さらに、count[1]は1を根とする部分木に含まれるすべての頂点に足され、count[2]は2を根とする部分木に含まれるすべての頂点に足され、…count[N]はNを根とする部分木に含まれるすべての頂点に足されていくことから、結局1を根とする木に対して、まず1の子ノードのcount[v]をcount[v]+=count[1]として更新し、次に1の各子ノードについて、さらにそれらの子ノードの子ノードについて、というふうに、子ノードがなくなるまでcountを更新していけばよいことが分かります。
この操作は1を始点としてDFSを行い、順次countを更新していくことで実現できます。
この計算量はO(N+M)となり、この問題を制限時間内に解くことができることが分かります。

サンプルコード(Python):
https://atcoder.jp/contests/abc138/submissions/7014797
(制限時間に間に合わなかったため、非本質な高速化(DFSを再帰ではなくスタックで実装する)を行っています)

import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1): #木グラフの隣接リストを作成
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
for _ in range(q): #各頂点についてcount[v]を計算
 v,val=map(int,input().split())
 cnt[v]+=val
q=collections.deque()
q.append(1) #DFSのスタックによる実装、まずスタックに始点1を積む
checked=[0]*(n+1) #各頂点を見たかどうかのフラグを持っておく
while q:
 v=q.pop()
 checked[v]=1 #頂点を見たかどうかのフラグを更新する
 for u in g[v]:
   if checked[u]==1: #vの子ノードuについて、まだ見ていない頂点であればcount[u]をcount[u]+=count[v]として更新する
     continue
   cnt[u]+=cnt[v]
   q.append(u) #スタックに子ノードuを積む
print(*cnt[1:]) #各頂点のcountが答えとなる

E問題:

まず、Tに出てくる各アルファベットがすべて1回以上Sに出てくるとき、必ず|T|回以内のループで処理が終わることが分かります。
また、Tに出てくる各アルファベットについて、Sに出てこないものがあるときはSを何回ループしても部分列としてTを作ることはできません。
最小のループ回数でSSS…Sの部分列としてTを作るためには、どのように文字を取っていけばよいのかを考えます。
すると、Sの先頭から順番にTの各文字と対応させていき、もしも対応させられる文字がなくなったら、再びSの先頭に戻るという操作を行うのが最善であることが分かります。
以上の操作を実現するために、まずSについて各アルファベットが何文字目に出てくるかという配列posを求めておきます。
その後、Tの各文字について、Sの何文字目に対応するかを順に求めていき、これをpos2とします。
pos2を先頭から見ていくと、ai>=ajのとき、そのときに一度Sを見終わってループしていることがいえ、そうでないとき、同じSからTに対応させていることが分かります。
したがって、pos2を最後まで見ることでSを何回ループしたかを求めることができ、またpos2の末尾の値は最後のループでSの何文字目を見ているかを表しているため、求める答えは(ループ回数)*|S|+(pos2の末尾の値)となります。
最後に、Tの各文字について、Sの何文字目に対応するかを順に求める方法を説明します。
これは、Tのi文字目t[i]がSのj番目の文字に対応しているとしたとき、Tのi+1番目の文字t[i+1]に対応するSのj+1番目以降の文字を、posを二分探索することで求め、そのような文字が存在すればj+1番目以降の文字に対応させ、そのような文字が存在しなければSの先頭から見て最も若い番号の文字に対応させることで求められます。
この計算量は、posの前計算がO(|S|)、答えの計算がO(|T|)、pos2の計算がO(|T|log|S|)となり、この方法で制限時間内に問題を解くことができることがいえます。

サンプルコード(Python):
https://atcoder.jp/contests/abc138/submissions/7014444

import bisect

def ctoi(char): #アルファベットをindex(0～25に変換)
 return ord(char)-97

s=input()
ls=len(s)
t=input()
lt=len(t)
pos=[[] for _ in range(26)]
for i in range(ls): #各アルファベットについて、Sの何番目(0-indexed)に出てくるかを求める
 val=ctoi(s[i])
 pos[val].append(i)
larr=[0]*26
for i in range(26): #各アルファベットがSに何回出てくるかの配列larrを作成する
 larr[i]=len(pos[i])
pos2=[]
cnt=[0]*26
flag=True
num=-1
for i in range(lt):
 val=ctoi(t[i])
 if larr[val]==0: #もしもTの文字がSに含まれていなければ、TをSの部分列として構成できない
   flag=False
   break
 tmp=bisect.bisect_right(pos[val],num) #Tの文字に対応するSの文字を探す
 if tmp==larr[val]: #そのような文字が存在しなければSの最も若い番号の文字に対応付ける
   num=pos[val][0]
 else: #そうでなければ条件を満たす文字に対応付ける
   num=pos[val][tmp]
 pos2.append(num) #Sの何文字目に対応するかの列を更新する
if flag==False: #もしもTの文字がSに含まれていなければ、TをSの部分列として構成できない
 print(-1)
else: #構成可能なときの最小の文字列長を求める
 loop=0
 tmp=pos2[0]
 for i in range(1,lt):
   if pos2[i]<=tmp: #(Tのi文字目に対応するSの番号)>=(Tのi+1文字目に対応するSの番号)となるとき、Sはループしている
     loop+=1
   tmp=pos2[i]
 ans=loop*ls+(pos2[-1]+1) #(ループ回数)*(Sの長さ)+Tの最後の文字が対応するSの番号(1-indexed)が答えとなる
 print(ans)