なつやすみ 49日目

  • RFAをやってた なかなか面白いっすね カニさんがとてもかわいい

  • yukicoder 少し埋めた そろそろ~400が埋まりそうだが残りは面倒臭いものばかりに……

 

  • ABC219 ひどいことに……
    C:サンプルが弱いことに気づかなくて1WAした
    E:ぱっと見でやばそ〜となって逃げてしまった
    F:こっちの方ができそう!とか言ってやってたらEより酷かった…… 橙Diffは草 
    G:流石にこれをFの後に置くのは理解できない というかさっさと開けばよかったな

ねまつ

なつやすみ 48日目

眠いので手短に

  • 片付けが少し進んだ

  • No.377 銅Diffだけどかなり典型
    ポリアの数え上げ定理が使えそう→ちょっと実験すると(0,0)と一致するマスの数はlcm(H,W)の約数になっていることがわかる→この時点で約数包除でなんとかできそうな気がする→さらに実験しまくると包除する前の関数がgcd(H,x)*gcd(W,x)なことがわかる→書くと通る
    実際には実験しまくると〜のところが良くなくて、ここは普通に求めることができた 単純に(0,0)から(i,j)ずつ移動して(0,0)に戻ってくる手数は?という問題で、これはxだけに注目するとgcd(H,i) そのため、xy両方見ればlcm(gcd(H,i),gcd(W,j))なことが簡単にわかる これを丁寧に式変形していけば求まる

  • No.399 LCA+imosではい

  • yukicoder contest 314 むずすぎ
    A:45度回転した時に正方形内に入る点の個数
    B:対称性と打ち消し
    C:これがむずい 最初うまくナップサックとかに帰着できないかな〜と考えるけどできない 適当に実験コードを書くと規則性がわかる
    どうやら1/2未満、1/2、1/2より大きいで式が閉じているのでDPができるらしい なるほどな〜〜〜
    D:1つ決めると束縛条件が3つあるのでパラメータ4つが一意に定まる

  • JOI-CandiesとABC-H
    解説見て放棄してたので埋めておいた なるほどな〜という感じ

 

  • Alien DPとかMonotone Minimaみたいな高度典型を使う(だけの)問題を出題する自主コンテスト、もしかして需要がある?
    FFCでこういうのやってもいいかもな〜と思った(というか今までFFCのこと忘れてた) でも今から準備するとなつやすみ終わっちゃうんですよね(ACPCもあるし)

なつやすみ 47日目

なつやすみ、特にイベントもないし生活習慣も壊れているので1日の境界が曖昧になりがち

  • yukicoder埋めた 橙diff8-黄diff1でぼちぼちの進捗 ただ解いてて面白いものはあまりなかった
    No.329
    昨日書いた方針でよかった logを載せたけど1700/2000msで通った
    No.330
    適当にエスパーした 
    No.332
    謎制約あるし適当に半分前列挙+DPで
    No.336
    上位互換が既出
    No.344
    なんかエスパーしちゃったんだけど蟻本で既出とのこと
    蟻本持ってるけど全然埋めてないのやばすぎになった
    No.348
    やるだけ
    No.359
    これ面白かった おすすめです
    No.387
    bitsetでやるだけ そこそこ早くてびっくり

    No.371 ぼく悪いプライムじゃないよ - yukicoder
    これ面白いと思います 解法を載せようかと思ったけどこれを読んでる人にも解いて欲しいので載せません

明日は無限片付けするぞ!!!!!!!!!!!!のきもち

 

 

なつやすみ 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をやるスペースを確保するために片付けをしているが遅々として進まない

 

 

なつやすみ 45日目

9月も半分終わっててやばいに

  • ずっとyukicoderを埋めていた
    Pythonの練習も兼ねてやっていたが、制約が厳しくてPythonだと通らない問題がそこそこあった
    本来ならばここに今日解いた問題の面白かったやつの感想を貼るはずだが、黄色以上を埋めていないので特に書くことがない

    No.328
    プログラミングではなく高校数学 制約がヒントになっているので基本対称式を作る
    No.319,362
    異常桁DPを書けば通る
    5次元の桁DPとかでもバグらせることが少なくなっていて、かなり桁DP力の向上を感じた

 

なつやすみ 44日目

なつやすみを雑に扱いがちで、よくない

  • 部屋の片付けをしようとしたらポケモンカードを発掘してしまい一日が潰れた
    なんなら爪の間にカードが刺さって指を負傷した

  • Pythonを書く練習をしている
    一応簡単なDPは書けるようになったが、グラフ系の問題が厳しい
    謎の仕様に苦しんでいる とりあえず参照渡しが厄介すぎる
    setとかないしPython使ってる人はどうやって競プロをやっているのだろう……となった
    setの代わりにセグ木を使おう!みたいなこと書いてる記事も見かけたけどbinary_Trieの方がいいのでは?とか思っていた(実際どうなんでしょう)

  • yukicoder埋め
    なんか意識がないうちに30問近く解いていたっぽい
    青Diffも13問くらいあったが無が多かった(5年近く前の青なので今の水くらいの難度)

今日はやけに時間の流れが早かった

明日は読書会に向けて本を読まねば

なつやすみ 43日目

眠すぎなので簡単に

 

  • RFAのマットをついに購入

  • yukicoder埋め
    No.307 
    各連結成分について境界を管理すると、境界の総和はO(H*W)なので、マージテクを使うと計算量がO(HWlog^2(H))で抑えられる

    No.308
    面白い算数パズル

  • 諸事情によりPythonを練習し始めた
    環境構築をぴょんす先生に助けてもらい感謝……
    decimalが便利度高い