ARC Div.2にratedで参加していました。ARC 198で緑になったのでratedではなくなりました。

ARC rated初参加だった。A,B 2完を42:34ノーペナで、初の青パフォである。

コードはこちら

両者の全カードの和は $S = N(N+1)$ である。最後の1ターンに注目する。それ以外は勝敗が確定した状態から後ろに考えれば同じである。

• $S mod M = 0$ なら、Bobは最後の一枚を引かされるのでAliceの勝ちである
• $S mod M > N$ なら、Aliceは最後に $1..N < M$ を出し、Bobは最後の一枚を引かされるのでAliceの勝ちである
• それ以外 $0 < S mod M \leq N$ なら、Bobは最後に $1..N$ を出せるが、その前にカード出すAliceは場のカードの和が $M$ の倍数にならざるを得ない。よってBobの勝ちである。

コンテスト中の思考の過程を追う。

• Grundy数かと思ったら、このゲームは可能手がすごく多い。
• $1..N < M$ より、場のカードの和が $M$ の倍数になる=負けるような手をほぼ確実に回避できる。公式解説を読んで再認識したが、カードはそれぞれ異なるので手札が2枚以上あれば確実に負けを回避できる。
• 最後の1ターンは出すカードに選択肢がない時である。ここで勝敗が決まるだろう。
• 後手が詰む一つの状況は、すべてのカードが出切ったときで、 $N(N+1) mod M = 0$ である。
• 後手が最後に出すカードを $S \in 1..N$ とする。 $N(N+1) - S mod M = 0$ なら後手がカードを出す前に、先手は場のカードの和が $M$ の倍数にならざるを得ない。条件を言い換えると、 $N(N+1) mod M \in 1..N$ である。
• 同様の議論から、上記でなければ、先手は負けず後手が負ける。

上記をまとめると、 $1 \leq N(N+1) mod M \leq N$ なら答えは Bob 、そうでなければ Alice が 答え である。

今回は理詰めで提出したが、ゲーム木を構築して解を推測することもできる。

// 0 means the first player wins
Num visit_dfs(std::vector<Set>& hands, Num turn, Num accum, Num m) {
    const auto other = 1 - turn;
    if (hands.at(turn).empty()) {
        return other;
    }

    if (hands.at(turn).size() == 1) {
        const auto s = accum + *hands.at(turn).begin();
        return ((s % m) == 0) ? other : turn;
    }

    Vec vs;
    for(const auto& x : hands.at(turn)) {
        vs.push_back(x);
    }

    for(const auto& x : vs) {
        const auto s = accum + x;
        if ((s % m) == 0) {
            continue;
        }

        hands.at(turn).erase(x);
        const auto result = visit_dfs(hands, other, s, m);
        hands.at(turn).insert(x);

        if (turn == result) {
            return turn;
        }
    }

    return other;
}

void solve(std::istream& is, std::ostream& os) {
    const std::vector<std::string> players {"Alice", "Bob"};

    for(Num m{2}; m<=10; ++m) {
        for(Num n{1}; n<m; ++n) {
            std::vector<Set> hands(2);
            Num total = n * (n+1);

            for(Num i{0}; i<2; ++i) {
                for(Num j{1}; j<=n; ++j) {
                    hands.at(i).insert(j);
                }
            }

            const auto r = total % m;
            const auto r_in = (1 <= r) && (r <= n);
            os << "m=" << m << ", n=" << n <<
                ", mod=" << r << ":" << ", 1<=r<=n " <<
                players.at(r_in) << " " <<
                players.at(visit_dfs(hands, 0, 0, m)) << "\n";
        }
    }
}

コードはこちら

ゼロサムなので、全要素が平均値付近にそろっている状況を作れる。つまり全要素の差を高々1にする。具体的には、 $A$ の総和が $S$ として、少なくとも $V = \lfloor S / N \rfloor$ 、余り $R = S mod N$ を後ろから1ずつつけるので、 $B = (A_1, .., A_{N-R} = V, A_{N-R+1} .. A_N = V + 1)$ にできる。

後は操作に矛盾がないことを確かめる。 $i=1..N$ について、 $B_i - A_i$ の累積和が負になるような操作はできないので、そのような操作を見つけたら No 、見つからなければ Yes が答えである。

この方法は公式解説1と同じである。ARC早解きで勝てるなら不変量だろうと思っていたら、強運が向いた。のちに、188-Bを不変量だと気づかずに0完するのだが。

コードはこちら

難易度が高すぎて参加しなかった。何時間経っても解くことができず、トポロジカルソートの数え上げを効率よくやる方法は無いかと探したら、この問題の公式解説にたどり着いてしまった。

前提条件として、部分木 $v$ に直接 $k$ 個の子頂点がつながり、子頂点の先には子頂点自身を含めて頂点が $(u_1, u_2, ... u_k)$ 個あるとする。このとき、ある子頂点とその先にある頂点を区別しないと木、頂点の並びが何通りあるか数える。

$S = \sum u$ として、頂点 $1$ の先にある葉の混ぜ方は $S \choose u_1$ 通りある。頂点 $2$ の先にある葉の混ぜ方は頂点 $1$ 以外を考え ${S-u_1} \choose u_2$ 通りある。同様に子 $i$ は ${S - \sum_{j=1}^{i-1}} \choose u_i$ 通りある。はずなのだが、1答えが合わない。これを頂点について再帰的に求めると、すべての頂点の組み合わせが何通りか得られる。ここがわからないので、頂点の入出次数に着目しても解けなかった。

この前提で、公式解説にある通り、頂点間の関係は木構造にできる。大きな番号の頂点から順に走査し、小さな番号の頂点を根とする部分木の頂点数を求める。一通り走査したら、小さな番号から大きな番号の頂点に向かって、それぞれの頂点について部分木の組み合わせを求めて掛けると木全体の頂点の並び方が何通りか求まる。

なお $i=1..n$ について階乗をあらかじめ求めておくと、 ${n \choose k} = n!/(n-k)!k!$ は高速に求まる。

ARC rated 2回目は、120分掛けて一問も解けなかった。前回のように上手くはいかない。

コードはこちら

解けるとすればA問題しかなさそうというのは、問題文からも順位表からも分かったので、ひたすら問題に集中して悩みはなかった。

手番の途中で広義単調増加になったら即刻打ち切ってよい。 $N \leq 50$ なので毎回広義単調増加かどうか調べても大したコストにはならない。

隣り合う数 $A_i, A_{i+1}$ を2回入れ替えると、両方とも $K$ 増やせる。これを利用することで最後の数 $A_N$ 以外は広義単調増加にできる。ここまではすぐ思いつくのだが、問題は $A_N$ をどうするかである。 $A_N$ を手前に持ってくると $K$ 増えて堂々巡りになる、という状況以外 No はなさそうだが証明できない。

翌朝気が付いたことに、 $A_i, A_{i+1}, A_{i+2}$ ついて、 $(A_i, A_{i+1})$ , $(A_{i+1}, A_{i+2})$ をそれぞれ $2M$ 回入れ替えると、 $A_{i+1}$ を $A_{i}, A_{i+2}$ より $KM$ 多くできる。これによって $A_2..A_{N-1}$ にある数を飛びぬけた最大値にできる(このために $N > 2$ である必要がある)。このことはコンテスト中に気が付いたが、活用方法が分からなかった。

ここまでくれば解法が分かる。まず入力が広義単調増加なら何もしない。 $N=2$ なら1回交換して広義単調増加なら答え、そうでなければ No である。

$N > 2$ のときは、 $(A_{N-2}, A_{N-1})$ , $(A_{N-1}, A_N)$ を $4 \times (5000 > 2500 \geq NK)$ 回入れ替えて増やす。次に $A_{N-1}, A_N$ を入れ替える。こうすると元々の $A_{N-1}$ が $A_N$ になり、他の数を十分たくさん足しても移動後の $A_N$ を超えないようになる。後は $i=1..(N-2)$ について、 $A_i \leq A_{i+1}$ なら何もせず、そうでなければ $(A_{i+1}, A_{i+2})$ を $A_i \leq A_{i+1}$ になるまで偶数回入れ替えて $K$ ずつ増やす。最初に思いたときは $A_2$ をバブルソートの要領で $A_N$ に 移動した が、そこまで手間を掛ける必要はない。

コンテスト後に $N=2$ という記述がちらっと見えたが、自力ACとしておく。 $N=2$ のときの固定出力 Yes 1 1 を間違えていたが、最後の2 WA 1 msec だと自分で気が付いた。 $N > 2$ なら常に解があると予想出来るが、そのことを具体的な解法に落とし込めなかった。半分手がかりが見えているこの問題は獲りたかった。

数列が広義単調増加かどうかは、 std::ranges::is_sorted で調べられる。返り値は狭義単調増加ではなく広義単調増加(非減少)かどうかである。

ARC rated 3回目、B問題 1完だった。コンテスト中に青diffをACしたのは初めて、26:17ノーペナで初の黄パフォである。最大瞬間18位から逃げ切った。A問題よりB問題の得点が高いことに助けられた。A問題は90分掛けたが全く分からなかった。

コードはこちら

DPだと思ったが、それ以上のことは分からなかった。

よい文字列の定義は、 A,B,C それぞれの出現回数の偶奇がそろっているもの、と言い換えられる。これを8状態として区別できる。公式解説にある通り偶奇が反転している状態を同一視して4状態に減らすことができる、と言うことに気が付かなかった。

ある状態に挟まれた文字列はよい文字列である。これは整数列の累積和について、 $modM$ が等しい区間の和つまり累積和の差は $modM = 0$ であることと似ている。このことに気がつかなかった。ここまで分かれば、状態 $i=0..3$ が $C_i$ 個のときに、 $C_i(C_i - 1)/2$ 通りの文字列を取れるのでこれを状態について組み合わせると、よい文字列の数になる。この先は公式解説にある通り多重ループを書いて数える。

公式解説にある状態遷移が巧妙である。 $state=1$ は $A$ を反転させる、 $state=2$ は $B$ を反転させる、 $state=3$ は $C$ を反転する代わりに $A,B$ を反転すると解釈できる。それ以外に何も反転していない、という状態 $state=0$ がある。

コードはこちら

丁寧に場合分けする。

$N = 2$ なら互いに初期位置を取って Yes である。

$N > 2$ が偶数かつ互いに対称 $K = N/2$ なら、互いに初期位置を取ったらもうできることがないので No である。

$N$ が偶数の場合、 $H = N/2$ と置く。 $K < H$ なら $K = N - K$ と読み替える(左右対称にしただけなので答えは変わらない)。Aliceの1回目は自分と対称の位置 $H$ 、Bobの1回目は直前に塗った頂点と対称の位置 $K + (K - H) = 2K - H$ 、Aliceの2回目は直前に塗った頂点と対称の位置 $N - (2K - H) = 2K - 3H$ を塗る(符号を反転しても答えは変わらない)。以後は原点を読み替えて同じことを繰り返す。よって $(2K-H,N)$ が互いに素かつ $(2K-3H,N)$ も互いに素なら、この繰り返しで全ての頂点を塗ることができるので Yes である。そうでなければ塗れない頂点があるので No である。

$N$ が奇数の場合、 $H = \lfloor N/2 \rfloor$ と置く。 $K > H$ なら $K = N - K$ と読み替える。Alice, Bobの順番に $0, 2K, 4K, ...$ と塗る。 $(2K,N)$ が互いに素なら、この繰り返しで全頂点を塗ることができる。そうでなければ塗れない頂点がある。

以上で答えを網羅できた。公式解説と、 $N$ が偶数の場合の式は異なるが、同じことを言っているはずである。ユークリッドの互除法がそうであるように、2変数の最大公約数は互いの数を足し引きしても変わらないので、きれいな形に変形しなくてもそのままコードにすればACする。

コンテスト中の思考の過程を追う。

• $N$ と何かが互いに素なら、同じことを繰り返してすべての頂点を塗れる。そうでなければ塗り残しがある。この何かを求めればいいと直観的にすぐわかる。
• マルチテストケースなので、エッジケースを間違えると大量のWAが返ってきて、根本的に解法が間違っているのかそうでないのか分からない。よって最初にエッジケースを挙げて、それ以外の場合分けを丁寧に行う。
• 題意を理解するために手を動かす。 $N = 2$ が特殊だと分かる。互いに対称な位置なら詰むのも分かる。
• $N$ が偶数なら初手は自分の位置か対称な位置しかないので、とりあえず対称な位置に打って、直前に打った点の対称な位置に打つのを繰り返す。 $N$ が奇数の場合も同様に繰り返す。以後原点を読み替えるだけなので周期性があり、これで全頂点を塗れるだろう。
• $gcd(N,x) = gcd(N,N-x)$ なので、 $K$ を $N - K$ に読み替えてもよい。これで場合分けが減る。符号を入れ替えても最大公約数は変わらないので、絶対値を取って場合分けを減らす。
• これ以上場合分けは無いので提出したらACした。最大瞬間順位から想像するに、この時点で多くの方はA問題を解いている途中で、B問題を最初に取り組んだ方は少なかったのかもしれない。

コードはこちら

Div.2 になって400点問題が出たのに、120分掛けて一問も解けなかった。ARCはそれほど甘くない。

解になりえないものを除外する。両端は変えられないので $A_1 = 1$ または $A_N = N mod 2$ が成立しなければ答えは0通りである。

リバーシ操作は、両隣が異なる場所 $[L,R]$ を2か所選んで、両隣をそろえることに相当する。ただしこの2か所の間 $[L+1,R-1]$ はそろっていなければならない。ここで $A$ をランレングス圧縮する。

入力 1010... では、幅 $W$ のマス列で連続する両隣が異なる場所は $W-1$ 箇所である。あるラン $[L,R]$ の長さ $W = R - L + 1$ が偶数の場合を考える。 $W$ が偶数なら $W-1$ は奇数である。リバーシ操作は両隣が異なる場所を偶数個しか変えられないので、両隣が異なる場所を0個にするつまりランをそろえることはできない。よって偶数長のランがあれば答えは0通りである。

以下ラン長はすべて奇数とする。ラン長が1のランは何も操作しないので無視する。ラン $i$ をそろえるための操作回数 $C_i$ は必ず $C_i = (W_i - 1) / 2$ 回である。なぜならリバーシ操作によって、両隣が異なる場所は必ず2か所減るので操作回数は操作順序に依らず一定だからである。あるランをそろえる操作列の数 $P_i$ は実験すると $P_i = \prod_{j=1}^{C_i} (2j-1)$ 回とわかる。この証明は後で与える。

異なるランの操作について順列組み合わせを考える。 $S = \sum_i C_i$ とする。どのランについて操作するかの順列組み合わせは、ランを区別しない順列においてラン内の操作順序を無視することに等しいので、 $S! / \prod_i C_i!$ である。これにランの選び方 $\prod_i P_i$ を掛けたものが答えである。

$C$ を固定したときに $P_c = \prod_{j=1}^{C} (2j-1)$ となることの証明を与える。 $C = 1$ のとき $P_1 = 1$ になることは、 101 の真ん中を 1 で塗るリバーシ操作しかないので分かる( 010 を反転しても同じなので、以後 0 と 1 を入れ替えた場合は考えない)。 $C + 1$ について考える。両端を除いたマスの数は $2(C + 1) - 1$ 個である。最初に $2(C + 1) - 1$ マスのうち一つを選んでリバーシ操作し、残りの操作回数はそれぞれ $P_c$ 通りなので $P_{c+1} = (2(C_i + 1) - 1) \prod_{j=1}^{C_i} (2j-1) = \prod_{j=1}^{C_i+1} (2j-1)$ である。よって帰納的に示された。

公式解説は上記と同じことを言っている。特に、あるランの操作回数 $P_i$ についてさらっと書いているが、実験するまでこれが分からなかった。マスを反転して $A$ と同じにすることと、マスを反転して $A$ と逆にすることは実は対称なのだが、下記に書くように両者を区別したのが敗因である。

コンテスト中の思考の過程を追う。上記に書いた $P_i$ 以外は合っていたので実に惜しかった。

解になりえないものを除外する。両端は変えられないので $A_i = 1$ または $A_N = N mod 2$ が成立しなければ答えは0通りである。

$A$ をランレングス圧縮する。ラン $[l,r]$ のラン長 $W = r - l + 1$ は奇数でなければならない。そうでないと最終形の操作を実現できない。偶数長のランがあったら答えは0通りである。

ランの要素をすべてそろえることを考える。両端はそろっているので、両端の間に $W - 2$ 個の要素を変える。 $H = (W - 1) / 2$ 個要素は反転しており、 $K = W - 2 - H$ 個の要素は反転していない。

反転方法は二通りある。一つは $H$ 個のマスを順に反転させる。この方法は $H!$ 個ある。もう一つは $K$ 個のマスを反転し、残りを反転させる。 $W-2$ 個の要素について $DP[W-2]$ 通りあるなら、 $K \times DP[W-2]$ 通りある。ここが完全に間違っていて、間違いを直せないままコンテストが終わってしまった。入力例だけは通ってしまうので、間違いに気が付かなかった。

あるラン $i$ について反転操作を $H_i$ 回行う。すべてのランについては $S = \sum H_i$ 回の操作を行うので、異なるランの操作の組み合わせは、 $S! / \prod H_i!$ 通りである。

と思ったのだが、入力例以外が答えが全然合わない。実験コードを15分で書けば分かったことである。しかしそれ以外のことに気を取られ過ぎて、実験コードを書こうと思わなかったのは反省点である。以下にある通り、 10... を 11... に変える方法を総当たりで求める実験コードはそれほど複雑ではない。

using Pattern = std::bitset<32>;
using Seq = std::vector<std::pair<Num,Num>>;

Num visit_dfs(Pattern current, const Pattern goal, Num width, Seq& seq) {
    Num total {0};
    if (current == goal) {
        for(const auto& [l,r] : seq) {
            std::cout << l << ":" << r << " ";
        }
        std::cout << "\n";
        return 1;
    }

    for(Num left{0}; (left+1)<width; ++left) {
        bool stop {false};
        for(Num right{left+1}; !stop && right<width; ++right) {
            if (current[left] == current[right]) {
                stop = true;
                const auto s = right - left;
                if (s <= 1) {
                    break;
                }

                auto next = current;
                for(Num i{left+1}; i<right; ++i) {
                    next[i] = current[left];
                }

                if (current != next) {
                    seq.push_back(std::make_pair(left+1, right+1));
                    total += visit_dfs(next, goal, width, seq);
                    seq.pop_back();
                }
            }
        }
    }

    return total;
}

void full_search(std::istream& is, std::ostream& os) {
    Num width = 5;
    is >> width;

    Pattern current(0);
    for(Num i{0}; i<width; i+=2) {
        current.set(i);
    }

    Pattern goal(0);
    for(Num i{0}; i<width; ++i) {
        goal.set(i);
    }

    Seq seq;
    os << visit_dfs(current, goal, width, seq) << "\n";
}

int main(void) {
    full_search(std::cin, std::cout);
    return 0;
}

コードはこちら

コンテスト数日後に解けた。Diff 1889 の問題を解けたのは、次回に期待が持てる。コンテスト中は15分掛けて分からなかったので見限ったが、分かってしまえば実装は簡単である。

この問題の要点は、コマではなくコマの間隔を移動できることである。コマの間隔を移動を左から右に移動できることを示す。右から左に移動するのは左右対称にするだけなのでやはり可能である。

左の端のコマが原点 $X_1^0 = 0$ になるように、コマの座標から $X_0$ を引いておき、 $D_i^0 = X_{i+1}^0 - X_i^0$ とする。

どのコマがどこに移動したかは気にしない。元のコマがどこにあったかを気にせず、初期配置から $k$ 回操作後のコマを左から( $X$ の昇順に) $X_1^k, ... X_N^k$ と呼び、ここから導出したコマの間隔を $D_1^k, ... D_{N-1}^k$ とする。 $X_2^0, X_3^0$ に対して操作することは、 $D_1^0, D_2^0, D_3^0$ を $D_1^1=D_3^0, D_2^1=D_2^0, D_3^1=D_1^0$ に変えることである。

$X_2^1, X_3^1$ に対して操作することは元に戻す、 $D_1^1, D_2^1, D_3^1$ を $D_1^2=D_1^0, D_2^2=D_2^0, D_3^2=D_3^0$ に変えることである。 $X_4^1, X_5^1$ に対して操作することは、 $D_3^1, D_4^1, D_5^1$ を $D_3^2=D_5^1, D_4^2=D_4^1=D_4^0, D_5^2=D_3^1=D_1^0$ に変えることである。

ここから分かるのは操作1回で、 $D_j$ を $D_{j-2}$ と $D_{j+2}$ のどちらか一方と入れ替える、ということである。これはバブルソートの手順そのものである。よって $D_j^0$ において $j$ が偶数番の間隔の集合を任意の順番に並び替えることができる。 $j$ が奇数番の間隔の集合も同様である。

答えを最小にするには、間隔が少ないものほど左側に寄せればよい(間隔が大きいものが左側にあるなら、右にある間隔と入れ替えると答えを小さくできるので)。よって偶数番 $D_{2j}^0$ 、奇数番 $D_{2j+1}^0$ それぞれを昇順にソートする。

ソート後の $D^0$ からコマの位置 $X^{'}$ を累積和で求め、さらに $X^{'}$ の累積和を求めると答えになる。最初に原点の分だけ $NX_1$ を引いたので忘れずに足す。

この方法は公式解説と同じである。上記が不変量だと後で知った。不変量を見抜けばコンテストで圧勝できるが、不変量を見抜くのはこの通り難しい。

コードはこちら

コンテスト中にはちらっと見たが解けそうも無いと諦め、その後4日ほど考えたが、全く答えが分からなかった。スライムは倍化することが計算量を決めるという発想に至らなかった。

スライムを大きくするのではなく、これ以上大きくならないという壁に注目するのは正しかった。しかし計算量の見積もりができず $O(N^2log(N))$ と思ってから先に進まなかった。この問題は ABC 368-G と同じ発想である。ただし ABC 368-G には答えが $10^{18}$ 以下と太字で示す親切さがあり、この問題はそう書いていないので見抜けなければならない。

この問題の2が次のABC 384に出た。こちらは緑diffのとっつきやすい問題だが、ペナルティを出してしまった。

コードはこちら

Div.1 はレーティングが足りないのでunrated確定である。A問題は解けると思ったが結局解けなかった。いろいろと足りない。

翌朝思いついた解法は、公式解説とほぼ同じだった。しかし解法の詰めが甘いというより、実装方法が分からなかった。以下半閉区間で考える。

ある範囲 $[L,R)$ が $[1,N+1)$ なら、その範囲に操作1を適用してコスト1で達成できる。

ある2つの範囲 $S1 = [L1,R1), S2 = [L2,R2)$ があるとき、これらを使ってコスト2で達成できるか考える。

• $S1 \cap S2 = \emptyset$ なら、両範囲に操作2を適用して達成できる
• $S1 \supset S2$ なら、 $S1$ に操作1、 $S2$ に操作2を適用して達成できる
• $S1 \cup S2 = [1,N]$ なら、両範囲に操作1を適用して達成できる。これが抜けていた。というより実装が合わなくて力尽きた。
• 上記以外で $M \leq 2$ なら解無しである

上記以外の場合、 $M \geq 3$ なら必ずコスト3で達成できる。範囲を $S=[L,R]$ の昇順に並べて $S_1 \leq S_2 \leq ... \leq S_M$ とする。このとき $S_1$ と $S_M$ に操作1、 $S_2$ に操作2を適用すると達成できる。

実装方法がさっぱりわからず、他の方のコードを読んでようやく理解した。コスト2のときの実装方法は以下の通りである。

• $S1 \cap S2 = \emptyset$ は、 $min(R_i) \leq max(L_j)$ を満たす $(i,j)$ を選ぶ。これは $min(R)$, $max(L)$ それぞれを 添え字 $1..N$ について更新する。
• $S1 \supset S2$ の求め方が分からなかった。セグメント木を使ったらどうしても答えが合わない。他の方のコードを参考に、 $S$ を $[L,R)$ の昇順にソートし、 $max(R)$ を更新し、 $R_i \leq max(R)$ つまり右端が逆転したら条件を満たす(左端 $L$ は非減少なので)。等号を含む(同一範囲が二つあれば、正転と反転で $[1,N]$ を覆える)。
• $S1 \cup S2 = [1,N]$ は、 $[1,R_i)$, $[L_j,N+1)$ だけ注目する。 $1,N+1$ を固定して $max(R)$, $min(L)$ を求め、 $max(R_i) \leq min(L_j)$ なら条件を満たす。これはこれであっているが、コスト3以下は必ず達成できると気が付かないとこの処理を思いつかない。

コンテスト中には間に合わなかったが、翌朝だいたい思いついたのだから自力ACしたかった。水diffが解けないとARC Div. 2も厳しい。

以下はコンテスト中に思いついた解法である。まるっきり的外れだったようだ。

操作1,2を円環上の操作として表現する。操作1は $[L,R]$ を1にし、操作2は $[0,L),[R,N)$ を1にする。ある一連の操作で解があるなら、全部の操作について操作1,2を互いに入れ替えても解になる。

円環の $[0,N)$ を原点 $0$ を中心として、時計回り( $0$ から増える方)に伸ばすのと、反時計回り( $N$ から減らす方)に伸ばすのを繰り返し、全域を覆うことができればその操作が答えである。全域を覆うことができないなら解無しなので -1 を出力する。操作の都合上、 $[L,R]$ に $N$ だけ下駄を履かせて、 $N \leq R \leq 2N$ にする。

各クエリに対応する操作1,2をそれぞれ用意する。Greedyな方法として、 $l=0..(N-1)$ に対して、 $l$ を含む区間 $[L,R]$ で、時計回りに $R$ が最も大きく伸びる、 $R$ が同じなら $L$ が小さい(時計回りに $L$ が最も大きく伸びる)区間を選ぶ。これはセグメント木で求まる。使うかどうか検討した操作は、実際に使ったかどうかは別として取り除いてセグメント木を更新する。これは $L$ を添え字とした操作を std::set で持ち、その最大要素をセグメント木に載せなおせばよい。

セグメント木に、 $L$ から始まり $R$ が最も長い区間を載せると、セグメント木の区間max $[0,L]$ はこのような区間を選ぶ。まだ使っていないクエリで、時計回り側で覆った最大の添え字 $N \leq left$ と、反時計回り側で覆った最大の添え字 $right \leq 2N$ を更新する。最終的に $left < right$ なら解無し、そうでなければそれまでの操作が答えである。

この方法は半分くらいACし、残りがWAになる。おそらくコスト3以下を達成できていない。実装をやり直すと少し きれいに なるがそれでも長い。

久しぶりのrated参加。A,B 2完を103:12の7ペナで、なんとか0完を逃れた。辛うじて水パフォを確保した。問題文をぱっと見ただけで、A,B問題は解かなければならない難易度(Aは茶diff, Bは緑diffを想定)、C,D,E問題は解けないと判断した。A,B問題はどのみち解かなければならないのでA問題から着手したが、結果的にB問題から解いた方がよかった。

コードはこちら

Greedyだとわかったが考察に手間取り、46分掛けて提出したら1 WAが返ってきて62分掛かった。

基本的に、 $S$ の先頭から順に、 $T$ の大きな数字で置き換える。まず $T$ を降順に並べ替えた $U$ を作り、 $U$ の先頭から順に $S$ を置き換え可能かどうか試す。併せて、 $T$ における $i=1..9$ の出現位置 $P[i]$ を数えておく。 $P[1]$ は1の全出現位置を昇順に並べたものである。具体的には以下の尺取り法を行う。0-based indexingとする。 $T$ の最後の置き換え位置 $L$ を $L=-1$ で初期化する。

• $S$ の置き換え先位置 $to$ を0とする
• $U$ の置き換え元位置 $from$ を0とする
• $S[to] < U[from]$ なら、 $S[to]$ を $T[from]$ で置き換える。
  • $T$ の最後の置き換え位置 $L$ を $max(L,P[U[from]])$ で更新する。 $to$ と $from$ をそれぞれ1つ増やす。
  • $S$ に $T[from]$ を書き込んだことを $R[T[from]]$ に記録する
• $S[to] \geq T[from]$ なら、 $S[to]$ を $T[from]$ で置き換えると損するので置き換えない。 $to$ を1つ増やす。 $S$ に $S[to]$ を書き込んだことを $R[S[to]]$ に記録する
• これを $to < N \land from < M$ である限り繰り返す

$q = M$ つまり $U$ のすべての文字を置き換えたら、その時の $S$ が答えである。そうではなく、 $U$ の文字が余ったときの処理を考える。

$L = -1$ なら $T$ の文字で $S$ をどう置き換えても損するとわかる。このときは $T$ の最後の文字で $S$ の最後の文字に置き換えたものが答えである。ここに気が付くのが遅かった。

$L \geq 0$ なら $T[L..(M-1)]$ の文字で、 $S$ にすでに書き込んだ数字があれば $S$ の数字を上書きし(要するに何もしなかったことと同じ)、そうでない数字が見つかったら $D$ とする。最後の $D$ で $S$ の最後の文字に置き換えたものが答えである。

1 WA対策として思いつく限りのことを入れたので余分なコードがあるかもしれない。 $M = 1$ なら、 $S[i=0..(N-1)] < T[0]$ を満たす最小の $i$ があれば $S[i]$ を $T[0]$ で置き換え、そのような $i$ がなければ $S$ の末尾を $T[0]$ で置き換える。

$T$ の最後の要素を使わざるを得ない状況を整理するのに手こずった。もっとすっきりした答えがありそうだが、コンテスト中に提出した解法はこの通りである。改めて実装すると、少し きれいな コードになる。公式解説は $U$ ではなく数字の出現頻度だけを持ち、本質的には同じことをもっと簡潔に実行している。

コンテスト中の思考の過程を追う。使うと損する数字は $S$ の最右に一つだけ置くが、置かなくて済む状況があるのを上手く整理できなかった。

• 問題をしっかり読む。 $T$ は順番に一つずつ処理しなければならない、つまりすべて数字の行き先を決める必要があるが、 $S$ はどれか1か所を選んで上書きしても構わない
• $T$ の数字で $S$ を置き換えて得するなら積極的に置き換える。置き換えると損するならぎりぎりまで溜めて、どうしても置き換えなければならない状況まで先延ばしできる。実際には溜めるというより、上書きしてなかったことにするのが正しい。
• 降順にソート済の $T$ を $U$ とし、 $U$ を左から右にみて、 $S$ を左から右にgreedyに置き換えれば大体答えはあっている。しかし入力例が微妙に合わない。
• 降順にソート済の $T$ だけ考えるのは乱暴で、元々の $T$ の順番に意味があると気が付く。方針が二転三転したために、色々とコードが間違っている。 $to$ を $from$ と書いたり。
• 改めて、 $U$ で、 $S$ を左から右にgreedyに置き換え、余った $U$ を $S$ に埋め込めるなら埋め込み、埋め込めないなら $S$ の右から当てはめるとよさそうである。 $S$ の場所は右から順ではなく最右しか場所はなく、埋め込む値は $T$ の行き場所のない数字のうち最右なのだが、このことになかなか気が付かなかったので時間が掛かった。
• 上記を踏まえて、 $U$ が当てはめた数字を順序付きの $T$ に当てはめる長いコードを書く。幾度かコードを書き直すが、重実装から離れていたので時間が掛かる。
• 早くB問題にいかないとまずいので提出すると1 WAが返ってきた。基本方針はあっているのだが、どのエッジケースが漏れているのかわからない。1完で遅いと負けそうなので、とにかく提出速度重視でペナルティ多発の2完を獲る乱打戦を覚悟する。
• 間違っているのは $T$ が一文字の場合と決め打ちして、色々書き替えたら通った。明らかに焦りからか余計なペナルティがある(5 WAsとか)。
• 0完は逃れたが正解者が多く、B問題を早く解かないとまずいとわかる

コードはこちら

B問題の方がA問題より解答時間が短かった。結果的には間に合ったが、問題選びが難しい。

$N \oplus X = N + X$ なら条件を満たすことは直感的に分かる。言い換えれば、 $X$ で立っているビットはすべて $N$ でも立っている。雑に言うと、 $X \oplus N = X + N$ なら余りの立っているビットが化けないので $(X \oplus N) mod N = (X - N) mod N$ であり、そうでなければ余りの立っているビットが化けてしまう。正確な証明は公式解説にあるが、私の雑な証明でもだいたいあっており、下記の通り実装すればACする。

このことは入出例の $N,K$ と出力例を2進数にして比較すると見えてくる。Rなら intToBits(20250126) を使う。理詰めもいいがARCは実験も大事という教訓が活きた。

これらの洞察から、 $N$ の 0 のビットを 0 または 1 にする方法かつ、 $N$ を超えない( $N$ の最上位ビットより上を立てない)数が $X$ の候補と分かる。 $N$ を超えない判定は最初にコードに書いたがなぜか削除してしまいWAした。残り時間が少ないので焦っていたとしか思えない。

Leading 0sがない $N$ のビット0の位置 $0..(W-1)$ の集合を $P$ とする。 $P$ が空なら $X=N$ が唯一の答えなので、 $K=1$ なら1、そうでなければ -1 を出力する。これが抜けていてWAした。

$P$ が空でなければ $C=2^{|P|}$ 個の候補がある。 $C < K$ なら解無しなので -1 を出力する。これも抜けていてWAした。解があるなら $K$ の各ビットをLSBから順に、 $N$ のビット0の位置に埋め込んだものが答えである。公式解説にある通り、x86のPDEP命令である。解無し -1 になる条件をtrailing 0sが無い数と勘違いしたのがWAの原因である。正しくはここに書いた通り、 $|P| = 0$ なら $2^0 = 1$ 個解があるので、trailing 0sが無い数を特別扱いする必要はなかったかもしれない。

マルチテストケースはエッジケースを間違えると大量にWAが返るが、今回は半分WAだったので解法に自信が持てた。テストケースのやさしさに救われた。

今回は整数の範囲がRの整数に収まったが、収まらないときはgmpライブラリかRubyを使って計算する必要がありそうだ。

as.integer(intToBits(20250126))

20250126.to_s(2)
# "1001101001111111000001110"
20381694.to_s(2)
# "1001101101111111111111110"

コンテスト中の思考の過程は、ほぼ上記の通りである。A,B問題ともおおまかな方針はすぐ見えたが、細部の詰めが甘く時間が掛かった上ペナルティの山を築き、終わってみればA,B 2完最遅であった。A,Bそれぞれ30分で解けないと青パフォは厳しい。改めて実装すると、こんなに 簡潔な コードになる。x86のPDEP命令は確かにハードウェアで速いが、C++で書いても数行である。

今回は観察だけで方針を立てたので実験コードを書かなかったが、実験コードを書いた方が早く解けたかもしれない。残り時間が50分くらいだったので実験コードを書く手間を省いたのが裏目に出た。 $N = 2^i$ を入力すると $N$ が唯一の解だとわかる。

void experiment(std::istream& is, std::ostream& os) {
    using Num = unsigned long long int;
    Num n {0};
    is >> n;

    Vec cs;
    for(Num x{1}; x<=n*n; ++x) {
        if ((x ^ n) == (x % n)) {
            cs.push_back(x);
        }
    }

    print_oneline(cs, os);
}

コンテスト中は成すすべがなく、残り16分は順位表を眺めて終わった。

公式解説のWriter解をそのまま実装すると こちら になる。Tester解は細かい実装方法がよくわからない。

A問題1完、74:55 2ペナで、またしてもなんとか0完を逃れた。自分のレーティング帯で正解率7割超の問題を落とすわけにはいかない。B問題をコンテスト中に解けなかったのはくやしい。C問題は力が足りない。

コードはこちら

深く考えすぎて悩んでしまった。

ARCR ARCR A... と並べれば、元の $A$ はどうあれ $A$ を1で埋め尽くすことができる。よって埋め尽くすことができない場合を探す。 $N \geq 3$ なのでエッジケースを省ける。

• $N$ が4の倍数であれば、 $A$ がどうあれ ARCR だけで全部1にできるので Yes である。
• $N$ が4の倍数+1であれば、 $A$ に一つでも 1 があればそれを終端の A にすることで、 ARCR をならべて元からある 1 を A にすることで全部1にできるので Yes である。 $A$ に 1 が一つもなければ No である。
• $N$ が4の倍数+3であれば、 $A$ に一つでも 1 があればそれを終端の A にすることで、 ARCR を多数ならべて、そのあとに ARC を置いて、元からある 1 を A にすることで全部1にできるので Yes である。 $A$ に 1 が一つもなければ No である。

$N$ が4の倍数+2のときがややこしい。 $A$ に 1 が2つ未満なら No である。

$A$ に 1 が2つ以上あるときを考える。 11 が連続するなら上記の要領で、 ARCR を多数ならべて、そのあとに AR を置いて、そのあと 11 にできて答えは Yes である。同様に、ある隣り合う 1 と 1 の間隔つまり座標の差が奇数長(間に挟まっている 0 が偶数個)とする。間隔を求めるときに $A$ が周回することを考慮する( $A$ を二周させると簡単に求まる)。以下のように場合分けできる。

• 11 は既述の通り
• 1001 は .CRA と置く。この A を先頭とする残りの文字列長は4の倍数なので、 ARCR を並べる。
• 100001 は .CRARC と置く。やはりこの A を先頭とする残りの文字列長は4の倍数なので、 ARCR を並べる。
• これより連続する 0 が多い場合は、 ARCR を並べて余りを上記の通り調整する

まとめると、隣り合う 1 と 1 の間隔(座標の差)が奇数長な箇所が $A$ に一か所でもあれば Yes 、そうでなければ No である。

この解法は公式解説と同じである。

もしかして隣り合う 1 と 1 の間隔ではなく任意の間隔ではないかと思ったが、既に2ペナだったので上記の証明を端折ったまま提出してACした。運に助けられた。コンテスト後にわかったがレーティングの時間減衰が緩やかだったので、ペナルティ覚悟で早く提出してtrial and errorでよかった。

コンテスト中は、ランレングス圧縮したり、前方から $S$ を構築したり、まったく的外れな方法で最初の40分くらいを過ごした。 0 の並びとそれを囲む 1 の並びの関係だと気づいたが、上記のような関係だとは思わなかった。ランレングス圧縮から構築するのが複雑すぎて、おそらくランを独立に考える戦略は上手くいかないと見切ったあたりで解法が見えた。

コードはこちら

コンテスト中には間に合わず、翌朝自力ACした。

自明な解として、 $N = 1$ は先手必勝 Fennec である。 $N = 2$ は $A = (a,b)$ として、先手が $a$ を選んだら後手は $b$ を選んで後手必勝 Snuke である。

以下 $N \geq 3$ とする。 $1..N$ のうち $S$ に無い要素を $U$ とする。 $A$ の奇数の要素数を $K$ とする。

$K = 0$ つまり $A$ の要素はすべて偶数の場合を考える。このときは基本的に後手は先手と同じものを取り続ければいい。つまり先手番が $i$ を取ったら、直後の後手番も $i$ を取る。 $U$ は手番を往復するごとに0個または1個ずつ減る。 後手番になったときに $|U| = 3$ で、 $|U| = 2$ になって先手番に移ったときに、先手番は何を取っても $|U| = 1$ で後手番になるので、後手番は残った $U$ を取れば必ず勝てる。この論法は以下で繰り返す。ここでは $N \geq 3 \land K = 0$ なら後手必勝 Snuke である。

以下 $N \geq 3 \land K > 0$ つまり $A$ に奇数の要素が少なくとも一つあるとする。

実は $N = 3 \land K > 0$ では先手必勝 Fennec である。ここがわからず2 WAsが残った。 $A = (a,b,c)$ として、一般性を失わずに $a$ を奇数とする。先手が $a$ を取ったら、後手は $a > 0$ でない限り $a$ を取らなければならない。なぜなら後手が $b$ を取ったら、先手は $c$ を取って先手が勝つからだ。しかし $a$ は奇数なので、先手後手が互いに $a$ を取り合うと、 $(a = 0, b > 0, c > 0)$ つまり $|U| = 2$ の状態で後手番になり、やはり先手必勝である。

上記以外の場合 $N > 3 \land K > 0$ を考える。 $A$ が偶数の要素はお互いに取り合って手番が往復するだけなので無いのと同等である。 $K$ が奇数なら、 $A$ の奇数の要素の和も奇数であり、先手は先手番に引き戻すことができる。よって $K$ が奇数なら先手必勝 Fennec 、 $K$ が偶数なら Snuke である。

この解法は公式解説2とほぼ同じである。

$N = 3$ の答えを見抜くのが大変である。実験するとわかるが実験はそこそこ実装量があり、コンテスト中に理詰めで考えるか実験コードを書くか悩ましい。解答は $A$ の偶奇だけで決まり、奇数なら1か3以上かは問わないという判断もいる。以下の実験コードは、部分木の勝敗をメモ化して高速化できるが(ABCならそうしないとTLEするが)、実験コードが間違っているとどうしようもないのでここは簡潔に書く。

#include <bits/stdc++.h>

using Num = unsigned int;
using Vec = std::vector<Num>;
using Stones = Vec;
using Touched = std::bitset<32>;

bool play(bool player, Stones& stones, const Touched touched) {
    const auto another = !player;
    const auto size = stones.size();

    for(size_t i{0}; i<size; ++i) {
        if (stones.at(i) <= 0) {
            continue;
        }

        auto next = touched;
        next.reset(i);
        if (next.count() == 0) {
            return player;
        }

        stones.at(i) -= 1;
        const auto result = play(another, stones, next);
        stones.at(i) += 1;

        if (result == player) {
            return player;
        }
    }

    return another;
}

bool search(const Stones& init) {
    Stones stones = init;
    Touched touched ((1LL << init.size()) - 1);
    return play(false, stones, touched);
}

void print_oneline(const Vec& vec, std::ostream& os) {
    const std::vector<std::string> strs {".", "1"};
    const auto size = vec.size();
    for(size_t i{0}; i<size; ++i) {
        os << strs.at(vec.at(i) % 2) << " ";
    }
}

void solve(std::ostream& os) {
    const std::vector<std::string> players {"Fennec", "Snuke "};

    for(Num offset{0}; offset<2; ++offset) {
        for(Num width{1}; width<6; ++width) {
            Num n_patterns {1};
            n_patterns <<= width;

            for(Num pat{0}; pat<n_patterns; ++pat) {
                Touched bits(pat);
                const auto ones = bits.count();
                Vec init(width);
                for(decltype(width) j{0}; j<width; ++j) {
                    init.at(j) = offset * 2 + (bits[j] ? 1 : 2);
                }

                print_oneline(init, os);
                const auto actual = search(init);
                os << players.at(actual + 0);

                if (((width == 1) && (actual == false)) ||
                    ((width == 2) && (actual == true)) ||
                    ((width == 3) &&
                     (((pat != 0) && (actual == false)) ||
                      ((pat == 0) && (actual == true)))) ||
                    ((width > 3) && (((ones % 2) == 0) == actual))) {
                    os << " : expected\n";
                } else {
                    os << " : UNEXPECTED\n";
                }
            }
        }
    }
}

int main(void) {
    solve(std::cout);
    return 0;
}

コードはこちら

コンテスト中はちらっと見ただけで、インタラクティブ問題は解けないだろうと諦め、翌日解いた。方針はすぐ立ったが、インタラクティブ問題のデバッグが泥沼にはまり2時間を超えてしまった。実装力が足りないというか、ABCの早解き重視の練習をしていないのでコンテスト中には間に合わない。

$P_1 < P_2$ を使って、 $P$ を仕分ける。集合 $S_1, S_2, S_3$ を $S_1 < P_1 < S_2 < P_2 < S_3$ を満たす集合とする。

問題文通り、クエリ $(i,j)$ は、 $[P_i, P_j]$ の区間和 $C_{i,j}$ を返す( $i,j$ の大小は問わない)。クエリ $(1,2)$ , $(1,i=3..N)$ , $(2,i=3..N)$ の計 $2N-3$ 回のクエリを投げる。 $C_{\ast, i}$ の大小関係から、 $P_i$ の位置が決まる。

• $C_{1,i} < C_{1,2} \land C_{2,i} < C_{1,2}$ なら $i$ は $S_2$ に属する
• そうではなく、 $C_{1,i} < C_{2,i}$ なら $i$ は $S_1$ に属する
• そうでなければ $i$ は $S_3$ に属する ($C_{1,i} > C_{2,i}$ である)

$S_1$ の要素を、 $C_{1,\ast}$ の降順に並び替える。 $S_2$ の要素を、 $C_{1,\ast}$ の昇順に並び替える。 $S_3$ の要素を、 $C_{1,\ast}$ の昇順に並び替える。こうすると、 $P_{1..N}$ の順序 $1..N$ が求まる。これは $P$ の逆引き $Q$ であり $Q[P_i] = i$ だとわかる。ここから $P$ を構成すると答えの半分が求まる。

$A$ を求める。 $P_1 = 1$ 言い換えれば $Q[1] = 1$ のときは、 $C_{1,\ast}$ は左から右に累積和を取った値である。 $A_1$ を最初に求める。これはクエリ $(Q[1],Q[N])$ の値からクエリ $(Q[2],Q[N])$ の値を引いたものである。あとは $A_{2..N}$ について累積和の差分を $A$ の値とする。 $A_i = C_{1,A[Q[i]]} - C_{1,A[Q[i-1]]}$ で求まる。

$P_1 \ne 1$ のときは、 $P$ において1は最左ではない。上記と同様に、クエリで得た $A_{Q[P_1]}$ からの累積和を再利用する。 $P_1$ が左から2番目か否かで場合分けする。

$P_1 > 2$ のときは、 $A_{Q[P_1]}$ を最初に求める。これは先ほどと同様にクエリ $(Q[1],Q[P_1])$ の値からクエリ $(Q[1],Q[P_1]-1)$ の値を引いたものである。 $P$ が1になる位置を $t = Q[1]$ として、 $i < t$ なら $C_{1,Q[i]} - C_{1,Q[i+1]}$ , $i > t$ なら $C_{1,Q[i]} - C_{1,Q[i-1]}$ が答えである。

$P_1 = 2$ のときは、単一のクエリに与える2個の値は異なる制約を満たす、つまりクエリ $(1,1)$ を避けるために、 $P_1$ の代わりに $P_2 > 2$ を使う。あとは上記と同様に求まる。

こうして求めた $P,A$ を出力すれば正解が得られる。クエリの回数は $2N-1$ 回であり制約を満たす。この方針は公式解説2と同じである。

A,B問題と異なり、問題文を読んですぐに方針が立った。実装力があればA,B問題の代わりに選べるが、実装力がなければインタラクティブ問題にはじっくり取り組めない。

私に700点問題は解けそうもないし、Div. 1はunratedだし、ということでコンテストには出ずに翌朝解いた。水diffだったようだが、水diffは解かなければならない。

コードはこちら

ARC 190-Aの類題に見えなくもない。

可能手があるなら1,2または3手で到達できる。到達可能なら $W_s + W_t$ は必ず答えに加わるので、他の重みを計算する。

$[L_s,R_s]$ と $[L_t,R_t]$ に重なりがなければ直行できる。これは $R_s < L_t \lor R_t < L_s$ で分かる。このとき追加の重みは無い。

$[L_s,R_s]$ と $[L_t,R_t]$ に重なりがあるとする。左側に大きく振って戻る、または右側に大きく振って戻る、のどちらかが可能なら1手追加する。どの1手を追加すべきか求める。

区間の右端 $R$ が $i$ 以下のすべての区間について、最小の重みを $A[i]$ とする。そのような区間が無いときは $A[i] = \infty$ とする。求め方は後述する。同様に左端 $L$ が $i$ 以上のすべての区間について、最小の重みを $B[i]$ とする。

このとき $min(A[min(L_s,L_t)], B[max(R_s,R_t)])$ が最小の追加コストとして候補になる。該当する区間がなければ $\infty$ である。

$[L_s,R_s]$ と $[L_t,R_t]$ について、一方が他方の包含関係にならない重なりがあるとする。つまり $L_s < L_t < R_s < R_t$ または $L_t < L_s < R_t < R_s$ を満たすとする。説明を簡単にするために、後者なら $s,t$ を入れ替えて前者と解釈する。このとき、 $s$ から $(R_s,\infty)$ に振って、 $[0,L_t)$ に振って、 $t$ に行くという経路がある。このとき $B[R_s+1] + A[L_t-1]$ も最小の追加コストとして候補になる。

ここまでを考慮して、最小コストが $\infty$ なら答えは -1 、そうでなければ最小コストを答える。

改めて、 $A,B$ の求め方を示す。 $[L_i,R_i]$ について、 $A$ を遅延セグメントに載せて区間に $min(W_i, [R_i+1,\infty))$ を取る。同様に $B$ を遅延セグメントに載せて区間 $min(W_i, [0, L_i))$ を取る。ここで遅延セグメント木の添え字を1間違えてペナルティの山を築いた。

上記は公式解説と同じである。 $A,B$ は $O(N)$ で求まるが遅延セグメントで実装した。累積minを使って 実装 できるが、やはり添え字がややこしい。 $A[r] = w$ は区間が $[0,r-1]$ つまり $[0,r)$ のとき重み $w$ を実現できるので、区間 $[L,R]$ については $A[L]$ は隣り合うが重ならない。 $B[l]$ は区間が $[l,\infty)$ のとき重み $w$ を実現できるので、区間 $[L,R]$ については $B[R+1]$ は隣り合うが重ならない。この $+1$ の有無がややこしい。

基本方針はすぐに思いついたものの、 $s,t$ が重なっているときの処理を忘れて1ペナ、デバッグに時間を掛けすぎて結局1時間掛かった。落ち着いて実装すれば30分でかなりのパフォーマンスが出る問題だった。

一問も解くことができず、記録的大敗を喫した。A,B,C問題を見てC問題なら解けると思ったが72分で提出したらWA、仕方ないので順位表を見るとA,B問題が大量に解かれていて、仕方が無いので残り47分をA問題に乗り換えたがやはりWAの山が返ってきた。どうしてC問題を解けると思ったのか、最初の70分間であるいは順位表を見すらしなかったのか、とにかく問題の解法も試合運びもおかしい。

コードはこちら

コンテスト後に解法を思いついた。他の方のコンテスト感想にDPという文字がちらっと見えたが、一応自力AC扱いである。どちらにせよ、コンテスト中には得点できなかったのだから。

スタック $S$ の長さ $L$ が $L=0..N$ のときに、 $S$ の総和として取りうる値の最大値を $R[L]$ とする。初期値は $R[] = -\infty, R[0] = 0$, である。値 $A_i$ について、以下の操作を選べる。

• スタックに $A_i$ を載せる。
  • $i$ が奇数なら、スタックは必ず奇数長になる。 $l = 0..\lfloor i/2 \rfloor$ として $R[2l+1] = max(R[2l+1], R[2l] + a)$ になる。
  • $i$ が偶数なら同様に、 $l = 1..\lfloor i/2 \rfloor$ として $R[2l] = max(R[2l], R[2l-1] + a)$ である。
• スタックに $A_i$ を載せず、スタックの最も上の値を除く。 $i$ が奇数なら、スタックが偶数長について既出の値になり、 $i$ が偶数なら、スタックが奇数長について既出の値になり、結局何もしないのと同じである。
• 正確には、 $R[|S|]$ はスタック長が $|S| $ちょうどではなく、 $R[|S|]$ と偶奇が等しい任意のスタック長における最大値と解釈する

スタック長が減る方向については何も操作しないので、 $A_i$ を積んでスタック長が伸びた時だけ考えればよい。よく考えると、スタックは奇数長についてひとまとめにして構わない。スタックが偶数長についても然りである。そうすると以下のDPになる。

• $i$ が奇数なら、 $R[1] = max(R[1], R[0] + a)$
• $i$ が偶数なら、 $R[0] = max(R[0], R[1] + a)$

答えは、 $N$ が奇数の時 $R[1]$ 、 $N$ が偶数のとき $R[0]$ である。

コンテスト中に思いついた解法はランレングス圧縮である。非負値が続くなら温存する。負の値が続くなら、ある負の値についてその値を載せずその直前の値を削除することで、偶数個単位で消去できる。

この考察から、負の値が偶数個続くなら、なかったことにできる。奇数個なら先頭を1として奇数番目の値のうちどれか一つだけを残す。これより雑な最も大きな値を残すのが得である。という解法を提出したらWAの山が返ってきた(奇数番目にしてもダメである)。まるっきり方針が間違っていた。万事休す。

公式解説も基本に同じことをしているが表現は異なる。

コードはこちら

コンテスト中にはちらっと見てそれ以上着手しなかったが、コンテスト後にすんなり解けてしまった。B,A,C問題の順に解けばそこそこの速さで1完できてレーティングの下がりもだいぶ少なかったが、問題選びを完全に間違えた。問題の得点はどうあれ解きやすい問題を解くのだ、という意気込みが完全に空回りしている。A,B問題の解答者数はだいたい同じであり、解きやすい方を選べばよかったのだが、C問題に時間を掛けすぎて、B問題を見ずにA問題に飛びついてしまった。

バブルソートしかなかろうと思い、実際それでACする。

位置 $i$ に数 $P_i$ があることを入力で受け取るが、この逆引きつまり数 $i$ が位置 $R_i$ にある対応表を作る。

よくあるバブルソートとは逆に、最大の数から順に定位置に持っていく。数 $i$ の移動先は当然 $i$ である。移動元は元々 $R_i$ だったが、 $i$ より大きな数をバブルソートした結果、右にずれている。どれだけずれるかといえば、初期状態で $R_{0..i-1}$ にある $N$ より大きな数の個数 $U_i$ である。これはセグメント木で転倒数を求める要領で分かる。

まとめると、 $f = R_i - U_i$ を $i$ に移動するコストがわかればよく、これは $\sum_{j=f}^{i-1} j$ である。この和はループを使わず、等差数列の公式を使って $O(1)$ で求めると $(f+i-1)(i-f) / 2$ である。0-based indexingで実装しているときは気を付ける。

$1..N$ の順に定位置に持ってくると上手くいかない。バブルソートで数を右に押し出す、つまり添え字を減らしてコストを下げる必要があるので $N..1$ の順にする。

公式解説も基本に同じことをしているが表現は異なる。

コードはこちら

自分のレーティング帯では正解率5%の問題を、どうして解けると思ったのだろう。基本方針だけはすぐ立ったので焦ったのだろうか。

場合分けは以下の通りである。

1. $A=1, B=0$ は $C$ が大きいものほど早く転換する
2. $A=0, B=1$ は $C$ が大きいものほど遅く転換する
3. $A=1, B=1$ は、いったん $A=0$ に変えて後で $A=1$ に変えるとコストが下がるときだけ転換する
4. $A=0, B=0$ は何もしない

上記の操作1の後に操作2を実行する。問題は操作3を実行するならいつ実行すると得かということである。操作3の数 $c$ について、 $c$ より小さい数について操作1,2の加算コストが減り、 $c$ より大きい数について操作3の加算コストが増えるとして、差し引きでコストが減るなら操作する。 $c$ を大きい方から調べていく。

操作3が $C$ について単調ではないので全探索が必要であり、コストが減少しなくなったところで止めるとWAする。これがわからなくて諦めた。

大まかな方針としては上記は公式解説の通りであっているが、単調ではないことを見抜けなかった。公式解説は証明を与えているが、直感的に正しいと分かった。しかし探索を打ち切った上、実装が全く上手くいかず解けなかった。「このように、直感に頼った未証明の Greedy は危険です」案件である。

コンテスト中はそもそも累積和まで考えが至らなかった。その後私もセグメント木で解こうとしたが、他の方の 実装 を見て、ようやく実装方法が分かった。他の方ははるかにすっきりした実装をしている。なおintだとオーバーフローする。

Fenwick Treeを2個、累積和と $C$ の出現回数で使い分ける。より正確には、操作3で $C$ を0に変えて1に変えるコストは以下の通りである。操作 $k$ の累積和を $Sk$ , $C$ の出現回数を $Wk$ とし、 $0 < C \leq 0..10^6$ についてFenwick Treeに載せる。操作4ついての $C$ の和と、操作3で $A=1$ のままにすると決めた $C$ の和を合わせて $T$ とする。 $T$ は操作3でどの $C$ を操作するかで変わることに注意する。

• $C$ を減らす操作は、操作1の $S1[0..C-1]$ と $T - C$ の和であり、これだけコストが増える
• $C$ を増やす操作は、操作2の $S2[0..C-1]$ と $T$ であり、これだけコストが増える
• $C$ の分だけ $T$ が減った利得は $C (W1[0..C-1] + W2[0..C-1])$ である。これだけコストが減る。
• これらの和を $D$ とする

後は操作3について、 $C$ の降順に全探索する。操作3は何もしないときのコスト $U$ を求めて、上記で求めながら更新する。

• $U$ を $U + D$ で更新する
• $T$ を $C$ 減らす
• $S12[C]$ に $C$ を足す。 $W12[C]$ に $1$ を足す。これらはつまり操作1,2を追加することに相当する。

一問は解いたがあまりにも遅く茶パフォになった。辛うじてレーティング1200に居残ったが、いよいよ後がなくなった。記録的大敗も、二度続けたら実力と言わざるを得ない。

コードはこちら

私がACした解法は以下の通りである。正解はするが論理の組み立てが怪しい。

$A$ の各数字 $a \in A$ が $B$ に出現する位置の集合を $S[a]$ とする。ここでは1-based indexingとする。 $A$ を先頭から順に走査して $a$ を見つけたら、長さ $p \in S[a]$ の接頭辞が何通りあるか更新する、というのが概要である。

$A$ を先頭から見ていって、長さ $i = 0..M$ の接頭辞が何通りあるかを $T[i]$ とする。区間minのセグメント木で持ち、初期値は $T[] = 0, T[0] = 1$ である。つまり長さ0の接頭辞が1通りある。

$a = A[1..N]$ を走査し、 $T$ を更新する。

• $a$ が $B$ に含まれない、つまり $S[a]$ が空なら何もしない
• $T[0..k]$ がすべて1以上であるような、最大の $k$ を求める。これは長さ $k$ 以下の接頭辞に $a$ をつなげられる可能性がある、という意味である。セグメント木を二分探索して求める。
• $p \in S[a] \land (p-1) \leq k$ を満たす、最大の $p$ を二分探索で求める。そのような $p$ がなければ何もしない。
• このような $p$ があれば、 $T[p]$ を $T[p] + T[p-1]$ で更新する。このときオーバーフローしないように、値の上限を設ける。値に上限が無いと3 WAsする。上限は 2でよい 。

上記の走査を終えて、 $T[M] > 1$ なら Yes 、そうでなければ No である。

公式解説はとっても簡潔である。部分文字列を数え上げようと努力して82分も掛けてしまった。というよりも、私の解法が本当に正しいかどうか怪しい。2以上か1以下かは判別できるが、そうでないときはどうなのだろう。解法が見えないときはDPという前回の反省に囚われすぎて、この問題もARC 194-AっぽくDPで解こうとした、というかDPにするとTLEするので、無理やりTLEを回避してごり押した。

公式解説通りに実装すると こう なる。正順と逆順の実装を共通化し、逆順のインデックスを正順にそろえ、部分文字列長が $M$ でないときは No にする。

コードはこちら

全く見当がつかなかった。

$A_i + B_i$ は高々 $N^2$ 通りしかないのが計算量を決めると分かったが、それ以上考察が進まなかった。 -1 はなんでも入るので、 $A$ に含まれる -1 と $B$ に含まれる -1 を合計 $M$ 個とすると、和のマッチングは $max(0, N-M)$ 個作ればよいことは分かった。 $N < M$ の例外扱いを忘れると2 WAsする。

結局和のマッチングが何通りあるか数える方法が分からなかった。公式解説にある通り、 $A_i + B_i = S$ について、 $A_i$ と $B_i$ のどちらか少ない方である。 $S$ に注目すると計算量が足りないが、 $A,B$ に注目すると計算量は $O(N^2)$ になる。 $S$ に注目したままこの発想がなかった。

最後に、 $S < max(A,B)$ は解ではない。入力例3はこれで No にできる。正解までには幾重の考察が足りなかった。

コードはこちら

だいたい合ってそうだがACできないまま解説を読んだ。エッジケースが漏れていた。

$R$ が奇数なら解無しなので No である。なぜなら $R$ は $|X-Y|$ の偶奇を入れ替え、 $B$ は $|X-Y|$ の偶奇を変えないので、 $R$ が偶数個無いと出発点に戻れないからだ。不変量である。

野球場のダイヤモンド形を考える。まず $B \geq 4$ について考える。

ホームベース $(0,0)$ から一塁 $(1,1)$ は、 $R$ を消化する。加えて、 $B$ が奇数なら $B$ を1減らして $R$ 2個に置き換える。具体的には、右に直進し、上または右上に一歩進み( $B$ が奇数なら上、偶数なら右上)、その後左に進む。 $R$ が足りないと右上に行けないのでそのときは No が答えである。

• 一塁 $(1,1)$ から 二塁 $(0,2)$ は $B$ で進む
• 二塁 $(0,2)$ から 三塁 $(-1,1)$ は $B$ で進む
• 三塁からホームベースは、左下に迂回する。 $\lfloor (B - 3) / 2 \rfloor$ 回左下に進んで戻る

$B = 0..3$ については、上記の要領で左に進んで $R$ を消化する。 $R$ が足りないときは No にする。 $B=0$ なら $R \geq 4$ 、 $B=1,2,3$ なら $R \geq 2$ 、 $B \geq 4$ なら $R \geq 2(B mod 2)$ いる。

というのを実装したのだが、13 WAs が返ってきた。エッジケースが足りないのか実装を間違えたのかわからない。公式解説をみても、 $R,B$ の偶奇はあっていそうと思ったが、 $B=0$ なら $R$ は4以上ではなかった。ロの字を考えて4にしたが、実は2でもよかった。縦棒 $R = 2, B = 0$ を正しく処理し、 / の字 $R = 0, B = 2$ を手書きするとACする。 $R = 0$ かつ $B$ が奇数なら No は織り込み済なので、改めて実装しなくても ACする 。

$R + B = 2$ を正しく実装すればACだった。コンテスト中には間に合わないが惜しかった。解法が全く分からないB問題より、C問題の方が正解に近いことがある。

コードはこちら

コンテスト外で考えたが全く分からなかった。解説を読んだ後の std::set 実装にもたっぷり時間を掛けてしまった。

久しぶりのratedである。A問題を1完早解き17:31、しかし後が続かなかった。B,C問題をコンテスト後に思いついたが遅かった。特にC問題は制約を見切って正解まであと一歩だったのに、道具に使われてしまった。

コードはこちら

ある列に注目すると、できるだけ上(行番号が小さい)コースと、できるだけ下(行番号が大きい)コースの間は、任意の場所を通れる。これは下(行を増やす)方向の移動と、右(列を増やす)方向移動を逆順にすれば実現できる。

$S$ が含むべき D は $H-1$ 個、 R は $W-1$ 個に固定なので、 ? をそのように置き換える。上コースは ? を出現順に R に置き換え、 R が尽きたら残りの ? を D に置き換える。下コースは ? を出現順に D に置き換え、 D が尽きたら残りの ? を　R に置き換える。

上コースと下コースの経路はシミュレーションすれば分かる。列 $x$ について、上コースが行 $A$, 下コースが行 $B$ を通れば、 $B+1-A$ 個のマスを塗れる。すべての列について値を求めて足すと答えである。

コードはこちら

コンテスト中は全く手掛かりがつかめず、コンテスト後になって方法を思いついた。

$A$ を昇順に並べ替える。基本的に $A$ の要素が多い方がスコアが高そうなので、 $A$ 全部入りのスコアを求めてスコアの最低値とする。その後 $A$ の値が大きい物から順に減らし(同値は一個ずつ減らす)、平均値を求めて、平均値以上の要素を数える(これは std::lower_bound で分かる)。 $A$ の要素が1個になるまで減らし、スコアの最大値を出力する。

雑に証明する。平均値を下げるには、その時点で $A$ の要素が最大のものを削除するのが最適である。要素を削除するとスコアは1下がるが、削除前後の平均値の間にあった値がスコアを押し上げるかもしれない。要素が最大のもの以外を削除すると、確実にスコアは1下がるが、平均値の下げは少なくなるのでスコアの押し上げが足りない。

公式解説通りかどうかまだ理解していない。

コードはこちら

クエリの数 $Q \leq 10^5$ からして、素数を $10^5$ 個取りつくしたら問題が終わる。雑に計算して130万以下の数には素数が $10^5$ 個あるので、その倍に見積もって $S \leq 3\times10^6 = L$ だけ考える。 $S$ が小さいとWAし、 $S$ が大きすぎるとTLEする。正しくは $Q + B = 2 \times 10^5$ 番目の素数であり、公式解説には $L = 2750159$ と書いてある。

コンテスト中はPolicy-Based Data Structuresを使うことにこだわりすぎて、平方分割で上手いこと計算量を減らそうと試みたが、結局TLEが取れなかった。正解はセグメント木である。転倒数をセグメント木で数えるのは典型なのに、下からn番目を探すのを二分探索できることを思い出せなかった。思い出したか再発明したときにはすでに遅し。

$S$ に含まれる $1..L$ の数をセグメント木で数える。要素は0または1、区間加算、単位元は0のセグメント木を作り、初期値は $1..L$ の値を1とする。下から $B$ 番目の要素は、 atcoder::segtree::max_right を使った二分探索で求まる。あとはクエリごとに $A$ の倍数を消せばよい。

• $A > L$ なら、 $S$ の要素は変わらないので何もしない
• $A \leq L$ かつセグメント木の値 $T[A] = 0$ なら、 $A$ の倍数は消えているので何もしない
• $A \leq L$ かつセグメント木の値 $T[A] = 1$ なら、 $A$ の倍数を消す。具体的には $T[Ai] = 0$ にする ($i$ は $Ai \leq L$ を満たす整数)

Policy-Based Data Structuresを知っていたが、道具に使われてしまった。ここですんなりセグメント木を取り出せないのは実装力が足りない。ABC 392-Fをセグメント木で実装しなかったからである。結果、ほとんど解けていた問題を落としてしまった。

この解法は公式解説通りである。なお公式解説には平方分割が載っており、上手く平方分割を使えば解けたのだが私にはその力量が無かった。

隣接先が同一な頂点を同一視して順列を求める、という方法は35 WAsする。諦めて公式解説を読んだが理解していない。

6:27 1ペナで残り113分何もできずに終わった。緑diffを落としてレーティング緑落ちが確定した。

コードはこちら

偶数の集合だろうという直感が生えたのでそのまま提出したら、 $N=1$ を忘れて 1 WAが返ってきた。大急ぎで再提出してACしたが、さすがに灰diffを1完 6:27では勝てない。

コードはこちら

コンテスト中は全く正解できず、コンテスト後に実装を間違えたと思った提出がACしてしまった。自分でも何を考えていたのか、公式解説を読むまで分からなかった。

状態遷移図を書く。

• 状態0: ここでは0の繰り返し。遷移先は一番目の1(状態1a)または2(状態2)もしくは自分自身(状態0)。
• 状態1a: 前の状態が0(状態0)。ここは一番目の1。遷移先は二番目の1(状態1b)または2(状態2)。
• 状態1b: 前の状態が一番目の1(状態1a)または2(状態2)。ここは二番目の1。遷移先は0(状態0)。
• 状態2: 前の状態が0(状態1)または一番目の1(状態1a)。ここは2。遷移先は二番目の1(状態1b)。

ここから条件を導出するが、公式解説の方がはるかに分かりやすい。

• 0は多い分には構わない
• 2と同数以上の0が要る $X \geq Z$
• $Z = 0$ なら、 $Y$ は偶数でなければならない。状態0,1a,1bを回るには $X \geq Y/2$ が要る
• $Z > 0$ なら、状態0,2,1bを通って $Y$ を偶数にできる。よって元の $Y$ が奇数なら、 $Y$ と $Z$ を1減らす。減らした後に状態0,1a,1bを回るには $X \geq \lfloor Y/2 \rfloor$ が要る
• 上記を満たすなら、以下のどれかをたどる。
  • 状態0,2,0 の順
  • 状態0,1a,1b,0 の順
  • 状態0,1a,2,1b,0 の順。これが見抜けなかった。

公式解説に指摘されるまで色々と分からなかった。状態0,2,1b,0 の順は、 $Y$ を奇数にする以外は要らない。わざわざ状態1aを通らないパスを作っても、 $Y$ が余るだけである。だとすれば $X$ と $Z, \lfloor Y/2 \rfloor$ の大小関係を、 $Y$ と $Z$ の関係式で表現する必要もない(状態0,1a,2,1b,0 の順で消化できない余りは、状態0,2,0 の順と状態0,1a,2,1b,0 の順のいずれかで消化できる)。

状態遷移図から制約を導く方法が、結局コンテスト中に分からず仕舞いだった。いかにもARCらしい良問であるが私の手には負えなかった。