AtCoder 168 E問題 ∙ (Bullet) 絵で見て解説
はじめに
今回のコンテスト、ABCと余裕で解けた。 これはもしかするとDEも解けちゃうかも！？ と淡い期待を抱いたものの、見事に撃沈。
ABCしか解けませんでした。 来週も頑張ろう。
前提
- 問題を理解している
- 内積を理解している
- 解説動画を見たがいまいちわからなかった
そんな人向けの解説です。
ACコードと可視化
from collections import defaultdict from math import gcd MOD = 1000000007 N = int(input()) zeros = 0 bads = defaultdict(lambda: [0, 0]) for _ in range(N): x, y = map(int, input().split()) # 1. 生データ if x == 0 and y == 0: zeros += 1 continue # 2. 最大公約数で正規化 g = gcd(x, y) x, y = x // g, y // g # 3. 180度回転 (第一・二象限に変換) if y < 0 or (y == 0 and x < 0): x, y = -x, -y # 4. 90度回転(第一象限に変換+回転したか管理) if x > 0: bads[(x, y)][0] += 1 else: bads[(y, -x)][1] += 1 ans = 1 for k, l in bads.values(): ans *= (pow(2, k, MOD) - 1) + (pow(2, l, MOD) - 1) + 1 ans %= MOD print((ans + zeros - 1) % MOD)
https://atcoder.jp/contests/abc168/submissions/13361553を参考にしました ここではこのコードのコメントアウト部分を順々に可視化していくことで、理解を深めます。
また、下記で扱う入力例は問題の入力例2を扱います。
- 注意事項
- 以下では第n象限($n \in${ 1, 2, 3, 4})と表現している箇所がありますが、厳密には、軸上の点はどの象限にも属さないため正しくありません。
- ここでは第n象限を曲座標系においてベクトルのなす角$\theta$が$90 \times (n-1) \leq \theta < 90 \times n$として話を進めます
1. 生データ
とりあえず、x軸: イワシの美味しさ、y軸: イワシの香り高さを、原点からのベクトルでプロットします。
このグラフ上でベクトル同士が直行する組み合わせはクーラーボックスに入れることができません。 つまり、(3, 7), (1, 6), (2, 6)の組み合わせです。
あと、5番のイワシがとても美味しくないこともわかります。
2. 最大公約数で正規化
内積ゼロは、あるベクトルとの相対的な角度のみが重要です。 つまり、ベクトルを適当に定数倍しても、なす角は変わらないため直行するベクトル同士の内積はゼロのままになります。
後ほど、第一象限における互いに素な座標値を用いて悪い組み合わせを管理するので、ここでは(x, y)をそれぞれ最大公約数で割ります。
3. 第一・第二象限に変換
一方で、あるベクトル同士のなす角は180度回転しても、内積の絶対値は変化しません。
第一象限にベクトルを落とし込む際に、ベクトル同士のなす角が90度なのか-90度なのか判定するのは面倒なので、第三・四象限にいるイワシ達を(評価ベクトル上で)180度回転させます。
これによって、ベクトルの定義域は第一・第二象限に
4. 第一象限に変換+回転したか管理
さて、ここまでくればもう一息です。
第二象限にあるイワシ達の評価値を-90度回転させ第一象限に押し込めます。
ここではイワシの評価ベクトルをキーとした辞書を使い、回転されていないイワシ、回転されたイワシの数をベクトルごとに保持します
あとは各ベクトルごとに可能な組み合わせを数え上げ、乗じて終了です。
まとめ
美味しさも香り高さもマイナスのイワシが可哀想
AtCoder 167 E問題 Colorful blocks 解説
はじめに
初めてAtCoderのコンテストに参加してみた。
大学入学当初、推薦で適当に進学したので高校数学が全くわからず、このままでは留年すると思って必死に勉強した。 当時はわからないことが多すぎてひたすら参考書とGoogleにお世話になっていたけど、 競技プログラミングの世界でもGoogle先生には今後もお世話になりそう。
そんな感想を抱いたのは余談で、メモがわりに問題解説していきます。
E問題
解説動画見て方針は理解したがmodulo演算がよくわからず、 AC提出者の短いコードを見て余計意味がわからなくなった。
今日は以下のコードの解説をしていきます。 使用言語はPython3です。
N,M,K=map(int,input().split()) out=0 P=998244353 c=1 for i in range(k+1): out+=c*M*pow(M-1,N-i-1,P) out%=P c*=(N-i-1)*pow(i+1,P-2,P) c%=P print(out)
※https://atcoder.jp/contests/abc167/submissions/13112411を一部加工
ちなみに初見の感想は、マジでなんもわからん
前提
解説動画などより以下の計算の結果を素数$998244353$で割った余りが解となることがわかっている。
$$
\sum_{k =0}^K M(M -1)^{N -k -1} {N -1 \choose k}
\tag{1}
$$
modulo演算による式の分解
各$k$についての分解
(1)式はmodulo演算の特性$(a \times b) \bmod p = \left((a \bmod p) \times (b \bmod p)\right) \bmod p$より以下のように分解できます。 $$ \sum_{k=0}^K \left(M \left((M -1)^{N -k -1} \bmod P\right) \left({N -1 \choose k} \bmod P\right)\right) \bmod P \tag{2} $$ ここで$P=998244353$です。 問題文より$M < P$なので、$M \equiv M \bmod P$が成り立ちます。 つまり、解は各$k$の余りを足すことで求まることがわかります。
これをコードに落とし込むと
N, M, K = map(int, input().split()) out = 0 P = 998244353 nCi_mod_list = [1, ..., n_1CK] for k in range(K+1): out += M * pow(M-1, N-k-1, P) * nCi_mod_list[k] out %= P print(out)
ここでnCi_mod_list は${N -1 \choose k} \bmod P$が$K$番目まで収まっているリストで、既に求まっているとしました。
Combinationの分解
ここでは(2)式のCombination項をさらに分解し、nCi_mod_list の中身を計算していきます。 $k$までの組み合わの剰余が求まっている時、$k+1$の組み合わせの剰余は以下で求まります。 $$ \left(\frac{(N -1)!}{k !(N -1 -k) !}\right) \bmod P = \left({N -1 \choose N -k -2} \bmod P \left(\frac{N - k -1}{K +1}\right) \bmod P\right) \bmod P $$ つまり、毎回一からCombinationの計算をする必要がないわけです。
ここで、フェルマーの小定理と割り算の関係より \begin{align} &\frac{(N -1)!}{k !(N -k -1) !} \bmod P\\ &= \left(\left({N -1 \choose N -k -2}\bmod P \right) \left(\left(N -k -1\right) \bmod P\right) \left(\left(k+1\right)^{P-2} \bmod P\right)\right) \bmod P \end{align} となります。
つまり、$k+1$の剰余を求めるためには$N -k -1$と$(k +1)^{P -2}$をそれぞれ$P$で割った剰余のみ求まればいいことがわかりました。 またまたこれをコードに落とし込むとこうなります。
N, M, K = map(int, input().split()) out = 0 P = 998244353 nCi_mod_list = [1] for k in range(K): c = nCi_mod_list[k] * (N-k-1) * pow(k+1, P-2, P) nCi_mod_list.append(c%P)
※nCi_mod_listの先頭の要素は${N-1 \choose 0}$に対応します。
コードをまとめる
まとめたコードが冒頭です。 for分と不要なmodulo演算をまとめているため、コードがあれだけ短くなっていたということでした。
この問題で個人的に学んだこと
- modulo演算の基礎
- フェルマーの小定理について
- 逆元とかそこらへんの話
