なつやすみ 52日目

• RFAをやった 2回目です
  初めてゲームオーバーになった　敵に1回殴られて2耐えするからって回復しなかったら次のターン2回殴られた
  
  
• yukicoderの301~400が一段落ついた
  

  

  310、364はまだ10人程度にしか解かれていない難問
  331、363、382は解法の検討がついているが実装が大変なので放棄
  
  解いて面白かったのは
  308、309(別解)、359、371、377
  377は典型気味だけど他はAd-hocな感じでよかった
  317、344は蟻本を確認するいい機会になった
  
  次は何しようかなと思ったけどとりあえずAtCoderの橙埋めかなという感じ　yukicoderは虚無埋め率が高いので学期中にも進むだろうという判断
  
  
  
• yukicoder No.1684 Find Bracketを解いた　むずすぎ
  本番中は前2問に時間を取られてf(S)の定式化までしか辿り着けなかった
  カタラン数の考え方が使えるというヒントを得た状態で考えた
  
  f(S)は{"("、")"}={-1、+1}とした時の累積maxをv、開き括弧の個数をxとして
  f(S)=(v+x)*2になるので、vとxを固定した時にO(1)で求められるかを考えると、カタラン数に近い構造になってて、これはできる　つまりO(N^2)は簡単に得られる*1
  
  とりあえずこれを書いて適当に式変形でまとめていくとカタラン数の計算に出てくるのがcomb(N,*)の形をしていて、さらに*が連続した区間になるので累積和で解ける
  
  よくこれが線形になるなあという気持ちになった
  というかこれが本番15人に通されてるのが怖すぎる
  
  
  

*1:ここまでで1時間かかったんですけどね