ABC187参戦記

今回のABCはお正月に開催されました。
運営のAtCoderさんありがとうございます。

この記事は、茶色下位の私が自分が理解できる内容でABC187のAからC問題までを書いていきます。

使用言語はPython3です。anacondaを利用しているため、Python3.8以降に追加されたメソッドなどは使用していません。

A – Large Digits

標準入出力と、文字列型と整数型の取り扱い、大小比較ができるかを問われる問題。

今回のA問題はA問題の中でも難しい問題だと思います。

各桁の数字の取り出しについて、私は一番簡単だと思うのは、
数字を文字列型として扱いつつ、先頭から数えて何番目にあるかを整数型で取り出す方法です。
ちょっと言葉では何を言っているかわかりにくい表現ですね。

# 変数を文字列として定義
num='123'

# 文字列の0番目を取り出す
d1=num[0]

print(d1) # -> 1
print(type(d1)) # -> <class 'str'>

# 文字列型を整数型として取り出す
d1_int=int(d1)

print(d1_int) # -> 1
print(type(d1_int)) # -> <class 'int'>

今回は制約により、3桁の整数が保証されているので、それぞれについて、整数型として取り出して足し算して、大小比較すればOKです。

# AtCoder Beginner Contest 187
# A - Large Digits

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

n=int(N[0])+int(N[1])+int(N[2])
m=int(M[0])+int(M[1])+int(M[2])

if n>=m:
    print(n)
else:
    print(m)

A問題ということで繰り返し処理を使用しない方法で記載していますが、コンテスト中はfor文を使用しました。

# AtCoder Beginner Contest 187
# A - Large Digits

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

n,m=0,0

for i in range (3):
    n+=int(N[i])
    m+=int(M[i])

print(max(n,m))

B – Gentle Pairs

xy平面上での2点を通る直線の傾きを求められるか、二重のfor文の取り扱いを問われる問題。

xy平面での座標を取り扱う問題については、自作のクラスを使って解いています。

AtCoderの問題でこれらを扱う問題が出るたびに少しずつ改善して、2点を通る直線の傾きも出るようにしました。

今回、自作のクラスを張り付けて、あとは2重のfor文で個数カウントして提出したら終わりだな。と思っていたのですが、サンプルが合いません。バグ取りしようにも焦っており、完全にパニック状態でした。

C問題を先に解いて、D問題も問題を見て、解いてみたけどWAだったため、B問題に戻ってきましたが、コンテスト中に解けませんでした。
この問題が解けたのはコンテスト翌日朝、落ち着いて自作のクラスを1行毎丁寧に見直していき、ようやく解くことができました。

バグらせていた原因は、
y=a(定数)(傾き0)について余計な処理をしていたせいでした。

座標関連のクラスを自作して、必要部分を削除してACしたコードです。

# AtCoder Beginner Contest 187
# B - Gentle Pairs

class Coodinate (object):
    def __init__(self,x=0,y=0):
        self.x=x
        self.y=y

    def lineSlope(self,other):
        deltax=self.x - other.x
        deltay=self.y - other.y
        slope=deltay/deltax
        if -1<=slope<=1:
            return True
        else:
            return False

N=int(input())
ls=[]

for _ in range (N):
    a,b =map(int,input().split())
    p=Coodinate(a,b)
    ls.append(p)

ans=0

for i in range (N):
    for j in range (i+1,N):
        if Coodinate.lineSlope(ls[i],ls[j]):
            ans+=1

print(ans)

傾きは、xの変化量に対するyの変化量ですね。
組み合わせは二重のfor文が理解しやすいと思います。

自分でクラス作っておいて、バグ取りできなかったのは悔しいですね。

C – 1-SAT

ハッシュテーブル(set)の使い方を問われる問題。

問題文を理解するのにものすごい時間かかりました。

入力を全部受け取って、!がついている文字列の内、!がついていないものも入力に含まれていたらそれを出力。上記の条件を満たすものがなければ’satisfiable’を出力。

全てsetで管理、実装しても出来ますが、私はsetがfor文で回すことができるのがあまり理解していなかったので、チェックする!がついている文字列はリストに格納して、!がついていない文字列はsetに格納していき、リストの単語がsetに含まれているかを確認する方法でコンテスト中は提出しました。

# AtCoder Beginner Contest 187
# C - 1-SAT

N=int(input())
ls=[]
st=set()
for _ in range (N):
    S=input()

    if S[0]=="!":
        S=S[1:]
        ls.append(S)
    else:
        st.add(S)

for i in range (len(ls)):
    if ls[i] in st:
        print(ls[i])
        exit()
    else:
        continue

print("satisfiable")

setでもfor文が使用できることが分かったので、listではなくて、すべてsetに入れた場合のコードはこちらです。

# AtCoder Beginner Contest 187
# C - 1-SAT

N=int(input())

st=set()

for _ in range (N):
    S=input()
    st.add(S)

for w in st:
    if w[0]=='!':
        if w[1:] in st:
            print(w[1:])
            exit()

print("satisfiable")

なお、この問題はsetをlistにすると、TLEします。

理由は、listの各要素があるかを判定するのが線形探索となるからです。
for文が1重なので、気づきにくいかもしれません。