ABC144

頭が悪いので得意セットでこれ。

A - 9x9

問題が表示されるまで20秒かかった(このくらいなら問題ない)。a * bを出力する、だけではなくちょっと分岐がある。ちょうどいい難易度。

B - 81

続き物いいね。今回はジャッジが重かった。

C - Walk on Multiplication Table

sqrt(N)まで全探索ができる、けど2数のうち大きくないほうを小さい順に見ていくなら最後に発見したやつでいいよね。証明はできそうだからしてない(そういうとこやぞ)。

D - Water Bottle

またatan2ググる。なかなか慣れんな。それはいいとして、場合分けが入るのできつい。どっちも簡単なんだけど、場合分けが入るだけで難度が1段階上がる。そして簡単と言いつつけっこうな時間紙に向かってウンウン言ってた。水が全体の半分あるかで場合分けして、簡単そうな水が多い場合から。水が少ないときは、なるほど90度倒した状態の水位がわかればいい。これをね、瞬殺したい。

E - Gluttony

こういう問題を読むのに5分かかるんだけど2分くらいでなんとかならんか。もちろん読めてしまえば把握できる。積の和ではなく積の最大値。それを最小化したい。K=0ならソートするだけ。Aを大きい順にFを小さい順に。証明は、うーん、ソートしてあるとして最小値より大きくなってるペア(A_i, F_i)を一つ選びそのA_iとペアにするのはF_iより小さくないといけないがそういうFはみんなA_i以上のAとペアになっているためF_iを引き受けてもらえるAがない。よさそう(これでは1回のswapでは改善できないことしか言ってないが結局A_i以上のAたちがいる領域にF_i以上のものを一つ送り込む必要があるのでそこでもとの最大値以上になる)。あとはK>0の場合だが、実現可能か判定していけば二分探索でできそう。ソートしてペアを作って、ここからAを変化させるわけだが、目標が広義単調減少なら元も広義単調減少でいいよね?(←大丈夫そうなのであんま考えてなかった)さて、あとは二分探索するだけ。lower_boundを使うかupper_boundを使うかいつも迷う。条件を満たす最小のものが知りたいのでlower_boundでよかった(upper_boundでも条件逆にするだけだからいいんだけど(この辺に自信がないから迷うんだよね))。典型っぽい問題だった。もうちょい速く実装できればというところ(Fに時間を残したい)。

F - Fork in the Road

塞ぐ操作がないなら、DPでできる。逆からかと思ったけど、普通に順方向でできる。この問題が対称かはわからなかった(改めて考えたらゴールできる道の選び方が必ず存在しても行き止まりがあるかもしれないなら(それでも同様の方法で解けそうではあるけど)「ゴールできた場合の期待値」とか問題にちょっと追記する必要が出てくるな)。塞ぐにしても1回だけだからできそう。Mは最大で18万くらい。O(M^2)は無理、O(NM)がギリギリ通りそう、実際はO(M)かなあという感じ。塞いだかどうかの情報を持ってDPすることを考える。そこへ来る確率とそこまでの通路の数の期待値を塞いだかどうかで2つ持つ。実装に異様に時間がかかる。最初は余裕のある時間だったのが、だんだんギリギリになっていくいつもの感覚。残り5分になったところで、塞いだ場合の確率と期待値は状況によってどういうのがいいか変わるので比較できないことに気づいた(そこの実装までにそれだけ時間がかかっている)。ここで死亡確定。O(NM)でいいならどこで塞いだかの情報も入れてDPできそうだなあとか思った。具体的なことはこれから考える。本当に疲れた(いつも日付が変わる前にブログ書いてるけど今日は無理だった)。