ABC165

ノンペナ全完ヒャッホーーー!!いやあCDが瞬殺できなかったときはどうなるかと思ったが、FがシンプルでEも意味がわかれば面白かったのでよかった。

A - We Love Golf

何このクソムズA問題。for文使って書いたけど、A問題ってことはループを使わない想定なんだよね。まあ(A+K-1)/A*AとしてBと比較するみたいのは思いついてたけど難しいでしょ。今気づいたけど、B/K*KをAと比較したほうが簡単だ。

B - 1%

これもむずい。最初、t*101/100みたいのを考えてて、オーバーフローしそうだから困ってた。t+=t/100でいいんだね。X=100のケースがないのが親切。最大回数の見積もりもB問題にしては難しいなあと思っていたが、入力例2にX=10^18のケースがあることにACしてから気づいた(いやちゃんと数えてはなかったけどこの見た目で10^17とかだったら詐欺でしょ(いやそれは甘えかなあ))。

C - Many Requirements

ヤバC。まず列挙ができない。少し考えて、M個の1の間にN個の仕切りを入れるのだと気づいた。20C10をまず計算して(ググって)意外と小さい(10!より小さいと思わなかった(感覚がひどい))ので(時間をかければ)解けそうだと思った。考察を寝かせるためにD問題へ。

あとは頑張って実装。M個の1ではなく、M-1個の1だった。差だけが重要なので0以上M未満としてよい。next_permutationで全探索。1の個数を累積させ0に当たったらA[j++]という感じで整数列を構成。あとは言われた通りに総和を求めてそれの最大値。けっこう難しいし実装も重い。これを早解きするのは化け物。

D - Floor Function

B倍して式変形するとx%B*A/Bの最大値を求めればいいことになる(B倍したらちゃんとBの倍数になって不思議だった(不思議、つまり理解してないのに答えがわかるのが数式のいいところの一つ))。x=min(N, B-1)とすればよい。

E - Rotation Matching

問題文を読むのがかなり大変そうなのでF問題を先にやった。FをACしてからじっくり読んでみると、内容自体は別に複雑じゃないし面白そう。まず、条件を満たさない割り当てを頑張って見つける。例えば差が1になるような整数のペアが2つの対戦場に書いてあると、隣の人と2回対戦してしまう。なるほどそういうゲームか。そして、差が1と差がN-1は同じことだ。つまり、Nが奇数のときはサンプル2のようにすればいけそう(ずいぶん親切なサンプルだと思った)(差が1,3,5のようにして(裏が6,4,2なので)被らない)。Mが小さいときは楽になるだけなので途中まで出力するだけでいい。

偶数のときも似た感じでできないか考える。差が0とN/2はダメ。例えばN=10のときは差が1,3,6,8とすればまあよさそう?いくつかの例を慎重に考えて大丈夫そうなので(証明してないけど(おい))それで実装した。差がN/2以上になったら1個広げる感じで。こういう実装は苦手意識があったけど、思ったより短く書けてAC、全完。

F - LIS on Tree

例によってChokudai SpeedRun 001のH問題の自分の提出を見に行く。LISには、lower_boundを使う方法とBITを使う方法があるので、どっちが使えるだろうなあと思いながら木上のDFSに思いを馳せる。根から葉までのパスでそれぞれ普通にLISすればいいだけだが、それを高速にできるかという話。lower_boundのほうはなんか簡単に差分計算できそうに見える(ある場所の値を更新して必要ならお尻を伸ばすだけなので)。解けてしまった。正直言ってLISはすらすら書けるほど理解してないので、コードを組み込む感じでミスが入り込まないように書く。サンプルが通ってから最後の見直しで、x.assign(n, n);の右側のnが要素数ではなく要素の最大値だと気づき1e9+1(+1は念のため(もう脳が限界なので))に書き換えてgot kotonaki(見直しが奏功する珍しいケース)(追記:と思ったらイテレータで使う範囲を管理してたので値nは使ってなかった)。