振り返りです。
AtCoder Beginner Contest 275 - 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関数を完成させて「Run」ボタンをクリックしよう！
def B(A, B, C, D, E, F):
pass
print(B(2, 3, 5, 1, 2, 4)) # 22
print(B(1, 1, 1000000000, 0, 0, 0)) # 1755647
print(B(*[10**8] * 6)) # 0
自由欄
try(WA)
「そういやNumpyに累積積のメソッドあったよなぁ～」と戯れに使ってみたらWAとなりました…
参照）numpy.cumprod — NumPy v1.23 Manual
import numpy as np
def B(*a):
a = np.array(a)
return (a[:3].cumprod()[-1] - a[3:].cumprod()[-1]) % 998244353
print(B(2, 3, 5, 1, 2, 4)) # 22
print(B(1, 1, 1000000000, 0, 0, 0)) # 1755647
print(B(*[10**8] * 6)) # 0
結果：#36043091
というか累積積じゃなくて普通にprod でよかった。dtypeをobjectにすればオーバーフローを回避可能。
import numpy as np
def B(*a):
a = np.array(a, dtype=object)
return (a[:3].prod() - a[3:].prod()) % 998244353
print(B(2, 3, 5, 1, 2, 4)) # 22
print(B(1, 1, 1000000000, 0, 0, 0)) # 1755647
print(B(*[10**8] * 6)) # 0
結果：#36498235
自由欄
try(AC)
どうしても乗算をまとめたかったので以下のようにしてACとなりましたが…
from functools import reduce
from operator import mul
def B(*a):
return (reduce(mul, a[:3]) - reduce(mul, a[3:])) % 998244353
print(B(2, 3, 5, 1, 2, 4)) # 22
print(B(1, 1, 1000000000, 0, 0, 0)) # 1755647
print(B(*[10**8] * 6)) # 0
結果：#36046116
mathモジュールにprod 関数あるやんけ！！！！！
from math import prod
def B(*a):
return (prod(a[:3]) - prod(a[3:])) % 998244353
print(B(2, 3, 5, 1, 2, 4)) # 22
print(B(1, 1, 1000000000, 0, 0, 0)) # 1755647
print(B(*[10**8] * 6)) # 0
結果：#36499406
ちょうど3.8からの追加なのでAtcoderのPyPy3では使えないので注意です。
︙
と思いmathモジュールを眺めてみると、gcd やlcm もあるんですね。
from math import gcd, lcm
# 最大公約数 バージョン 3.5 で追加.
gcd(6, 9)
# 最小公倍数 バージョン 3.9 で追加.
lcm(6, 9)
やってみよう！
C関数を完成させて「Run」ボタンをクリックしよう！
test_dataC = [
{
"in":[['##.......', '##.......', '.........', '.......#.', '.....#...', '........#', '......#..', '.........', '.........']],
"out": 2
},{
"in":[['.#.......', '#.#......', '.#.......', '.........', '....#.#.#', '.........', '....#.#.#', '........#', '.........']],
"out": 3
},
]
def C(S):
pass
test_all(C)
自由欄
try(振り返り)
コンテスト中は正方形の判定に手こずりました。以前の凸包アルゴリズム を引っ張り出したりしてるうちに泥沼にハマりACならず…
以下の振り返りでは、
前処理として2点間の距離(の二乗)を求めておき、
全ての点から4つを選ぶパターンを全探索。
⇨4点のうち2点を結ぶ距離(6つ)が正方形の4辺と対角線の条件を満たしているか判定
という流れて実装しました。
from itertools import combinations
def C(S):
def dist(a, b):
x1, y1 = a
x2, y2 = b
return (x1 - x2) ** 2 + (y1 - y2) ** 2
points = []
for i in range(9):
for j in range(9):
if S[i][j] == "#":
points.append((i, j))
p_len = len(points)
dists = [[None] * p_len for _ in range(p_len)]
for i in range(p_len):
for j in range(i+1, p_len):
d = dist(points[i], points[j])
dists[i][j] = d
dists[j][i] = d
cnt = 0
for com in combinations(range(p_len), 4):
d = []
for pair in combinations(com, 2):
a, b = pair
d.append(dists[a][b])
s = set(d)
if not len(s) == 2: continue
edge = min(s)
diag = max(s)
if d.count(edge) != 4: continue
if diag == 2 * edge: cnt += 1
return cnt
test_all(C)
結果：#36509602
自由欄
解説を見る
上の提出は2つ目の解説 の考え方と大体一緒ですが、どうもコードがごちゃついてます。3つ目の解説 がスッキリしてるのでトレースしてみます。
from itertools import product
def C(S):
cnt = 0
for x1, y1, x2, y2 in product(range(9), repeat=4):
if (
x2 > x1 and
y2 >= y1 and
S[x1][y1] == "#" and
S[x2][y2] == "#"
): pass
else: continue
a = x2 - x1
b = y2 - y1
x3 = x2 - b
y3 = y2 + a
x4 = x1 - b
y4 = y1 + a
if(
0 <= x3 <= 8 and
0 <= y3 <= 8 and
0 <= x4 <= 8 and
0 <= y4 <= 8 and
S[x3][y3] == "#" and
S[x4][y4] == "#"
): cnt += 1
return cnt
test_all(C)
結果：#36510301
自由欄
解説を見る2
せっかくなので1つ目の解説 も見てみます。
from itertools import combinations
def C(S):
points = []
for i in range(9):
for j in range(9):
if S[i][j] == "#":
points.append((i, j))
cnt = 0
for i1, i2 in combinations(range(len(points)), 2):
x1, y1 = points[i1]
x2, y2 = points[i2]
a = x2 - x1
b = y2 - y1
x3 = x2 - b
y3 = y2 + a
x4 = x1 - b
y4 = y1 + a
if(
0 <= x3 <= 8 and
0 <= y3 <= 8 and
0 <= x4 <= 8 and
0 <= y4 <= 8 and
S[x3][y3] == "#" and
S[x4][y4] == "#"
):
cnt += 1
return cnt // 2
test_all(C)
結果：#36510669
自由欄
やってみよう！
D関数を完成させて「Run」ボタンをクリックしよう！
test_dataD = [
{
"in":[2],
"out": 3
},{
"in":[0],
"out": 1
},{
"in":[100],
"out": 55
},{
"in":[1000000000000000000],
"out": None
},
]
def D(N):
pass
test_all(D)
自由欄
try(振り返り)
コンテスト中は見てもいないD問題ですが、せっかくなのでやってみます。
from functools import lru_cache
@lru_cache(None)
def D(N):
if N == 0: return 1
return D(N // 3) + D(N // 2)
test_all(D)
結果：#36512335
「メモ化」やlru_cache を知らなくとも、「引数同じ呼び出し多そうじゃね？」という気付きがあれば自力でメモ化のアイディアにたどり着けるかもしれません。
memo = {}
def D(N):
if N in memo: return memo[N]
if N == 0: return 1
ans = D(N // 3) + D(N // 2)
memo[N] = ans
return ans
test_all(D)
結果：#36512675
lru_cacheより速い…！Pythonで提出 してみたらさらに速くなりました。
自由欄
一言
E問題 も見てみましたが、『確率 mod』の意味が分からず諦めました…
コンテスト中に取り掛かれるようになった時にちゃんと調べよう
自由欄
AtCoder Inc.
