# のマスでグループを作って、. のマスがいくつの異なるグループを連結してその結果連結成分がいくつになるかを数える。実装していて気がついたけど、. のマスが新たな孤立グループになることもある。期待値を求める式に難しいところはない。すべての . マスについて、連結成分の数を数えて合計し、. マスの数で割る。■F 問題「Christmas Present 2」。DP をしたいけど線形時間で解けと制約がいっている。どうしましょう。いったん時間を忘れると、ある子供のところに行くにあたり、２通りのルートが考えられる。(プレゼントが１つ以上あるなら)直前の位置から直行して手持ちのプレゼントを１つ減らす。もしくは、サンタさんの家に寄って K 個のプレゼントを手にしてから来て、K-1 個にプレゼントを減らす。K+1 要素のデックに移動距離を記録して、shift、push、最小値の取得をすれば答えは出る。しかし TLE が避けられない>提出 #48793891 (TLE)。アイデアはある。K+1 要素の固定長ではなく、スライド最小値の要領で意味のある値だけを記録すればいい。全要素に対して移動距離を加算したり、プレゼント数を減算したりしたくなるのは、ベースとなる値をそれぞれに用意して、それとの差分を記録するようにすればいい(ベースを増減すれば全体が増減する)。提出 #48800858 (AC / 415 Byte / 305 ms)。数字が合わなくて提出が間に合わなかったのだけど、原因は 12 行目の処理を 13-14 行目の後ろに置いていたこと。基準値(d0)を加味した値と基準値からの差分とを比較してはいけない。あーあ、解けてたのになー。■それでも青パフォうれしい。コンテスト成績証。最近不調だったけど、今日のここが定位置だと自認している。次のステップは F 問題を時間内に通すことなんだよな。■F 問題を Ruby で最初に通した人はセグメント木を使っている。最小値を取得するのにセグメント木を使いたくなったのは自分も同じだけど、shift/push をどうするかがわからなくて深追いしなかった。セグメント木で解けるとわかってそういう前提でもう一度考えてみると、N+K 個くらいの要素数でセグメント木を初期化しておいて、参照する K 幅の範囲を１ずつ右にずらしていくという方法で shift/push 操作がまかなえるのではないか。セグメント木をそういう風に使ったことがないので思いつかなかった。……と思ったんだけど、セグメント木を使う２つの提出 #48799502、#48806332 を見てみるとそれぞれ K+2 と N のサイズで初期化している。なんで全部違うんだ。いや、まあ、説明できないことはない。N+K と N は、最初は参照するべき値が K 個ないことを考えると実質同じようなものだし、K 要素の方は、無効になったインデックスに新しい値を詰めるようなリングバッファ的な使い方で理解できる。実際にそういう使い方をしているのかは確かめていないので知らないけども。