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

振り返りです。

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 - Find Takahashi

略

B - ABC-DEF

やってみよう！

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 - Counting Squares

やってみよう！

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つ目の解説がスッキリしてるのでトレースしてみます。
上では「点から4つ選ぶパターンを全探索」でしたが、こちらでは「マス(9x9)から2つ選ぶパターンを全探索」で前処理等も不要なので、だいぶ実行時間も短縮されました。

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 <= 0 x3 <="8" and s[x3][y3]="=" "#" s[x4][y4]="=" ): cnt +="1" return cnt< py-cell> test_all(C)

結果：#36510301

自由欄

解説を見る2

せっかくなので1つ目の解説も見てみます。
上が「マス(9x9)から2つ選ぶパターンを全探索」だったのに対して、こちらでは「点から2つ選ぶパターンを全探索」なので、さらに時間短縮となっています。(数ミリ秒ですが)
正方形判定の考え方は上と同様。

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 <= 0 x3 <="8" and s[x3][y3]="=" "#" s[x4][y4]="=" ): cnt +="1" return 2< py-cell> test_all(C)

結果：#36510669

自由欄

D - Yet Another Recursive Function

やってみよう！

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より速い…！
そしてPyPyは再帰コールが遅いことを思い出してPythonで提出してみたらさらに速くなりました。

自由欄

一言

E問題も見てみましたが、『確率 mod』の意味が分からず諦めました…
逆元とか逆数とか…

コンテスト中に取り掛かれるようになった時にちゃんと調べよう