0 はじめに
0-1 軽く自己紹介
こんにちは、橘諸兄です。
某国立中学校で1年程AtCoderをしています。
使用言語はPythonとCppです。
Ratingは1159程です。入水したいです。
詳しくは私のプロフィールをご覧下さい。
0-2 記事について
AtCoder Beginner Contest 267の解説です。
Pythonで書きます。
公式な解説とは異なる場合がありますがご了承下さい。
ミス等ございましたらコメント欄よりお知らせ頂ければ幸いです。
1 ABC267 解説
1-1 個人的な感想
今回は個人的には当たり回でした。
Diff(難易度)は、ABが灰、Cが茶前半、Dが緑前半、Eが水前半でFはEとは掛け離れて青後半といった感じです。
私は60分で5冠できましたので過去最高Perfを取れました。
Ratingも+55で満足です。
1-2 A問題 Saturday
問題
Monday, Tuesday, Wednesday, Thursday, Fridayが入力として与えられます。
その曜日について、次の土曜日まであと何日か出力して下さい。
解説
if文を書くだけでACできます。
Mondayなら答えは5、Tuesdayなら答えは4、といった要領です。
特に言う事はありませんがタイプミスに気をつけましょう。
実装①
S=input()
ans=0
if S=="Monday":
ans=5
elif S=="Tuesday":
ans=4
elif S=="Wednesday":
ans=3
elif S=="Thursday":
ans=2
else:
ans=1
print(ans)
又、私は曜日の配列を用意し、入力に対応するIndexから答えを計算しました。
どちらでもACできますが、これの方が簡潔かと思います。
念のためコードを置いておきます。
実装②
S=input()
L=["Monday","Tuesday","Wednesday","Thursday","Friday"]
ind=L.index(S)
print(5-ind)
1-3 B問題 Split?
問題
ボウリングにおいて、スプリットとは次のようなピンの状態を指します。
次の二つの条件が満たされている。
・ピン1は倒れている。
・ある二つの異なる列について次の条件を満たすものが存在する。
・それぞれの列にピンは一本以上立っている。
・それらの列の間にはピンが一本も立っていない列が存在する。
ボウリングのピンの状態が長さ10の文字列Sとして与えられます。
1<=i<=10についてS[i]が0であればピンiは倒れており、1であれば立っています。
ボウリングのピンが「スプリット」の状態か判定して下さい。
解説
S[0]が1ならば答えはNoです。
S[0]が0の場合についての実装を考えましょう。
まずそれぞれの列にピンが一本以上立っているか求めましょう。
列を格納する配列をLとして実装します。
0-indexedと1-indexedの添え字のズレに注意しましょう。
実装①
S=input()
if S[0]=="1":
print("No")
L=[]
L.append(S[6]=="1")
L.append(S[3]=="1")
L.append(S[1]=="1" or S[7]=="1")
L.append(S[0]=="1" or S[4]=="1")
L.append(S[2]=="1" or S[8]=="1")
L.append(S[5]=="1")
L.append(S[9]=="1")
次に、「両方にピンが一本以上立っている」「その間に、ピンが一本も立っていない列が存在する」という条件を二つとも満たす二列があるか求めます。
二重ループを使って全探索しましょう。
実装の際はrange関数の引数に注意しましょう。range(a,b)は、a以上b未満の範囲となります。
実装②
ans="No"
for i in range(7):
for j in range(i+1,7):
if L[i] and L[j]:
for k in range(i+1,j):
if not L[k]:
ans="Yes"
最後に答えを出力して終了です。
全体の実装を載せます。
全体の実装
S=input()
if S[0]=="1":
print("No")
exit()
L=[]
L.append(S[6]=="1")
L.append(S[3]=="1")
L.append(S[1]=="1" or S[7]=="1")
L.append(S[0]=="1" or S[4]=="1")
L.append(S[2]=="1" or S[8]=="1")
L.append(S[5]=="1")
L.append(S[9]=="1")
ans="No"
for i in range(7):
for j in range(i+1,7):
if L[i] and L[j]:
for k in range(i+1,j):
if not L[k]:
ans="Yes"
print(ans)
実装量が割と多くて苦労した方も多かったかも知れません。
実を言うと私も10分程掛ってしまいました。
最近のB問題は難易度が上がっています。茶Diffに到達する時もあるので、日々の精進を欠かさないようにしましょう。
1-4 C問題 Index × A(Continuous ver.)
問題
長さNの整数列Aが与えられます。
長さMのAの連続部分列であるBについて、$\sum_{i=1}^{M} i×B[i]$ をスコアとします。
スコアの最大値を求めて下さい。
解説
シグマ記号の意味についてはご自身で調べて下さい。
まず、Bとしてあり得る数列はたかがN-M+1個しかありません。
なのでBのスコアを全探索したい訳ですが、愚直な全探索では$O(NM)$掛ってしまいます。高速化が必要です。
ここでは入力例2の場合を考えます。
$N=10,M=4,A=[-3,1,-4,1,-5,9,-2,6,-5,3]$です。
Bの左端がA[0]にある場合、スコアは$A_0 ×1+A_1 ×2+A_2 ×3+A_3 ×4$となります。
Bの左端がA[1]にある場合、スコアは$A_1 ×1+A_2 ×2+A_3 ×3+A_4 ×4$となります。
この時$A_0 +A_1 +A_2 +A_3$小さくなり、$A_4 ×4$大きくなりました。
つまり、左端がiからi+1に動くと、スコアがsum(A[i:i+M])小さくなりA[i+M]×M大きくなります。
(突然一般化してしまいましたが紙に書いて考えると解ります。)
これを実装すればいいです。
最初に、Bの左端がA[0]にある時のスコアを求めて、それ以降のスコアを先程の一般化を使って求められます。
sum(A[i:i+M])の部分の計算は、愚直に計算すると一回当たり$O(M)$掛かってしまい間に合わないので、累積和を使いましょう。
今回はセグ木でもACできました(PyPy)が区間和を求める場合は累積和の方が高速ですから基本的に累積和を使うようにしましょう。
そう言っておきながらコンテスト中にセグ木で通したなんて言えませんね...
又、スコアは負にもなり得るのでansの初期値は-INFにしておきましょう。
実装
N,M=map(int,input().split())
A=list(map(int,input().split()))
tot=[0]
for i in range(N):
tot.append(tot[-1]+A[i])
now=0
for i in range(M):
now+=(i+1)*A[i]
ans=now
for i in range(N-M):
minus=tot[i+M]-tot[i]
plus=A[i+M]*M
now+=plus-minus
ans=max(ans,now)
print(ans)
1-5 D問題 Index × A(Not Continuous ver.)
問題
長さNの整数列Aが与えられます。
長さMのAの部分列(連続でなくてもよい)であるBについて、$\sum_{i=1}^{M} i×B[i]$ をスコアとします。
スコアの最大値を求めよ。
解説
C問題とは異なり、Bとしてあり得る数列の個数が多く、とても全探索できそうにありません。
ここで動的計画法(通称DP)を使います。
DPは難易度問わず多くの問題で用いられているアルゴリズムですので、知らなかった方はこれを機にDPを覚えましょう。
NとMと制約からして、$O(NM)$くらいでも良さそうです。
次のようなDPを考えます。
DP[i][j]=i項めまで見て、そのうちBの要素としてj項選んだ時のスコアの最大値
初期値は-INFです。私はこれで2ペナしました。
遷移を考えます。
選ぶ場合の遷移はDP[i+1][j+1]=max(DP[i+1][j+1],DP[i][j]+A[i]×(j+1))です。
選ばない場合の遷移はDP[i+1][j]=max(DP[i+1][j],DP[i][j])です。
添え字を間違えないように気を付けましょう。
答えはmax(DP[i][M])です。
(解説だとDP[N][M]となっていますが、渡す遷移と貰う遷移では違う結果となります。)
(22/09/04 22:01訂正)解説ではDP[N][M]となっていますが、DP[i][M]→DP[i+1][M]の更新をしていないだけです。ご指摘頂いたFlkanjinさん、ありがとうございます。
実装
N,M=map(int,input().split())
A=list(map(int,input().split()))
DP=[[-INF]*(M+1) for _ in range(N+1)]
DP[0][0]=0
for i in range(N):
for j in range(M):
DP[i+1][j+1]=max(DP[i+1][j+1],DP[i][j]+A[i]*(j+1))
DP[i+1][j]=max(DP[i+1][j],DP[i][j])
ans=-INF
for i in range(N+1):
ans=max(ans,DP[i][M])
print(ans)
DPは前述の通り、難易度に関わらず頻出の分野なので完璧にできるようにしましょう。
1-6 E問題 Erasing Vertices 2
問題
N頂点M辺の単純無向グラフが入力として与えられます。
頂点iにはA[i]が書かれていて、あなたは次の操作をN回繰り返します。
まだ削除されていない頂点
xを選び、頂点xと、頂点xから出ている辺を削除する。
この操作のコストは、頂点xと辺で直接結ばれている頂点に書かれている数の総和である。
N回の操作全体のコストを、それぞれの操作に於けるコストの最大値と定めます。操作全体のコストの最小値を求めて下さい。
解説
まず、「操作」とは何でしょうか。
少し言い方を変えると、
頂点
xの操作に必要なコストを払って、次のことを行う。
頂点xと辺で直接結ばれている全ての頂点のコストを、A[x]減らし、その頂点との辺を切る。
この操作は、それぞれの回でコストが最小の頂点から順にやると良さそうです。
コストが小さいものを優先的に操作する訳ですし、頂点のコストは増えてしまうことはありませんから、操作によって、将来のコストに悪影響を及ぼすことはありません。
この手法を「貪欲法」と言います。
実装しましょう。
入力を受け取り、初期段階のコストを計算します。
実装①
N,M=map(int,input().split())
A=list(map(int,input().split()))
G=[set() for _ in range(N)]
cost=[0]*N
for i in range(M):
a,b=map(int,input().split()); a-=1; b-=1
G[a].add(b); G[b].add(a)
cost[a]+=A[b]; cost[b]+=A[a];
その後、コストと頂点番号を優先度付きキューに入れて、ダイクストラ法の要領で操作を行っていきます。
コストを一番前に持ってくることで、コストが小さい頂点から優先的に取り出すことが出来ます。
尚、コストは優先度付きキュー内では更新されませんので、取り出したコストの情報が古ければ使わないようにしましょう。
ansの更新も忘れずに。
実装②
H=[]
for i in range(N):
H.append([cost[i],i])
heapify(H)
ans=0
while H:
co,now=heappop(H)
if co>cost[now]: continue
ans=max(ans,co)
for nxt in G[now]:
cost[nxt]-=A[now]
heappush(H,[cost[nxt],nxt])
G[nxt].remove(now)
print(ans)
全体の実装も載せておきます。
全体の実装
from heapq import *
N,M=map(int,input().split())
A=list(map(int,input().split()))
G=[set() for _ in range(N)]
cost=[0]*N
for i in range(M):
a,b=map(int,input().split()); a-=1; b-=1
G[a].add(b); G[b].add(a)
cost[a]+=A[b]; cost[b]+=A[a]
H=[]
for i in range(N):
H.append([cost[i],i])
heapify(H)
ans=0
while H:
co,now=heappop(H)
if co>cost[now]: continue
ans=max(ans,co)
for nxt in G[now]:
cost[nxt]-=A[now]
heappush(H,[cost[nxt],nxt])
G[nxt].remove(now)
print(ans)
二分探索法での解法もあるそうですが、私としてはダイクストラ法の要領で貪欲法をやる方が効率がよいかと思います。
水Diff前半ですが解けた時はとても嬉しかったです。
2 さいごに
最後までお読み頂きありがとうございます。
累積和やDP、貪欲法、二分探索など、色々な手法が出て来た回でした。
特にDPや二分探索法は、最も出題されているアルゴリズムという統計もあるので、使えない方はできるようになり、使える方は難しい問題や早解きなどに挑戦してみると良いでしょう。
以上です。
ありがとうございました。
よい競プロライフを!!
いいねお願いします...(切実)