AtCoder Beginner Contest ABC435 解法メモ

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

ABC435

ABC435A - Triangular Number

解法

(1..N).toSeq.sumを出力すればよい
ACコード

ABC435B - No-Divisible Range

解法

問題文通りシミュレートすればよい
$1≤l≤r≤N$をみたす整数の組をすべて試すべく、
for l in 0..<N:
　for r in l..<N:
として、
$l≤i≤r$について、$Ai$は$Al+⋯+Ar$の約数でない、
つまり、A[l..r].sumを$A[i]$で割った余りが$0$でない、ということなので、
初めに、f=trueとしてから
for i in l..r:
　if A[l..r].sum mod A[i]==0: f=false
として、f==trueのときに答えをカウントアップしていけばよい
ACコード

ABC435C - Domino

解法

問題文通りシミュレートしていけばよい
ドミノは間隔$1$で並んでいるので、隣のドミノだけでなく、その先のドミノも倒す可能性があるため、
倒せる一番右の位置$j$を記録、j.max=i+A[i]として更新しながら、
その位置より手前、$i<j$なら倒れる、として進めればよい
ACコード

メモ

題意の読み取りに時間がかかり、実装でもインデックスの処理に時間をかけてしまった

ABC435D - Reachability Query 2

解法

クエリ$2$で「頂点$v$から辺を辿って黒色の頂点に到達可能かどうか判定する」ためには、クエリ$1$で$v$を黒色にしたときに、有向辺を逆にたどって「どこからなら、黒色である頂点$v$に到達できるか」のフラグを頂点につけておけばよい
はじめに、有向辺を逆に張ったグラフを用意し、
クエリ$1$の度に、そこからDFSしてフラグをつけて回ればよく、
最大でも頂点数しかフラグを付けないので、それでも充分に間に合う
ACコード

メモ

逆向きに有向辺を張るという考えもあったが、パスを生成して判断する、という考えに囚われてしまった
それでは計算が収まるはずがない

ABC435E - Cover query

解法

遅延セグメント木なら、クエリによってノードの状況を変化させながらも、全体の合計を出すことができる
しかし、$1≤N≤10^9$のため、座標圧縮せざるを得ない
まず、すべての$Li$、$Ri$を先読みして、全部の$Li-1$、$Ri$（0-indexedにして、半開区間$[Li-1,Ri)$で扱うため）と、$0$と$N$をHashSetにいれてからソートした配列$c$を用意する
次項との差の配列(1..n).toSeq.mapIt(c[it]-c[it-1])を$d$とすれば、これは白く塗られているマスの個数であり、それを遅延セグメント木に乗せる
AC-Libraryで、opはa+b、mappingはx*f、compositionはf*gとすればよく、
0..<Qの$q$で
l=c.lowerBound(L[q])
r=c.lowerBound(R[q])
とすれば、
s.apply(l..<r,0)として、区間を黒く塗る、すなわち、区間の白の個数を$0$にした上で、その都度s[0..<n]を出力していけばよい
ACコード

メモ

半開区間にすることで、実装の見通しがここまでよくなるということがわからなかった

---

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