ABC332(A~D)をPythonで解く

# A: Online Shopping

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

問題文の通りに実装します。

<details><summary>コード</summary>

```python
N, S, K = map(int, input().split())
cost = 0
for _ in range(N):
    p, q = map(int, input().split())
    cost += p * q

if cost >= S:
    print(cost)
else:
    print(cost+K)
```

</details>


# B: Glass and Mug 

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

問題文に従って丁寧に実装していきます。

まずはグラスに入っている水の量とマグカップに入っている水の量を表す変数`gc`と`mc`を用意します。操作を順番に見ていきます。

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

<details><summary>コード</summary>

```python
if gc == G:
    gc = 0
```

</details>

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

<details><summary>コード</summary>

```python
elif mc == 0:
    mc = M
```

</details>

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

マグカップが空になるということは、今のマグカップの水量とグラスの水量を足してもグラスが水で満たされないということです。
その場合は、グラスにマグカップの水量を足してマグカップの水量を０にします。

グラスが先に満たされる場合は、グラスがいっぱいになるまでに必要な水量(G-今の水量)だけマグカップから注ぎます。

<details><summary>コード</summary>

```python
else:
  if mc + gc < G:
      gc += mc
      mc = 0
  else:
      mc = mc - (G-gc)
      gc = G
```

</details>


これをk回繰り返します。まとめたコードが下記のものです。

<details><summary>コード</summary>

```python
K, G, M = map(int, input().split())

gc = 0
mc = 0

for i in range(K):
    if gc == G:
        gc = 0
    elif mc == 0:
        mc = M
    else:
        if mc + gc < G:
            gc += mc
            mc = 0
        else:
            mc = mc - (G-gc)
            gc = G

print(gc, mc)
```

</details>


# C: T-shirts 

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

0の日には全てのシャツが洗濯されるので、日程を0の日で区切ってそれぞれの区間を考えます。

具体的には、

```[1,1,2,0,1,1,0,1,2,2,2,1,0,1]```

を

```[[1,1,2], [1,1], [1,2,2,2,1], [1]]```

のように分割して考えます。

このようにすると、各区間で必要になるロゴ入りTシャツの枚数の最大値を取れば答えが求められます。

必要なTシャツの枚数は、「１の日数-持っている無地Tシャツの枚数」+「２の日数」です。持っている無地Tシャツの枚数が１の日数より多い場合は２の日数だけ考えればよいことに注意します。

<details><summary>コード</summary>

```python
def split_list_by_zero(input_list):
    result = []
    sublist = []

    for value in input_list:
        if value == "0":
            if sublist:  # Check if the sublist is not empty
                result.append(sublist)
                sublist = []  # Reset the sublist
        else:
            sublist.append(value)

    if sublist:  # Append the last sublist if not empty
        result.append(sublist)

    return result
```

```python
def main():
    N, M = map(int, input().split())
    S = list(input())
    li = split_list_by_zero(S)
    ans = 0

    for i in li:
        one = i.count("1")
        two = i.count("2")

        one_needs = max(one-M, 0)
        needs = two+one_needs
        ans = max(ans, needs)
    
    print(ans)

main()
```

</details>


# D: Swapping Puzzle 

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

制約がとても小さいので、それぞれ列と行を入れ替えてできる盤面を全探索できそうです。

好きな行同士、列同士を入れ替えることが可能なことに注意します。

まずは可能な列の並べなおし方、行の並べなおし方を列挙します。`itertools`の`permutations`を使うと簡単に書くことができます。

例えば、行(`H`)の並べ方は

```python
list(permutations(range(H)))
```
で列挙ができます。
リストの中身はイミュータブルなタプル型なことに注意します。

行の並べ方と列の並べ方のペアを全探索します。共に最悪で$5!$通りの並べ方があるので、ペアは$(5!)^2=14400$通りできます。十分に全探索可能です。

盤面が一致した場合、その盤面にするのに最低で何手必要かを計算します。

これは並び替えられたリストの要素を何回入れ替えればもとのリストに戻るのか考えると、ある要素の右にあってその要素より小さいものは必ず入れ替えなければいけないので、そのような要素の数を数えることによって計算できます。

これは一般に転倒数と呼ばれ、[このブログ](https://output-zakki.com/inversion_number/)が参考になります。ちなみにこの問題を解くのに$O(N^2)$のコードをお借りしています。

列と行で最低何回入れ替える必要があるのか計算して足し、それらの最小値を求めれば答えです。



<details><summary>コード</summary>

```python
def InversionNumberByBubleSort(A):
    ans = []  #転倒数
    for i in range(len(A)):
        for j in range(len(A) - i - 1):
            #左側の方が小さい場合
            if A[j] > A[j + 1]:
                ans.append((A[j], A[j+1]))
                A[j], A[j + 1] = A[j + 1], A[j]
    
    return len(ans)
```

```python
from itertools import permutations

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)]

h_perm = list(permutations(range(H)))
w_perm = list(permutations(range(W)))

ans = 10**18

for h in h_perm:
    for w in w_perm:
        flag = True
        for r in range(H):
            for c in range(W):
                if A[r][c] != B[h[r]][w[c]]: 
                    flag = False
        
        if flag:
            ans = min(ans, InversionNumberByBubleSort(list(h))+InversionNumberByBubleSort(list(w)))

print(ans if ans != 10**18 else -1)

```

</details>


別解でBFSを使うこともできます。

https://qiita.com/Pitta/items/b4a69672bb9ca865b900