C問題をACできなかった因縁の回。
AtCoder Beginner Contest 259 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
def test_all(f):
for i, data in enumerate(eval(f"test_data{f.__name__[0]}")):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
A - Growth Record
A - Growth Record
やってみよう！
A関数を完成させて「Run」ボタンをクリックしよう！
test_dataA = [
{"in": [38, 20, 17, 168, 3], "out": 168},
{"in": [1, 0, 1, 3, 2], "out": 1},
{"in": [100, 10, 100, 180, 1], "out": 90},
]
def A(N, M, X, T, D):
pass
test_all(A)
自由欄
try
こんな感じ
def A(N, M, X, T, D):
return T - D * (X - M) if M < X else T
test_all(A)
結果：提出 #34108134
自由欄
def A(N, M, X, T, D):
return ([T]*(N-X)+[T-D*i for i in range(X+1)])[::-1][M]
test_all(A)
結果：
B - Counterclockwise Rotation
B - Counterclockwise Rotation
やってみよう！
B関数を完成させて「Run」ボタンをクリックしよう！
test_dataB = [
{
"in":[2, 2, 180],
"out": [-2, -2]
},{
"in":[5, 0, 120],
"out": [-2.49999999999999911182, 4.33012701892219364908]
},{
"in":[0, 0, 11],
"out": [0.00000000000000000000, 0.00000000000000000000]
},{
"in":[15, 5, 360],
"out": [15.00000000000000177636, 4.99999999999999555911]
},{
"in":[-505, 191, 278],
"out": [118.85878514480690171240, 526.66743699786547949770]
},
]
import numpy as np
def test_B(f):
for data in test_dataB:
i, o = data.values()
ans = f(*i)
if ans is None: return
if np.allclose(ans, o, rtol=1e-6, atol=0) or np.allclose(ans, o, rtol=0, atol=1e-6):
print("AC: ", end="")
else:
print("WA: ", end="")
print(f"expected: {o}, output: {ans}")
def B(*n):
pass
test_B(B)
自由欄
try
コンテスト中の提出はひどいものだったので、改めてこんな感じ。
回転行列を作ってnumpyで行列とベクトルの積を計算してます。
import numpy as np
def B(a, b, d):
s = np.sin(np.deg2rad(d))
c = np.cos(np.deg2rad(d))
return np.matmul([[c, -s], [s, c]], [a, b])
test_B(B)
結果：提出 #34126212
回転行列の復習
個人的な理解なので、検索したらもっと分かりやすい説明があると思います。
点$(a, b)$の原点との距離を$r$、x軸からの角度を$\phi$とします。ここで、$
\begin{pmatrix}
a \\
b
\end{pmatrix} = \begin{pmatrix}
r \cos\phi \\
r \sin\phi
\end{pmatrix}
$ です。
$$
\begin{aligned}
& \begin{pmatrix}
a' \\
b'
\end{pmatrix} && \\
= \:&\: \begin{pmatrix} % 極座標から直交座標
r\cos\big(\phi+\theta\big) \\
r\sin\big(\phi+\theta\big)
\end{pmatrix} && 極座標系から直交座標系に変換\\
= \:&\: \begin{pmatrix} % 加法定理
r\big(\cos\phi\cos\theta - \sin\phi\sin\theta\big) \\
r\big(\sin\phi\cos\theta + \cos\phi\sin\theta\big)
\end{pmatrix} && 加法定理\\
= \:&\: \begin{pmatrix}
a\cos\theta - b\sin\theta \\
b\cos\theta + a\sin\theta
\end{pmatrix} && \\
= \:&\: \begin{pmatrix}
\cos\theta & -\sin\theta \\
\cos\theta & \sin\theta
\end{pmatrix} \begin{pmatrix}
a \\
b
\end{pmatrix} &&
\end{aligned}
$$
自由欄
C - XX to XXX
C - XX to XXX
やってみよう！
C関数を完成させて「Run」ボタンをクリックしよう！
test_dataC = [
{
"in":['abbaac', 'abbbbaaac'],
"out": "Yes"
},{
"in":['xyzz', 'xyyzz'],
"out": "No"
},
]
def C(S, T):
pass
test_all(C)
自由欄
try
コンテスト中にACできなかったが、その後当日中にACしてたらしい。(記憶がない)
だいたい解説と同じような実装になりました。
def enc(s):
ret = [["", 0]]
for c in s:
if c == ret[-1][0]: ret[-1][1] += 1
else: ret.append([c, 1])
return ret
def C(S, T):
s = enc(S)
t = enc(T)
if len(s) != len(t): return "No"
for c1, c2 in zip(s, t):
# 文字が違う
if c1[0] != c2[0]: return "No"
# 同じ文字、同じ数
if c1[1] == c2[1]: continue
# Sの文字数が多ければNG
if c1[1] > c2[1]: return "No"
# Tの文字数が多いけどSの文字数が2未満だと操作できないのでNG
if c1[1] < 2: return "No"
return "Yes"
test_all(C)
結果：提出 #34153172
場当たり的にロジックを組んでたらバグる、そしてちゃんとしたロジックを組むために最適なデータ構造を選ばなければならない、という教訓の1問です。
自由欄
D - Circumferences
D - Circumferences
やってみよう！
D関数を完成させて「Run」ボタンをクリックしよう！
test_dataD = [
{
"in": [4, [0, -2], [3, 3], [[0, 0, 2], [2, 0, 2], [2, 3, 1], [-3, 3, 3]]],
"out": "Yes"
},{
"in": [3, [0, 1], [0, 3], [[0, 0, 1], [0, 0, 2], [0, 0, 3]]],
"out": "No"
},
]
def D(N, s, t, circles):
pass
test_all(D)
自由欄
try
せっかくなのでコンテスト中は見ることもなかったD問題もやってみます。
なんだか小難しそうですが、全ての円の中心と点s, tを頂点とするグラフを作りながら全探索すればよいのでは？
from collections import deque
def D(N, s, t, circles):
def check(a, b):
d2 = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
return d2 <= (a[2] + b[2]) ** 2 and d2 >= (a[2] - b[2]) ** 2
circles = [s + [0]] + circles + [t + [0]]
q = deque([0])
remined = set(range(1, N+2))
while len(q):
now = q.popleft()
for c in list(remined):
if check(circles[now], circles[c]):
if c == N + 1: return "Yes"
q.append(c)
remined.remove(c)
return "No"
test_all(D)
結果：提出 #34189988
自力ACできた！解説の考え方とも大差なさそうです。
自由欄
まとめ
1ヶ月ちょっとの間でも自分の成長を感じる今日このごろ。
自由欄
AtCoder Inc.
