【バチャ】ARC143

2完遅解き。途中BCが全然解けなくて、バチャでこれはきつい。

A - Three Integers

ソートしていいのでソートしておく。操作を逆に考える。Cが最大として、AとCの差を作るためには1個目の操作がC-A回必要。AとCの差を付ける操作はちょうどその回数である必要がある(あ、逆にCを相対的に小さくする操作で打ち消すことができるの気づいてなかった(まあ2個目の操作が上位互換っぽい))。必要なだけ操作したら、あとは2個目の操作で合わせるだけ。既にターゲットより大きくなってたら-1。

ACしたものの考え方がかなり雑だった。解説見てもよくわかんねえな。

B - Counting Grids

「少なくとも一方」は扱いづらいので反対側を考える。縦に自分より小さい数しかなくて横に大きい数しかないようなマスが少なくとも一つ存在するのは何通りか。例えば左上隅のマスが何か特定の数でその条件を満たしているとすると、そういうのが何通りかはわかる(下に自分より小さい数の中からN-1個、右に自分より大きい数の中からN-1個、右下に他の数を(N-1)*(N-1)個)。包除みたくなりそうだけど、全然できそうにない。

しばらくして、同じ列や同じ行には存在しないことに気づく(Nが3以上を考えていて、横に大きいのも小さいのもあるマスが存在する(と思ってたけどそうじゃないのが存在しないこと言わないとダメでは何考えてたんだ))。C問題と交互に考えていたが、だいぶ経ってからそういうマスは高々1個しかないことに気づく。はー。他のマスから見ると、該当するマスの数より大きいのが上に小さいのが右にあるんだからそういう大小関係にならなすぎる。実装は、combから書き換えたpermを使わずcombと書いていたためなかなかサンプルが通らなかった。

C - Piles of Pebbles

XとYをペアにして、あまりを考える。勝ち側がペアを崩さないように行動しても勝ちというゲームであると信じて考えてみたが、(XがYより小さいとして)Xの立場で考えて2つの山でYXY(これで残り0個)と取られたらXXと取る山が生じてしまい無理なことに気づいた。そうなると複雑すぎて解ける気がしない。他の方針も思いつかない。

(追記)たまに考えていたが全くわからず、解説は間違っているように感じるし、動画解説も肝心なところを説明してくれないと思っていたが、誤読していた(山をちょうど1つ選ぶのだと思い込んでいた)。それなら解ける。XがYより大きいときがやや面倒。

DFは一応読んだ。