masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

ABC187 解説（A～C）

AtCoder 高校数学 python3

はじめに

Twitterを見ていると，意外と競技プログラミングに出てくる高校数学に慣れ親しんでいない人が多いという話だったので，簡単な問題でも解説記事は需要があるかもしれないと思ったので，解説記事を書くことにしました．また，最近ABCにはあまり参加できていなかったのですが公式Editorialはテキストベースから動画ベースに変わったのでしょうか？動画を見るのがめんどくさい，移動中なのでテキストが良いという人もいそうなのでそういう意味でも解説記事は価値がある（と思いたい）．なお，Pythonでの解説とする．

A - Large Digits

A - Large Digits - 3桁の文字列を1桁ずつに分割する - 文字列をint型に変換する という2つのことができればＯＫ

A, B = input().split()

if int(A[0]) + int(A[1]) + int(A[2]) < int(B[0]) + int(B[1]) + int(B[2]):
  print(int(B[0]) + int(B[1]) + int(B[2]))
else:
  print(int(A[0]) + int(A[1]) + int(A[2]))

Pythonでは文字列はリストのようにindex（何文字目か）を指定してその文字を取り出すことができます．さらにそれをintで囲んで整数型に変換して和を求めればＯＫです．
別解

sumA = sum(int(i) for i in A)

のようにしていっぺんに整数に変換することもできます．

A, B = input().split()
sumA = sum(int(i) for i in A)
sumB = sum(int(i) for i in B)
if sumA < sumB:
  print(sumB)
else:
print(sumB)

B - Gentle Pairs

B - Gentle Pairs - 2点の座標から直線の傾きを求める ことができればＯＫです．ここで，その方法を復習します．

そもそも，（ xy平面上の）直線は y = ax + bという形で表すことができます（実はこの形ではx=kというようなy軸に平行な直線を表すことができない．しかし，このようなことが起こるのは2点のx座標が一致するときであり，今の問題では条件からこのような状況は除外されている）．このaを傾き，bを（y）切片といいます．今の問題では切片は関係ないのでaについてだけ考えます．

傾きaの求め方

公式的に書けば，直線の傾きは「yの増加量／xの増加量」となります．

f:id:masuTomo:20210105212407p:plain
つまり，2点のx座標の差とy座標の差を計算すればよい．
　　 したがって，2点の座標をそれぞれ(x_1,y_1),(x_2,y_2)とすると，傾きを\frac{y_2-y_1}{x_2-x_1}として求めることができる．したがって，問題文に書かれている条件は -1 \leq \dfrac{y2-y1}{x2-x1} \leq 1ということになる．しかし，これをそのまま実装してしまうとWAとなってしまう．テストケースがわからないので想像だが，傾きを求めるときの除算の処理で誤差が発生したものによると考えられる．

除算での誤差への対処

では，どうすればよいかと言えば条件の不等式-1 \leq \frac{y_2-y_1}{x_2-x_1} \leq 1の分母を払ってしまえばよい．つまり不等式全体にx_2-x_1を掛けるのである．ただし，ここでも注意が必要で，それは不等式に掛け算をするときは掛ける値がマイナス（負）の場合は不等号の向きが反対になってしまうのである．しかも，今のままではx_1とx_2のどちらが大きいかわからないので，x_2-x_1が正なのか負なのかが確定しない（iによって異なる）．そこで，傾きを計算する前にx_1とx_2の大小をチェックして，次のようにしてx_1の方を小さくなるようにしておけばよい（あるいは絶対値を用いても良い）．

if x1 > x2: x1, x2 = x2, x1

こうしておくことで，分母を払うときに不等号の向きを変えなくて済むようになる．

以上のことを考慮して実装すると次のようになる．

N = int(input())
XY = []
for i in range(N):
  x, y = map(int,input().split())
  XY.append([x,y])

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    x1, y1 = XY[i][0], XY[i][1]
    x2, y2 = XY[j][0], XY[j][1]
    #(x1,y1)を左側にする
    if x1 > x2:
      x1, x2 =x2, x1
      y1, y2 =y2, y1
    if x1 - x2 <= y2-y1 <= x2-x1: ans += 1

print(ans)

C - 1-SAT

C - 1-SATは，与えられた文字列の中に，すべての文字列について「abc」だけ，または「!abc」だけがあるような状況になっているときに限り「satisfiable」である．したがって，Pythonではsetを用いて「!」が混じっている文字列のセットと「!」が混じっていない文字列のセットを用意し，それらのセットを比べればよい．

N = int(input())
SE = set()
S = set()
for i in range(N):
  s = input()
  if '!' == s[0]:
    SE.add(s[1:])
  else:
    S.add(s)
for s in S:
  if s in SE:
    print(s)
    exit()

for s in SE:
  if s in S:
    print(s)
    exit()
    
print('satisfiable')