ABC332をPythonで解いてみたよ。(A～D問題)

[AtCoder Beginners Contest 332 (ABC332)](https://atcoder.jp/contests/abc332) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。


# A - Online Shopping

## 問題
オンラインショップで、 $P_i$ 円の商品を $Q_i$ 個だけ購入します。 ( $1 \leq i \leq N$ )
送料は $K$ 円ですが、購入金額が $S$ 円以上なら送料は無料です。
いくらかかるでしょうか？

https://atcoder.jp/contests/abc332/tasks/abc332_a

## 考察
$P_i$ 円の商品を $Q_i$ 個だけ購入すると、 $P_i \times Q_i$ 円かかります。
これをfor文を利用して、全商品に対して計算して、いくらかかるかを計算します。

その後、if文を用いて、その金額が $S$ 円未満であれば送料の $K$ 円をプラスします。

## コード
```Python
N, S, K = map(int, input().split())

ans = 0
for _ in range(N):
    p, q = map(int, input().split())
    ans += p * q
if ans < S:
    ans += K
print(ans)
```
# B - Glass and Mug

## 問題
容量 $G$ mlのグラスと容量 $M$ mlのマグカップが1つずつあります。
指定された操作を $K$ 回行った後、グラスとマグカップの中に水がそれぞれ何ml入っていますか？

https://atcoder.jp/contests/abc332/tasks/abc332_b

## 考察
問題文の操作がごちゃごちゃしているので、1つ1つ見ていきましょう。
> - グラスが水で満たされているとき、すなわちグラスにちょうど $G$ ml 入っているとき、グラスの水をすべて捨てる。
> - そうでなく、マグカップが空であるとき、マグカップを水で満たす。
> - 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。

以下、グラス・マグカップに入っている水の量をそれぞれ $g, m$ とします。
1つ目の条件はこう書けます。
```Python
"""グラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。"""
if g == G:
    g = 0
```
2つ目の条件はこうです。
```Python
"""マグカップが空であるとき、マグカップを水で満たす。"""
elif m == 0:
    m = M
```
3つ目の条件は、移動する水の量に注目すると、マグカップが空になるときは $m$ mlだけ移動して、グラスが水で満たされるときは $G-g$ mlだけ移動します。これの小さい方が実際に移動する水の量になるので、こう書けます。
```Python
"""マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。"""
else:
    move = min(G - g, m)  # 移動する水の量
    m -= move
    g += move
```
これで操作1回分です。

この操作をfor文で $K$ 回だけ行えば正解できます。

## コード
```Python
K, G, M = map(int, input().split())

g, m = 0, 0
for _ in range(K):
    if g == G:
        g = 0
    elif m == 0:
        m = M
    else:
        move = min(G - g, m)
        m -= move
        g += move
print(g, m)
```
# C - T-shirts

## 問題
食事に行く日は無地Tシャツorロゴ付きTシャツを、競プロのイベントの日はロゴ付きTシャツを着ます。それ以外の日はすべてのTシャツを洗濯し、次の日にはそのTシャツはすべて使えます。
いくつロゴ付きTシャツを買えばいいですか？

https://atcoder.jp/contests/abc332/tasks/abc332_c

## 考察
実際にシミュレートします。
何枚買えばいいかすぐには分かりませんが、シミュレートしている中でロゴ付きTシャツが足りなかったらその都度買うことにしてしまえば、最終的に必要なロゴ付きTシャツの数が分かります。



## コード
```Python
N, M = map(int, input().split())
S = input()

ans = 0  # 購入したロゴTシャツの数
muji, logo = M, 0  # 洗濯済みの無地Tシャツ、ロゴ付きTシャツの数

for s in S:
    match s:
        case '0':
            muji = M
            logo = ans
        case '1':
            if muji > 0:
                muji -= 1
            elif logo > 0:
                logo -= 1
            else:
                ans += 1
        case '2':
            if logo > 0:
                logo -= 1
            else:
                ans += 1
print(ans)
```
# D - Swapping Puzzle

## 問題
2つのグリッド $A, B$ が与えられます。
$A$ について、「隣り合った行を入れかえる」という操作を何回でもできます。列に関しても同様の操作が何回でもできます。
この操作をして、$A$ を $B$ に一致させられますか？一致させられるなら、そのときの操作の回数の最小値はいくつですか？

https://atcoder.jp/contests/abc332/tasks/abc332_d

## 考察
$2 \leq H,W \leq 5$ とサイズがかなり小さいので、 $A$ を操作して得られるグリッドを全探索します。

行番号のリスト $(0,1, \cdots , H-1)$ と列番号のリスト $(0,1,\cdots W-1)$ を用意します。
たとえば、 $0$ 行目と $1$ 行目をスワップしたとき、行番号のリストは $(0,1,2,3,4)$ から $(1, 0, 2, 3, 4)$ になるとします。列番号のリストに関しても同様です。
この順列を全探索します。
順列全探索は `itertools.permutations()` が便利です。(使い方は下のコードを参考にしてね)

行番号・列番号のリストから操作後の $A$ を復元し、 $B$ と一致するかどうかを確認します。

もし一致していたら、何度スワップすれば行番号・列番号のリストを得られるのかを計算します。
これは転倒数を計算すればいいというのが典型です。
<details> <summary>転倒数とは</summary>
数列 $P=(P_1, P_2, \cdots P_N)$ の転倒数は、 $ 1 \leq i < j \leq N$ かつ $P_i > P_j$ を満たす $(i,j)$ の数です。

たとえば、$(0,1,4,2,3)$ は、 $4>2, 4>3$ の部分があるので、転倒数は $2$ になります。
</details>

## コード
```Python
from itertools import permutations

# 操作回数(転倒数を計算する)
def move_cnt(tup):
    n = len(tup)
    result = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if tup[i] > tup[j]:
                result += 1
    return result


H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

ans = 1000
for i_perm in permutations(range(H), H):
    for j_perm in permutations(range(W), W):
        C = [[A[i][j] for j in j_perm] for i in i_perm]  # 操作後のA
        if C == B:
            ans = min(ans, move_cnt(i_perm) + move_cnt(j_perm))
if ans == 1000:
    ans = -1
print(ans)
```