気晴らしのために動物園に行くなどした。
スクワットをした。
今日解いた競プロの問題。
競プロ典型90問
029 Long Bricks: Nがクソデカなら座圧しても無意味なので、遅延セグ木を使った。遅延セグ木はなんだかんだスクラッチで書いたことはなかった。一応ACしたがライブラリバグがないか不安。
015 Don’t be too close: 前に解説読んだが分からなかったので解きなおし。調和関数がNlogNになるのは良くて、コンビネーションに帰着させる部分の方が理解できなかった。ちゃんと読んだら分かった。教育を意図している部分と別のところで悩んでるのはどうか。
ABC248-F: 前に考察した通りのやり方で通った。ただ、添え字とかの細々としたところを詰めるのに死ぬほど手間取った。
ABC243-E: 解説AC。全点対間距離を持ってるのになぜか「ある点を経由した距離は分かんないよねー」という支離滅裂な思考になっており、解説コードを読むまで解法の意味が分からなかった。
あと、ワーシャルフロイドの添え字の順番をバグらせた。kijの順！間違えない！
約1年ぶりにABCに出た。
ABC249
A: Xが小さく、また時間も整数区切りなので十分に全時間シミュレートが出来る。時間を(A+C)で割ったあまり、および(D+F)で割ったあまりを持つと楽。変数を取り違えて1WA
B: やるだけ
C: bit全探索するだけ
D: $A_i=A_jA_k$なので、hashmapなどで各数ごとに存在する数を数えておき、約数列挙して$A_i$にできる$A_j,A_k$の組み合わせの数を数えれば$O(N\sqrt{N})$で解ける。なんかソートして工夫すれば$O(N\log N)$で出来る気がするが、この解き方がきれいで気に入っている。オーバーフローさせて1WA。long longとintを使い分けるようにしてみようかと最近思い始めているが、やっぱり注意力散漫だと死ぬ。
E: 数式をこねたら$O(N^3)$のDPが出来たので、区間更新部分を区間更新BITや双対セグ木にして$O(N^2\log N)$にしてみたが遅すぎてダメだった。セグ木の頭になると単純な累積和が頭から抜けることが知られている。
手前のセグ木が遅いのではという話もあり、非再帰セグ木にした方がいいのかなどとも考えている。
ABC後の感想戦のようなことをしていたらあっという間にすごい時間になった。やはり競プロと規則正しい生活は両立しづらいものを感じる。
Categories: 未分類