ABC310復習

# ABC310復習
[freee プログラミングコンテスト2023（AtCoder Beginner Contest 310） - AtCoder](https://atcoder.jp/contests/abc310)
## ■結果  
* ABC3完。3完なのに緑パフォ(859)とランクは良かったが、今回はインドの大学が一斉出場して0完が多かった特殊事情の模様。
* Dも含め復習（中々に難しかった）

## ■Ａ問題（Order Something Else）
シンプルに判定文を書いて提出。
所要時間約10分（もう少し速くても良い。）

```python
n,p,q = map(int, input().split())
d_list = list(map(int, input().split()))

dmin=min(d_list)
if dmin < p-q:
    print(dmin+q)
else:
    print(p)
```

## ■Ｂ問題（Strictly Superior）
所要時間30分（ちょっとかかり過ぎ。）
* 出題の上位互換の意味が概念として判り難く、論理の整理に手間取る。
* `int, int, int list`の入力受取り方法をちょっと調査。（`p,c,*funcs = map(int, input().split()`)の可変長リスト受取りを発見）
* 機能表の比較について。setの包含関係で判定したいという辺りは直ぐに発想。しかし、`set1 in set2`で包含判定できるかな、とあてずっぽうで実装してしまいデバグに時間かかる。実際は`set1 <= set2`で判定する必要があった。
以上が整理出来たらコードはシンプルでした。

```python
n,m = map(int, input().split())
funcs = []
products = []
for ii in range(n):
    p,c,*funcs = map(int, input().split())
    products.append([p,c,set(funcs)])
#print(products)
for ii in range(n):
    for jj in range(n):
        if (products[ii][0] >= products[jj][0] and (products[ii][2] <= products[jj][2]) and (products[ii][0] > products[jj][0] or len(products[ii][2]) < len(products[jj][2]))):
            print('Yes')
            exit()
print('No') 
```
**AtCoder解説確認**
公式解説、解説より、[原案者の解法](https://atcoder.jp/contests/abc310/editorial/6797)がシンプル。
そしてsetの包含関係の判定`set1 <= set2`の部分は`set2.isupperset(s1)`でも出来る模様。
直観的に理解しやすい記述で良い。（[Pythonで集合を扱う](https://esu-ko.hatenablog.com/entry/2016/02/06/Python%E3%81%A7%E9%9B%86%E5%90%88%E3%82%92%E6%89%B1%E3%81%86%28set%E3%81%AE%E4%BD%BF%E7%94%A8%29)　）
|  集合 |  メソッド  |
| ---- | ---- |
| ∨ | union |
|∧|	intersection|
|∧|	difference|
|∨-∧|	synemtric_difference|
|∋|	issubset,isupperset|

## ■Ｃ問題（Reversible）
所要時間10分（処理立案、実装とも易しかった。）
”何種類の異なる棒があるか”の処理にsetを使う。setに無い語を追加して行って最後にユニークな要素数をカウントする。
setに無いかの判定を正順・逆順両方でするのがポイント。どっちでsetに追加しても問題無い。（問題名のReversibleがそのままで判り易い。）
逆順の文字列を作るのにはs[::-1]を利用。（リストに変換してreversed()するより文字列スライス記法にお任せ。）
```python
n  = int(input())
ss = set()
for ii in range(n):
    s = input()
    r = s[::-1]
    if s in ss or r in ss:
        continue
    else:
        ss.add(s)
#print(ss)
print(len(ss))
```
**AtCoder解説確認**
解説では平衡二分木を使っているが、順序などの凝った処理の必要がない今回はハッシュテーブルベースのsetで扱っても充分と思った。
[原案者の解法](https://atcoder.jp/contests/abc310/editorial/6792)は流麗。min(S, S[::-1])だけで文字列を辞書順で小さいほうに統一して一意に出来る。そしてsetには比較の必要もなくaddのみで良い。大変コンパクトな記述で素晴らしい。

## ■Ｄ問題（Peaceful Teams）
まず提出が間に合わなかった。次にグループ分けをitertoolsで列挙して判定する方法で解いてみたら完全にTLE。
### １）itertoolsを使って下記を試しTLE
itertoolsの直積(product)を使って下記の方針でチーム分けを生成してみた。
* n人のプレーヤをtチームに分ける＝0～t-1までの数字をn人全てに割り当てると考える。
* そしてそれは0～t-1から重複を許しn回選ぶ順列（重複順列）である。
* そしてそれは0～t-1をn回直積(product)するのに等しい。
```python
from itertools import product

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

# load unpeaceful pairs
pairs = set()
for ii in range(m):
    a,b = map(int, input().split())
    pairs.add((a-1,b-1))
#print(pairs)

count = 0
prods = product(range(t), repeat=n)
for prod in prods:
    Peaceful = True
    if len(set(prod)) == 1:
        continue
    for pair in pairs:
        if prod[pair[0]] == prod[pair[1]]:
            Peaceful = False
    if Peaceful:
        count = count + 1
    #print(prod, Peaceful)
print(count)
```
見事に玉砕。まずかったと思われる点は、このコードは[0,0,1]と[1,1,0]は別のものとして扱うが、出題上同じと扱うべきだった。そのため、組み合わせ数が実際より多く算出されてしまう上、計算量が増えてTLEする。

### ２）以下の解説を元にやりなおし
[AtCoder ABC 310 D - Peaceful Teams (水色, 400 点) - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/entry/2023/07/17/213800)
* 「注意点」の所を読むと何故方法１）が駄目だったか判る。
*  _最小添字規則_ に沿って攻略するべし。
    * 「ここで、選手 00をいきなりグループ 2 やグループ 5 などに入れる意味はないことに注意しよう。選手 0 はグループ 0 に入れればよいのだ。一般に、すでにできているグループが 0,1,…,s−1であるときに、新しい選手を新しいグループに入れることにしたならば、グループ s に入れればよい。このような最小添字規則を導入することで、計算時間が削減できているとも言える。」

[よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/entry/2020/05/04/190252)
* 最小添字規則に沿った列挙に使うアルゴリズムとしては、再帰関数を用いたDFS全探索が適切だそう。（数学力は要らず判っておれば力業でよい、というあたりは自分向きかも。）
* アルゴで何をするか整理すると「チームリストにプレイヤーを１人づつ再帰的に追加する」「その際仲の悪いペアを既存チームに追加しない」「チームリストは0,1,…任意個のチームまで増やしてよい」「n人追加しきった所でtチーム分けの条件に合っているか判定する」

[【AtCoder】ABC310 – D問題について解説【Python】](https://somachob.com/abc310-d/)
* 再帰関数を用いたDFS全探索のpytnonコードを順を追って解説している上記サイトを参考に実装。

```python
n,t,m = map(int, input().split())

# load unpeaceful pairs
NG = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    NG[a].append(b)
    NG[b].append(a)

def is_NG(player, team):
    for member in team:
        if member in NG[player]:
            return True
    return False

def dfs(player,teams):
    global match_count
    if player == n: # 全プレーヤを追加したとき
        if len(teams) == t:
            #print(teams)
            match_count += 1
            return
        else:
            return

    # 既存teamにplayerを追加する（枝を伸ばす）
    for ii in range(len(teams)):
        if is_NG(player, teams[ii]):
            continue
        teams[ii].append(player)
        dfs(player+1,teams)
        teams[ii].pop()

    # 新teamにplayerを追加する（新しい枝を生やす）
    teams.append([player])
    dfs(player+1, teams)
    teams.pop()

match_count = 0
dfs(0,[])
print(match_count)
```
本コードでAC