abc 310考察（A~C）

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

A問題(Order Something Else)

問題文
提出したコード

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)

問題文
提出したコード

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

振り返り
今回のコードはとりあえず実装できたがすごく汚い。。。
公式解説とその他の解説をもとにリファクタリングに取り組んでみた。以下リファクタリングしたコードである。

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)

問題文
提出したコード

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が出せなかった。
公式解説を参考にリファクタリングしたコードが以下

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型にも使えて、辞書順で最小なものを取得できる。