NECプログラミングコンテスト2022(ABC267) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

NECプログラミングコンテスト2022(AtCoder Beginner Contest 267)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

日本電気株式会社（NEC）様について

本コンテストはNFC様が主催されています。
研究開発内容

採用情報

A - Saturday　Dif:13

入力が
Mondayなら5
Tuesdayなら4
...
と条件分岐します。「Monday」「Tuesday」は文字列なので「""」(ダブルクオーテーション)で囲むのを忘れないように気をつけましょう。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
S=input()

# S=「Monday」ならば
if S=="Monday":
    # 5を出力
    print(5)
# S=「Tuesday」ならば
elif S=="Tuesday":
    # 4を出力
    print(4)
# S=「Wednesday」ならば
elif S=="Wednesday":
    # 3を出力
    print(3)
# S=「Thursday」ならば
elif S=="Thursday":
    # 2を出力
    print(2)
# S=「Friday」ならば
elif S=="Friday":
    # 1を出力
    print(1)

B - Split?　Dif:171

まず各列についてピンが1本以上立っているか？を確認します。
入力例2の図を見てください。

左から1,3,4,7列目はピンが立っており、2,5,6列目は立っていません。
ピンが立っている列をA、そうでない列をBとして、xという文字列に表しましょう。
x=ABAABBA
xの1,3,4,7番目はAで、2,5,6番目はBになっています。

『ある二つの異なる列であって・・・』という条件は、すなわち以下のいずれかがxのなかにあればよいということになります。
ABA
ABBA
ABBBA
ABBBBA
ABBBBBA

ピン1が倒れており、かつxに上記の中のどれかがあれば「Yes」です。

入力を受け取るとき、そのままだとSの1文字目=S[0],Sの2文字目=S[1]、...となって実装しづらいので0文字目を"?"などてきとうな文字で埋めると良いです。

【提出】

# 入力の受け取り
# 0文字目を「?」で埋める
S="?"+input()

# ピン1が倒れていなければ
if S[1]=="1":
    # 「No」を出力
    print("No")
    # 終了
    exit()

# どの列が倒れているかを確認
x=""

# ピン7が倒れていなければ⇔S[7]=「1」ならば
if S[7]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン7が倒れていれば⇔S[7]=「0」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン4が倒れていなければ⇔S[4]=「1」ならば
if S[4]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン4が倒れていれば⇔S[4]=「0」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン2 または ピン8が倒れていなければ⇔S[2]=「1」 or S[8]=「1」ならば
if S[2]=="1" or S[8]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン2とピン8両方が倒れていれば⇔S[2]=「1」 and S[8]=「1」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン5が倒れていなければ⇔S[5]=「1」ならば
if S[5]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン5が倒れていれば⇔S[5]=「0」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン3 または ピン9が倒れていなければ⇔S[3]=「1」 or S[9]=「1」ならば
if S[3]=="1" or S[9]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン3とピン9両方が倒れていれば⇔S[3]=「1」 and S[9]=「1」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン6が倒れていなければ⇔S[6]=「1」ならば
if S[6]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン6が倒れていれば⇔S[6]=「0」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# ピン10が倒れていなければ⇔S[10]=「1」ならば
if S[10]=="1":
    # xの末尾に「A」を追加
    x+="A"
# それ以外(ピン10が倒れていれば⇔S[10]=「0」ならば)
else:
    # xの末尾に「B」を追加
    x+="B"

# 「ABA」がxにあれば
if "ABA" in x:
    # 「Yes」を出力
    print("Yes")
# 「ABBA」がxにあれば
elif "ABBA" in x:
    # 「Yes」を出力
    print("Yes")
# 「ABBBA」がxにあれば
elif "ABBBA" in x:
    # 「Yes」を出力
    print("Yes")
# 「ABBBBA」がxにあれば
elif "ABBBBA" in x:
    # 「Yes」を出力
    print("Yes")
# 「ABBBBBA」がxにあれば
elif "ABBBBBA" in x:
    # 「Yes」を出力
    print("Yes")
# それ以外
else:
    # 「No」を出力
    print("No")

C - Index × A(Continuous ver.)　Dif:524

以下の例を考えます。
N M：6 3
A：1 2 3 4 5 6

BはAから連続でM個の要素を取って作るので、B1が決まればBは決まります。
「B1=A1(B：A1 A2 A3)の場合」
1*1+2*2+3*3=14
「B1=A2(B：A2 A3 A4)の場合」
2*1+3*2+4*3=20
...

「B1=A1(B：A1 A2 A3)の場合」→「B1=A2(B：A2 A3 A4)の場合」について、差分を取ってみましょう。
(2*1+3*2+4*3)-(1*1+2*2+3*3)
=4*3-(1*1+2*(2-1)+3*(3-2))
=4*3-(1+2+3)
「A4*M」-「A1~A3の和」になっていますね。
つまり
「B1=A2(B：A2 A3 A4)の場合」=「B1=A1(B：A1 A2 A3)の場合」-(「A1~A3の和」)+A4*M
と計算できるということです。
同様に
「B1=A3(B：A3 A4 A5)の場合」=「B1=A2(B：A2 A3 A4)の場合」-(「A2~A4の和」)+A5*M
と計算できます。

一般には以下のようになります。
「B1=Ai(B：Ai A(i+1) A(i+2) ... A(i+M-1))の場合」=「B1=A(i-1)(B：A(i-1) Ai A(i+1) ... A(i+M-2))の場合」-(「A(i-1)~A(i+M-2)の和」)+A(i+M-1)*M

「Ai~A(i+M-2)の和」をそのまま計算しているとTLEしますので、これは累積和を使って計算します。

区間和(累積和による)
予め累積和を計算しておくことで区間和をO(1)で計算することができます。
Aの累積和(Cumulative sum)をACumとすると区間[l,r]の和はACum[r]-ACum[l-1]と計算できます。
累積和は以下のように計算することでO(N)で計算できます。
i=1,2,3,...,Nについて
ACum[i]=A_cum[i-1]+A[i]
※A[0]=0で埋めておきます

「例」
A：1 3 5 7 9 11 13 15 について区間[3,5]の和を求める場合
まず累積和を求めます。ACum[x]はA[1]~A[x]までの和を意味します。
例えばACum[3]=A[1]+A[2]+A[3]=1+3+5=9です。

ACum[2]=4
ACum[5]=25
ですので区間[3,5]の和は
ACum[5]-ACum[3-1]=ACum[5]-ACum[2]=25-4=21
となります。
なぜこのように計算できるかはACumを開いてみるとわかりやすいです。
ACum[5]-ACum[2]
=(A[1]+A[2]+A[3]+A[4]+A[5])-(A[1]+A[2])
=A[3]+A[4]+A[5]
と、いい感じにいらないところを引き算できるというわけです。

【提出】

# 入力の受け取り
N,M=map(int,input().split())
# 0番目を[0]などてきとうな数で埋める
A=[0]+list(map(int,input().split()))

# 答え
ans=0

# i=1~M
for i in range(1,M+1):
    # i*A[i]を足す
    ans+=i*A[i]

# 累積和の計算
ACum=[0]*(N+1)
# i=1~N
for i in range(1,N+1):
    # 計算する
    ACum[i]=ACum[i-1]+A[i]

# S：「B1=Ai(B：Ai A(i+1) A(i+2) ... A(i+M-1)の場合」のΣi*Biの値
S=ans

# i=2~(N-M+1)
for i in range(2,N-M+2):
    # 「B1=Ai(B：Ai A(i+1) A(i+2) ... A(i+M-1))の場合」=「B1=A(i-1)(B：A(i-1) Ai A(i+1) ... A(i+M-2))の場合」-(「A(i-1)~A(i+M-2)の和」)+A(i+M-1)*M
    S=S-(ACum[i+M-2]-ACum[i-2])+A[i+M-1]*M
    # それまでの答えより大きければ更新
    ans=max(ans,S)

# 答えの出力
print(ans)

D - Index × A(Not Continuous ver.)　Dif:864

DPで解きます。

DPとは「ある状態までの答えがわかっていれば→その次の状態の答えも出せる」という手続きを何度も行って最終的な答えを出す方法です。

DPの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。

具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する

以下の例で考えます。
N M：5 3
A：3 1 5 7 9

(1)表を作る
今回作る表は「Aからk個を選択し、かつBk=Axとしたときの、Σ[i=1,k]i*Biの最大値」
とします。表の名前はdpとします。

例えばdp[2][3]ならば「Aから2個を選択し、かつB2=A3としたときの、Σ[i=1,2]i*Biの最大値」となります
この場合、「B：A1 A3」=「B：3 5」として
Σ[i=1,2]i*Bi=1*3+2*5=13
とするのが最大値です。よってdp[2][3]=13となります。

(2)すぐにわかるところを埋める
すぐにわかるのはk=1の行です。
k=1の行というのは「Aから1個を選択し、かつB1=Axとしたときの、Σ[i=1,1]i*Biの最大値」となります。
dp[1][1]ならばB1=A1となり、Σ[i=1,1]i*Biの最大値=1*B1=1*A1=3となります。
dp[1][2]ならばB1=A2となり、Σ[i=1,1]i*Biの最大値=1*B1=1*A2=1となります。
同様に考えて
dp[1][x]=Ax
と計算できます。

(3)表の小さい方から答えにたどり着くまで埋める
k=2の行を考えましょう。
k=2の行というのは「Aから2個を選択し、かつB2=Axとしたときの、Σ[i=1,2]i*Biの最大値」となります。
まずdp[2][1]ですが、これは「Aから2個を選択し、かつB2=A1としたときの、Σ[i=1,2]i*Biの最大値」となります。
ですが、BはAの部分列(Aのインデックス番号が小さい方から取ってくる)のでB2=A1とすることはできません。
(B2=A1とするならB1はなににする？となりますね)
よってここは無視です。

dp[2][2]を考えます。dp[2][2]は「Aから2個を選択し、かつB2=A2としたときの、Σ[i=1,2]i*Biの最大値」となります。
B2=A2とするならB1=A1とする他ありません。Σ[i=1,2]i*Bi=1*B1+2*B2=1*A1+2*A2=1*3+2*1=5となります。
よってdp[2][2]=5です。

dp[2][3]を考えます。dp[2][3]は「Aから2個を選択し、かつB2=A3としたときの、Σ[i=1,2]i*Biの最大値」となります。
B2=A3なので、B1=A1またはA2が考えられます。
B1=A1としたときのBの1番目までの和Σ[i=1,1]i*Biの最大値はdp[1][1]=3です。
B1=A2としたときのBの1番目までの和Σ[i=1,1]i*Biの最大値はdp[1][2]=1です。
これに2*B2=2*A3=10を足して最大値となるようにします。当然大きい方、B1=A1とした場合の3に2*B2=2*A3=10を足すのが良いですね。
dp[2][3]=3+10=13となります。

dp[2][4]を考えます。dp[2][4]は「Aから2個を選択し、かつB2=A4としたときの、Σ[i=1,2]i*Biの最大値」となります。
B2=A4なので、B1=A1またはA2またはA3が考えられます。
B1=A1としたときのBの1番目までの和Σ[i=1,1]i*Biの最大値はdp[1][1]=3です。
B1=A2としたときのBの1番目までの和Σ[i=1,1]i*Biの最大値はdp[1][2]=1です。
B1=A3としたときのBの1番目までの和Σ[i=1,1]i*Biの最大値はdp[1][3]=5です。
これに2*B2=2*A4=14を足して最大値となるようにします。最も大きいもの、B1=A3とした場合の5に2*B2=2*A4=14を足すのが良いですね。
dp[2][3]=5+14=19となります。

なんとなく理屈がわかってきたと思います。
要するに「k=1行目、(1~x)列の最大値」+2*Axがdp[2][x]になっています。

これを一般化すると以下のようになります。
(2≤k,k≤x)dp[k][x]=「(k-1)行目,(1~(x-1))列の最大値」+k*Ax

(4)答えを出力する
表をすべて埋めると以下のようになります。

k=3行目は「Aから3個を選択し、かつB3=Axとしたときの、Σ[i=1,3]i*Biの最大値」ですから、3行目の最大値dp[3][5]=46が答えになります。

ちなみに「✕」の部分は、実装では初期値としてとても小さな数を埋めておきます。

【提出】

# 入力の受け取り
N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))

# (1)表を作る
dp=[[-10**15]*(N+1) for i in range(M+1)]

# (2)すぐにわかるところを埋める
# x=1~N
for x in range(1,N+1):
    dp[1][x]=A[x]

# (3)表の小さい方から答えにたどり着くまで埋める
# k=2~M
for k in range(2,M+1):
    # (k-1)行目の最大値
    dpMax=dp[k-1][0]
    # x=k~N
    for x in range(k,N+1):
        # (k-1)行目の最大値 dp[k-1][x-1]がそれまでの最大値より大きければ更新
        dpMax=max(dp[k-1][x-1],dpMax)
        # (2≤k,k≤x)dp[i][x]=「「(k-1)行目,(1~(x-1))列の最大値」+k*Ax
        dp[k][x]=dpMax+k*A[x]

# (4)答えを出力する
# M行目の最大値
print(max(dp[M]))

【広告】

『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