なつやすみ 36日目

旅行行きて〜〜〜〜

• 親のポケモンGOの手伝いをする
  
  
• Educational Codeforces Round 112 (Div.2) バチャをした A~Eの5完
  A：勢い余って謎DPを書く
  B：長方形の敷き詰めが縦横独立になるの、ABCで見た記憶がある
  C：全探索すると累積*2
  D：2以上任意の長さの回文が存在しない⇔長さ2または3の回文が存在しない
  Yukicoderで何回か見た記憶ある
  E：Max-Minを最小化したいとき、にぶたんは微妙で、Minの全探索+差分更新が有効がち
  区間を処理するデータ構造が必要になって、遅延セグ木を持ってくる　
  いきなり高度な知識が必要になったから非想定かと思ったら想定でびっくり
  Codeforces、なんとなく全体的にTLが厳しいんだけどこれは何故なんだろう
  F：とりあえずCactus-graphになることがわかる　Tree-edgeかcycle-edgeかを見分けるためにUnionFindが必要なことがわかって書き始めるもサイクルに使われた辺を見分けるの無理じゃね？となって終了
  解説を読む　確かに先読みして全域木を作ってその上で操作を考えてもいいことがわかる　つまりHLDかEular tour+BITで検出できる
  なるほど〜って感じ　クエリ先読みして全域木を作るのは教育的かもしれない

もしかして通常のDiv.2とECRのDiv.2って難易度違う？

早く寝るか