Educational Codeforces Round 2
A. Extract Numbers
ポイント
- leading zeroの判定をどうするか。len(w)==len(str(int(w))))が今思いつく最良かな？w[0] != “0”で判定もできるけど、w==“0”の場合だけは分けて考える必要あり(“000”のようなケースの条件分岐ミスったせいで数回WA出した…)
- 正規表現で何度もsplitするような時は、words = re.split(”[,;]“,s)とするよりもre.compile()で予め正規表現パターンオブジェクトを生成しておいたほうが高速になるとのこと
- この問題に限った話じゃないけど英文の読解ミスが多い…最初 ’,‘(コンマ)と’;‘(セミコロン)だけじゃなくて’.’(ピリオド)も分割文字だと思ってた。AtCoder以上に問題提出前の確認を念入りにやったほうがトータルで見て効率良さそう
extract_numbers.py
import re
s = input()
ptn = re.compile(r'[,;]')
words = ptn.split(s)
a = ""
b = ""
for w in words:
if w.isdigit() and len(w) == len(str(int(w))):
a += w + ","
else:
b += w + ","
a = '"' + a[:len(a)-1] + '"' if a else "-"
b = '"' + b[:len(b)-1] + '"' if b else "-"
print(a)
print(b)B. Queries about less or equal elements
ポイント
- この問題はシンプル！リストAを昇順ソートしてbisect.bisect_right()を使うだけ
- 複数の整数値を入力として受け取ってソート済リストとして変数格納する術を知った
extract_numbers.py
import bisect
n,m = map(int, input().split())
A = sorted(map(int, input().split()))
B = list(map(int, input().split()))
ans = []
for b in B:
idx = bisect.bisect_right(A, b)
ans.append(idx)
print(*ans)C. Make Palindrome
ポイント
- 回文にできるということは、文字列に登場する各字種をカウントした時に奇数個になるやつが高々1個になるということ
- 既に偶数個ある字種は無視して、奇数個のみの字種で辞書順リストを作り、お尻の字種から順に頭の方の字種に変換していく操作を繰り返すと、奇数個の字種が0か1個にできる
- 回文文字列の作成は、偶数個ある字種を辞書順に先頭から半分個ずつ並べていって、奇数個(個数1)の字種があるならそいつを回文の真ん中に置く。できた文字列を折り返せば回文完成
- 辞書順で文字数カウントしたかったので初めてOrderedDictを使った。…が、最初から入力文字列をソートした上でCounterにかければよかった模様。ただ強い人は結構ord()関数でUnicode値変換して文字数カウントしてた(以下コード例)。速いんかな？
- 奇数の判定っていつもn % 2を使ってたけど、ある人のコードでn & 0x1で判定してたの、なるほど～ってかんじ
alphabet_counter.py
s = input()
a = [0] * 26
for c in s:
a[ord(c)-ord('a')] += 1
make_palindrome.py
from collections import Counter
s = Counter(sorted(list(input())))
odds = [key for key in s if s[key]%2]
l = len(odds)
for i in range(l//2):
s[odds[i]] += 1
s[odds[l-i-1]] -= 1
mid = odds[l//2] if l%2 else ""
ans = "".join([key*(s[key]//2) for key in s])
print(ans + mid + ans[::-1])D. Area of Two Circles’ Intersection
ポイント
- もう浮動小数点演算の誤差何も分からない。これ以上深入りすると精神崩壊してしまう…あととかまで自前関数用意されてるのしゅごい
- 他の方の正解コードコピペ回答でうまくいったが、このサイトやこのサイト、はたまたこのサイトの式に従い実装したら(下記コードのコメントアウト箇所)テストケースの途中でWAになってしまう。実装ミス？
- のところ何やってるか分からない…
- 公式解説のやり方だとうまくいった(answer2)
- 直角三角形の面積を斜辺と角度を使ってで出せるの、言われてみればそうやなって思うけど新鮮でした
area_of_two_circles_intersection.py
#! /usr/bin/env python3
#! /usr/bin/env python3
import sys
import math
from decimal import *
pi = Decimal('3.141592653589793238462643383279502884197169399375105820974')
def cos(x):
getcontext().prec += 2
i, lasts, s, fact, num, sign = 0, 0, 1, 1, 1, 1
while s != lasts:
lasts = s
i += 2
fact *= i * (i-1)
num *= x * x
sign *= -1
s += num / fact * sign
getcontext().prec -= 2
return +s
def sin(x):
getcontext().prec += 2
i, lasts, s, fact, num, sign = 1, 0, x, 1, x, 1
while s != lasts:
lasts = s
i += 2
fact *= i * (i-1)
num *= x * x
sign *= -1
s += num / fact * sign
getcontext().prec -= 2
return +s
def acos(x):
getcontext().prec += 2
y, y0, b = Decimal(0.0), Decimal(0), Decimal(0.5) * Decimal(math.pi)
if x < Decimal(-1.0) or x > Decimal(1.0):
return Decimal(0.0)
for i in range(80):
y0 = y
y += b
if cos(y) < x:
y = y0
b *= Decimal(0.5)
getcontext().prec -= 2
return y
x1, y1, r1 = [Decimal(x) for x in sys.stdin.readline().strip().split(" ")]
x2, y2, r2 = [Decimal(x) for x in sys.stdin.readline().strip().split(" ")]
d = ((x2 - x1) ** 2 + (y2 - y1) ** 2).sqrt()
if d >= r1 + r2:
print(0.0)
elif d <= max(r2 - r1, r1 - r2):
print(Decimal(math.pi) * min(r1, r2) ** 2)
else:
# answer1
f1 = 2 * acos((r1 ** 2 - r2 ** 2 + d ** 2) / (2 * r1 * d))
f2 = 2 * acos((r2 ** 2 - r1 ** 2 + d ** 2) / (2 * r2 * d))
s1 = r1 ** 2 * (f1 - sin(f1)) / 2
s2 = r2 ** 2 * (f2 - sin(f2)) / 2
print(s1 + s2)
# answer2
# angle1 = acos((r1 ** 2 - r2 ** 2 + d ** 2) / (2 * r1 * d))
# angle2 = acos((r2 ** 2 - r1 ** 2 + d ** 2) / (2 * r2 * d))
# tri1 = r1**2 * cos(angle1) * sin(angle1)
# tri2 = r2**2 * cos(angle2) * sin(angle2)
# print(r1**2 * angle1 - tri1 + r2**2 * angle2 - tri2)
# wrong answer1
# f1 = acos((r1 ** 2 - r2 ** 2 + d ** 2) / (2 * r1 * d))
# f2 = acos((r2 ** 2 - r1 ** 2 + d ** 2) / (2 * r2 * d))
# # s = r1**2 * f1 + r2**2 * f2 - ((-d+r1+r2)*(d+r1-r2)*(d-r1+r2)*(d+r1+r2)).sqrt() / 2
# print(s)
# Wrong Answer2
# a = (d**2 + r1**2 - r2**2) / 2
# df = (d**2 * r1**2 - a**2).sqrt()
# ix1, ix2 = (a*dx + dy*df) / (d**2), (a*dx - dy*df) / (d**2)
# iy1, iy2 = (a*dy - dx*df) / (d**2), (a*dy + dx*df) / (d**2)
# ix1 += x1
# ix2 += x1
# iy1 += y1
# iy2 += y1
# cx = (ix1 + ix2) / 2
# cy = (iy1 + iy2) / 2
# if isinstance(cx, complex) or isinstance(cy, complex):
# print(0)
# exit()
# angle1 = acos(((cx-x1)**2 + (cy-y1)**2).sqrt() / r1)
# angle2 = acos(((cx-x2)**2 + (cy-y2)**2).sqrt() / r2)
# s = r1**2 * angle1 + r2**2 * angle2 - d*r1*sin(angle1)
# print(s) E. Lomsat gelral
まだです…
F. Edge coloring of bipartite graph
まだです…
以上です。