なつやすみ 41日目

ほげ〜〜

  • yukicoder埋め
    0-1パズル 難しい 実装もむずい

    サイコロで確率問題(2)
    サイコロをN回振った時出た目の和が[L,R]に含まれる確率は?という問題(1<=N,L,R<=10^18)
    AtCoderでは見ないタイプの知識を使った

  • yukicoder contest 313 う〜〜ん
    D:面倒なので遅延セグ木で殴る
    F:構文解析を一昨日初めて書いた人だったので気持ちよく解けた
    ICPCとか予選で落ちるから出なくていいか〜つって構文解析の練習してないけどABCで出されても文句は言えないのだな……
    G:負辺を含むMCFを一回も書いたことなかったから*1蟻本読んで実装しようとしたけどよく見たら計算量がO(E^2logV)になってて終わった……
    結局ダイクストラを始める前にポテンシャルを計算しておけばいいのだなに
    最大流も最小費用流も完全にブラックボックスとして使っているので何やってるかわからんになっていた

f:id:fumofumofuni:20210911014902p:plain

yukicoderのNo.1~No.300がある程度埋まった
残っているのは

  • 強実装(重実装の幾何とか階乗埋め込みとかbit詰め込みとか)
  • 強いアルゴリズム(最小シュタイナー木とかgarnerとかテトレーションとか)
  • 普通に難しいやつ(解いたユーザー数15人以下)

とりあえず先に301~を埋めようと思います

*1:使う辺の本数が固定の場合は経験あるのでこれは嘘だが