AtCoder Beginner Contest 137(ABC137) A~E解説

AtCoder Beginner Contest 137(ABC137)のA~Eまでの解説です。
コンテスト中はA~Dまでの4完(65:43)+3WA、その後Eも解きました(Dの実装に手間取り少しレートを落としてしまいました…)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc137
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc137/editorial.pdf

A問題:

指示通りにA+B,A-B,A*Bの3つの計算結果を求め、これらの最大値を出力すればよいです(max関数を使うのが簡単ですが、言語によっては少し書き方に注意する必要があります)。

B問題:

長さKの区間の左端がXであるような区間[X,X+K-1]と、長さKの区間の右端がXであるような区間[X-K+1,X]の和が答えの範囲となります。
これは[X-K+1,X+K-1]と表すことができるので、結局X-K+1からX+K-1までの数を出力すればよいです。

C問題:

まず、各文字列が一方のアナグラムであるかどうかを判定する方法を考えます。
各文字列について、aからzまでのアルファベットがそれぞれ何回出てくるかを求め、aからzまでの個数の組の出現回数を数えることを考えると、aからzまでの個数の組が等しい文字列どうしはアナグラムになります(∵出現する文字の種類とその個数が一致していないと文字列を1対1対応させることができませんが、これは2つの文字列がアナグラムでないことと同値です)。
各組の出現回数をnとすると、その組の中での組み合わせはnC2=n(n-1)/2通で求められます(ただしn<2のときはnC2=0とします)。
したがって、各文字列についてaからzまでの個数の組の出現回数を連想配列などで求め、各組の出現回数についてnC2を答えに加えていくことで、求める答えが得られます。
この計算量はO(N)(各文字列中の各文字について、aからzまでのどのアルファベットに当てはまるかを数える必要があるので、定数倍が10*26=260倍程度かかります)で、制約よりN<=10^5なので、10^7のオーダーでこの問題を解くことができ、この解法で制限時間内に問題を解くことができることが分かります(公式の解説では各文字列をソートした文字列が一致していればアナグラムになるという判定法を用いていました、こちらはO(|S|log|S|)(制約より|S|=10)で行えるため定数倍が14倍程度となり、上記の解法よりも高速に動作します)。

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

n=int(input())
arr=[input() for _ in range(n)]
dic={}
alphabet='abcdefghijklmnopqrstuvwxyz'
for s in arr:
 count=[0]*26 #aからzまでの個数の組を求める
 for i in range(10): #各文字列の各文字について、どのアルファベットに一致するかを確かめる
   for j in range(26):
     if s[i]==alphabet[j]:
       count[j]+=1
       break
 count=tuple(count)
 if count not in dic: #aからzまでの個数の組の出現回数を求める
   dic[count]=1
 else:
   dic[count]+=1
ans=0
for val in dic.values():
 ans+=val*(val-1)//2 #各組の出現回数nについて、nC2を答えに加える
print(ans)

D問題:

いかにも優先度付きキューを使いそうな問題なので、その方針で考えます。
t(=0 to M-1)日目に仕事を請けることを考えると、Ai>M-tなるiについては、その仕事を請けるかどうかを考えなくてよいことが分かります(∵この仕事を請けても、Ai>M-t⇔Ai+t>Mより報酬はM日目より後にしかもらえません)。
したがって、tを大きい順に見ていくと、M-1日目にはAi<=1なるiについて、報酬が最大となる仕事iを請けるべき、M-2日目にはAi<=2なるiについて、まだ請けていない仕事の中で報酬が最大となる仕事iを請けるべき、…0日目にはAi<=Mなるiについて、まだ請けていない仕事の中で報酬が最大となる仕事iを請けるべきであるといえます。
ここで、各時点においてまだ請けていない仕事の中で報酬が最大となる仕事を愚直に探すとO(N)かかってしまい制限時間に間に合いませんが、優先度付きキューを用いることでO(logN)でまだ請けていない仕事の中で最大の報酬を求めることができます。
したがって、元の配列をAiの小さい順にソートしておき、Ai=1の仕事について優先度付きキューに報酬Biを追加し、優先度付きキューから取ってきた最大値を答えに加え、次にAi=2の仕事について優先度付きキューに報酬Biを追加し、優先度付きキューから取ってきた最大値を答えに加え、…最後にAi=Mの仕事について優先度付きキューに報酬Biを追加し、優先度付きキューから取ってきた最大値を答えに加えることで、求める答えが得られます。
この操作は、Ai=1 to Mまで見るのにO(M)、また優先度付きキューの更新にO(NlogN)かかるので、トータルでO(M+NlogN)でこの問題を解くことができました。

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

import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+2)] #すべてのAi=1 to Mについて報酬0の仕事を追加する
arr.extend(arr2)
arr=sorted(arr,key=lambda x:x[0]) #Aiの小さい順にソート
q=[]
ans=0
pos=0
while 1:
 a,b=arr[pos]
 if a>m: #AiがMより大きければその仕事を請ける意味はない
   break
 if a==arr[pos+1][0]: #Aiの値が等しいとき、その仕事を優先度付きキューに追加する
   heapq.heappush(q,-b)
 else:
   heapq.heappush(q,-b)
   ans-=heapq.heappop(q) #Aiの値が変化したとき、そのAiまででの仕事の報酬の最大値を答えに加える
 pos+=1
print(ans)

E問題:

グラフの経路の最大値を求める問題で、いかにもベルマンフォード法を使いそうな問題なので、その方針で考えます。
各辺のコストを-(Ci-P)と置き換えたグラフを考えると、このグラフの1からNまでの道の間に負閉路がある場合は無限に答えを大きくできるので答えは-1、そうでない場合は、たとえグラフのどこかに負閉路があったとしても、このグラフの1からNまでの道の最小コストが答えになります。
これは、まず各頂点について1からNまでの道上の点かどうかを判定し、その後1からNまでの道上の点についてベルマンフォード法を行うことで求めることができます。
1からNまでの道上の点かどうかの判定は、1からNに向かう道上の点の集合と、Nから1に向かう道上の集合の共通部分を求め、その集合に含まれているかどうかで判定できます(実際にはDFSを用いて判定します)。
以上の操作は、1からNまでの道上の点の判定がO(N+M)、ベルマンフォード法がO(NM)となるので、制約よりこの問題を制限時間内に解くことができることが分かります。

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

import sys
sys.setrecursionlimit(10**9) #DFSを行うので再帰回数の上限を指定しておく

def BF(edges,n,s): #ベルマンフォード
   inf=float("inf")
   d=[inf for i in range(n+1)]
   d[s]=0
   update=True
   for i in range(n+1):
     update=False
     for v,u,cost in edges:
       if cand[v]!=1 or cand[u]!=1: #1からNまでの道上の点でない場合は考慮しない
         continue
       if d[v]!=inf and d[u]>d[v]+cost:
         d[u]=d[v]+cost
         update=True
     if update==False: #辺の値の更新が行われなければ終了
       break
     if i==n: #更新回数がnを超えたとき負閉路が存在し、かつその負閉路は1からNまでの道の間に存在するので答えは-1
       return inf
   return -d[-1] #1からNまでの最短経路(最大の得点)を返す

def DFS_1toN(v): #1からNまでの道上に含まれる点の集合を求める
 for u in to[v]:
   if toflag[u]==0:
     toflag[u]=1
     DFS_1toN(u)
     
def DFS_Nto1(v): #Nから1までの道上に含まれる点の集合を求める
 for u in ot[v]:
   if otflag[u]==0:
     otflag[u]=1
     DFS_Nto1(u)
   
n,m,p=map(int,input().split())
g=[]
to=[[] for _ in range(n+1)]
ot=[[] for _ in range(n+1)]
for _ in range(m):
 a,b,c=map(int,input().split())
 g.append([a,b,-(c-p)]) #辺のコストを-(Ci-P)に置き換える
 to[a].append(b)
 ot[b].append(a)
toflag=[0]*(n+1)
toflag[1]=1
DFS_1toN(1) #1からNまでの道上に含まれる点の集合を求める
otflag=[0]*(n+1)
otflag[n]=1
DFS_Nto1(n) #Nから1までの道上に含まれる点の集合を求める
cand=[0]*(n+1)
for i in range(1,n+1): #1からNまでの道上の点を求める
 cand[i]=toflag[i]*otflag[i]
ans=BF(g,n,1) #答えはベルマンフォードで求めることができる
if ans==float('inf'): #答えが無限大になるとき-1を出力する
 print(-1)
else: #そうでないとき、ベルマンフォードで得た値が正であればそれを出力、負であれば0を出力する
 print(max(ans,0))

この記事が気に入ったらサポートをしてみませんか?