【AtCoder】ABC332解いてみた

海月

こんにちは、海月(うみつき)です。
久しぶりにAtCoderに参加しました。
ABC332にトライしたのでその話をしようと思います。
今回は、ABCというタイトルだけっぽいですね。(企業名がコンテスト名に入っていることが多いですよね)

(今回は入力等を省いてみました。)


A問題(Online Shopping)

AtCoder 社は、オンラインショップでグッズを販売しています。
高橋君はそこで N 種類の商品を購入することにしました。
1 以上 N 以下の整数 i について、i 種類目の商品は 1 個 ​$${P_i}$$ 円で、高橋君は $${Q_i}$$ 個購入します。
また、高橋君は送料を支払う必要があります。
送料は購入する商品の合計金額が S 円以上なら 0 円、そうでないならば K 円です。
高橋君が支払う金額は購入する商品の合計金額と送料の和です。
高橋君が支払う金額を求めてください。

考えたこと

商品代金を求めて、その後に送料がかかるかどうかを判定しました。
特に変わったことはしていないと思います。

n, s, k = map(int, input().split())

#支払い金額 = 商品 + 送料
payment = 0
for i in range(0, n):
    p, q = map(int, input().split())
    payment += p * q

if payment < s:
    payment += k

print(payment)


B問題(Glass and Mag)

AtCoder 社はグラスとマグカップを販売しています。
高橋君は容量が G ml のグラスと、容量が M ml のマグカップを 1 つずつ持っています。
ここで、G,M は G<M をみたします。
最初、グラスとマグカップはいずれも空です。
以下の操作を K 回繰り返した後で、グラスとマグカップに水がそれぞれ何 ml ずつ入っているか求めてください。

  • グラスが水で満たされているとき、すなわちグラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。

  • そうでなく、マグカップが空であるとき、マグカップを水で満たす。

  • 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。

考えたこと

グラス、マグカップの最大量が提示されています。現在のグラス、
マグカップの量を示す変数(current_X)を作成し、操作を記述しました。
また、３つ目の操作では、全ての水の量を求め、グラスに満杯入れ残りをマグカップに残すのか、グラスに全ての水を入れるのかとして、条件分岐を行いました。

k, g, m = map(int, input().split())

#現在の水の量
current_g = 0
current_m = 0

for i in range(k):
    if current_g == g:
        current_g = 0
    else:
        if current_m == 0:
            current_m = m
        else:
            water = current_g + current_m
            if water > g:
                #グラスは満杯になる
                current_g = g
                current_m = water - current_g
            else:
                #グラスが満杯にならない
                current_g = water
                current_m = 0
print('{0} {1}'.format(current_g, current_m))

"elif"を用いるとインデントが少なく、綺麗に書けそうだなと感じました。


C問題(T-shirts)

AtCoder 社はロゴ入りの T シャツを販売しています。
高橋君の N 日間の予定が 0, 1, 2 のみからなる長さ N の文字列 S で与えられます。
具体的には、1≤i≤N をみたす整数 i について、

  • S の i 文字目が 0 のとき、i 日目に何の予定も入っていません。

  • S の i 文字目が 1 のとき、i 日目に高橋君は食事に行く予定があります。

  • S の i 文字目が 2 のとき、i 日目に高橋君は競技プログラミングのイベントに行く予定が入っています。

高橋君は無地の T シャツを M 枚持っており、1 日目の直前の時点ですべて洗濯済みの状態となっています。
これに加えて、次の条件をみたすように行動できるように、高橋君は AtCoder のロゴ入りの T シャツを何枚か購入する事にしました。

  • 食事に行く日には、無地の T シャツ 1 枚またはロゴ入りの T シャツ 1 枚を着用する。

  • 競技プログラミングのイベントに行く日にはロゴ入りの T シャツ 1 枚を着用する。

  • 何の予定もない日には T シャツを着用しない。加えて、その時点で着用済みの T シャツを全て洗濯する。 洗濯した T シャツは翌日から着用できる。

  • 一度着用した T シャツは次に洗濯するまで着用できない。

N 日間のうち予定が入っている日すべてについて、条件をみたす T シャツを着用できるようにするために、高橋君は最低何枚のTシャツを購入する必要があるか求めてください。 新しく T シャツを購入する必要がないならば 0 を出力してください。
ただし、購入した T シャツも 1 日目の直前の時点ですべて洗濯済みの状態で存在するものとします。


考えたこと

Bに似たような感じで、現在のシャツの数を変数として置いて進めました。ロゴ入りTシャツは0から始め、負の数になるようにしました。その負の数になった分が購入する必要があるTシャツの数として表されるためです。

$$
\begin{array}{|c|c|} \hline
S=0 & Tシャツが復活 \\ \hline
S=1 & 無地orロゴTシャツを1枚使う \\ \hline
S=2 & ロゴTシャツを1枚使う \\ \hline
\end{array}
$$

S=0のとき、Tシャツが復活と書きましたが、これは全てのTシャツが最初の状態に戻ることを示しています。
Tシャツの優先順位はもちろん、
無地→ロゴ
の順番です。

ロゴTシャツが復活する直前の使用したロゴTシャツの絶対値が必要枚数として表されます。また、最後の日に使用されたロゴTシャツも、必要な枚数であるので、その最大値を取っています。

n, m = map(int, input().split())

s = input()

#購入数
buy_shirt = 0

#現在の無地シャツの数
current_m = m
current_r = 0

for s_i in s:
    if s_i == "0":
        #何もしない
        current_m = m
        if buy_shirt < abs(current_r):
            buy_shirt = abs(current_r) 
        current_r = 0
    elif s_i == "1":
        #食事
        if current_m > 0:
            #無地シャツ
            current_m -= 1
        else:
            current_r -= 1
    else:
        #プログラミング
        current_r -= 1    

if abs(current_r) > buy_shirt:
    buy_shirt = abs(current_r)

print(buy_shirt)

結構綺麗に書けたと思っています。

最後に

D問題の内容は見ましたが、どのように進めれば良いかが全くわからなかったです。
A(i, j) が移動することができるのは、A(i, X) または、A(X, j) ということまではわかり、グリッドの一致ができるかどうかのイメージはついたのですが、、、、(X は整数)
一致できるときの操作回数の最小値がどのように求められるかがわかりませんでした。

久しぶりのABCでしたが、C問題も解けたのは良かったと思います。ABCの解説を見ると、そもそも知らない方法で解いているもの(ABCの後半部分)もあるので、アルゴリズムの勉強として、何か本を買おうかと迷っています。
おすすめがあれば教えてください。


海月でした〜
それでは、また。

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