paizaプログラミング問題Rank S (Python)

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

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

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

# Rank S
## 村人の友好関係
https://paiza.jp/works/mondai/s_rank_skillcheck_archive/group_popularity

```python:group_popularity.py
import numpy as np

N, M, Q = map(int, input().split())
N += 1  # 入力が1～Nのため

m = np.zeros((N, N), dtype=int)
for _ in range(M):
    a, b, f = map(int, input().split())
    m[a][b] = m[b][a] = f

g = np.zeros(N, dtype=bool)
for _ in range(Q):
    q = input().split()
    g[int(q[1])] = q[0] == "+"
    print(np.max(m[g][:, ~g], initial=0))
```
pythonの配列が`0`始まりであるのに対して，入力が`1～N`のため，相性が悪いです．
入力が来るたびに`-1`するのを避けるため，Nを`+1`して配列作成に利用します．

`m`は，村人間の友好度を格納した2次元配列です．
村人`a`と`b`の友好度`f = m[a][b] = m[b][a]`です．

`g`は，同好会グループに入会している村人を表す1次元配列です．
`g[i]`が`True`の場合，村人`i`は同好会グループに入会しています．

`m[g][:, ~g]`は，グループ内の村人とグループ外の村人の間の友好度です．
最大値の算出や配列の反転は，`numpy`の機能を利用しています．

## 島探し
https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island

```python:search-island.py
from scipy.ndimage import label

f = lambda: list(map(int, input().split()))
m = [f() for _ in range(f()[1])]
print(label(m)[1])
```
`scipy.ndimage`の`label`関数を使います．
分かり易さのため，標準入力1行を数値リストとして受け取る処理を関数化しています．
2次元配列`m`を`label`関数に渡すと，欲しい出力が2番目に出てきます．

## mod7占い
https://paiza.jp/works/mondai/s_rank_skillcheck_sample/mod7

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

a = [int(input()) for _ in range(int(input()))]
print(sum(not sum(x) % 7 for x in combinations(a, 3)))
```
`itertools`の`combinations`を利用します．
まず，入力を数値リスト`a`として受け取ります．
そして，リスト`a`から取り出した3要素について，その合計が7の倍数であれば`True`，
7の倍数でなければ`False`とします．
リスト`a`から3要素を取り出す全ての組み合わせを試し，`True`の合計を出力します．

## 文字列収集
https://paiza.jp/works/mondai/real_event/word_collection

```python:word_collection.py
from collections import defaultdict

N, M = map(int, input().split())

d = defaultdict(int)
for _ in range(N):
    k, v = input().split()
    d[k] += int(v)

for _ in range(M):
    q = input()
    print(sum(v * k.startswith(q) for k, v in d.items()))
```
`collections`の`defaultdict`を利用します．
文字列とその価格は，辞書型のデータ`d`として保存します．
同じ文字列が複数売っていた場合，その文字列の価格は，合計して1つにまとめます．
例えば，`abcd 14`と`abcd 6`が入力にあった場合，`d["abcd"] ⇒ 20`とします．

各クエリ文字列`q`について，`d`の全データと先頭の文字列が一致するか検証します．
`items`を使うと，辞書の`key`と`value`を取り出してループできます．
自分は掛け算の方が好みですが，以下のように`if`文を書く方法もあります．
```python
    print(sum(v for k, v in d.items() if k.startswith(q)))
```

## 十億連勝
https://paiza.jp/works/mondai/real_event/continuous_winning

```python:continuous_winning.py
from collections import Counter

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

# b：(現在の連勝数, X連勝後に敗北) とその数
b = Counter({(0, False): 1})

for a in A:  # 各ステージの処理
    c = Counter()
    for (w, t), n in b.items():
        if w + a <= X:
            # 全勝しても連勝数がX以下の場合
            c[(w + a, t)] += n  # 全勝パターン
            c[(0, t)] += n * a  # 途中敗北
        else:
            # 全勝すると連勝数がXを超える場合
            c[(0, True)] += n  # X連勝後に敗北
            c[(0, t)] += n * (X - w)  # X連勝以下で敗北
            # n * (w + a - X) パターン # 連勝数がX以上

    b = c  # 状態を更新

print(sum(n for (w, t), n in b.items() if w == X or t) % 10**9)
```
`collections`の`Counter`を利用します．
`b`は，`(現在の連勝数, X連勝後に敗北) とその数`が保存されています．
ステージ単位で`b`を更新し，最後に，`X`連勝中 `or` `X`連勝後に敗北のパターン数の合計を出力します．出力は下9桁に制限します．

ステージ`a`では，まず，空のデータ`c`を用意します．
そして，1つ前のステージでの状態別に，ステージ`a`終了後のパターンを計算します．
全勝しても連勝数が`X`未満の場合，考えるべきなのは，全勝パターンと途中敗北の2つです．
全勝すると連勝数が`X`を超える場合，考えるべきなのは， `X`連勝後に敗北パターンと`X`連勝未満で敗北パターンの2つです．連勝数が`X`以上になるパターンは，考慮不要です．

<details><summary><code>X=3</code>，<code>A=[2, 3]</code>の例</summary>

`b`は以下のように推移します．
* `b`: `((0, False), 1)`
* `b`: `((2, False), 1)`, `((0, False), 2)`
* `b`: `((0, True), 1)`, `((0, False), 7)`, `((3, False), 2)`

1ステージ終了後の全パターン数は，`1 * (A[0] + 1) = 3`です．
2ステージ終了後の全パターン数は，`3 * (A[1] + 1) = 12`です．
`b`には4連勝，5連勝したパターンが記録されない点に注意が必要です．
最大`X=3`連勝するパターン数は，`3`になります．
</details>

# 終わりに
Rank Sの問題は，素のPythonで解くのは大変そうでした．
一方で，適切なパッケージや関数を知っていると楽に解ける問題も多かったです．
最後の問題「十億連勝」は，楽に解く方法が見つからず，一番苦労しました．

関連記事

https://qiita.com/tomtkg/items/2c3b737848e47ff91903

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