オフラインバチャ会 4/20 - ugisの活動記録

やろうという流れになったのでやりました。

こういうの久しぶりだから楽しみ～～～と思っていたら完全に破滅して泣いちゃった。

A

Rの個数 > Bの個数だったのでBを1つ置いて区切りにしてRをB+1個の領域に分割して配置すればいいだろうと思って適当にやったらWAが出て無理になった。
いろいろ試しても落ちるし、どういうケースで落ちるかもよくわからなかったので、テストケースを全通り生成して落ちるケースを探したら、上の方法だとBが余るケースがあるらしいので、Bが余らないようにBを2つおいて区切りにするところをいい感じにつくると通った。

B

各bitに対してflipされる回数を考えればよさそうで、とりあえず上のbitから順にそのビットを選ぶか選ばないかを考える。
そうやって全部のbitを見た後でも操作回数が余る場合があって、そういうときは最下位bitに全部押し付けておけばよさそうなんだけど、どのbitも選ばないケースで落ちる。
どうすればいいか考えていたけど、時間内に分からず。
後でおるふぇさんが「全体をK回flipした後に、選んだbitだけをflipする操作をちょうどK回するのと同じなので」みたいなことを言っていて確かに～～～になった。
なんでこの言い換えが思いつかなかったのか。

C

よく考えると、移動にかかるコストの総和はどこまで右に進んだかにしか依存しないので、基本的には征服するたびに移動する方が得ということがわかる。
これが分かると、どこで止まるかを考えればよさそうだと思える。ある地点x_kで止まった場合のすべての国を征服するのにかかるコストの式を書いてみると、累積和をもっておくと各点についてO(1)で計算できることが分かるので、計算して最小値を取ればいい。
Cが一番すんなり解けた気がするな。まったく間に合ってないけど。

総評

文芸部門をやっていると競プロをやる確率が小さくなるので、オフラインバチャ会みたいなのはいいなと思った。
今回は破滅したので次は成功したい。