ARC137

ABDの3完。久しぶりにあったまった。最近はレート下がってて気分的にもどうでもいい感じだったので、1時間経ってBのみ1完でも焦りはなかった。前回の冷えたABCと同じく、コンテスト中に楽しむ/成長する(もうちょっとうさんくさくない表現ないか)ことに重きを置いていた。

A - Coprime Pair

全くわからなくて開始2分で飛ばした。Bを通してもわからず、Dを通してから戻ってきた。順位表を見ると俺以外全員ACしてる。

愚直を書いて50以下の全パターンで実験すると、やはり両端から離れた解はない。もっと大きい数で試しても一瞬で見つかる(y-xの最大とR-Lの差が一定以下になるというなら、幅の広い順に探索すればいい(こうすれば実行時間と探索範囲のトレードオフは生じない))。そうなる理由とかはやはり全くわからないけど、これが通れば順位が大きく上がるので提出してAC。

解説を見ると素数が頻繁に現れることを使っていてそりゃそうだった。GCDから素数を思いつかない人だったね。

B - Count 1's

サンプルが意味不明で問題文を何回も読み直して、スコアの最大ではなくスコアが何通りかを求めるのだと気づいた。極端なケースで少し考えてから、累積和を思いつく(0は-1にする)。その最大と最小を求めればいい(片端の位置を1ずらして高々1しか変化しないので中間は全部作れる)と思ったが、サンプル合わないし普通に間違ってた落ち着け。累積和から好きな区間を選んでそれが最初のスコアとの差になるから、最大値と最小値を更新しながらそれらとの差の最大と最小を求めればいい。低難度帯の良問という感じだが、最初に色々考えて引きずっていたせいか、落ち着いて考える/実装することができなかった。

C - Distinct Numbers

けっこうしっかり考えたが、わからなかった。非負整数の位置にN個のピンが打ってあって、それを移動させるゲームと捉える。最大と2番目の間に動かすのとそれ以外で違いそうだけど、うーん。

D - Prefix XORs

これはビット毎に考えていい。累積xorをM回とるということ。どういう操作になっているか観察すると、各kに対する各数の重みが(Aの末尾から見て)1 1 1 1だったり1 2 3 4だったり1 3 6 10だったり。実際はこの偶奇だけでいいのでなんか法則性ないかなとか。三角数の次がn*(n+1)*(n+2)/6になるか確信がなかったので、三角数でググりWikipediaで一般化が書いてないか見る。すると一般化が書いてあって、パスカルの三角形もあって確かに累積和の寄与が現れている。その偶奇ということで、ようやくシェルピンスキーのギャスケットに辿り着く。法則性の正体はこれかあ。その構造から、FFTみを感じる。分割統治できそうだ(図を観察するとM列のうち半分は寄与が共通してたり)。わかりやすくするため、NもMもmax(N, M)を2冪に切り上げたものとする(高々2^20、Aが増えたぶんは0で埋める)。Aはreverseして受け取る(先頭がA_N)。ループでやろうと思ったけどできなかったので再帰。ポインタと長さを渡す。長さが1ならそのまま返す。2以上ならMの前半分を再帰呼び出しで処理し後半にコピー、Mの前半部分はNの後半部分も処理する必要があるので再帰呼び出ししてそれを足す(Mの後半部分は0)。半分の長さで2回呼び出している。これビット毎にやる必要ないんじゃないかとか再帰内でvectorで確保してるの遅そうとか思ったけど、短時間でミスなく改善できるとは思えず、4秒あるし通ってくれと提出したら1262msで通った。TLの半分以下だしまあ合格。実際はフラクタル部分の思考/実装にめちゃくちゃ時間をかけている。