おいうリーグのともくんvs.ゆうきの視聴をいいところでやめてABCをやったら最初の3問でゴミみたいな時間の使い方させられた。5完でDEFの3問は面白かった。水パフォだけど、内容は悪くない（すみませんpredictor見て書いたけど実際はギリ青パフォでした）。
A - Humidifier 1
水がなかったら水は減らないっぽいのに対し、水があふれることに関しての記述が見つからない。十分な容量があるとかの一言欲しかったなあ。そこで不安になってけっこう時間使った。問題の意味がわかったとしてもけっこう難しくて、前回水を入れてからの時間を得て0未満にならないように水を減らすという処理をした。A問題なのに3分以上かかってゴミ。
B - Humidifier 2
全探索。6乗なので間に合う。実装の重さはまあいいとして、計算量の見積もりがB問題にしてはかなり大変。実装上のポイントとして、同じマスに2個の加湿器を置けるとしても得しないのでそうしてよい。
ここまでの2問で10分かかっている。おいうリーグ視聴を中断して得た10分でこんなゴミみたいな作業してたのマジ！？
C - Humidifier 3
BFSするだけ。ライブラリをもっとちゃんと整備しておくべきだった。こんなのに10分かかっている。
D - 9 Divisors
コンテスト開始から20分が経ち、ここで初めて楽しみが得られた。食べ放題の前菜かよ。
約数が9個ということは、素因数が1個で9または素因数が2個で3*3。9の場合をまずやると、8乗してN以下になる素数を列挙すればいいのでこれは簡単。3*3は、2個の異なる素数（順序なしのペア）でそれぞれ2乗したものの積（つまり積の2乗）がN以下というのを数えたい。2乗してN以下の素数を列挙して、そしたら最大ケースでも2000個以下だったので、全探索すればいい。オーバーフローするものはdoubleで概算してはじく。最初は4*10^12まで全部生成してと思ってたけど単にN以下をカウントできたのでvectorに突っ込んでたのは要らなかった（WAのときデバッグに使える保険にはなっている）。この方法だと素因数の個数や種類が全部異なるので被りはない。
E - Sum of Max Matching
解ける見た目をしていないので、Fを読んで順位表を見た。まずEをやる。
全ペアのパス重みを求める時間はないし、そこを越えてもABのマッチングが難しい。まずパスの重みを求めようとしてみる。辺の重みの最大値なので、重みの小さい辺から追加していくことを思いつき、UnionFindを思いつく。これで二分探索ができるかと思ったが、最小化したいのはパス重み最大値ではなくパス重みの和だった（実装して初めて気づいた）。実行時間制限2.5秒だから二分探索のlogが付くだろうと思ってしまった（本当によくない）。それでも希望はありそうで、UnionFindのイメージを考え続ける。辺は重み昇順でソートしておく。辺を重みWまで追加したら、同じグループ（連結成分）内のABは重みW以下でつながれる。最善のパスがちょうどWとはかぎらない。しかし、重みW未満の辺しか追加していなかったときには違うグループだったABが重みWの辺を（全て）追加して同じグループになったなら、それはちょうど重みWのパスでつながることになる。でも合併したときにABの個数が違っていたらどれを優先してつなげるかが難しいのでは？と思ったけど、同じグループになった時点でどいつも状況は同じ（今ペアを作れば重みWだし、あとでならそのとき追加した辺の重み）なので個数だけ管理すればよかった。あとは、UnionFind内でABの個数も管理するようにして、ペアを貪欲に作っていく。実装していて、ああ、だからA_1==A_2はあってもA_1==B_2はないんだなと。未証明だけどAC。こういうのも面白い。
F - Diversity
種類数と価格でDPするのが素直だが、DPテーブルの時点で2.5*10^7くらいのサイズなので更新ができない。ということでまずEをやった。
かなり考えて思いついたが、色毎にまとめるといい。全体の色数が多いか少ないかで平方分割みたいになるのかなあとか思いながら。とりあえず同じ色だけで価格を状態とするDPを書いてみる。で、これもかなり時間が経ってから気づいたのだが、色毎に考えているなら色を追加するとき満足度がちょうどK増えるので、外側のDPで種類数を持つ必要はない。これでO(X)のDPが2種類だが、それらを合わせるときに2乗かかってしまう。ただ、同じ色の個数が少ないなら高速にできるし、多いなら色数が少ないので2乗もワンチャンある。無理だとは思ったけど時間も残り1分を切っていたので（無理であることを確認する時間がないので）それで提出するとTLE。
初期の考察で、1個ずつやると種類数が掛かってくるイメージがあった。それが尾を引いていた。O(X)のDPしかないんだからN回やればよかった（単純に考える時間が足りなかったという感じ）。Xの制約はもっと大きくても成立したと思うけど、このくらい小さくても簡単になってないと思うし、自分は惑わされてTLEしたから、いい制約だったと思う（こういう制約の問題もっと増えてほしい）。手なりにDPを書いてサンプルが通ってからその正しさを確認するのが難しかった。ここでは、種類数が0か1のDPをする。種類数が0は元のDPテーブル。そこから現在の色の最初の1個を使うと、種類数が1のときの最大満足度になる。また、これは現在の色を現在の位置まで使ったときの最大で、種類数が1から1への遷移もある。後ろからやれば同時にin-placeでできる。この正しさを確認した方法に書き直して提出、AC。次に、最初にサンプルが通った方法が正しいか考える。種類数が0のテーブルをコピーしておいて、本体のDPテーブルを直接更新する。1種類のときの値が0種類ので初期化されているけどいいのかと心配したが、種類数ボーナスをもらわない選択もできるというDPになっているだけなので影響はない。また、「価格がちょうどj円のときの最大満足度」ではなく、「価格がj円以下のときの最大満足度」とすることで、最後にDPテーブルの最大値をとらずに済む。
このところ、最後にやっていた1問が解けずにレーティングを落としているが、その1問は自分にとって練習になるいい問題で、満足度が高い。
