[ABC267]NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)A～C問題Python解説

2022年9月4日 00:15

ABC267のPython解説記事です。
いいね・コメントお待ちしています。

(サムネイルの誤字が発覚したため、画像を変更いたしました。
　ご指摘いただいた方ありがとうございました！)

A問題

S = input()
if S == "Monday":
    print(5)
elif S == "Tuesday":
    print(4)
elif S == "Wednesday":
    print(3)
elif S == "Thursday":
    print(2)
elif S == "Friday":
    print(1)

難しく考えず、全部書いていった方がよさそうです。

今日が月曜日なら、
土曜日までは火曜日、水曜日、木曜日、金曜日、土曜日
と行くので、
5日ですね。
同様に考えると、
月曜日→5日
火曜日→4日
水曜日→3日
木曜日→2日
金曜日→1日
となります。

それぞれ日数を出力します。
土曜日と日曜日は入力されません。

B問題

S = list(input())
n = ["0" for _ in range(7)]
if S[0] == "1":
    print("No")
    exit()


if S[0] == "1":
    n[3] = "1"
if S[1] == "1":
    n[2] = "1"
if S[2] == "1":
    n[4] = "1"
if S[3] == "1":
    n[1] = "1"
if S[4] == "1":
    n[3] = "1"
if S[5] == "1":
    n[5] = "1"
if S[6] == "1":
    n[0] = "1"
if S[7] == "1":
    n[2] = "1"
if S[8] == "1":
    n[4] = "1"
if S[9] == "1":
    n[6] = "1"
# print(S,n)
n = "".join(n)
l = ["101","1001","10001","100001","1000001"]
for i in range(5):
    if l[i] in n:
        print("Yes")
        exit()
print("No")

この問題もボーリングのピン10ピン分なので、
全部書いた方が分かりやすそうです。
スプリットの定義を理解することができるかが肝になります。

まず、条件を見てください。
スプリットになるためには、ピン1が倒れていないといけませんので、
ピン1つまりS[0]が0でなければいけません。
(インデックス番号に注意)

次に列に着目します。
条件には列の話しか出てきていませんので、
どのピンが倒れているかはあまり関係がありません。
例えばピン2とピン8のどっちかが立っていれば、
列3は立っていることになります。
つまり今回はピン1～10で考えるのではなくて、
列0~6で考えるべきでした。

まず立っている列を探します。
まずはすべての列を0つまり倒れていることにして、
もしピンが立っていれば、そのピンがある列を1にして立っていることにします。
そして、列が2本立っている場合にその列の間に倒れている列がある場合スプリットです。

列は0もしくは1が7個含む文字列になっていますので、
倒れている列をはさむ2本の立っている列
つまり、"101","1001","10001","100001","1000001"
が文字列に含まれればスプリットとなります。

C問題

N, M = map(int, input().split())
A = list(map(int, input().split())) 
a = [0 for _ in range(N-M+1)]

for i in range(M):
    a[0] += (i+1)*A[i] 
import itertools
csum = [0] + list(itertools.accumulate(A))

for i in range(1, N-M+1):
    a[i] = a[i-1] - csum[i+M-1] + csum[i-1]  + M*A[i+M-1]
# print(csum,a)
print(max(a))

少し難しい問題ですね。
順番に解説していきます。

まずは、単純にA(i)×M+A(i+1)×MとしてしまうとTLEです。
計算を簡単にしていきましょう。

入力例1を例として扱います。
入力例1は以下でした。
N = 4
M = 2
A = [5, 4, -1, 8]

M=2なので、長さ2の配列を取り出しながら考えます。
組み合わせは
①[5,4]
②[4,-1]
③[-1,8]
になりますね。

それぞれ求める値は
①1×5+2×4 = 13
② 1×4+2×(-1) = 2
③ 1×(-1)+2×8 = 15

この中で最大なものなので、15が出力されればOKです。
これをどうやって高速に解くかですが、
①→②もしくは②→③に移るとき何か法則に気づきますでしょうか？

①→②の時、
1×4+2×(-1) = 2
-)1×5+2×4 = 13
-1×5-1×4++2×(-1) = -11
となりますね。
-1×5-1×4 = -(1×5+1×4)
と変形でき、(1×5+1×4)はA[0:2]の和ですね。(sum(A[0:2])

つまり、求める値は先頭の場所i(①の場合はi=0つまり5)から1つずづずれる時に、
-sum(A[i:i+M])+M*(A[i+M])
すればいいということになります。

ここでsum(A[i:i+M])をそのまま計算してしまうとTLEになりますから、今度は累積和を使用します。
累積和は自分で作ってもいいですが、
私がいつもお勧めしているitertoolsを使うといいでしょう。
記事を載せておきます。

累積和はリストAの最初から最後までを取っているので、
部分和にしたい場合はその直前の値(i-1)を引けば大丈夫です。

それをN-M+1回繰り返し、値をリストaに代入することで、
全探索することができました。
最後にmax(a)を出力で終了です。

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