| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
50分6完2ペナで、85位でした。
最近ペナルティが多いような…緩んでいますね。
ここ数回、ABCコンテストの難易度が平均からちょい上で推移しているように思います（年末に易化が続いていた）。私としては、ありがたいですね。
問題C – Low Elements
全ての $(i,j)$ を調べると間に合いません。$P_i\leq \min\{P_1,\ldots, P_i\}$ として、累積maxとの比較にします。
Pythonだと、itertools を利用して
itertools.accumulate(P, min)のようにするか、numpyを利用して
np.minimum.accumulate(P)などとすると簡潔です。
問題D – Handstand 2
- $\text{ind} = 10a + b$ をインデックスとして配列に入れる
- $(a,b)$ をキーとして dict, defaultdict に入れる
などがあるでしょう。また、$(a,b)$ を羅列するsequenceを作って collections.Counter を利用するのも良いと思います。
より良い解法として、$A$ も $a\cdots b$ ごとにまとめてあげると全ての $N$ に対するループを回さなくてよくて、定数倍改善になります（前処理に $\Theta(N)$ 使うので全体として定数倍）。また、$a\cdots b$に属する整数の個数は $\Theta(1)$ で分かるので問題全体を $\Theta(1)$ で解けますが、本問では手間が増えるだけだと思います。
問題E – Flatten
- $A_i$ の最小公倍数 $L$ を求める
- $\sum_i\frac{L}{A_i}$ を計算する
というのが課題です。これが普通にやると桁あふれしてしまうというのが難しいところです（Pythonで多倍長整数を使えば桁あふれしませんが、桁数が大きすぎると演算1つ1つが重くなるので、そのまま計算すると当然パフォーマンスが著しく下がります）。
まず、後半の課題は簡単です。$L$ さえ求まっていれば、$A_i$ の $\pmod{p}$ での逆元 $A_i^{-1}$ を求めて、$L\sum_iA_i^{-1}$ を答とすればよいです。
最小公倍数の計算が肝心です。$\mathrm{lcm}(x,y) = xy/\mathrm{gcd}(x,y)$ というのが有名ですが、除算しながら計算しようとすると、約数の情報が失われて $\mathrm{gcd}$ が計算できません。
そこで、素因数分解を利用しました。
- 各素数 $p$ に対して各 $A_i$ が $p$ で割れる最大回数 $e_p$ を計算する。
- 最小公倍数は $\prod_p p^{e_p}$ である。
これならば 適当な mod での計算が可能です。各項の素因数分解は、$1000$ 以下の素数表を用意して試し割りをするのが簡潔だと思います。
多倍長整数によるLCM計算解法
想定解法よりは遅いですが、間に合うようです。
※ lcm が最大となるケース（素数べきを大きい方から並べた場合）にも間に合うことを確認しています。
$\mathrm{lcm}(a,b) = \frac{ab}{\mathrm{gcd(a,b)}}$ を繰り返し適用して最小公倍数を計算。それが求まったら、$\sum_{a\in A}\frac{\mathrm{lcm}}{a}$ を計算させます。
(1) 1890ms：■
lcm = reduce(lambda x,y: x*y//gcd(x,y), A)(2) 1507ms：■
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)除算を入れるタイミングを変更しています。 $\mathrm{lcm}(a,b) = a\cdot \frac{b}{\mathrm{gcd(a,b)}}$ のように計算することで、巨大な数の除算回数を削減しています（とはいえ、gcdの計算が残っています）。
(3) 1081ms：■
lcm = 1
answer = 0
for x in A:
n = x//gcd(lcm,x)
lcm *= n
answer *= n
answer += lcm//x答も同時に更新していきます。$\frac{\mathrm{lcm}}{x}$ の計算を最小公倍数が小さいうちに行ってしまうことで、巨大数の除算を減らしています。
(4) 579ms：■
lcm %= MOD
coef = sum(pow(x, MOD-2, MOD) for x in A)
answer = lcm * coef % MODそもそも、本問の難しさの大部分は最小公倍数の計算にあります。多倍長整数の計算により、最小公倍数のロジックさえ簡略化してしまえば、残りの部分は適切な mod で計算することができます。
問題F – Tree and Constraints
「少なくとも1つが黒」というパスに対する制約が、個々の条件だけで見てもそのままだと扱いにくいです。余事象が「全て白」でこちらの方が扱いやすいです。全体から各条件を満たさないものを上手く引いていく…「包除原理」と呼ばれるテクニックで解決します。
包除原理を使うときは、計算対象が何か分かりにくくなりやすいので、なるべく集合の記号を使って正確な定式化を心がけています。今回は、\[S_i = \{塗り方 \mid パス i 上の辺が全て白\}\] としました。
$|S_0\cup S_1\cup\cdots\cup S_{M-1}|$ が求めるものの余事象です。$\{0,1,\ldots,M-1\}$ の部分集合 $I$ に対して、$S_I = \bigcap_{i\in I} S_i$ とすると、\[|S_0\cup S_1\cup\cdots\cup S_{M-1}| = \sum_{I\neq \emptyset} (-1)^{|I|-1}|S_I|\] となります。
補集合をとることも含めて、答は $\sum_{I} (-1)^{|I|}|S_I|$ となります。制約 $M\leq 20$ より、これは $2^{20}$ 件以下の和です。あとは各 $S_I$ の求め方を検討すればよいです。
$S_I$ に該当する塗り方は、「全ての $i \in I$ に対してパス $P_i$ 上の辺が白」という条件を満たす塗り方です。この塗り方について、白と強制されている辺と、白黒自由に選べる辺が存在します。結局、$E_I = \{辺\mid どの P_i にも含まれない\}$ としたとき、$S_I = 2^{|E_I|}$ であることが分かります。
最後に $E_I$ の求め方を考えればよいです。これはおおよそ、$i\in I$ に対するパス $P_i$ の和集合の計算と同値です。パス上の辺集合を 64 bit 整数で持っておけば、これは bit演算で書けます。
結局 $i=0,1,\ldots$ の順に、$I\subset \{0,1,\ldots,i-1\}$ に対して $E_{I\cup\{i\}} \leftarrow E_I\cup P_i$ を繰り返す形で計算できて、この部分は $\Theta(2^M)$ で計算できます。
