なつやすみ 46日目

もはや惰性で日記を書いている……

• カレーを作りました　はい
  
  
• yukicoderを埋めていた　橙を中心に埋めた　
  
  No.309
  ぱっと見でO(HW2^(H+W))が見える　ただH,W=11でかなり厳しそう　実際書いて定数倍削るとTL4secのところ5.4secくらいで厳しい気持ちになる　
  結局解説を見る　前計算でO( (H+W)2^(H+W) )に落とすのが想定だったようだ　でも出題当時はO(HW2^(H+W))もそこそこ通っていたようである
  
  maspyさんの解法を見つけてあまりのおしゃれさに感動してしまった
  もし前と左だけを参照するなら畳の問題みたいにdp[H][W][直前一行のbit]と持つ方針が通るが、今回は右からも影響が来るので出来なさそうに見える
  しかし、右からの影響が伝播する場合は連続区間でしかあり得ないため、dp[H][W][直前のbit][自分より左にいて右からの影響があれば挙手する人の連続する区間の長さ]と持つことができ、O(HW^2*2^W))を実現出来る
  実装にも無理がなく計算量を大きく落としていて極めておしゃれ
  
  No.315
  N以下の各数字についてmod3*mod800で分類してそれぞれの該当する個数を数えてください、N<=10^20000という問題
  普通にやるとTLEだが、mod800は下5桁の値のみに依存するので、上から桁DPをして残り5桁になったらmod800を数え始めれば良い　2つの桁DPを結合する感じでやった
  
  No.317
  総和に制約がついた部分和問題に帰着
  正整数の多重集合であって要素の総和がNのものについて、多重集合内に含まれる整数の種類はO(√N)で抑えられるので、各種類についてO(N)程度で抑えられれば全体O(N√N)で間に合う
  スライド最小値でやったが2冪に分解してやる方針でも間に合うっぽい
  
  No.329
  まだ解いてないけど方針だけ書いておく
  とりあえずi→jとなる全射が存在することは、
  辺集合E上で、i→jのパスであって、通る各頂点についてw>=wjが成り立つものが存在するとwi>=wjが成り立つことが必要十分
  これは愚直にやっても間に合う
  数え上げは包除でなんとかなりそう 全体O(NN(W+E))で間に合うと思います
  
  下は青
  No.323 BFSするだけ Pythonで初めてBFSを書いた
  No.313 カスとしか言いようがない

寝ますか
RFAをやるスペースを確保するために片付けをしているが遅々として進まない