今日解いた競プロの問題。

ARC151-B: 数列Aが数列Bより辞書順で小さいということは、あるiがあって、$1\leq k < i$において$A_k=B_k$であり$A_i<B_i$であるということである。つまりこのiがどこかによってN通りの場合がある。この問題では$A_1<A_{P_1}$の場合、$A_2<A_{P_2}$の場合…と考えていけばよい。

$A_1<A_{P_1}$のとき、$P_1=1$ならば実現不可能。そうでなければ$A_1$と$A_{P_1}$の選び方は$_MC_2$通りある。残りの$N-2$要素は任意にとれるので$M^{N-2}$通りある。

$A_1=A_{P_1}$かつ$A_2<A_{P_2}$のとき、$P_2=2$ならば実現不可能。また$P_1=2, P_2=1$のような場合、$A_2=A_{P_2}$ということになってしまうので実現不可能になる。そうでなければやはり$A_2$と$A_{P_2}$の選び方は$_MC_2$通りあり、残りの縛られていない要素は任意にとれる。$A_1=A_{P_1}$があるのだけ自由度は余分に減ることに注意。

要するにN通りの各場合について、実現可能かどうか＋縛られていない要素はいくつあるか(自由度がいくつあるか)を計算できればよい。同値関係を管理したいとなったらこれはUnionFindである。

$A_k=A_{P_k}\ (k<i)$、$A_i<A_{P_i}$のパターン数を調べるには、まずi-1個のイコールについてUnionFindで繋げたうえで、$i$と$P_i$がイコールで結ばれているか判断して実現可能性を調べる。次に連結成分の数を数え、$_MC_2\times M^{連結成分数-2}$を計算すればよい。

この計算は順に$i$を増やしていけば前回の結果が使える。二分累乗でべき乗を計算するときのlogがボトルネックになり、全体$O(N\log N)$。実際には連結成分数はどんどん減っていくはずなので、厳密に見積もればさらに速いかもしれない。

---

今週の胎界主を読んだ。サタナキア、お前それ明らかに破滅の流れでは？？？？せめてこう、「大惨事が起こらない方に賭ける」とかなら分かるけどさあ。日奈子をもうこれ以上クソみたいな目に遭わせないでくれ。

サタナキアの策は予想通り何かしらの神獣の召喚だったようだ。アバドンていうのはどこの何のどういう神獣だろうか。ろくなことが起こりそうにないが。

Wikipedia情報だとヨハネの黙示録に登場する奈落の王であり、「破壊者」といった意味の名前らしい。壊す力の司神の神獣なのだろうか。全く関係ないが「腐海に眠る王女のアバドーン」というゲームがbiim兄貴にプレイされていたな。

---

PICO4が早速届いた。とりあえず開封して中身と装着感などを確かめた。

Valve Indexに比べると、後頭部に当たる部分がちょっと硬い。ゴムに皮をかぶせてある感じなのでクッション性はあまり高くない模様だ。そのほかはあまり気になる点はない。軽いといえば軽いかもしれない。

コントローラは親指押しボタン4つ+スティック1つ+人差し指と中指それぞれにボタンが1つづつといった形だ。Indexコンとちがって、人差し指で押せるキーは「カチッ」とは言わない。輪っかになっている部分の存在意義は全くわからない。

今日はもう遅いので明日本格的にいじる。

---

筋トレをした。今日はスクワット。また間が空いてしまった。