ABC131

途中で測ったら37.2あって調子良すぎだった(若干空回りを感じたので落ち着いて熱を測った意味もある)。Dまでの早解きでとりあえず人権を得たいのだが、最近のABCはそれを許してくれない。

A - Security

問題が表示されるまでに30秒かかった。「連続したほうが押しにくいのか」と思ったのに実装するころには忘れている。双子回でもないのにYes,Noじゃないとかどうなってんの。あらゆる場所を逆にしてしまい時間がかかった。

B - Bite Eating

「なお、この値は一意に定まることが証明できます」ってビビるよね。頭の中で証明を考えて、0を通過するか0を通過しないかだからOKとか(文字にすると何も言ってないな)。とにかく、全体の和から絶対値が最も小さい要素を引けばいい。絶対値と値そのもの両方を記録する必要があるのが意外だった。int b = abs(b);と書いて気づかなかったりした。これはいつものBより難しい。

C - Anti-Division

こういう包除原理ならできます。ということで区間の倍数の個数を求める問題に帰着させそこを書く。最初、ラムダ式の中でbを変化させてしまった(constキャプチャやコピーキャプチャも考えたが使い慣れず自信なかったんだよなあ時間がないから慣れた方法でやるしかない)。ちょっと、区間を1ずらしたほうがいいのかなあとか思ったけど、なんか対称性のあるコードになったのでまあいいか安全側に倒したむしろ危険な汚いコードで提出。まあ時間かかったといっても10分とかだから、こういう境界を考える問題だと仕方ないところはある。実際は、f(t)ではなくf(t, b+1)-f(t, a)でよかった(なぜ思いつかない!!!!いつもこういう書き方しかしたくなかっただろ!!!卑屈すぎるんだよなあ)。

D - Megalomania

なにやら難しそうな問題。N通りの時刻B_iについて、その時刻までに「締切がその時刻と同じかより前のものが全て完了している」必要があり、逆にそれができていればOK。O(N^2)かと思うが、これはBが小さい順に処理していけば(ソートを除いて)O(N)でできる。この計算量の落とし方は、BITを更新しながら利用する難しい問題で覚えがある。この難しい部分に時間を使わずに済んだのがよかった。

E - Friendships

とりあえずサンプル1を手でチェック。まっすぐに並べてよさそうだと思い、とりあえず最大を考える。難しい。S<X<TでSとTの最短距離が2のケースを考えたが、XがSとTに挟まれてなくていいことに気づいてなかった。とりあえず隣同士は辺でつないで、端から多くなりそうな辺の伸ばし方をしていくが、どうもわからない。Fと並列に考えることにする。Dまでは全部解く前提なのでズガガンと1問ずつやっていくが、ここからはまず両方の問題を見て基本順番にやっていくという感じ。

FをACして戻ってきた。K=0のケースを考えて、完全グラフから辺を除いていく方法を思いつく。しかし、除きすぎると最短距離が3になったり∞になったりする。これを解消できない。二部グラフも思いついた。2つに分けて、うーん、細かい調整が難しい。最初のまっすぐに立ち返ったりもしたが、結局何もわからなかった。細かい調整できそうだけど思いついた方法ではできない(つらい)。

F - Must Be Rectangular!

これは見た瞬間面白そう。y座標が同じペア(というか3つ以上でもいい)を持ってきて、x座標がそのどれかと同じ別の点があったら増える。増え始めたらもう全部埋まるんじゃないかこれは。こう、縦横に連結であることで同値類に分けると、それぞれでx座標の種類数とy座標の種類数と元の点の数がわかればいい。単にグラフにすると辺の数をO(N)にするのが面倒そう。ということでUnionFind(まあグラフと同じことなんだけど2方向で隣同士手をつなぐ)。途中でソートするのでやっぱりインデックスも持たせる。N個の点をいくつかに分けるのだが、最大N個に分かれるし、1個あたり最大でN個含むので、O(N^2)にならないようにするのが案外難しい。uf.root(p[i].i)の値でソートして、長さNをいくつかに分けることにした。rootの値でソートしてrootの値で分けるのだが、現在のrootの値とソート済みの中でのインデックスの両方を保持しておく必要があることに気づかなかった(ここは力不足)。コピペしてsy.insert(p[i].x);とかなってたりしたし、ほんと今日はダメ(2回書くほうが悪いとは思うけど)。頭はよく回ってるけど細部に目が行かない。おおらかすぎる。解けた問題に興味がなくなるのはまあいいことだけど。x,yの絶対値も小さいし、もうちょっと簡単に書きたかったけど、F全体としてはけっこういい動きだったと思う。