先日開催された、AtCoder Beginner Contest 335の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。
公式解説
A～C
FAはそれぞれhiroyuk1さん、ayu777proさん、tatyamさんでした。
おめでとうございます。
D Loong and Takahashi
解法
うずまき状に書き込めばいいです。
これはDFS・BFSで突き当たるたびに右折すれば達成できます。
うずまき以外の方法もありますが、実装が大変なのでやらなくてよいです。
別解 ジグザグ構築
龍のパーツを降順に並べます。
N = 3,7,11, ･･･ のときはTの真上から始め、それ以外はTの真左から始めます。
左に直進→上下にジグザグ→左右にジグザグ で構築できます。
下図を見れば何がしたいかはわかると思います。(終)
N = 7 : Tの真上から左へ
7 6 5 4 3 2 1
8 9 10 11 12 13 14
45 46 47 48 17 16 15
44 37 36 T 18 19 20
43 38 35 24 23 22 21
42 39 34 25 26 27 28
41 40 33 32 31 30 29
N = 9 : Tの真左から左へ
9 8 7 6 5 4 3 2 1
10 11 12 13 14 15 16 17 18
27 26 25 24 23 22 21 20 19
28 29 30 31 32 33 34 35 36
77 78 79 80 T 40 39 38 37
76 69 68 61 60 41 42 43 44
75 70 67 62 59 48 47 46 45
74 71 66 63 58 49 50 51 52
73 72 65 64 57 56 55 54 53
E Non-Decreasing Colorful Path
解法
頂点の数字が同じ場合の移動処理がやっかいです。
同じ数字の頂点はできるだけまとめるか、まとめなくても問題ない方法で解きましょう。
- 頂点の圧縮を行う場合
$A_v$の値が等しく、かつ隣接した頂点どうしを圧縮し、ひとつの頂点とみなします。
この処理はUnionFindを使うと便利ですが、せっかくなので強連結成分分解(SCC)で実装しました。
SCCの実装は高校数学の美しい物語の図が参考になります。
(DFS1回で済むTarjanのアルゴリズムも存在しますが、実装が難しいです)
頂点を圧縮した後のグラフはDAG(有向非巡回グラフ)になっており、適切に扱うと逆戻りすることなくグラフをたどることができます。
なのであとは動的計画法で解けます。 - ダイクストラ法を行う場合
$A_v$の値が小さい順に見てゆけば、自然と最長パスになります。
問題は$A_v$の値が等しいときですが、このときは既に採用した数字の種類数が大きい順に見ると更新回数を減らせます。
二分ヒープでのダイクストラ法なので、計算量は$O((N+M)logM)$です。
提出例: 頂点圧縮(SCC), 頂点圧縮(UF), ダイクストラ法
F Hop Sugoroku
解法
想定解は平方分割ですが、累積和を用いた$O(N√N)$の解法を紹介します。
DP[i]: コマがマスiにある移動方法の場合の数
としたDPを考えます。
ここで、同じ幅で移動する遷移を累積和でひとまとめにしましょう。
sub[i][step]: マスiに幅stepの倍数で移動してくる場合の数
と定義すると、同じ遷移をまとめることができます。計算量は$O(N√N)$です。
(最悪ケースは 'A = [1, 2, 2, 3, 3, 3, ･･･]` です)
A = [ 2, x, 2, x, 2, x, 2, ･･･]
DP = [ 1, x, 2, x, 3, x, 6, ･･･]
(1) → 1 → 1 → 1 ･･･ マス1からの遷移
(2) → 2 → 2 ･･･ マス3からの遷移
(3) → 3 ･･･ マス5からの遷移
(6) ･･･ マス7からの遷移
同じ周期の遷移を毎回計算するとO(N^2)になるので、遷移を累積和にする
(1) → (2) → (3) → (6) →･･･
1 1+2 3+3 6+6
しかし、1マスごとに遷移を分割する実装だと定数倍が悪くTLEします。
コンテスト中はこれが原因でTLEしていました。Pythonの運命です。
以下のような、非自明な定数倍高速化を行えばACできます。
- 連想配列の呼び出しコストが重いので、dictではなくlistにします。
(コマの移動幅step, 累積の場合の数)のタプルをマスごとに配りましょう。
また除算は重いので、可能な限り% 998244353の回数を減らしましょう。 - 遷移を1マスごとに刻まず、できる限りまとめてくばるようにすると早いです。
具体的には、A[i]が同じ値のマスに到達するまで配り続ければよいです。
実装にあたり、Kiri8128さんのユーザ解説が参考になります。
提出例: 平方分割(658ms), もらうDP・list(2245ms), くばるDP(286ms)
G Discrete Logarithm Problems
解法
わかりません。
公式解説を頑張って追いましょう。
公式解説 自分用メモ
理解不十分な箇所が多いのでご容赦ください。
$A_i^{B_i} ≡ 1 (mod P)$ を満たす$B_i$の最小値を位数と呼びます。
フェルマーの小定理から、$A_i^{P-1} ≡ 1 (mod P)$なので、$B_i$はP-1の約数です。
なので$B_i$はP-1の素因数ためし割りの要領で計算可能です。計算量は$O((logP)^2)$です。
さて、mod Pの原始根のひとつをRとします。原始根の存在定理から、素数Pに対して原始根はかならず存在するようです。
$A_i ≡ R^k (mod P)$を満たすR,kの値を求めたくなりますが、原始根Rをひとつ求めるのにはexpect $O((logP)^2 × loglogP)$かかり、kを求めるのはBaby-Step Giant-Stepで$O(√P)$かかるようです。
37zigenさんの原始根アルゴリズム解説のページが詳細でした。
kを求めるのは非現実的なので、位数を用いた計算を行います。
このあたりの証明はまだ追えていませんが、どうやら$B_i | B_j$であればよいらしいです。
理解したら追記します。(終)
おわりに
おわりです。
いろいろなかいほうをおもいつきたいなとおもいました。