ABC350に出た。

A: やるだけ

B: やるだけ

C: 先頭から普通に選択ソートしていけば最後は必ず揃うのでN-1回の制限はクリアするが、計算時間が$O(N^2)$になってしまう。permutationであることを利用し逆置換を持っておくと各O(1)で欲しい数字の場所が取れるので$O(N)$で解ける。

D: 大きさXの連結成分には友達関係が最大$_XC_2=X(X-1)/2$まで作れるので、UFで連結成分を計算し最大の関係数を出す。既にある友達関係の数Mを引けば答えが出る。

E: ちょっと時間をかけすぎた。$10^{18}<2^{60}$なので、どの数で割っても最大60回までしか割ることはない。サイコロの出目に含まれる素因数は2,3,5しかないので$60^3$通り程度の数しか考えなくてよいことが分かる。6で割るのと2と3で1回ずつ割るのを区別しなくていいのか迷ったが、ググったらどうやら$\lfloor \lfloor a/b \rfloor /c \rfloor=\lfloor a/(bc) \rfloor$らしい。

https://math.stackexchange.com/questions/4718508/can-floorfloora-b-c-ever-be-different-to-floora-bc

期待値DPにちょっと手間取った。冷静になって数式を立てて整理したら普通に解けた。親の顔より見た問題になりつつあるからそろそろ慣れないといけない。今回の場合$DP[i] = (数字iを0にするために必要なお金の期待値)$とすると、

Aで割った場合

$DP[i] = DP[\lfloor i/A \rfloor]+X$

サイコロの出目で割った場合

$DP[i]=\{\sum_{k=1}^6(DP[\lfloor i/k \rfloor]+Y)\}/6$

整理すると

$DP[i]=\frac{6}{5}Y+\{\sum_{k=2}^6 DP[\lfloor i/k \rfloor]\}/5$

Yに6/5がかかるのがちょっと気持ち悪い。2者を比較して小さい方を選んでいくように実装すると貰うDPが完成する。

F: まず前計算として、各カッコについて対応する相手のカッコをもとめてやる。こういうカッコ列の処理はスタックを使うと良い。なおスタックとキューがごっちゃになって取り違えてデバッグに手間取った。愚か。

先頭から順に見ていき、カッコが開くならそのカッコの閉じカッコへ移動して進行方向を転換する。カッコが閉じるならそのカッコの開きカッコへ戻り進行方向を転換する。これによって$O(N)$で最終文字列の通りの順に文字列全体を走査することができる。開いたカッコの数の偶奇で大文字小文字反転をするかしないかを変えればよい。あまりやらないような実装だが結構簡単な実装で解けるので割と好き。

G: 解けず。いろいろやりようがあるらしい。