LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
LINE Verda様について
VerdaはLINE社内で開発・運用されているプライベートクラウドプラットフォームです。
一般的なパブリッククラウドサービスのように、VMやKubernetes, ロードバランサやNATなどのIaaS/PaaSをLINE社内に提供しています。
チーム紹介ページは以下です。興味があれば御覧ください。
A - Full House Dif:27
今回のA問題は「やや難」です。
普段のA問題はもっと簡単なので、今回解けなかった人も落ち込まずに競技プログラミングを続けてください。
カードを小さい順に並び替えると判定が簡単にできます。
まず入力をA,B,C,D,Eという変数ではなく、リストに受け取りましょう。
リストの名前をCardとしておきます。
次にCardをソート(小さい順に並び替え)します。
並び替えは(リスト名).sort()と書きます。
フルハウスになっているということは小さい順から数えて
1枚目と2枚目が同じ かつ 3枚目と4枚目と5枚目が同じ
または
1枚目と2枚目と3枚目が同じ かつ 4枚目と5枚目が同じ
上記のどちらかになります。
※「A,B,C,D,E全てが同じ値ではない」という制約があるので5枚同じカードにはなりません。
実装ではリストの1つ目の要素は0番目、すなわちCard[0]、2つ目の要素は1番目、すなわちCard[1]、...と一つずつずれているということに注意してください。
これらの条件を満たしているかifで判定します。
「Yes」を出力するときは文字列のため、print("Yes")とダブルクオーテーションをつけることに注意してください。
pythonに「これは文字だよ」と伝えるためです。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
Card=list(map(int,input().split()))
Card.sort()
# 1枚目と2枚目が同じ かつ 3枚目と4枚目と5枚目が同じ
if Card[0]==Card[1] and Card[2]==Card[3]==Card[4]:
# 「Yes」を出力
print("Yes")
# 1枚目と2枚目と3枚目が同じ かつ 4枚目と5枚目が同じ
elif Card[0]==Card[1]==Card[2] and Card[3]==Card[4]:
# 「Yes」を出力
print("Yes")
# どちらでもない
else:
# 「No」を出力
print("No")
B - Ancestor Dif:136
人Nから順に親をたどって何回で人1にたどり着くかを確認します。
例えば入力が以下である場合を考えます。
7
1 1 3 3 5 5
人7の親は人5
人5の親は人3
人3の親は人1
3世代分戻ったところで人1にたどり着いたので答えは3代前とわかります。
【提出】
# 入力の受け取り
N=int(input())
# P[0]とP[1]をてきとうな値で埋める
P=[0]+[0]+list(map(int,input().split()))
# 人Nから辿っていく
i=N
# 世代を遡った回数
Count=1
# 人1にたどり着くまで
while P[i]!=1:
# 回数のカウント
Count+=1
# P[i]の親へ
i=P[i]
# 遡った回数を出力
print(Count)
C - Monotonically Increasing Dif:298
itertoolsを使います。
itertools
itertoolsは数列の順列や組み合わせなどを作ることができるライブラリです。
「使い方」
import：import itertolls
順列：permutations(range(始まり,終わり+1))
重複なしの組み合わせ：combinations(range(始まり,終わり+1),取る個数)
重複ありの組み合わせ：combinations_with_rep(range(始まり,終わり+1),取る個数)
直積：product(range(始まり,終わり+1),range(始まり,終わり+1)):
「使用例」
# import：import itertolls
import itertools
N,K=4,2
# 順列：permutations(range(N))
# seq=(0,1,2,3),(0,1,3,2),(0,2,1,3),(0,2,3,1),...,(3,2,1,0)
print("[順列]")
for seq in itertools.permutations(range(N)):
print(seq)
# 重複なしの組み合わせ：combinations(range(N),K)
print("[重複なしの組み合わせ]")
# seq=(0,1),(0,2),(0,3),(1,2)...,(2,3)
for seq in itertools.combinations(range(N),K):
print(seq)
# 重複ありの組み合わせ：combinations_with_rep(range(N),K)
print("[重複ありの組み合わせ]")
# seq=(0,0),(0,1),(0,2),(0,3),(1,1)...,(3,3)
for seq in itertools.combinations_with_replacement(range(N),K):
print(seq)
# 直積：product(range(N),range(N)):
print("[直積]")
# seq=(0,0),(0,1),(0,2),(0,3),(1,0)...,(3,3)
for seq in itertools.product(range(N),range(N)):
print(seq)
本問では重複なしの組み合わせ=combinationsを使います。
列挙の際は自動的に辞書順になります。
出力の際、「*」をつけると余計な[]なしで出力できます。
【提出】
# 入力の受け取り
N,M=map(int,input().split())
# itertoolsのインポート
import itertools
# 重複なしの組み合わせ
# (1,2,3),(1,2,4),---,(7,8,9)
for p in itertools.combinations(range(1,M+1),N):
# 答えの出力(*をつけると[]なしで出力できる)
print(*p)
D - Left Right Operation Dif:1016
まずLで置き換える操作だけの場合を考えましょう。
Aのうち長さiまで(A1~Ai)の総和を最小化することを考えます。
長さiまでの総和の最小値をf(i)とします。
A(i-1)までの最小値(f(i-1))がわかっているなら、Aiまでの最小値というのは
・それまでの最小値+Ai⇔f(i)=f(i-1)+Ai
・全てLに変えてしまう⇔f(i)=L*i
このどちらかになります。
具体例をみてみましょう。
A：10 10 10 1 100
L：5
A3までの最小値は当然全てL=5に変えたもので
f(3)=5*3=15
となります。
A4までの最小値を考えます。
・それまでの最小値+Ai⇔f(i)=f(i-1)+Ai
f(4)=f(3)+A4
f(4)=15+1=16
・全てLに変えてしまう⇔f(i)=L*i
f(4)=5*4
f(4)=20
前者のほうが小さいですね。よくよく考えれば当然で、A4が1(Lより小さい)ですからA1~A4まで全てLにしてしまうよりA1~A3だけLにしてA4は置いておいた方がいいに決まっています。
A5までの最小値を考えます。
・それまでの最小値+Ai⇔f(i)=f(i-1)+Ai
f(5)=f(4)+A5
f(5)=16+100=116
・全てLに変えてしまう⇔f(i)=L*i
f(5)=5*5
f(5)=25
今度は後者のほうが小さいです。A5=100が大きすぎるのでここをLに変えることで全体を小さくできるというわけです。
f(0)=0と初期値を決めるとf(i)は以下のように表せます。
f(i)=min(f(i-1)+Ai,L*i)
これをi=0,1,2,...Nまで計算しておきます。
R側も全く同様に計算します。
すなわちAのうち(N-i+1)~Nまで(A(N-i+1)~AN)の総和を最小化した値を計算し、g(i)とします。
同様に考えてg(0),g(1),...を計算しておきます。
実装ではAをひっくり返してLのときと同じ操作を行えばよいです。
f,gを使ってA全体の値を考えましょう。
L側でA1~Ai番目までを最小化したものはf(i)
R側でA(i+1)~AN番目までを最小化したものはg(N-i)
です。
よって2つ組み合わせたf(i)+g(N-i)はA全てをカバーできます。あとはi=0,1,2,...についてこれを計算し、最も小さいものを答えとすれば終わりです。
【提出】
# 入力の受け取り
N,L,R=map(int,input().split())
A=list(map(int,input().split()))
# fの計算
# A[0]を埋める
A1=[0]+A
# fを作る(f(0)=0)
f=[0]*(N+1)
# i=1~N
for i in range(1,N+1):
# fの計算
f[i]=min(f[i-1]+A1[i],L*i)
# Aをひっくり返す
A=A[::-1]
# A[0]を埋める
A2=[0]+A
# gを作る(g(0)=0)
g=[0]*(N+1)
# i=1~N
for i in range(1,N+1):
# fの計算
g[i]=min(g[i-1]+A2[i],R*i)
# 答え
ans=10**15
# i=0~N
for i in range(N+1):
# これまでの答えとf[i]+g[N-i]の小さい方で更新
ans=min(ans,f[i]+g[N-i])
# 答えの出力
print(ans)
【広告】
『AtCoder 最速で緑になる 基礎・典型50問詳細解説』
ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP
【booth(pdf)】
https://booth.pm/ja/items/4102300
冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/
【booth(pdf)】
https://sano192.booth.pm/items/3179185
1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV
【booth(pdf)】
https://booth.pm/ja/items/3698647
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/
【booth(pdf)】
https://sano192.booth.pm/items/3698668
『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS
【booth(pdf)】
https://sano192.booth.pm/items/4025713
ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF
【booth(pdf)】
https://sano192.booth.pm/items/4025737
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb
【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW
【booth(pdf】
https://sano192.booth.pm/items/3785312