ABC280の振り返り(A, B, C, D, E)

振り返りです。

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 - Pawn on a Grid

問題略

itertoolsのchain.from_iterableを使えば2次元配列を1次元にすることができます。

from itertools import chain *chain.from_iterable([[1, 2, 3], [4, 5, 6]]),

結果：#36951941

自由欄

B - Inverse Prefix Sum

問題略

これはitertools.accumulateの逆変換って感じですかね。
考え方は解説通りです。

結果：#36961483

自由欄

C - Extra Character

問題略

末尾に追加のパターンを見落として一度WA…

結果：#36965848

自由欄

D - Factorial and Multiple

やってみよう！

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

test_dataD = [ { "in":[30], "out": 5 },{ "in":[123456789011], "out": 123456789011 },{ "in":[280], "out": 7 }, ] def D(K): pass test_all(D)

自由欄

解説を見る

コンテスト中は①どこまで探索するかと、②階乗の数で割り切れない場合の処理、が分からず仕舞いでした…
早速解説を見ます。

①については、

よって答えは高々$2×10^6$

とのことですがその導出がいまいち理解できない…

②については最大公約数で割ればいいんですね、はい…

以下、写経

import math def D(K): for i in range(1, 2000000 + 1): K //= math.gcd(K, i) if K == 1: # print(i) return i # print(K) return K test_all(D)

結果：#37091578

自由欄

E - Critical Hit

やってみよう！

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

test_dataE = [ { "in":[3, 10], "out": 229596204 },{ "in":[5, 100], "out": 3 },{ "in":[280, 59], "out": 567484387 }, ] def E(N, P): pass test_all(E)

自由欄

解説を見る

コンテスト中はたどり着けなかったE問題ですが振り返ってやってみます。
とは言え、①期待値の求め方、②期待値($\frac{P}{Q}$)のmod($R \times Q \equiv P$となる$R$)の求め方、がさっぱり分からないので解説を見ます。

期待値の求め方は理解できた(できるとは言ってない)のですが、この類の問題では定番のACLのmodintを使っていて、上記②が依然として腑落ちしない感じです。
とりあえず以下の記事を~~コピペ~~参考にして解説をpythonで書き直してみました。

【Modint編】AtCoder Library 解読〜Pythonでの実装まで〜 - Qiita

class Modint: mod = 0 has_been_set = False def __init__(self, v=0, m=None): if m != None and not self.has_been_set: assert m >= 1 assert not Modint.has_been_set Modint.mod = m Modint.has_been_set = True self._v = v if 0 <= v < modint.mod else % def __add__(self, other): if isinstance(other, modint): res="self._v" + other._v> Modint.mod: res -= Modint.mod else: res = self._v + other return Modint(res) def __sub__(self, other): if isinstance(other, Modint): res = self._v - other._v if res < 0: res += Modint.mod else: res = self._v - other return Modint(res) def __mul__(self, other): if isinstance(other, Modint): return Modint(self._v * other._v) else: return Modint(self._v * other) def __floordiv__(self, other): if isinstance(other, Modint): other = other._v inv = pow(other, -1, Modint.mod) return Modint(self._v * inv) def __pow__(self, other): assert isinstance(other, int) and other >= 0 return Modint(pow(self._v, other, Modint.mod)) def __radd__(self, other): return Modint(self._v + other) def __rsub__(self, other): return Modint(other - self._v) def __rmul__(self, other): return Modint(self._v * other) def __rfloordiv__(self, other): inv = pow(self._v, -1, Modint.mod) return Modint(other * inv) def __iadd__(self, other): if isinstance(other, Modint): self._v += other._v if self._v >= Modint.mod: self._v -= Modint.mod else: self._v += other if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod return self def __isub__(self, other): if isinstance(other, Modint): self._v -= other._v if self._v < 0: self._v += Modint.mod else: self._v -= other if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod return self def __imul__(self, other): if isinstance(other, Modint): self._v *= other._v else: self._v *= other if self._v < 0 or self._v >= Modint.mod: self._v %= Modint.mod return self def __ifloordiv__(self, other): if isinstance(other, Modint): other = other._v inv = pow(other, -1, Modint.mod) self._v *= inv if self._v > Modint.mod: self._v %= Modint.mod return self def __ipow__(self, other): assert isinstance(other, int) and other >= 0 self._v = pow(self._v, other, Modint.mod) return self def __eq__(self, other): if isinstance(other, Modint): return self._v == other._v else: if other < 0 or other >= Modint.mod: other %= Modint.mod return self._v == other def __ne__(self, other): if isinstance(other, Modint): return self._v != other._v else: if other < 0 or other >= Modint.mod: other %= Modint.mod return self._v != other def __str__(self): return str(self._v) def __repr__(self): return str(self._v) def __int__(self): return self._v def E(N, P): Modint(m=998244353) x = 1 ans = 1 for i in range(1, N): x = Modint(1) - x * Modint(P) // Modint(100) ans += x return ans test_all(E)

結果：#37060212

自由欄

modの除法を理解する

上のmodintのPythonでの実装の記事とコードを眺めて、なんとなく設問の注記の意味が分かってきました。
要は普通に期待値($\frac{P}{Q}$)をmodの除法をで求めよってことなんですね。

そしてPython(3.8以上？)なら組み込みのpow関数でmodの逆元を求められる(！)ので、わざわざmodintを再現しなくてもそこだけ実装すればよくね？という訳で以下。

def E(N, P): MOD = 998244353 P = P * pow(100, -1, MOD) % MOD x = 1 ans = 1 for i in range(1, N): x = (1 - x * P) % MOD ans += x ans %= MOD return ans test_all(E)

結果：#37134179

実行時間が1/10になった！

まとめ

食わず嫌いしてたmodの世界に少しだけ踏み込めた気がします😁