AtCoder Beginner Contest ABC425 解法メモ

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC425

ABC425A - Sigma Cubes

解法

1..Nの$i$で(-1)^i*i^3)を足し合わせればよい
ACコード

ABC425B - Find Permutation 2

解法

$i$を1..Nと回しながら、$i$が$A$に入っているかみて、
入っていなかったら$A$から$-1$を探し、
その場所の$A$を$i$に変える
もし$-1$がなかったらNo
最後、Yesとともに$A$を出力すればよい
ACコード

メモ

Yes、Noだけと思い込み、toCountTableなどを始めてしまった

ABC425C - Rotate and Sum Query

解法

クエリ$1$に対応するには、$c$の累計をとっておき、mod Nして$l$、$r$に加えればよい
クエリ$2$は累積和をとっておけば、$r$の項から$l-1$の項を引くだけで答えを得られる
累積和を作る際には、クエリ$1$を考え、$A$を$2$回繰り返しておき、$l-1$を参照するので頭に$0$をつけておくとよい
ACコード

ABC425D - Ulam-Warburton Automaton

解法

初期値を含む操作ごとに新たに塗られた黒マスの周囲だけ、黒マスに$1$つしか隣接していないかどうかを確認していけばよく、
そうすれば、マスの数以上の調査が必要になることはない
新たに塗られたマスの位置をHashSetの$d$でもち、一つひとつ調べた結果、次に塗られるべき条件を満たす白マスの位置をHashSetの$nd$でもつ
すべての$d$を調べ終えた段階で、各$nd$の箇所の$S$を#で書き換え、$d$を$nd$で更新する
$nd$が空集合だったら終了し、#の数を数えればよい
ACコード

メモ

全マス舐めることを繰り返さずに更新箇所だけを処理すれば充分間に合うことには気づいたが、$S$をいじらずに#マスも集合に入れ、隣接判定もすべて集合で処理することにこだわってしまいTLE

ABC425E - Count Sequences 2

解法

各テストケースですべき計算は、いわゆる同じものを含む順列であり、

$$\frac{C.sum!}{C_1!\times C_2!\times...\times C_N!}$$

だが、この問題では、各$Ci$と$M$が互いに素であることが担保されないので、逆元が存在しない可能性がある（modintは使えない）
一方、C.sumが$5000$以下なので、これを前計算をしておけば、
全体から$C_1$箇所を選ぶ組み合わせと、（全体－$C_1$）から$C_2$箇所を選ぶ組み合わせと、…をかけ合わせることで求めることができる

$$_{C.sum}C_{C_1}\times _{C.sum-C_1}C_{C_2}\times...\times _{C_N}C_{C_N}$$

組み合わせCは二項係数であり、パスカルの三角形を模して遷移させていけば計算できる
前計算やテストケース内の過程に出てくる和や積の度にmod Mを取り続けていけばよい
ACコード

メモ

Cの計算にメモ化再帰を使うと、やはりTLE

---

反復学習にはmochiがおすすめ
全問入ったdeckはこちら