なつやすみ 42日目

昼夜逆転生活が続いている

• yukicoder埋め
  No.303 割れません
  かなり険しい問題　まずコーナーケースの処理から難しい
  本題パートはフィボナッチ数のN番目の値を求めるというもの(N<=10^6)
  一見簡単だが、modを取らないという異常問題
  C++で多倍長を実装して、掛け算をNTTで処理しながら行列累乗すると通る
  
  
  
• ABC218　
  

  

  A~Fを倒したところまでは良かったんですけどね……
  
  D：Cを飛ばしたら幾何っぽいのが見えて焦る
  y座標が等しい点同士で線分を全列挙してx座標で組み合わせた
  E：やります
  F：最短経路木が見えるからそれをうまく高速化するのかな？とか思った(可変全域木を解いたことがあったので)　これってデータ構造とかで高速化できるんですかね？
  C：悩んだけど結局黒い座標をsortして比較に落ち着いた
  G：中央値は二分探索！つって木DPを書くけど合わない　結局解説ACになってしまった　
  
  binary_trie強いね　もしかして最強のデータ構造ですか？　
  k番目が取得できるmultisetというだけで強いのにSetXORMinまで出来るのは偉い