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

Arakaki Tokyo -

振り返りです。

Panasonic Programming Contest 2022(AtCoder Beginner Contest 273) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.
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 - A Recursive Function

やってみよう！

A関数を完成させて「Run」ボタンをクリックしよう！

def A(N): pass print(A(2)) # 2 print(A(3)) # 6 print(A(0)) # 1 print(A(10)) # 3628800

自由欄

try

A問題っぽくないですが、逆に言えば「再帰関数が分かる、実装できる」ことまでAのレベルで求められるってことですよね…
私はまだまだ新参者ですが、今後も同じレーティングに求められるレベル感は上がっていくんだろうなぁ～😇

def A(N): if N == 0: return 1 return N * A(N - 1) print(A(2)) # 2 print(A(3)) # 6 print(A(0)) # 1 print(A(10)) # 3628800

結果：#36091312

自由欄

B - Broken Rounding

やってみよう！

B関数を完成させて「Run」ボタンをクリックしよう！

test_dataB = [ { "in":[2048, 2], "out": 2100 },{ "in":[1, 15], "out": 0 },{ "in":[999, 3], "out": 1000 },{ "in":[314159265358979, 12], "out": 314000000000000 }, ] def B(X, K): pass test_all(B)

自由欄

try

なかなかの妙問です。
まずはコンテスト中にACした提出がこちら。

def B(X, K): for _ in range(K): if X % 10 >= 5: X += 10 X //= 10 return X * 10 ** K test_all(B)

結果：#35673269

なぜroundではダメなのか？

ここではPythonの組み込み関数についてのみ扱います。

偶数への丸め
ドキュメントに明記されている通り、roundは一般的な四捨五入ではなくいわゆる偶数への丸めで処理します。

# 偶数への丸め。見事に偶数。 for i in range(10): x = i + 0.5 print(x, round(x))

これは処理する桁が少数でなくとも同様なので、

# 偶数への丸め。見事に偶数。 for i in range(10): x = i * 10 + 5 print(x, round(x, -1))

例えば1つ目のテストデータで1桁目を四捨五入した後の2050の結果が2000になってしまいます。

round(2050, -2)

少数の精度問題

「ではいっそのこと少数にしてしまえば、偶数への丸めは回避できるのでは？」という発想で以下のようにコーディングしてみます。

from math import log10, ceil def B_ng(X, K): keta = ceil(log10(X)) X /= 10 ** keta for i in range(K): X = round(X, keta - 1 - i) return int(X * 10 ** keta)

が、やはり1つ目のテストデータでWAとなってしまいます。

test_all(B_ng)

結論から言えば、少数にも偶数への丸めは適用されます。
それに加えて、ほとんどの小数が浮動小数点数で正確に表せないことによって別の問題も生じてしまいます。

例を見てみましょう。
以下は少数のround結果と、小数点以下20桁の精度まで表示したものです。

for i in range(10): x = 0.05 + i / 10 print(f'{x:.2f}', round(x, 1), f'{x:.20f}')

例えば0.35は内部的に0.35よりわずかに小さい数として保持されているため、少数第2位でroundすると0.3になっています。
逆にわずかに大きな値は切り上げで処理されているのが分かります。
他方で0.25と0.75は浮動小数点数で正確に表せられていて、一つ上の桁の数字が偶数になるように処理されています。

偶数／奇数というのは整数の中での概念で、一般に『偶数への丸め』も少数を整数にするイメージですが、Pythonのroundに関する文脈では「処理する一つ上の桁の数字」が偶奇を考慮する対象になると考えてよさそうです。

decimalを使う

という訳で、どうしても四捨五入がしたければ、decimalモジュールを使いましょう。

decimal --- 十進固定及び浮動小数点数の算術演算 — Python 3.8.10 ドキュメント

quantizeメソッドに丸めモードを引数として渡せばしっかり四捨五入してくれます。

from decimal import Decimal, ROUND_HALF_UP for i in range(10): x = 0.05 + i / 10 dec = Decimal(f'{x:.2f}') print(dec, dec.quantize(Decimal(".0"), rounding=ROUND_HALF_UP))

decimalを使った提出

from decimal import Decimal, ROUND_HALF_UP def B(X, K): X /= 10 ** (K + 1) X = Decimal(str(X)) for i in range(K): X = X.quantize(Decimal(10) ** -(K - i), rounding=ROUND_HALF_UP) return int(X * 10 ** (K + 1)) test_all(B)

結果：#36212401

自由欄

C - (K+1)-th Largest Number

やってみよう！

C関数を完成させて「Run」ボタンをクリックしよう！

test_dataC = [ { "in":[6, [2, 7, 1, 8, 2, 8]], "out": """2 1 2 1 0 0 """ },{ "in":[1, [1]], "out": """1 """ },{ "in":[10, [979861204, 57882493, 979861204, 447672230, 644706927, 710511029, 763027379, 710511029, 447672230, 136397527]], "out": """2 1 2 1 2 1 1 0 0 0 """ }, ] def C(N, A): pass test_all(C)

自由欄

try(コンテスト中)

コンテスト中に「意図がよく分からん問題だなぁ」と思ったのですが、振り返ってもよく分かりませんでした…
競プロの読解力ってどうやって鍛えたらいいんだ

from io import StringIO def C(N, A): out = StringIO() A2 = {a:i for i, a in enumerate(sorted(set(A)), 1)} K = {i: 0 for i in range(N)} for a in A: K[len(A2) - A2[a]] += 1 for v in K.values(): print(v, file=out) return out.getvalue() test_all(C)

結果：#35680010

try(振り返り)

「set使った気がするなぁ」と思い出しながらやろうとしたのですが、結局思い出せず無難なところに落ち着きました。
解説の考え方も大体同じ？(C++のコードが読めん…)

from io import StringIO def C(N, A): out = StringIO() A3 = {} for a in A: if a in A3: A3[a] += 1 else: A3[a] = 1 for a in sorted(A3)[::-1]: print(A3[a], file=out) print("0\n" * (N - len(A3)), end="", file=out) return out.getvalue() test_all(C)

結果：#36215943

自由欄

D - LRUD Instructions

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in":[5, 5, 4, 4, 3, [[5, 3], [2, 2], [1, 4]], 4, [['L', '2'], ['U', '3'], ['L', '2'], ['R', '4']]], "out": """4 2 3 2 3 1 3 5 """ },{ "in":[6, 6, 6, 3, 7, [[3, 1], [4, 3], [2, 6], [3, 4], [5, 5], [1, 1], [3, 2]], 10, [['D', '3'], ['U', '3'], ['L', '2'], ['D', '2'], ['U', '3'], ['D', '3'], ['U', '3'], ['R', '3'], ['L', '3'], ['D', '1']]], "out": """6 3 5 3 5 1 6 1 4 1 6 1 4 1 4 2 4 1 5 1 """ }, ] def D(H, W, rs, cs, N, rc, Q, dl): return test_all(D)

自由欄

try(コンテスト中)

愚直に実装してみます。

def D(H, W, rs, cs, N, rc, Q, dl): out = StringIO() def check(r, c): return 1 <= 1 r <="H" and [r, c] not in rc now="rs," cs for d, l dl: _ range(int(l)): r, c="now" if d="=" "l": nxt="[r," - 1] elif "r": + "u": 1, "d": check(*nxt): continue break print(*now, file="out)" return out.getvalue()< py-cell> test_all(D)

結果：#35694033

当然のごとくTLE

try(振り返り)

愚直実装では単純に$O(QL)$の計算量となります。
ここで$L$の部分を削減したいとなると、何かしら前処理が必要だよなぁと考え実装したのが以下。

前処理として、全てのマスで上下左右のどこまで行けるかを計算してます。
これで$O(HW + Q)$に改善されました！

改善…されたのか？

from operator import add, sub def D(H, W, rs, cs, N, rc, Q, dl): out = StringIO() grid = [[[] for _ in range(W)] for _ in range(H)] for r, c in rc: grid[r-1][c-1] = None def preproc(grid, rev=False): r = len(grid) c = len(grid[0]) range_c = range(c - 1, -1, -1) if rev else range(c) op = sub if rev else add for i in range(r): ava = 0 if not rev else c - 1 for j in range_c: if grid[i][j] is None: ava = op(j, 1) else: grid[i][j].append(ava) preproc(grid) preproc(grid, rev=True) *grid, = zip(*grid) preproc(grid) preproc(grid, rev=True) *grid, = zip(*grid) # print(*grid, sep="\n") nr, nc = (rs - 1, cs - 1) for d, l in dl: l = int(l) if d == "L": if nc - grid[nr][nc][0] <= l: nc="grid[nr][nc][0]" else: -="l" elif d="=" "r": if grid[nr][nc][1] <="l:" +="l" "u": nr grid[nr][nc][2] "d": grid[nr][nc][3] print(nr 1, file="out)" return out.getvalue()< py-cell> test_all(D)

結果：#36218924

ACが8個に増えるも、なおTLE…
制約を確認すれば当然で、オーダー的には全然改善してないです。

解説を見る

どうしようもないので解説を見ます。

︙

あ、二分探索ですか…。

他、要点は以下

  • 壁を1個以上含む行$i$や列$j$についてのみ、配列$A_i$や配列$B_j$を陽に構築
  • 番兵を使う
from bisect import bisect def D(H, W, rs, cs, N, rc, Q, dl): out = StringIO() def search(a, x, rev=False): idx = bisect(a, x) return a[idx] - 1 if not rev else a[idx - 1] + 1 vertical = {} horizontal = {} for r, c in rc: if c in vertical: vertical[c].append(r) else: vertical[c] = [r] if r in horizontal: horizontal[r].append(c) else: horizontal[r] = [c] vertical = {k: sorted([0] + v + [H + 1]) for k, v in vertical.items()} horizontal = {k: sorted([0] + h + [W + 1]) for k, h in horizontal.items()} rn, cn = rs, cs for d, l in dl: l = int(l) if d == "L": if rn not in horizontal: c = 1 else: c = search(horizontal[rn], cn, rev=True) dist = abs(cn - c) cn = c if dist <= l else cn - elif d="=" "r": if rn not in horizontal: c="W" else: cn) dist="abs(cn" c) <="l" + "u": vertical: r="1" rn, rev="True)" r) "d": rn) print(rn, cn, file="out)" # return out.getvalue()< py-cell> test_all(D)

結果：#36276903

ようやくAC😣

自由欄

まとめ

二分探索に気づけなかったときの無力感が半端ない。

自由欄