600-800強化期間です
Atcoderの問題で最近考えたもののまとめ。だいたい30分考えて解けなかったら諦めて解説見てます。
ARC101D Median of Medians(700) トケナイ
実験などするも取っ掛かりが何も分からず。解説を見て愕然。
中央値を言い換え続けるだけでできるとは...あるiについてa[i]が中央値にあなるような区間の個数、というのは考えたけど、値そのもので切り取っていればもう少し進んだのかも。しかしこういうのトケナイのはショックだなぁ。
ARC068E Snuke Line(700) トケナイ
単純だけど計算量が落とせずギブアップ。クエリ系なのでSegment Treeとか使えないかなーと思ったが、どう使っていいか分からず。解説を読んだらそもそもの考察が全然足りてなかった。反省。
間隔dをfixして、「名産品を (何種類じゃなくて) 何個買えるか？」だとSeg.treeやBITを用いて準備O(NlogM)とO(MlogM/d)で判定でき、合計でO(NogM+Mlog^2M)で判定できる。で、「間隔が広いと絶対買える」「狭い場合だと0個か1個なので「何個買えるか」という問題になる」という考察から、dが狭い方からチェックして間隔がd以下の区間を追加すればそれで計算できる。なのでさっきの計算量で元の問題も解ける。
なんかこれSegment Treeっぽい、DPっぽいみたいな感覚も大事だけど、手法はあくまで手法であって、考察ありきなんだなぁというのを痛感した。
ARC077E guruguru(700) トケナイ
今度は逆に手法を知らなかったパターンか。
ショトカを全く使わない場合との差が何回出るかを見たいが、各区間で減らせる回数が1次関数的に加算されるので、なんかSegmentTreeかBITでやるやつあったなぁ、でも別に最後一回最大値が分かればいいだけだしなぁと思って頓挫。実際はimos法でできるのであった。
ARC076E Connected?(700) トケタ
端点が辺に無いと無視できることに早めに気付けた。そこから「円の弦を何本か引いて、交わらないか判定せよ」と帰着でき、どっかで切ってstackを使えばよいと気付けたのでよかった。最後のはちょっと詰まるポイントだったかもしれない。実装の時、誤ってqueueを使いかけたのはナイショ。
ARC085E MUL(700) トケナイ
N=100だしなんとかなるやろと思ったらわかんなかった。解説見てびっくり。最小カットに帰着は知らなかったなぁ。引き出しが増えたね。
ARC098E Range Minimum Query(600) トケタ
時間はかかったが最小値の方をfixすればよいことに気付けた。部分問題として「取り出すものの最大値を最小化する」だと簡単、ということにもっと早く気付いても良かったかもしれないが、変数固定はよくあるアイデアなので今後も忘れないようにしたい。
アイデア集
・変数固定
「ある値を固定する」というのはどんな問題でも通用しそう。2変数関数の最小値を、一方の変数を固定して最小を取るのと同じ感覚。
競プロでは特に困難を分割して単純な問題いくつかに分解する、というのがよく利く。何かしらいい値を固定すると、部分問題が簡単になるケースが多い。しかし、うまく変数を固定しないと計算しやすい関数にならないように、いい値を固定しないとうまくいかないこともある。そのへんはセンスと慣れか。
・imos法
単純なケースとして、「N個の列にQ回区間加算をしてmaxを求める」的な問題で、ナイーブだとO(NQ)かかるが、先に差分を考えあとで足すことでO(N+Q)でできるよ、というもの。累積和の逆演算は差分である。差分の方が簡単ならそっちを利用するといいよという話。
これが強いのは、二次元以上への応用が利きやすいのと、多項式関数でも何回か差分を取って計算できちゃうこと。今回みたいに一次関数の和でも、2回差分で解ける (解説も実質的にそうしてる)。Segment Treeみたいに何回も最小値を呼び出す必要が無ければこれでやった方が簡単。
・最小カット問題の応用
最小カット問題は、「始点0と終点1を除いた他の点を0,1に振り分け、0から1に行く辺のコストの和を最小化する」と言い換えられる。これを利用して、見た目最小カットに見えない問題も解いてやろう、というもの。
今回は叩き割るものたち0と、残すものたち1という分類をする最小カットだった。ただし、割り方への倍数という制約については、「条件を満たさない辺」に無限のコストを課しておくとよい。Nが小さければ今後も使えるかも。
・(おまけ) 逆数和
1からNまでの逆数和はlogN. よってi=1, ... , Nについて、N以下のiの倍数の個数の和はだいたいNlogN. 倍数に注目する問題で、倍数に対応する辺を全部引いたりすることがあるが、計算量はそんなにない。O(N^2)だと思わないように。
