ABC266の振り返り(A, B, C, D)
振り返りです。
A - Middle Letter
略
B - Modulo Number
やってみよう！
B関数を完成させて「Run」ボタンをクリックしよう！
自由欄
try
やってみたらできた、という感じ。
def B(N): return N % 998244353 print(B(998244354)) # 1 print(B(-9982443534)) # 998244349結果：提出 #34376944
自由欄
【補足】pythonの剰余演算でマイナスの場合について
要点は以下の3つです。
dm = lambda a, b: print( f"{a:2} // {b:2} = {a // b:2} {a:2} % {b:2} = {a % b:2} 参考：{divmod(a, b)=}" ) dm(4, 3) dm(-4, 3) dm(4, -3) dm(-4, -3)剰余演算子は常に第二引数と同じ符号 (またはゼロ) の結果になります
参照) 6. 式 (expression) — Python 3.10.6 ドキュメント切り捨て除算演算と剰余演算は、恒等式: x == (x//y)*y + (x%y) の関係にあります。
参照) 6. 式 (expression) — Python 3.10.6 ドキュメント(整数除算の)結果は常に負の無限大の方向に丸められます。
組み込み型 — Python 3.10.6 ドキュメント
本問では、上で2つ目に引用した恒等式がまんま当てはまります。(以下のyが998244353)
x == (x//y)*y + (x%y)⇨
x - (x%y) == (x//y)*y
また1つ目の引用の通り、剰余演算の結果は被除数の符号に関わらず除数と同じ符号になるので、「0以上」という題意も満たせる訳ですね。
C - Convex Quadrilateral
mnt/cp/ABC266/t (7) - JupyterLab
やってみよう！
C関数を完成させて「Run」ボタンをクリックしよう！
自由欄
try
ムズかった…
解説も三者三様といった感じで、分かりやすい定番の方法があるってタイプの問題じゃなさそうです。
私は予備知識ゼロだったので、コンテスト中に必死にググって以下のサイトのたどり着きました。
Pythonで凸包を求める方法 \| You Look Too Cool
「外積を使うと、対象となる点が、ある向きに対して右にあるか左にあるかを判定できます」とのこと。
という訳で実装してみたのが以下。
凸なら対角は2辺の延長線に挟まれた領域にあるだろう、っていう条件で判定してます。
計算が面倒くさいのでnumpyを使うことに。
結果：提出 #34398966
自由欄
ギフトラッピング法(Gift wrapping algorithm)
せっかくなので、上で参照したサイトで紹介されていたギフトラッピング法を実装してみました。
import numpy as np def ch(points): """Return convex hull by Gift-wrapping algorithm. Parameters ---------- points : array_like [[x_1, y_1], [x_2, y_2], ..., [x_n, y_n]] Returns ------- convex hull : ndarray [[x_1, y_1], [x_2, y_2], ..., [x_1, y_1]] """ if not isinstance(points, np.ndarray): points = np.array(points) # 出発点の設定 start_idx, _ = points.argmin(axis=0) ret = [points[start_idx]] nex_idx = start_idx - 2 while nex_idx != start_idx: now = ret[-1] # 探索の初期値はテキトー。自分以外であれば何でも良い。 nex_idx += 1 nex_idx %= len(points) a = points[nex_idx] - now # nowから見て最も左側にある点を全探索 for i in range(len(points)): b = points[i] - now if np.cross(a, b) > 0: a = b nex_idx = i ret.append(points[nex_idx]) return np.array(ret) import matplotlib.pyplot as plt def plot_ch(n, f): """凸包生成確認用描画関数 """ # ランダムな点を生成 x, y = np.random.normal(size=(2, n)) # 凸包を計算 boundary = f(np.array([x, y]).T) # 描画 fig, ax = plt.subplots() ax.scatter(x, y) ax.plot(*boundary.T, color="red") ax.axis("square") return plt.show() plot_ch(1000, ch)Graham scan
もう一つ、凸包を求める簡単なアルゴリズムとしてGraham scanというものがあるようです。
上のギフトラッピング法だと最悪$O(n^2)$ですが、Graham scanでは$O(n \log n)$の計算量になるらしい。
という訳で以下実装してみました。
from operator import itemgetter as ig import numpy as np def ch2(points): """Return convex hull by Graham scan algorithm. Parameters ---------- points : array_like [[x_1, y_1], [x_2, y_2], ..., [x_n, y_n]] Returns ------- convex hull : ndarray [[x_1, y_1], [x_2, y_2], ..., [x_1, y_1]] """ if not isinstance(points, np.ndarray): points = np.array(points) # 出発点の設定 start_idx, _ = points.argmin(axis=0) ret = [points[start_idx]] x0, y0 = points[start_idx] # 出発点から各点に引いた直線の傾きでソート srtd = sorted( [ [i, (p[1] - y0) / (p[0] - x0)] for i, p in enumerate(points) if i != start_idx ], key=ig(1), ) ret.append(points[srtd[0][0]]) # ソート順に追加しつつ凸包に含まれるか判定 for i, _ in srtd[1:]: now = points[i] while True: a = ret[-1] - ret[-2] b = now - ret[-2] if np.cross(a, b) > 0: break ret.pop() ret.append(now) ret.append(ret[0]) return np.array(ret) plot_ch(1000, ch2)確かに早い！😲
他に手っ取り早い高速化の方法として、x, yの最大値・最小値を持つ4点に囲まれた点は凸包には含まれないので除くという前処理があるようです。が、今回は割愛。
自由欄
D - Snuke Panic (1D)
やってみよう！
D関数を完成させて「Run」ボタンをクリックしよう！
自由欄
try
コンテスト終了後に自力ACしたコードがこちら。
def D(N, TXA): max_t = TXA[-1][0] dp = [0] * 7 j = 0 for i in range(max_t + 1): new = [0] * 7 for k in range(1, 6): new[k] = max(dp[k - 1 : k + 2]) if i == TXA[j][0]: t, x, a = TXA[j] j += 1 if x <= i: new[x + 1] dp="new" return max(dp)< py-cell> test_all(D)結果：提出 #34406688
解説を見る
入力が「すぬけ君が出現する時間・場所」だけだからDPで扱いづらいなぁ～と思っていたら、解説のpythonコードではDPと同じ長さの配列を予め用意した上で入力を受け取っているんですね。
なるほど、その手があったか…！
ほんで、私の提出では $時刻T_i >= 座標X_i$ のときだけすぬけ君をゲットできる、という分岐を入れているんですが(14行目)、解説ではそのような処理がありません。
よくよくコードを読むとDPが-10**18で初期化されています。
これなら $時刻T_i < 座標X_i$ のときに本来はゲットできないすぬけ君を「ゲットした」と算入してしまっても($A_i<10^9$なので)問題ないという訳ですね。
(個人的には、要件と実装の結びつきが明示的でないのは分かりづらいので避けたいところです)
自由欄