テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

ABC023回想

解けなかったが, 思いついた方針だけは書いておく.

C

N2は簡単に破綻する. なので, 片方をバイナリサーチするのだと思った. 各列・行の個数を求めてソートしておく. ある行の個数がr個の時, Kを満たすためにはK-rかK-r+1の個数の列とペアを組めばいい. これはlower_bound(K-r), upper_bound(K-r+1)で計算出来る. それぞれ, 降り立った場所に飴がない場合とある場合(あるならば-1しないといけないから).

サンプルでうまく動かないので, 調べてみると, 降り立った場所に飴があるかないかの判定が, 最初にソートしたおかげで不可能になっている. ちなみに判定のためには(int,int)のsetを使った. オーダはN logNと思った.

たぶん, ペアのセットを使うという時点でゴリ押し感があるので, たぶん方針が悪いんだろう.

D

「次の瞬間に最大になるやつを見つけて一歩手前で殺していけばよい」という方針だと思った. なので, 次の瞬間の最大値を計算し続けるセグメントツリーを更新し続ければよいと思ったが, 全風船に対して更新するとN logNかかる. 当然TLEだし, 壊した風船をどうやって管理するかも分からなかった. というわけで静かに投了.