ABC117

終了後に熱を測ると37.0度。うーん、頭は回っていたものの、この頻度で熱が出るのはさすがにまずい。何なんだ。

A - Entrance Examination

複雑に見えるが、要するに割ればいいみたい。AやBが変数名じゃないことになかなか気づかなかった(高速で読もうとしてるので)。1分を大きく超えたが、printfをコピペしてきたり複雑なので許容範囲。どっちで割るか最初間違えた。

B - Polygon

遠慮なく定理を使わせてもらった。辺が交差してもいいのかなとか思ったけど、後から考えると長さL_iの棒をつなげたものを考えれば普通にできそうか。凸にできるのかな。気づいてなかったけど、順にこの長さの辺なのかな。証明は難しそう。よく考えず出したので提出してからやや不安だった。まあABCはスピード重視。

C - Streamline

いかにもABCのCで、解けないうちから安心感があった。目標地点が(N個ではなく)M個なのがややこしい。コマはXからスタートするとしてよさそう(あまり考えてなかったが、最初に訪れるXに元からいたほうがいい)。そこからの移動は、短い距離のものがいい。どのコマが動いてもいいので、好きな区間を選べそうだ。つまり、Xをソートして、区間の距離でソートして、小さい順に最初に置けないM-N個を取る。コマが足りてる場合は最初に処理しておく(入力を受け取る必要もない)。答えは高々max(X)-min(X)なのでintでいい。最初vectorの要素数をnにしててサンプルが通らなかった(ややこしい)。

D - XXOR

10^12とやや大きいので入力のコードを先に書く。さて、ちょっと難しそうに見えるが、2進法で紙に適当な数を昇順に書いて様子を見ると、別に昇順である必要もなくビット毎に和が大きくなるよう値が決まることがわかる。例えば最下位ビットが立ってるAが3個なら、3とN-3の好きなほうを選べる(N-3を選ぶときはXの最下位ビットを立てる)。これでコードを書くが、Kを考慮していないことに気づく。上位ビットから取れるだけ貪欲に取っていけばいいか?いや、それではダメだ。例えばK=100で上位から貪欲でX=100になったとして、X=10のほうがいいかもしれない(1ビット下がっても半分にしかならないのに対しNは10^5もある)。これはかなり困ったことになったぞ。もう400点ぶんの考察はしたつもりになっていた。えーと、どっちでもいい場合(3==N-3みたいな)はXのビットを立てないほうが得。もう少し考えると、貪欲の場合のXの最上位ビットが1か0かで場合分けするだけでいいのではと思う。0のときは、どんな取り方をしてもK(貪欲Xの最上位ビットだけからなる数以上)より小さくなるので貪欲でいい!場合分けは、コピペで(このムーブがどうだったかは今でもよくわからない)。Kより大きくなるビットはスルーするが、和をとる処理もスキップしていたのでサンプルが通らなかった。場合分け処理がやや複雑で少し時間がかかる。提出してなんとかAC!久しぶりにいい順位だね。体が人権で満たされる。

と思ったが?これを書いていて気づいたが、貪欲の場合のXの最上位ビットが1のままのケースで、K=110,X=110でいいと思ってたらX=101のがいいってことあるのでは!?うわあ、嘘を通してしまったか。ええと、上位から見ていってビットを立てたほうがよくて立てることができる場合、立てるケースと立てないケースをやる。立てないケースはKの制限にかからないので簡単。立てるケースも1ビット短くなってるので解ける。あ、1回あたりO(N)かけてたから事前に計算しないとまずいか(いや、O(N*log^2(K))だから通る可能性も?)。WA。おいまたスキップしとるやんけ!直してギリギリ時間内にAC。