ABC310振り返り

ABCの3完！ペナ量産回！フハハハ！！
でも、klu大学さんのおかげで緑パフォでたよありがとう…！！！たなぼた！！！！

A問題

atcoder.jp

問題概要

P円のドリンク飲みたい！

• 方法その1：単品購入　P円
• 方法その2：セット購入　Q円 + 料理の値段（セットにする料理はN種類の中から1つ自由に選べる）

いっちゃん安い方法で飲みたい！

考察

• P円（単品）　と　Q円 + 料理リストの中でいちばん安い値段 （セット）の小さい方を出力しよう

コード

# 入力
n, p, q = map(int, input().split())
a = list(map(int, input().split()))

# セット価格
set_p = q + min(a)

# 単品とセット価格を比べ、安い方を出力
print(min(p, set_p))

感想

本番は慌てて変なコード書いたけど、方針はいっしょ
シンプルに考えよう、シンプルに…（念）

B問題

atcoder.jp

問題概要

商品Aに対しての、上位互換商品Bがあるか調べたいよ
定義は3つあるよ

• 商品Aと商品Bの値段を比べたとき、商品Bは同価格または安い
• 商品Aにある機能を、商品Bは全て持っている
• 商品Aより商品Bは安い、または、商品Aより商品Bは機能が多い

考察

• 制約がN≦100なので、O(N²) = 10⁴ で、二重ループの全探索が余裕！
• 配列内を上手に分割してあげよう
• 条件②については、部分集合（AはBの一部か）を判定してあげよう

コード

# 入力
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]

for a in range(n):
    for b in range(n):
        
        price_a = g[a][0] # 商品Aの値段
        price_b = g[b][0] # 商品Bの値段
        func_a = g[a][1] # 商品Aの機能数
        func_b = g[b][1] # 商品Bの機能数
        func_a_set = set(g[a][2:]) # 商品Aの機能の種類
        func_b_set = set(g[b][2:]) # 商品Bの機能の種類
        
        # 条件① 商品Aと商品Bの値段を比べたとき、商品Bは同価格または安い
        if price_a >= price_b:
            # 条件②商品Aにある機能を、商品Bは全て持っている（部分集合判定）
            if func_a_set.issubset(func_b_set):
                # 条件③商品Aより商品Bは安い、または、商品Aより商品Bは機能が多い
                if func_a < func_b or price_a > price_b:
                    # 全て当てはまったら即座にYesで終了
                    exit(print('Yes'))

# 当てはまるものがなかったらNo
print('No')

感想

公式解説、たしかにすごかった！すごかった！！
なので、わたしは分かりやすさ重視で書いてみた！！！ あれ、M、使わなかったな…

C問題

atcoder.jp

問題概要

N個の文字列が入っている、配列Aがあるよ。
abc と、反転した cba は同じ種類と見做すよ。
文字列は、何種類ある？

考察

• a, ab, ba の3つの文字列がある場合、答えは 2 種類になる

他の文字列と比較して解く

• 配列Aから、同じ種類のものを判定し、引く作戦
• カウント用変数 cnt を用意
• 各文字列について、反転したものと同じものがAの中にあるかつ、反転したものが自分自身ではない場合、cnt += 1
  • a は、反転したもの（a）と同じものがAの中にある、かつ、反転したもの（a）が自分自身なので、カウントしない
  • ab は、反転したもの（ba）と同じものがAの中にある(ba) かつ、反転したもの（ba）が自分自身（ab）ではないので、カウントを+1する
  • ba は、反転したもの（ab）と同じものがAの中にある(ab) かつ、反転したもの（ab）が自分自身（ba）ではないので、カウントを+1する
• 重複でカウントするため、cntをわる2する
• 配列Aの長さから cnt を引き算

バグらせ狂ったので、本番はACしたけど、他の方法を学ぶどん！

正規化して解く

• 正規化とは：データを扱いやすいようにしてあげること！主に重複削除のことを指す
• 今回『どんな文字列』が何種類ある？とは問われていないので、文字列自体はどうでもいい（？！）
• ab ab ba は同じとみなすので、全て辞書昇順（または降順）で揃え ab ab ab に揃えたら、かんたんに重複を削除できる！
• ab と、反転した ba を比較して、大きい方（または小さい方）を、setに入れてあげれば重複削除ができる！！（すごい）

コード 他の文字列と比較

# 入力
n = int(input())
# setで入力して、普通の重複は削除しておく
a = set(input() for _ in range(n))

# 種類数（この時点で、反転は別種類と判断している）
ans = len(a)
cnt = 0

for i in a:
    # iを反転したものがaの中にあるかつ、iを反転したものとiが不一致なら
    if i[::-1] in a and i[::-1] != i:
        cnt += 1

# 重複削除
cnt //= 2
print(ans - cnt)

コード 正規化

# 入力
n = int(input())
a = [input() for _ in range(n)]

# 答え格納用set 重複は自動的に削除される
c = set()

for i in a:
    # aの中の各iについて
    # 自分自身と、反転したものを比較。大きい方をcへ入れる
    c.add(max(i, i[::-1]))

# cの要素数を出力
print(len(c))

感想

正規表現と正規化を勘違いしてたので、ついでに両方学んだ！
用語を知るだけじゃなくて、理解するができてよかったあ

DとEはわたしにはまだはやすぎた腐ってやがる！になるので、あきらめた！！またね！！！

来週のburiodenは

女子大生とおいしいパンケーキして、お昼寝したあとに、ABCやるぞお！！うおおおおおお！！！！！！