paizaプログラミング問題Rank A, B (Python)

[paiza×Qiita記事投稿キャンペーン](https://paiza.jp/pages/campaign/paiza-qiita)に参加しました．
関連リポジトリは，以下になります．

https://github.com/tomtkg/Python-Sample/tree/main/paiza

ここでは，Rank A, B問題の解答と簡単な解説を公開します．
言語はPythonを選択しました．結果は以下のようになりました．

# Rank A
## お菓子の詰め合わせ
https://paiza.jp/works/mondai/a_rank_skillcheck_archive/school_hiking

```python:school_hiking.py
from itertools import combinations

N, X = map(int, input().split())
a = [int(input()) for _ in range(N)]

for r in range(N):
    b = [X - sum(c) for c in combinations(a, N - r) if X >= sum(c)]
    if b:
        print(min(b))
        break
```
`itertools`の`combinations`を利用します．
`N - r`種類のお菓子を購入した時の合計金額`sum(c)`を全パターン求めます．
合計金額`sum(c)`が`X`以下の場合のみ，お菓子購入後のお釣り`X - sum(c)`を求めます．
お釣りの出る買い方があった場合，最小のお釣りを出力します．

購入するお菓子の種類を`N`から1つずつ減らしながら検証するのがポイントです．

## じゃんけんの手の出し方
https://paiza.jp/works/mondai/a_rank_skillcheck_sample/janken

```python:janken.py
N, M = map(int, input().split())
s = input()
a = [s.count(x) for x in "GCP"]

max_wins = 0
for p in range(N):        # パーの数
    c = (M - p * 5) // 2  # チョキの数
    g = N - p - c         # グーの数
    if g >= 0 and p * 5 + c * 2 == M:
        max_wins = max(max_wins, sum(map(min, [p, g, c], a)))

print(max_wins)
```
相手が出したグー，チョキ，パーの回数をカウントし，`a`に格納します．
そして，パーを0回出す場合からN回出す場合まで，結果を検討します．

パーの数`p`が決まると自動的にチョキの数`c`とグーの数`g`も決まります．
ただし，グーの数がマイナスになったり，指の合計本数が`M`にならない可能性があります．
グー，チョキ，パーの回数が適切な場合，相手に勝利した回数を求め，それを他の結果と比較することで，じゃんけんで勝つ回数の最大値`max_wins`が求められます．

パーで相手に勝つ回数は，`min(自分が出したパーの回数, 相手が出したグーの回数)`です．
グー，チョキで勝つ回数も同様に，相手が出したチョキとパーの回数の考慮が必要です．

## ハノイの塔
https://paiza.jp/works/mondai/real_event/hanoi

```python:hanoi.py
def h(n, a, b, c, move):  # ハノイの塔の再帰関数
    if n > 0:
        h(n - 1, a, c, b, move)
        move.append((a, b))  # 移動を記録
        h(n - 1, c, b, a, move)

n, t = map(int, input().split())
move = []  # 移動記録用のリスト
h(n, 0, 2, 1, move)

poles = [list(range(n, 0, -1)), [], []]
for a, b in move[:t]:  # 円盤をt回動かす
    poles[b].append(poles[a].pop())

for x in poles:
        print(*x or "-")
```
再帰関数を利用し，問題を解き終えるまでの全移動工程を記録します．
そして，円盤を`t`回動かし，その時の状態を出力します．

## 山折り谷折り
https://paiza.jp/works/mondai/real_event/origami

```python:origami.py
v = []
for _ in range(int(input())):
    v += [0] + [1^i for i in v[::-1]]
print(*v, sep="")
```
紙を折る回数が1回増えると，既存の折り目に`0`と`逆順で反転した折り目`が追加されます．
pythonでは，べき乗に`**`を使うことを思い出してください．
`^`は，XOR＝排他的論理和を表し，`1^0⇒1`，`1^1⇒0`になります．
ちなみに，`~`は，ビット単位の補数を計算するため，`~0⇒-1`，`~1⇒-2`になります．

## 本の整理
https://paiza.jp/works/mondai/real_event/book_sort

```python:book_sort.py
input()  # 不要な入力を捨てる
x = [int(x) - 1 for x in input().split()]

count = 0
for i in range(len(x)):
    while x[i] != i:
        x[x[i]], x[i] = x[i], x[x[i]]
        count += 1
print(count)
```
問題文に忠実な入れ替え（ソート）を実装すると，テストでタイムアウトが発生します．
そのため，同じ出力（入れ替え回数）になる，より高速な入れ替え法を利用しています．

# Rank B
## 名刺バインダー管理
https://paiza.jp/works/mondai/b_rank_skillcheck_archive/name_card

```python:name_card.py
n, m = map(int, input().split())
a, b = divmod(m - 1, 2 * n)
print(2 * n * a + 2 * n - b)
```
関数`divmod`は，割り算の商`a`と余り`b`を同時に取得できます．
`a`は`0,1,...`の値を取り，`b`は`0～5`のいずれかの値を取ります．

番号`m`の名刺は，`a+1`毎目のファイルの`b+1`番目に存在します．
番号`m`の名刺の裏側は，`a+1`毎目のファイルの`2*n-b`番目です．
番号`m`の名刺，その裏側の名刺の番号は，`2*n*a + 2*n-b`になります．

## 長テーブルのうなぎ屋
https://paiza.jp/works/mondai/b_rank_skillcheck_sample/long-table

```python:long_table.py
f = lambda: map(int, input().split())
n, m = f()

y = set()  # 客がいる座席の集合
for _ in range(m):
    a, b = f()
    c = {(b + i) % n for i in range(a)}
    if not y & c:  # 集合yとcに重複がない
        y |= c  # yにcを追加（yとcの和集合でyを更新）

print(len(y))
```
入力から複数の数字を取り出す処理が2箇所で登場するため，最初に関数`f`を定義します．
客がいる座席の集合`y` と 新規の客が座りたい座席の集合`c` の2つがあると考えます．
あとは，2つの集合の積集合を確認し，それが空なら2つの和集合を`y`に保存するだけです．

集合`y`と`c`に重複がない ＝ 集合`y`と`c`の積集合が空です．
`y |= c` ＝ `y = y | c`で，`y`と`c`の和集合で`y`を更新します．

## みんなでしりとり
https://paiza.jp/works/mondai/b_rank_skillcheck_archive/word_chain

```python:word_chain.py
N, K, M = map(int, input().split())
a = {input() for _ in range(K)}  # 単語集
b = set()  # 発言集
c = ""  # 直前の人の発言の最後の文字

y = list(range(1, N + 1))  # 参加者リスト
i = 0  # 手番
for _ in range(M):
    x = input()
    if x not in a or (c and x[0] != c) or x in b or x[-1] == "z":
        y.pop(i)
        c = ""
    else:
        i += 1
        c = x[-1]

    b.add(x)
    if i >= len(y):
        i = 0

print(len(y))
print(*y, sep="\n")
```
まず，単語集`a`，発言集`b`，最後の文字`c`を用意します．
そして，参加者リスト`y`と手番`i`も用意します．

ループの中では，発言集`b`への単語の追加，次の手番`i`の確認が共通処理になります．
4つのしりとりのルールは`or`で接続し，ルールに従っているか否かで分岐が発生します．
分岐内では，必要に応じて`c`，`y`，`i`を更新します．

最後に，参加者リスト`y`の長さとその中身を出力します．

## 神経衰弱
https://paiza.jp/works/mondai/b_rank_skillcheck_archive/concentration

```python:concentration.py
f = lambda: list(map(int, input().split()))
H, W, N = f()
a = [f() for _ in range(H)]
f()  # 不要な入力を捨てる

b = [0] * N  # 各プレイヤーの所持トランプ枚数
i = 0  # 手番
while sum(b) < H * W:
    s, t, r, u = f()
    if a[s - 1][t - 1] == a[r - 1][u - 1]:
        b[i] += 2
    else:
        i = (i + 1) % N

print(*b, sep='\n')
```
入力から複数の数字を取り出す処理が4箇所で登場するため，最初に関数`f`を定義します．
4行目の`f()`は，不要な入力を最小文字数で捨てています．
ここでは，「与えられた回数ループする」ではなく，「プレイヤーが取ったカードの枚数が場に存在したカードの枚数と等しくなるまでループする」と考えるのが適切です．

ユーザーがめくった2枚のトランプを確認し，内容が同じであれば所持トランプを2増やし，内容が異なれば手番を次の人に移動します．
これを繰り返し，最後に各プレイヤーの所持トランプ枚数を出力します．

## 3Dプリンタ
https://paiza.jp/works/mondai/b_rank_skillcheck_archive/3d_printer

```python:display_3d_printer.py
def get_row(x: int) -> str:
    row = list(input())
    for _ in range(x):
        for i, c in enumerate(input()):
            if c == "#":
                row[i] = "#"
    return "".join(row)

x, _, z = map(int, input().split())
rows = [get_row(x) for _ in range(z)]
print(*rows[::-1], sep="\n")
```
ネストが深くなるので，出力1行分を計算する処理を関数`get_row`として切り分けます．
まず，入力に合わせて`z=1`のケースから順番に，関数`get_row`でデータを処理します．
そして，処理したデータを逆順で出力します．

関数`get_row`では，最初の入力行`row`を基準として，新しい入力行と比較をします．
入力行の`i`番目に`"#"`があれば，`row[i]`を`"#"`で更新します．
`X`行ごとに出現する区切り記号`"--"`も，他の入力行と同様に処理をします．
`"--"`は不要な入力ですが，特殊な処理も不要です．

# 終わりに
Rank A, Bは，考えさせられる問題が多く，難しかったです．
プログラム実装前に解法を複数検討する必要がある，そんな問題が多かった印象です．
問題の本質を理解して，コンパクトに解答できたと思います．

関連記事

https://qiita.com/tomtkg/items/c57376161baa12095c9e

https://qiita.com/tomtkg/items/22810085c548b134e8ce