Cまで三完。良い成績とはいえないが、ARCで黄パフォを出せたのは久しぶり。
コンテスト後のツイート
B 各数字を0と1で塗り分け、数字が異なる間に仕切りを入れる。できるだけ同じ色にしたいので貪欲。
— titia (@titia_til) February 22, 2026
C (x,y,z)と(a,b,c)についてa>=x or b>=y or c>=zなら勝敗が付かないのでUnion-findでくっつける。くっつけたあと、(min(x,a),min(y,b),min(z,c))にして良い。x,y,zについてソートし大きい方から処理。
D - cresc.
解法ツイートを参考にAC。
Aの一つおきの配列が広義単調増加になることはコンテスト中に気付いていた。しかし、それだけだと重複があってダメ。
じゃあ、重複をなくすためどこか固定・場合分けすればいいのでは？ と考えるのが重要。
A[0]=0とした場合、A[1],A[3],...は全ての広義単調増加列を取りうる。
それ以外の場合、A[奇数]の最後の値がMにならなくてはダメ。なぜなら、A[偶数]を全てｰ1したものが同じ配列を作るから。
これで重複なく全て数えられているので、二項係数を使って計算できる。
初項を固定・場合分けする発想がもてれば決して難しくないし、重複をなくすためにどこか固定してみようと考えるのは自然。
今見ると難しくない気がする。
また、二項係数の何か（積か和か）になりそうなことはコンテスト中から見当がついていたし、実験コードも書いていた。
それで解けないのは、こういう二項係数を使う数え上げに苦手意識があるのかなぁ、と思ってしまう……。
E - CNOT Party
悩んだが自力でAC。
・最初にできるだけ0→1にする
のは最適そう。なぜなら、逆の手順をやれば1を0に戻せるので。
コンテスト中は、その後、今作ったトポロジカルソート順の逆順？ などと考えてしまいダメだった。
この後、
・1→0にする部分は別の問題
と捉えると分かりやすい。こう思いつくのが重要だった。
すると、B[i]=1のものは最後まで残ると分かるので、そこを根としたトポロジカルソートの逆順を考えれば良い。
ただし。x_i=y_iなるものがあればそれも起点になることに注意。
その順に1→0に戻していけば答えになる。
F - Scapus
自力AC。
直径は明らかに良いパス。
そこから考えると、直径上に通らなくてはいけない点が何点かあり、それを含む全てのパスが良いパスになると分かる。
あとは通らなくてはいけない点が一点になるかパスになるかで場合分け。
パスの場合は、二つの端点から距離xでいける点の個数は何個あるかを調べ、それらを足し合わせれば良い。これが畳み込みの形になり、FFTが必要になったのにはびっくりした。
一点の場合も同じなのだが、畳み込みの際の配列の長さを意識しないと計算量が落ちない。そこを気を付けて実装したらACできた。
実装は面倒だが、割合素直な発想で解ける問題だった。
0 件のコメント:
コメントを投稿