昨日の日記を書いたあと、寝ようとしたら敷布団を干しっぱなしにしていた。ベランダの窓を開けると雨がざんざか降ってて布団がびっしょびしょになっててすべてが嫌になったので、ベランダの庇の下に取り込んで適当に放置した。
仕方ないので掛布団と毛布を床に敷いて寝たら、固い。起きてもなんか疲れが取れていなくて最悪だった。
夕方までの記憶マジでない。なにしてたっけ？ 整数論とか近似アルゴリズムとか勉強してた気がする。一般の巡回セールスマン問題には多項式時間近似アルゴリズムが存在しない（ハミルトン閉路問題が解けてしまうため）が、三角方程式を満たす辺長のグラフなら2-近似アルゴリズムが設計できる、というのが面白かった。
ABC-Fを1問解いた。
F - Distributing Integers
atcoder.jp
解法と感想（クリックで展開）
全方位木DPをやる問題。しばらく前に理論を勉強したので、何も見ずに実装できるか挑戦してみた。少しバグらせたが、全体としてはスムーズに実装できた。全方位木DPを学んだときは、こんなものが で計算できるのかと驚いた記憶があって、かなりお気に入りのアルゴリズム。
21時からABC219に出た。54分5完、274位。
Aは面倒だったのでupper_boundで求めた。Bはやるだけ。Cはソートの比較関数を実装する。Dはナップサック問題のアレンジ。個数が 以上になるものを
にまとめる。Eは面倒だった。堀の内部に入れる位置をbit全探索する。堀の内部が連結で、かつ穴がなければOK。穴がないかの判定はすべての
0が外周の0から到達できるかをBFSで調べた。自分が実装している最中に、ほとんど解法を教えているようなclarが公開されてかなりびっくりした。聞く側はあのように聞くしかないだろうが、そのまま公開するのはどうなんだろう……？ Eを通したあと、順位表を見てFより解かれていたGを考えたが解けなかった。解説を読むと平方分割で解くらしい。平方分割を使う問題は一度も解いたことがないので、これは無理だったと思う。終了後のTLを見ると、どうも典型90問でほとんど同じ解法の問題が既出だったらしい。勉強不足を咎められて反省。典型90問は埋めよう埋めようと思って放置している状態が続いている。
パフォは2088で、レートは1692から1738に上がった。ここ3回ABCで黄パフォを出せていてとてもいい。もう一段実力が伸びれば黄色になれそうな気がしている。明日のARCも温まりたい。
23:35からCodeforces Round #743 Div. 2に出た。A問題のジャッジに一万年くらいかかっていて、案の定30分くらい経ってunratedになった。C問題までは通したので解法を書く。Aは1の位の数を0にしたあと、各桁とswapして減らしていく。Bはよくわからなかったので、 の先頭を固定してセグ木上の二分探索で
の先頭を求めた。Cは閉路判定をしたあとDAGの最長パスを求める。番号が小さい頂点から大きい頂点へは遷移する必要がない。Dは後ろから見る貪欲を投げたが落ちてしまった。TLを見るに累積xorを使ってどうにかするらしい。01列で累積xorを考えるのは何回か見たのに自分の典型引き出しに入っていなかったので、以降意識することにする。upsolveは明日。
こどふぉがunratedになったので高校同期と通話しながらコードネームをやった。今日は全体的に荒れてて楽しかった。
ちなみに想定解は「オブラート」。どっちもどっち。
寝る。
