ABC136

堅実な5完で200位以内。よし。Fは難しかったが、Eまでは数学系の面白い問題が多くて得意セットだった。終了後36.9。久しぶりにレーティング上がったー!珍しく0時前にブログも書き終えて、けっこう内容的にすっきりしていた。

A - Transfer

よく考えれば解き方はわかる。要するにどれだけ水を移せるかわかればよく、それはmax(C, A-B)だ。それを出力してもダメで、容器2に残る量を答えるんだった。複雑すぎて、解けたころには道のりを忘れている。

B - Uneven Numbers

じっくり考えた。1桁なのは1から9(0は含まない)、3桁なのは100から999。しかし、愚直より簡単になる気がしないので愚直へ。幸い、ここまでの時間で桁数の簡単な判定方法がわかっている(各iについて10^iを超えるならインクリメントしていく)。

C - Build Stairs

またこの典型か。左から考えていくと、低くして(それより右の人は)損しない。最初深読みして「マスの高さを 1 高くする」と言い換えてしまった。そのままでいい。

D - Gathering Children

RLの境目が1つ以上存在し、そこへ向かって落ちていく。左右対称なので、R側だけやればいい実装に変更。境目に向かって落ちていき、それが偶数個なら境目の前後へ均等に溜まり、奇数個なら「10^100が偶数なので」(←ここ面白い)Rがあった側が1個多くなる。reverseしてLも同様。最後の要素がRでないことも利用できたし、いい実装だった。

E - Max GCD

絶対に解けそうにない問題に見えるが、「0をたくさん作ればいいんじゃね」と思って考え進めたところで+1と-1がセットなことを思い出す。意外と制約がきつい。たとえば全体の和の偶奇は保存される。ていうか、何で割ったあまりも保存されるやん!?全体の和は正なので、最大値が存在しないこともありえない(とりあえず安心しとく)。全体の和は10^9にも達しないので約数を全列挙できる。あとは各約数についてK回以内で実現できるか。ここがむずい。いや、そこまで難しいわけでもないけど、考察の山場が何回も来るのが、十分な実力があるか試されているかのようだ。増やす側と減らす側に分けないといけない。なんとなく減らしたいのとかあるけど厳密にはわからない。まず、(約数をqとして)qで割ったあまりの和はqの倍数になる。逆から考えたり色々やったけど、結局思いついてた貪欲っぽいのでよかったんだよね。これけっこうきついというか面白い。あまりの和をqずつ減らしていくのを(あまりの和/q)回やると0になる。回数が決まってるなら、貪欲に回数が少なくなる(あまりが大きい)ほうから取っていけばいい。全ての約数に対してO(NlogN)の時間をかけることも可能。最大値を求めるのだが、約数を大きい順に列挙してもいいが単に条件を満たすやつのmaxを取ってもいい。min(a[i]%q, q-a[i]%q)とか書いてたのがそのままになっててサンプル合わなかったりした(道のりが長いからなあ)(考察が完了する前に実装すると生じる問題だが実装は考えの整理に有効なので悩ましい)。そこ以外はわりといい実装だった。

F - Enclosed Points

まず座標圧縮できる。x座標でソートすると各ペアの間に含まれる点はわかる。条件を分解する?いや、xでもyでも含まれてない個数がわからないのでダメ。長方形のパターン数はO(N^4)には収まるんよね。どの長方形も、2個から4個の決まった点に支えられてる。長方形が決まればカウントできそうだが、その長方形があるかも大変そうだし、そもそもO(N^2)も許されないからなあ。ずっと、個数がO(2^N)の和とかどうすりゃいいんだよってなってた。