ARC142

3完。最近のARCはAがつまらない。実力は測れるかもしれないが、何のためのARCだよ。BCは面白かった。レーティングとしては、早解き回で微減は実質勝ち。

A - Reverse and Minimize

K=240は0通り(最小値が240とするとそこから2回操作して24となり矛盾)(書いてみてこんなのに背理法要る?って思うしコンテスト中もかなり考えづらかった)。なのでまず10の倍数を処理する。次にKの反転を求め(to_string, reverse, stoll)、KとKの反転に0を付けていって(10倍していって)N以下の間カウントする。反転しても同じときは片方だけ。

提出してWA。332も0通りなのを見落としていた(最小値が332とするとそこからもう1回操作して233になって最小値でなくなり矛盾)。注意力コンテストなのはいいんだけど、これ解けて何の意味があるんですかと思う問題でされてもなあ。

B - Unbalanced Squares

角と辺は周囲のマスが奇数個なので考える必要がない。順番に並べると、ちょうど半々になってしまいまずい。それがダメとなると、確実に条件を満たせるような配置はかなり難しそうだ。左3個だけ小さくなるような配置を探っても、右だけでなく上下も大きくないといけないとなると規則性のある配置がなさそう。規則的に置くと半々になるし、規則的でないものはプログラムにできないしで困る。1行ずつ考えてみる。上の行から順に0 5 1 6 2 7 3 8 4としてみると、端以外のどの行から見ても上下どちらも小さいかどちらも大きいかのどちらかになっている。過半数である6個が自分より小さい(大きい)のだから条件を満たしている。さっきの数にNを掛けてそれをベースに横位置を足して1を足して出力。

C - Tree Queries

まず、0-indexedの頂点番号2個を渡すとその距離を返してくれる関数を書く(-1が来たらその関数内でちゃんとプログラムを終了させる)。頂点1を根とする図、番号が1でも2でもない頂点を根とする図などを描く。色々な距離を観察していると、最短経路上にある頂点からの距離の和が求める距離になると気づく(言われてみれば当たり前だが)。そういう頂点がある場合、単に(N-2)*2回質問して距離の和が最小のものが答えになる。問題は、最短経路上に他の頂点が存在しない場合(答えが1の場合)。そういうときは、頂点1までの距離と頂点2までの距離の差が常に1になる。しかし逆は成り立たない。N=3のときは質問に使える頂点が少ないので場合分けが要るかもしれない。N=4を考えると、パスグラフで3 1 2 4と並んでいるのと1 3 4 2となっているのを見分ける必要がある(1,2を含めた質問のみでは不可能)。そこで、(N-2)*2回の質問の結果を頂点毎にN-2個保存して距離の和で(それが同じなら頂点1との距離で)ソートする。最小値が偶数ならそれが答え。そうでないとき、N=3なら答えは1(少なくとも3は答えじゃない)。そうでないとき、質問の結果は2個以上あるので最初の2つを比較して、距離の和が異なるなら答えは1(距離の和は3以上なので答えが1でないなら少なくとも最短経路上に2個の頂点があるはず)。そうでないとき、その2頂点の距離を質問して1でないなら答えは1(ソートしてあるので最短経路上にあるなら隣同士)。そうでないときはその距離の和が答え(距離が1ということは辺で直接結ばれていて、答えが1とすると頂点1か頂点2と直接結ばれる2頂点が結ばれてると閉路になってしまう)。

提出してRE。ソートの比較部分を手癖でミスしていた。

DEFは全部読んだが、結局座っているだけに。自分は浅瀬でパチャパチャやってるだけという実感が得られて生きる気力をなくす。ベタな予想通りの崖になるの逆に意外だった。EFはこの見た目でクソ難しいらしいのすごい。

E - Pairing Wizards

(追記)解説AC。コンテスト中も一目フローだったが、ここまで難しいとは想像できなかった。本当に難しく、解説を見るたびに「するべきペア」を「かいりきベア」に空目していた。自明に必要な操作をしたあとの状況が、強い人には自明なのだろうけど自分にはわからなかった。a_xとa_yとb_xとb_yの位置関係のパターンが多すぎて整理できない。aはどちらもmin(b_x, b_y)以上なのだから、片方をmax(b_x, b_y)以上にすればそれでOKなのだけど、それが難しかった。a_xがb_xより小さいxとそうでないxに分けるのも、確かにそう分ければ二部グラフみたいになるんだけど、難しい。解説にあるようにXとYに分けて、X同士は最初の操作で存在しなくなり、Y同士は既に達成されているので考えなくていい。さて、操作の仕方にどんなバリエーションがあるかだが、Xの要素に対しては、何もしないか、a_xをb_xまで増やすかしかない。Yの要素は、相手のいくつかのxに対しb_xまで増やすとか。担当を入れ替えて既に達成されているケースをちゃんと除けば、b_xはa_yより大きい。yへの操作は回数が何通りも考えられるけど、操作回数99通りぶんの頂点を用意する。これで「少なくとも片方」が実現できているというのがよくわかんないけど。xがS側でyがY側というのはxからyへの辺で禁止されている(これは「少なくとも片方」が達成されておらず、それを禁止できている)。xがT側でyがS側なのはOK(両方がb_xに達している)。計算量が心配になるが、流量が少ないのだった。