振り返りです。
AtCoder Beginner Contest 266 - 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}")
略
B - Modulo Number
B - Modulo Number
やってみよう！
B関数を完成させて「Run」ボタンをクリックしよう！
def B(N):
pass
print(B(998244354)) # 1
print(B(-9982443534)) # 998244349
自由欄
try
やってみたらできた、という感じ。
def B(N):
return N % 998244353
print(B(998244354)) # 1
print(B(-9982443534)) # 998244349
結果：提出 #34376944
自由欄
【補足】pythonの剰余演算でマイナスの場合について
要点は以下の3つです。
剰余演算子は常に第二引数と同じ符号 (またはゼロ) の結果になります6. 式 (expression) — Python 3.10.6 ドキュメント
切り捨て除算演算と剰余演算は、恒等式: x == (x//y)*y + (x%y) の関係にあります。6. 式 (expression) — Python 3.10.6 ドキュメント
(整数除算の)結果は常に負の無限大の方向に丸められます。組み込み型 — Python 3.10.6 ドキュメント
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)
本問では、上で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」ボタンをクリックしよう！
test_dataC = [
{"in": [[0, 0], [1, 0], [1, 1], [0, 1]], "out": "Yes"},
{"in": [[0, 0], [1, 1], [-1, 0], [1, -1]], "out": "No"},
{"in": [[0.1, 0.1], [1, 0], [1, 1], [0, 1]], "out": "Yes"},
]
def C(*points):
pass
test_all(C)
自由欄
try
ムズかった…解説 も三者三様といった感じで、分かりやすい定番の方法があるってタイプの問題じゃなさそうです。
私は予備知識ゼロだったので、コンテスト中に必死にググって以下のサイトのたどり着きました。
Pythonで凸包を求める方法 \| You Look Too Cool
「外積を使うと、対象となる点が、ある向きに対して右にあるか左にあるかを判定できます」とのこと。
という訳で実装してみたのが以下。
import numpy as np
def C(*points):
points = np.array(points)
for i in range(2):
a = points[i - 1] - points[i]
b = points[(i + 1) % 4] - points[i]
c = points[(i + 2) % 4] - points[i]
o = [np.cross(a, c), np.cross(b, c)]
if min(o) < 0 and max(o) > 0:
pass
else:
return "No"
return "Yes"
test_all(C)
結果：提出 #34398966
自由欄
ギフトラッピング法(Gift wrapping algorithm)
せっかくなので、上で参照したサイトで紹介されていたギフトラッピング法を実装してみました。
ギフト包装法 - Wikipedia
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 - Snuke Panic (1D)
やってみよう！
D関数を完成させて「Run」ボタンをクリックしよう！
test_dataD = [
{"in": [3, [[1, 0, 100], [3, 3, 10], [5, 4, 1]]], "out": 101},
{"in": [3, [[1, 4, 1], [2, 4, 1], [3, 4, 1]]], "out": 0},
{
"in": [
10,
[
[1, 4, 602436426],
[2, 1, 623690081],
[3, 3, 262703497],
[4, 4, 628894325],
[5, 3, 450968417],
[6, 1, 161735902],
[7, 1, 707723857],
[8, 2, 802329211],
[9, 0, 317063340],
[10, 2, 125660016],
],
],
"out": 2978279323,
},
]
def D(N, TXA):
pass
test_all(D)
# 以下、AtCoder 提出用
# N = int(input())
# TXA = [list(map(int, input().split())) for _ in range(N)]
# print(D(N, TXA))
自由欄
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] += a
dp = new
return max(dp)
test_all(D)
結果：提出 #34406688
解説を見る
入力が「すぬけ君が出現する時間・場所」だけだからDPで扱いづらいなぁ～と思っていたら、解説 のpythonコード ではDPと同じ長さの配列を予め用意した上で入力を受け取っているんですね。
ほんで、私の提出では $時刻T_i >= 座標X_i$ のときだけすぬけ君をゲットできる、という分岐を入れているんですが(14行目)、解説ではそのような処理がありません。-10**18で初期化されています。
自由欄
自由欄
AtCoder Inc.
