ABC273の振り返り(A, B, C, D)
振り返りです。
A - A Recursive Function
やってみよう!
A
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
A問題っぽくないですが、逆に言えば「再帰関数が分かる、実装できる」ことまでAのレベルで求められるってことですよね…
私はまだまだ新参者ですが、今後も同じレーティングに求められるレベル感は上がっていくんだろうなぁ~😇
結果:#36091312
自由欄
B - Broken Rounding
やってみよう!
B
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
なかなかの妙問です。
まずはコンテスト中にACした提出がこちら。
結果:#35673269
なぜround
ではダメなのか?
ここではPythonの組み込み関数についてのみ扱います。
偶数への丸め
ドキュメントに明記されている通り、roundは一般的な四捨五入ではなくいわゆる偶数への丸めで処理します。
これは処理する桁が少数でなくとも同様なので、
# 偶数への丸め。見事に偶数。 for i in range(10): x = i * 10 + 5 print(x, round(x, -1))例えば1つ目のテストデータで1桁目を四捨五入した後の2050
の結果が2000
になってしまいます。
少数の精度問題
「ではいっそのこと少数にしてしまえば、偶数への丸めは回避できるのでは?」という発想で以下のようにコーディングしてみます。
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桁の精度まで表示したものです。
例えば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」ボタンをクリックしよう!
自由欄
try(コンテスト中)
コンテスト中に「意図がよく分からん問題だなぁ」と思ったのですが、振り返ってもよく分かりませんでした…
競プロの読解力ってどうやって鍛えたらいいんだ
結果:#35680010
try(振り返り)
「set
使った気がするなぁ」と思い出しながらやろうとしたのですが、結局思い出せず無難なところに落ち着きました。
解説の考え方も大体同じ?(C++のコードが読めん…)
結果:#36215943
自由欄
D - LRUD Instructions
やってみよう!
D
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
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$を陽に構築
- 番兵を使う
結果:#36276903
ようやくAC😣
自由欄
まとめ
二分探索に気づけなかったときの無力感が半端ない。