ABC259の振り返り(A, B, C, D)

C問題をACできなかった因縁の回。
というわけで振り返りです。

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関数を完成させて「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関数を完成させて「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で行列とベクトルの積を計算してます。
実際これぐらいの計算であれば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} $ です。
原点を中心に$\theta$だけ回転させた点$(a', b')$は以下のようになります。

$$ \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関数を完成させて「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関数を完成させて「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 <= 2 (a[2] + b[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ヶ月ちょっとの間でも自分の成長を感じる今日このごろ。
「振り返ってできる」から「本番でできる」まで成長せねば！