ARC106

4完。朝から体調悪かったけど、どうにか戻して戦えた。コンテスト中やる気ない感じはしていたが、落ち着いてできたとも言えるので悪くはない。ひっさびさの黄パフォ。

ABCとARCは点数と難易度の関係が同じらしいけど、本当にその通りで、自分にとってはただのABCだった。

A - 106

問題名はどういう意味だ（ARC106なのと、サンプルに106があってきれいな式）。AとBの候補は100個以下（10^18は2^64より小さい）なので全探索。簡単そうだが、オーバーフローが心配になる。uint32_tは4*10^9を表せる、よってuint64_tは16*10^18を表せる、int64_tは8*10^18を表せる。ということで、Nを超えたら打ち切るようにすれば5*10^18とかにしかならんので大丈夫。あと、A,Bが正の数であることに注意する。

B - Values

何でもできそうな操作。全体の和は変わらないのと、連結でなかったら行き来できないこと（「連結」とは書いてないからね（「連結とは限らない」とは書いてないので解釈が正しいか頑張って確認する））。連結成分毎に和を求めて一致するか見ればいいのだが、楽な実装考えるのが本質という感じ。まずUnionFindで辺をつなげて、次に長さNの配列を用意し連結成分をrootの番号で区別してA_i-B_iを足していく。全部0ならYes。

C - Solutions

問題Pの出力は最大数なんだけど、高橋君と青木君のプログラムはそうと限らないというよくわからない設定。区間が交わる条件がこう書けることも知らなかった（あるいは忘れてた）。調子がいまいちでコンテスト時間も短いという中でこういうのをやっちゃいけない（こんがらがって無限に時間を消費してしまう）。それに気づいてDに行った。

Dを通して戻ってきた（Eは見た目がやばそうなのでやらなかった）。この時点で順位がいいので余裕がある。ぼんやりと考える。何もやりようがないので時間が解決してくれるのを待つという感じ。さて、高橋君のほうがいいプログラム書いてそうだなとは思ったが、本当にそうであるようだ。全体を覆うような区間1個と、互いに交わらないN-1個の区間を考えると、高橋君のプログラムなら1個残しに選べるが、青木君のだと1個しか選べない。半端に覆うようにすれば微調整もできそう。Mはどこまで大きくてもできるか考えると、交わる区間がない場合は差が付かないし、交わる区間があると高橋君でも全部は選べず青木君も1個は選べるので、0からN-2までだ。N-2が負にもなりえる制約なのでそこはちゃんと書く（0 <= m && m <= max(n - 2, 0) と書いた）。青木君が上回るケースも考える必要があるが、どうしてもできない（できないことが証明できるんだろうなという雰囲気）（弱めのサンプルからしても正しそうだ）（要するに未証明AC）。実装は、出力が1以上でなければならないことに注意して、基本的に等間隔で置きつつ最初の区間だけRをMに応じて伸ばす。M=0のときでも次の区間を覆うようにすると楽。

残り10分ちょっとしかないし、さすがに疲れたので、残りはほぼ休んでいた。

D - Powers

えらく簡単そうな見た目。Σが難しそうにも見えるが、要するに 1 <= L < R <= N となるL,Rについて全部足している。計算量も愚直でO(K*N^2)とかなので、まあ行けそうではある。K個出力させる意図がまだわかってないけど、とりあえずX=Kだけ計算しようとしてみる。(A_L+A_R)^Xを展開してにらむと和をまとめて計算できそうな雰囲気はある。L < Rの場合だけ足そうとしていたが、しばらくやってややこしいのでやめた。1 <= L,R <= N として、L = R のケースは普通に計算できそうだし、それを引いたら2で割るだけだ。展開したやつを0からKまでN*N個ずつまとめて足していく。ここで Σ( (A_i)^l ) を各lについて前計算しておくのがいい感じ。前計算がO(K*N)でできるのも面白い実装だった。各XについてO(X)の計算量なので全体でO(K*(K+N))。こういう計算量になるのかあという面白さがあった。

L = R のケースについて、2倍してX乗するから4倍と考えていてサンプルが合わなかった。いやあX=2のとこだけ合ってるとは思ってたんだよ。4倍ではなく2^X倍だった。無意識に2乗で考えてた。