📚

AtCoder Beginner Contest ABC434 解法メモ

2025/11/30に公開

Nim

AtCoder

tech

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

ABC434

ABC434A - Balloon Trip

解法

$W\times 1000[g]$ が $n\times B[g]$ 未満になるときの $n$ であるから、
答えはW*1000 div B+1となる
ACコード

ABC434B - Bird Watching

解法

種類毎に鳥の大きさを登録していけばよい
b=newSeqWith(M,newSeq[int]())
を用意して、
$N$ 羽の鳥に対して、b[Ai-1].add(Bi)していき、
最後に、0..<Mの $i$ に対して、
b[i].sum.float/b[i].len.float
を出力すればよい
ACコード

初め $H$ にいるので、 $t_1$ までには
u=max(0,H-t1)
l=H+t1
の間にいることができる
一方で、次に進むには、 $l_1$ 、 $u_1$ の間にもいなくてはならないので、区間を合成した、
u=[0,H-t1,u1].max
l=min(H+t1,l1)
の間にいる必要がある
もし、それが $u<l$ だと、区間がつぶれてしまうので、目標が達成できない、ということになる
次の $t_2$ までには、
max(0,u-(t2-t1))
l+(t2-t1)
の間にいくことができるが、
同様に、 $l_2$ 、 $u_2$ との区間合成をしていけばよく、
これを繰り返していけばよい
最後まで、目標が達成できたらYesを出力することになる
ACコード

メモ

区間がつぶれた際、Noを出力して、即breakするように書いてしまったため、次のテストケースの入力と混同するWAを起こした
原因がすぐにわからず、かなり時間を溶かした

ABC434D - Clouds

解法

$i$ が1..Nの際に、雲が一つもないマスの数の合計に、雲 $i$ しかかかっていないマスの数の合計を足した数を答えればよい
二次元の累積和をとるimos法を用いれば、雲が一つもないマスの合計 $z$ と、雲が $1$ つしかかかっていないマスの座標を求めることができる
新たに、「雲が $1$ つしかかかっていないマスだけ $1$ 、他は $0$ の配列」 $o$ を考えれば、その配列の $Ui$ 、 $Di$ 、 $Li$ 、 $Ri$ で囲まれた範囲の合計は、冒頭に言った、雲 $i$ しかかかっていないマスの数の合計に他ならない
これは改めて二次元の累積和をとれば、求めることができる
ACコード

メモ

雲番号別に、その雲しかかかっていないマスを数えることができなかった

ABC434E - Distribute Bunnies

解法

公式解説にある通り、
ジャンプ後のすべての $Xi+Ri$ 、 $Xi-Ri$ の重複を除いた座標を頂点に、
$Xi+Ri$ と $Xi-Ri$ を結ぶ辺をもつグラフを考え、
辺のどちらかをジャンプ先に選ぶと考える
連接成分内にループがあれば、
そこでジャンプ先を余らせることなく使い切ることができるので、すべての頂点を使うことができるが、
木構造、つまり、その連結成分に含まれる辺が、頂点数 $-1$ のときは、
葉の中の $1$ 箇所は使い切らずに余らせてしまう
まずは、ジャンプ先の座標を座標圧縮し、
さらに、各辺をUnion-Findしながらmergeしていき、
ジャンプ先の $Xi+Ri$ と $Xi-Ri$ が同じ連結成分にいたら、頂点番号を控えておく
控えた頂点の各leaderを求め、重複を除けば、ループのある連結成分数が求まる
答えは、全頂点からgroup数を引き、ループのある連結成分数を足せばよい
ACコード

メモ

グラフを用いることすら浮かばない

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