なつやすみ 63日目

あと1日ですか……

• 出かけてた　本を探しに行くも見つからず
  
  
• ABC221　8200人中33位となかなかいい成績
  A：草
  B：愚直　Rolling Hashで線形になりますかね
  C：bit全探索したあとそれぞれ降順sort　ユーザー解説が強い
  D：実装で手間取りまくり　イベントソートの書き方が未だに定まっていない
  区間を開区間で考えて+と-をmapに埋め込む、直前のtを持ちながらループを　　　回して先に区間長を計算して答えにたし込み、差分を更新するのが良さそう
  E：めちゃ悩んだ　結局セグ木で書いた
  座圧して、dp[v]:=最初に選んだ数字がvとなる部分列の総数とするとin-lineになる　全体を2倍する操作をするので適当に1/2した状態で埋め込んで答えに加算するときに復元する
  F：直径は木の中心を通るので中心から見た方向ごとにグループになる
  直径を求めつつ中心を求めておく　直径の偶奇で場合分けした
  頂点倍化みたいなのすると場合分け減るらしいけどそれはそれで面倒では……？
  H：そもそも分割数をどうやって求めるかな〜って検索するとヤング板の記事を見つける　転置を考えると条件が簡単に言い換えられる　累積和をサボってセグ木で書いたらTLEして涙
  G：Robot Armsを思い出したけど流石に何もできず終了