abc 310考察（A~C）

今回はバーチャル参加で回答を提出しました。

# A問題(Order Something Else)
[問題文](https://atcoder.jp/contests/abc310/tasks/abc310_a)
**提出したコード**
```python:abc_310_A.py
N, P, Q = map(int, input().split())
D = list(map(int, input().split()))

payment = P

for i in range(N):
    payment = min(payment, D[i]+Q)

print(payment)
```
**振り返り**
今回の問題の標準出力は最小の支払金額である。
よって最小の支払金額を求めるコードをかけばよい。
以下二点に注目すれば上記のようなコードが書けると思う。

**1. 支払金額は具体的にどう表せるのか。**
   　 P(通常料金) か D[i]+Q（セット割引料金）で表せる。

**2. 支払金額のうち最小のものをどう求めるか。**
   　 今回の制約はゆるいのでループによる全探索でいけそう。
    最小の支払金額を保持する変数をループの中でmin()をつかって更新すればいけそう。


# B問題(Strictly Superior)
[問題文](https://atcoder.jp/contests/abc310/tasks/abc310_b)
**提出したコード**
```python:abc_310_B.py
def price_or_alpha_feature_condition_checker(product_i, product_j):
    if product_i[0] > product_j[0]:
        return True
    i_feature_list = product_i[2:2+product_i[1]]
    j_feature_list = product_j[2:2+product_j[1]]
    for feature in j_feature_list:
        if feature not in i_feature_list:
            return True
    return False

def enough_feature_condition_checker(product_i, product_j):
    i_feature_list = product_i[2:2+product_i[1]]
    j_feature_list = product_j[2:2+product_j[1]]
    for feature in i_feature_list:
        if feature not in j_feature_list:
            return False
    return True

def compare(i, j):
    product_i = products[i]
    product_j = products[j]

    price_condition = True if product_i[0] >= product_j[0] else False
    enough_feature_condition = enough_feature_condition_checker(product_i, product_j)
    price_or_alpha_feature_condition = price_or_alpha_feature_condition_checker(product_i, product_j)
    if price_condition and enough_feature_condition and price_or_alpha_feature_condition:
        return True
    else:
        return False

N, M = map(int, input().split())
products = []

for _ in range(N):
    products.append(list(map(int, input().split())))

for i in range(N):
    for j in range(N):
        there_is = compare(i,j)
        if there_is:
            break
    if there_is:
        break

if there_is:
    print("Yes")
else :
    print("No")
```
**振り返り**
今回のコードはとりあえず実装できたがすごく汚い。。。
[公式解説](https://atcoder.jp/contests/abc310/editorial/6797)と[その他の解説](https://qiita.com/hyouchun/items/17566069cf5915a19e42)をもとにリファクタリングに取り組んでみた。以下リファクタリングしたコードである。
```python:abc_310_B_refactoring.py
N, M = map(int, input().split())
P, F = [], []

for _ in range(N):
    p, c, *f = map(int, input().split())
    P.append(p)
    F.append(set(f[2:]))

ans = False

for i in range(N):
    for j in range(N):
        ans |= P[i] >= P[j] and F[j].issuperset(F[i]) and (P[i] > P[j] or len(F[j]) > len(F[i]))

print("Yes" if ans else "No")
```

ポイントとしては2つある。
**1.各条件が真か偽かをどう判定するのか。**
　自分が初めに実装したコードでは関数をそれぞれ作りTrue, Falseを返していたが、リファクタリング後では式として表している。
**2.各条件が真か偽かをどう保持するのか。**
　累算代入演算子を使ってループの全探索で更新できる。


今回ためになったことは以下である。
* 変数前方のアスタリスクの役割が理解できた。
* 集合同士の比較（要素それぞれではなく要素すべて）ではset()が早いし使いやすい。→setはハッシュテーブル使っているから探索が高速。
* ansに三つの条件を集約し、累算代入演算子をつかうことで出力の条件分岐が楽に更新できる。
* 地味にfor文はスコープを形成しないことは勉強になった。

# C問題(Reversible)
[問題文](https://atcoder.jp/contests/abc310/tasks/abc310_c)
**提出したコード**
```python:abc_310_C.py
N = int(input())
shaping_sticks = []

for i in range(N):   
    stick = input() 
    if (stick in shaping_sticks):
        pass
    elif (stick[::-1] in shaping_sticks):
        pass
    else :
        shaping_sticks.append(stick)

print(len(shaping_sticks))
```
**振り返り**
今回のコードはTLEとなってしまいACが出せなかった。
[公式解説](https://atcoder.jp/contests/abc310/editorial/6792)を参考にリファクタリングしたコードが以下

```python:abc_310_C_refactoring.py
N = int(input())
shaping_sticks = set()

for i in range(N):   
    stick = input() 
    shaping_sticks.add(min(stick, stick[::-1]))

print(len(shaping_sticks))
```

ポイントとしては2つある。
**1.棒の種類の数をどう求めるのか。**
   　 set()に保存していってlen()で求める。
**2.同じか異なるかをどう判定するのか。**
    　set()を使えばハッシュテーブルにより判定がしやすくなる、または判定が必要なくなる。


今回ためになったことは以下である。
* set()によってinの計算量が定数オーダーにできる。
* min()はStr型にも使えて、辞書順で最小なものを取得できる。