💬

AtCoder Beginner Contest ABC405 解法メモ

2025/05/11に公開

Nim

AtCoder

tech

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

ABC405

ABC405A - Is it rated?

解法

R in 1600..2999 and X==1
もしくは、
R in 1200..2399 and X==2
であればYes、そうでなければNo
ACコード

ABC405B - Not All

解法

$Ai$ の制約を考えれば、1..Mまでの整数がすべて含まれているかどうかは、
A.toHashSet.lenをみていけばよい
$M$ である限りA.popしていき、その回数が答えとなる
ACコード

メモ

お決まりで、「以下の条件が満たされるように」に誤読
$Ai$ の制約から、Setにしてlenをとればよいことに気付かない
Seqにもpopがあるが、Dequeでもよい

ABC405C - Sum of Product

解法

求める値に対して、
$(A_1+A_2+...+A_N)\times (A_1+A_2+...+A_N)$ を展開したものを考えれば、
そこから $A_1^2+A_2^2+...+A_N^2$ を引いて、半分にすればよいとわかる
したがって、
(A.sum^2-A.mapIt(it^2).sum) div 2
が答え
ACコード

メモ

求める値の数式を、 $A$ の各項でまとめれば、
$A_1*A_2$
$+(A_1+A_2)\times A_3$
...
$+(A_1+..+A_{N-1})\times A_N$
となるので、累積和として
c=A.cumsummedとすれば
(1..N-1).toSeq.mapIt(c[it-1]*A[it]).sum
と書ける

ABC405D - Escape Route

解法

各非常口を始点としてBFSすればよい
入力後、Eの座標をすべてとっていき、
最初にそれをすべて入れたDequeを用意、
現在位置から上下左右したときに、行先の $S$ が'.'だったら、上下左右反対の記号に置き換えていけばよい
すべて書き替割った後の $S$ が答え
ACコード

メモ

入力例をよく見ず、Eが複数あることを見落とした
Eが複数あったので、BFSを一からやりなおすように組んでしまい、TLE
答えに必要なものから考えると、Eからの距離を保持する必要すらない

初めに、リンゴ $A$ 個をまとめて左側に、バナナ $C$ 個をまとめて右側に置く
一番左端のブドウの位置iに注目すると、
とり得る範囲は左から $A+1..A+C+1$ 個目であり、
それより左側にあるリンゴとバナナの個数 $i-1$ とオレンジ $B$ 個の並べ方の場合の数と、
その右側のバナナの個数 $A+C-(i-1)$ と残りのブドウ $D-1$ 個の並べ方の場合の数をかけたものの総和をとればよい
これは重複組合せで、modint998244353として階乗を $f$ とすれば、
for i in A+1..A+C+1:
　a+=f[(i-1)+B]/f[i-1]/f[B]*f[A+C-(i-1)+(D-1)]/f[A+C-(i-1)]/f[D-1]
が答え
事前にmodint998244353で $A+B+C+D$ までの階乗 $f$ を求めておけばよい
ACコード

メモ

情けないことに、重複組合せが計算できない

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