AtCoder Regular Contest 104
まえがき
ARCなんてめちゃめちゃ久しぶりですね...。前回のARCから2年も経ってるらしいですよ。
というか、2年前とperfが変わってなくてショック受けました。
コンテストリンク
A問題
一瞬迷いますが、落ち着いて(A+B)/2と(A-B)/2を出力すればおkです。
軽く腕ならしするつもりで[AC]していきましょう。
B問題
解法
Tに含まれる'A'と'T'、'C'と'G'の個数が同じの時に条件を満たします。
N≦5000なので、愚直にシミュレーションしても間に合います。
感想
制約がN≦200000でも、Zero-Sum Rangesみたいにすれば簡単に解けます。N≦5000なのはwriterさんの優しさでしょうか。
C問題
これすき
解法
ある人がk階上がるとき、その間に乗り降りする人も全員k階上がるので、結局「ある階からk-1階上の階までの人がみんなk階上がる」ってことになります。
すると、その集団で最初の人が乗る前と最後の人が降りる後にはエレベーターはすっからかんになります。
そうすると、
dp[i]=エレベーターがi階目を出発する時にすっからかんになりうるかどうか
というbool値を持つDPが書けて、状態O(N)遷移O(N)遷移時間O(N)でO(N^3)時間になって無事ACです。
感想
コンテスト中の自分は、「ある人Aがk階上がるとき、その間に乗る人もみんなk階上がるから、Aさんが乗る階からk-1階上の階までの人はみんなk階上がるよね」と、Aさんが乗ってる間に人が降りる可能性を無視して脳内考察してました。
どっちみち同じ結論になるのでまぁ結果オーライなんですが、危ない危ない...。
D問題
こっからACできなかった問題です。
解法
まず真っ先に常套テク、全体をxズラして平均を0にします。
ズラした後の数を正と負に分けると、それぞれのグループで選んだ数の和が同じになればいいので、
dp[i][S] = 1, 2, ... iのそれぞれをK個以下選んでSにする方法の個数
が求まればSをO(N^2K)通り全探索で解けます。
このDPは累積和を使って遷移してあげると状態O(N^3K)遷移O(1)でO(N^3K)時間で解けます。
感想
コンテスト中は、常套テク以降の方針を決めあぐねて5乗高速化とか6乗高速化とかしてました(もちろん軒並み失敗)。
正と負にグループ分けもちょっと考えましたが、それ以降が思いつかなくてEに移ってました。
E問題
解法
X_iを座圧すると全要素がN以下になるので、座圧後の数列は高々6^6=46656通りです。
X_iのLISを考える代わりに座圧後の列のLISを考えてもLISの長さは変わらないので、
Σ(X_iのLISの長さ) = Σ(座圧後のLISの長さ)×(座圧してその列になるX_iの個数)
と変形できます。
座圧後の数列を一つ固定すると、そのLISの長さは全探索で求まり、(座圧してその列になるX_iの個数)はDPで求まる...らしいです。[要出典]
感想
コンテスト中はDPではなく多項式をこねて考えてましたが、時間内に実装しきれませんでした。
僕が思いついた多項式解法は実質DP解法の下位互換みたいなものなので、完全に考察不足って感じでしたね...。
あとがき
C(600)は相性良くてすんなり解けたのに、D(700)とE(700)でだだ詰まりしてボコボコになりました。
Dを解き続けるのがいいムーブだったのかな......わからん
蛇足
コンテスト中はMegalovaniaの100分耐久をBGMにしてました。
100分耐久はいいぞ〜
