ARC131

ABDの3完。依然としてあまりやる気は出ず。青に落ちて楽になった面もあるのかな。コンテスト中の動きは悪くなかったと思うが、多くの時間を「C全くわからん」とDの実装に費やしたので、楽しさはいまいちだったかな。双子ARCだから期待が高かったというのはあるけど。途中で「今回はDの実装で楽しもう」と決めてなんとか通せたのでその意味ではよかった。

A - Two Lucky Numbers

とっかかりがない問題はつらい。まあこれは簡単なので思いつく。Bを作ることを考えると、Bが奇数のケースが気になる(サンプルにない)。それは10倍すればいい(13ではなく130が与えられたと思えばいい)。9桁ずつ使える。8桁の数なら2倍しても10倍しても上の桁に影響を与えずに済むので、10^9*A+B*5を出力。

B - Grid Repainting 4

1234に囲まれた場所は5にするしかない。そう考えると5色ある意味が見えてくる。どこかを周囲にない色で塗ったとして、状況が悪化していない。つまり貪欲でいい。周囲にない色を一つ求めるところの実装が大変だった。楽な実装をコンテスト後に考えたいやつだ。

C - Zero XOR

全くわからない。初手で全体のXORと等しいものがあれば勝ち。XORが0になる空でない部分集合がないとき、Nの偶奇で勝敗が決まる。それは自明だが、そこから進まない。負けになるパターンを具体的に見てみる。ABCDの4枚のクッキーが残っているとして、Aを取ってBを取られて負けたとする。ABを除いた残りのXORが0ということ。この局面ではAかBを選ぶと負けになるが、上手く選べば回避できそうな気もする。ただ、何も見えない。3個以上で0になるパターンがあるから、その扱いがわからない(しかも、0になる部分集合同士が共通部分を持つこともある)。

解説を見た。順位表を見て、めちゃくちゃ通されているのは知っていた。だから、気づけば簡単な解法があるのだろうと思っていたが、まさか気づいても証明が難しいものがこんなに提出されているとは思わなかった。

D - AtArcher

ちょっとずつずらしながらスコアを差分計算できればよさそう。矢の位置が境界をまたいだときにスコアが変化するので、それがどのくらいの回数になるか。どこ視点で考えるかかなり難しい。結論としては、矢ではなく得点の境界視点でやる。N本の矢を1ずつD回ずらすことを考えると、M*2個の境界それぞれについてそこを通過するのは1回だけ(つまり間に合う)。細かいところを詰めておく。まず初期解として座標0に矢を置くものを考える。それより右に何本撃つか決めたら、間隔Dで(できるだけ詰めて)撃つとして損しない(どれを右に動かしても得しない)。左側も同様。また、左右均等に(Nが偶数で1あまる場合は左優先)したとき、そこから左にDだけ動かしても得しない(一番左の矢からDだけ左の位置へ一番右の矢を移動させたのと同じなので(移動させた矢は中心から遠くなっているので得点は増えない))。右にDだけ動かしても、Nが奇数のときは対称性から左に動かすのと同じで得しないし、Nが偶数のときは左右反転しただけになるので何もしないのと同じ。結局、そこから1ずつD回右へ動かしてスコアを計算すればいいことになる(他の全ての位置はそれらの中のどれかの劣化版になる)。整数でない位置に撃つのは考えなくていい(どこかが境界に当たるまで連続的に動かしてもスコアは変わらない)。

実装は気が遠くなるけど頑張ってやっていく。入力を受け取るときに、s_M=0も追加しておく。次に、M*2個の境界について左にある最も近い矢までの距離を求める。境界は得点の高い側に入ってる扱いなので、座標が負のところでは境界の位置を左に1ずらす。矢はN本しかないので相手が存在するかを確認する必要があり、左を見ているので左右対称な処理ではない(1WA)。距離と得られるスコアの差を構造体に入れて距離でソート。スコアの初期値をしゃくとり法で求め、距離が同じものをいっぺんに適用しスコアの最大値を更新していく。なんとこれでもう解けている(終わりが見えなくてもやってみるもんだ)。最初の提出はWAが出たが、細かい部分をちゃんと詰めてあったので、それでも間違っている可能性のある部分に絞って確認できた(15分かかってるけど)。