AtCoder ABC 146 - こんちゅう

解けなかった問題の簡単な説明を覚え書き程度に残す．

ABC146D

使用する最小の色数は最大の頂点の次元数．あとはどう構築するかだけれど，例えばqueueを使った幅優先探索を用いればいい．らしい．

ABC146E

難しくない？めげそう．
とりあえず累積和をとる（らしい）． $S_i=A_1+...A_i$ とすると，求めるのは
$(S_j-S_i) \% K=j-i, j-i< K, j> i$
なるi,jのペアの個数．もちろん $O(N^2)$ なのでナイーブには解けない．

こんなときにはしゃくとり法が使えるらしい．式を
$(S_j-j)\% K = (S_i-i) \% K$
と変形する（この変形すら思いつける気がしない）． $S_i-i$ を改めて $S_i$ とする。すると,iを固定したときに，求めるのは[i,i+k-1]のなかの，S_iと等しいSの個数．これは区間のSの個数をmapで管理しておいて，区間をずらすたびにそれらを増減させると $O(NlogK)$ で解ける． $logK$ はmapのコスト．

ABC146F

atcoder.jp

難しくない？（２回目) でもFにしては簡単らしい．というのも

解き方1

貪欲でいける．後ろから飛べるだけ飛べばOK．もしスタートからゴールまでのルートが存在すればこの方法で必ず解が見つかる．
複数個の解があったとき，このような解のとり方が辞書順最小となることも示せる．なんてこったい．

解き方2

貪欲じゃなくても解けるみたい（強い人はこっちがすぐ思いつくのかな）．
dp[i]:地点iからゴールまでの最小手数とする．するとこれはdp[i+1]~dp[i+M]までの最小値+1になる．
つまり[i+1,i+M]の区間内の最小値をいい感じの計算量で求められたらいい．これはRMQを使うと実現できる．
dequeでも出来る．らしい．あとでやらねば．