見出し画像

[ABC265]AtCoder Beginner Contest 265 A～C問題Python解説

Kai

2022/8/21に行われましたABC265の解説記事です。
ご質問・ご要望等ありましたらコメントにてお知らせください。
必ず返信いたしますので、返信もご覧いただけると幸いです。

A問題

X, Y, N = map(int, input().split())
if 3*X < Y:
    print(N*X)
else:
    yy = N//3
    xx = N%3
    print(X*xx + Y*yy)

N<=100なので、組み合わせを全て出力してもいいのですが、
少し工夫することで、計算量を短縮することができます。

N個のリンゴを買うためにX円のリンゴを買うのか、Y円のリンゴを買うのかを考えなくてはなりませんが、
Y円のリンゴは3個でY円なので、3倍のXとYがどちら大きいかを比較して、安いほうをN個分買えばいいということになります。

もし、X円のリンゴの方が安ければ、X円のリンゴは1個分ですので、
総額はX×Nです。
Y円のリンゴの方が安ければ、Y円のリンゴは3個分ですから、
Nを3で割り切れる分（N=10 なら3×3の9個分)はY円のリンゴを購入し、
残り(3で割った余り)はX円のリンゴを購入することで、計算できます。

B問題

import itertools
N, M, T = map(int, input().split())
A = list(map(int, input().split()))
sumA = list(itertools.accumulate(A))
# print(A)
if M == 0 and sum(A) >= T:
    print("No")
    exit()
elif M == 0:
    print("Yes")
    exit()

for i in range(M):
    x, y = map(int, input().split())
    # print(a[:x-1])
    if sumA[x-2] >= T:
        print("No")
        exit()
    T += y
print("Yes")

結構苦戦した方が多かったのではないかと思います。
過去にも出たことがある（思い出せないので、知っている方いたらコメントしてください笑）問題なので、この機会に覚えておきましょう。

この問題のポイントはズバリ「累積和」です。

累積和の解説記事は以下を参考にしてください。

問題文通りに移動→消費を繰り返すと、
TLEになります。
考え方としては、これまで累積で消費した時間ともらったボーナスを足したTの大小を調べるという感じになります。

スクリプトを見ていきましょう。

import itertools
N, M, T = map(int, input().split())
A = list(map(int, input().split()))

ここまでは大丈夫ですね。
累積和に使うitertoolsライブラリをインポートして、
入力値を受け取ります。

sumA = list(itertools.accumulate(A))

これが累積和を表します。
累積和を簡単に説明すると例えば、
A = [5, 7, 5]であれば、
sumA = [5, 12, 17]となります。
これまでの和が要素になるわけですね。

if M == 0 and sum(A) >= T:
    print("No")
    exit()
elif M == 0:
    print("Yes")
    exit()

まずは、例外としてボーナスがない(M=0)の時だけ条件分岐しておきましょう。
ボーナスがないとTは変動しませんから、
部屋全てを回る時間sum(A)とTを比較して、
sum(A)の方が大きければ全部を回ることは当然不可能になります。

for i in range(M):
    x, y = map(int, input().split())
    # print(a[:x-1])
    if sumA[x-2] >= T:
        print("No")
        exit()
    T += y
print("Yes")

最後にボーナスがある場合について見ていきましょう。
まずこのループはrange(M)なので、ボーナスの箇所分ループを回します。
x(ボーナス部屋の場所)、y(ボーナス時間の数)を入力値として受けとります。
まず、ここまで来ることができたのかを確認します。
ここまで来るまでにある持ち時間はT、
消費する時間は先ほどの累積和sumAを使って、
sum[x-2]で表されます。
(インデックス番号の調整を忘れずに)
消費する時間がT以上だった場合は次に行く時間を持っていないので、
その部屋で脱落、つまり部屋Nにたどり着くことはできません。

最終的にすべての地点をクリアすれば、部屋Nにたどり着くことができます。

C問題

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
i = 0
j = 0
place = [[False for _ in range(W)] for __ in range(H)]
for n in range(H*W + 1):
    if place[i][j] == True:
        print(-1)
        exit()
    else:
        place[i][j] == True
    if G[i][j] == "U":
        if i == 0:
            print(i+1, j+1)
            exit()
        else:
            i -= 1
    if G[i][j] == "D":
        if i == H - 1:
            print(i+1, j+1)
            exit()
        else:
            i += 1
    if G[i][j] == "L":
        if j == 0:
            print(i+1, j+1)
            exit()
        else:
            j -= 1
    if G[i][j] == "R":
        if j == W - 1:
            print(i+1, j+1)
            exit()
        else:
            j += 1     

print(-1)

考え方はそんなに難しくはないと思います。
現在(i,j)にいます。
（最初は(1,1)にいますが、インデックス番号で表すと(0,0)になります。)
移動する条件が問題文に書いてありますね。
つまり、この条件を満たさない場合は移動できず、自分のいる場所(i,j)を出力してください、ということになります。

それを表したのが以下のスクリプトです。

if G[i][j] == "U":
        if i == 0:
            print(i+1, j+1)
            exit()
        else:
            i -= 1
    if G[i][j] == "D":
        if i == H - 1:
            print(i+1, j+1)
            exit()
        else:
            i += 1
    if G[i][j] == "L":
        if j == 0:
            print(i+1, j+1)
            exit()
        else:
            j -= 1
    if G[i][j] == "R":
        if j == W - 1:
            print(i+1, j+1)
            exit()
        else:
            j += 1

その場所の文字とi=0,i=H-1,j=0,j=W-1(インデックス番号なので全て-1されます。)を満たせばその場所を出力しexit()でプログラムを終了します。

そして条件を一向に満たさず、無限に移動し続ける場合は-1を出力するのですが、無限に探すのは当然無理ですので、いつまで探せばいいのかというのが今回のポイントになります。

今回の解法では、1回言った場所に戻ってくる場合は移動自体がループしてるということになり、問題文の条件を満たさないので、無限に移動し続けると判断しました。

このために、まだ行ったことのない点をFalse、行ったことがある点をTrueと表し、もし自分の今いる点が、Trueであれば場所を出力する作業に移ります。
逆にFalseであれば行ったことを示すため、Trueに変えます。
この作業は1か所でもTrueであれば終わるため、
ループ回数は最大でH×W+1で済みます。
最初にH×Wマス分のFalseをリストplaceに作っておき、それを更新していくという作業が効率良いでしょう。

いいなと思ったら応援しよう！