ABC466

5完。Eまで早解きする価値は、パフォではなくFを考える時間を得ること。

A - Compromise

こういうの簡単だけど瞬殺するにはけっこう怖いよな。ギリ1分切れたのはえらい。

B - Representative Balls

初期値を-1にするのは思いつくけど、なんかずるいというか不安になる。まあ正しいのでそれでいいんだけど。

C - Count Close Pairs

これD問題だろ。まあしゃくとりを思いつく難易度がCで、インタラクティブ成分もC相当なら、合計でCということか。ただ、インタラクティブで威圧された状態でこのしゃくとりは相当見えづらい。紙に描いて考えてようやく見えた。[i0, i1)でやっていて、i1をi0より大きくする処理を入れて見覚えがないので不安になったが、通常のしゃくとりなら自分との距離は1以下だからその処理は不要だし、そもそも区間の長さが0になることは一般のしゃくとりならありえる。1を引いたときも不安になったが、今考えると距離が1以下になる空でない区間の個数ではないからだ（1個のみからなる区間は数えない問題設定）。質問回数は、最初不安だったけど提出時には忘れていた（カス）。[0, 1)から[N-1, N)まで左右片方1ずつ増えるから2*N回よりは少ない。コードを見て「N回程度で済むのでは？」と思ったけど、右が進まないこともある。しゃくとりのコードって意外と左右対称。

しゃくとりを思いついてすぐ、二分探索を封じてあることに気づいて、いい問題だと思った。まあ二分探索が許される設定でもやるのは難しそうだが。

D - Placing Rooks

どの行にもどの列にも高々1個のコマしか置かれることはない。mapを使って相互監視するやつかと心配したけど、よく考えるとvectorでいける。各行（各列）についてコマがなければ-1、あればその位置を持つ。これはちゃんと更新できるのだが、怖かったのがちょうどコマがある位置に操作した場合。まあちゃんと考えれば大丈夫なんだけど不安だった。

解説の解法1、これは難しい。仮に思いついても提出できるほどの確信を持てない気がする。

E - Range Flip

（左端は表として）表を使うか裏を使うかの切り替わり場所はK*2箇所しか作れない（これは区間の端が2個しかないから当たり前だけど、コンテスト中は多くの例を試すしかできてなかった）。そしてK*2箇所は端からそこに合わせて区間を置けば簡単に作れる。そこからは、E問題とは思えないクソ簡単なDP。

F - Many Mod Calculation

forでも書ける再帰というのが最初のイメージ。ただ、少し考えると普通に前からという感じに。Aは狭義単調減少としてよい。f(0)=0なので、0以上X以下で求めて1を引けばいい。最初、[0, X]が1個ずつという状態。個数が同じものをまとめて、いくつかの区間で表す。区間はけっこう増えそうに思える。上ちょっとしか削れないとしても区間はたくさんあるかもしれない。階段状になったものを、切って重ね直す。そもそも、2乗でいいと言われても実装がむちゃくちゃ難しそう（結局何もできないなら2乗の実装に挑戦するべきだったか）。でっかく削れる（半分になるとか）のはO(log(X))回なのでそこで毎回O(N)かかるのはいい。ただ、Xは大きいし、区間が増えてからちまちま（今気づいたけどこれが半分以下になるのか！）削られるとわからない。解ける見た目はしているが、自分から見える解法では解けていないようにしか思えない。逆からやるのも、不規則になったものが積み重なっていくので、無理に見える。何もできずに時間が過ぎ、終了3分前くらいに撤退した。解説見てもなんもわからん。

桁DPでn以下の非負整数の個数を求める その3

前回までは下からやっていたが、今回は上から桁DP。また、nは文字列として受け取り、998244353で割ったあまりを出力している。

「nの上i桁」は、例えば456の上2桁は45、上0桁は0（文字列ではなく数）。

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
using ll = long long;

using T = array<mint, 2>;

int main() {
    string n;
    cin >> n;

    T dp = {};
    dp[0] = 1; // 「nの上i桁」と等しいi桁の非負整数の個数（現在はi=0）
    dp[1] = 0; // 「nの上i桁」未満のi桁の非負整数の個数

    for (const auto c : n) {
        T p = {};
        int d0 = c - '0';
        for (int d = 0; d < 10; d++) {
            if (d <= d0) p[d != d0] += dp[0];
            p[1] += dp[1];
        }
        dp = p;
    }

    cout << (dp[0] + dp[1]).val() << endl;

    return 0;
}

Xor Sum（ARC066 D）

ABCで桁DPが出たので復習して過去問を解き直していたら、こいつがAC済みなのに全然できなくて。

D - Xor Sum

a+bというのは、a xor bに(a and b) * 2を足したもの。足して繰り上がりが続くかもしれないが、値としてはそれ。あるu,vを生成するa,bは色々ありえる場合があるけど、a,bの各桁の値を足したもの（2まで許す2進法みたいなもの）は一意に定まる（uが1の部分は足して1だし、そうでないときは(v-u)/2が1のところが2で他が0）のでこれを数える。

以前は下から桁DPしたと思うので、今回は上から。

「2まで許す2進法」で、N以下のものを数える（値として同じでも表記が異なるものは別々に数える）。これを下の桁から計算して普通の2進法に直すことを考えると、繰り上がりは高々1。通常の桁DPでは、i桁目まで見て、i桁目以上がNと一致しているものの個数とNより小さいことが確定した（i桁目以上で比較してNより小さい）ものの個数を数えるが、今回は繰り上がりが0か1かという状態を追加する。

ここまでは、時間はかかっても止まることなく進むことができた。遷移をどうすればいいかが長時間見えなかった。桁DPは、配るDPなのか貰うDPなのかよくわからんところがあり、配ったつもりだけどちゃんと貰うべき人は全員貰っただろうかとか、（今回は違うけど）状態が排他的でないときダブって渡してないかとか、不安になる。

条件からvはu以上。vはN以下なので、Nの最上位の位置が2になることはない。よってNの最上位（またはより上の位置）から、その上はキャリー0でNと一致するものが1通りで他は0通りという値からDPを始めればいい。下からのキャリーがいくつか、現在の桁が0,1,2のどれかでforを回す。それらの情報から、普通の2進法に直したとき現在の桁が何になるかとキャリーがいくつになるかがわかる。これらの情報で遷移できる。普通の桁DPと違うのは、Nより小さいかの判定に2進法に直したあとの値を使うこと、遷移先（現在位置）の情報から遷移元がどこかを求めていること。

キャリー0,1と、Nと一致・Nより小さいという状態で、排他的になっている。Nと一致とかNより小さいとかは一旦無視して、現在位置からのキャリーがc0で下からのキャリーがcならc0からcへの遷移になる。貰うとか配るとか考えなくても、DAGの辺を過不足なく列挙できていればいい。最後は、最下位より下からのキャリーはないのでキャリー0の（Nと等しいのとNより小さいのの）和を出力する。

ABC465

ABCDFの5完。Eも7分遅れなので悪くない。Fからやった判断は結果的にも良かった。

Fまでやって、特に実装が重いと感じた問題はなかった。重いと感じるならお前が悪いという感じ。桁DPできないのが悪いかはおいといて。

A - Supermajority

そのまま書いてから両辺に3を掛けるみたいな感じ。

解説マジかよと思ったけど、誤差が気になるのは両辺が等しい場合だけで、等しいときは整数になるから誤差は出ないのだった。

B - Parking 2

そのまま半開区間で考える。3時から5時までは、3時からの1時間と4時からの1時間として考える。あとは[A, B)でforを回すだけ。解法はすぐ見えたが、入力が多いので時間がかかった。例えば、料金の制約を確認しに問題文に戻ってどこを見ればいいかわからず自分が何をしようとしてたかもわからなくなりしばらくフリーズするなど。

C - Reverse Permutation

愚直にreverseしたら間に合いませんよという問題だが、サンプルを見てもけっこう乱雑な結果になりうるし難しい（サンプル3まで見れば気づいたかも）。「はいARC」って言った。後ろから考える。最後に反転するのがk=9のときだった場合、9は先頭に来る。k=8で反転がなければそのまま先頭から9,8となり、k=7で反転していたら...,7,10,11となる。区間を持って反転でswapして埋めていく。1個埋めたら区間を1縮める（相手に近づける）。

dequeを使って解いた人を見たときずるいと思った。当然、それを思いつけなかった俺の負け。

D - X to Y

最初に思ったのは、同じくらいの大きさになるように揃えたらあとは1回みたいなの。難しそうなのでK=2で考えてみる。本当はK=3で考えたい。2だとかなり小さくて特殊なことが起こりそうだから3のが安心できる。でもそんなこと言ってられないくらい難しい。操作が可逆であることに気づく。（グラフで考えるかは別にして）グラフとして見ると無向グラフになっている。で、K=2だとこれはセグ木だ。「揃えたらあとは1回」ではなかった。K=3も試してみると、これも構造は似ている。ただし、K=2のときは1が根みたいな感じだったけど、K=3だと0が根でそこから1と2が出ている（正確には0から0へ行くことも可能で、0の次数はKになっている）（このときは、X,Yは1以上だと勘違いしていた）。最初はX,Yの大小で場合分けとか考えてたけど無向グラフだからswapしてもよくて、歩み寄るという形でもいい。LCAを求めろみたいな問題になって、できるけど面倒だなって思って、XとYが異なるあいだ大きい側が上に移動するという実装に。

E - Digit Circus

桁DPに見えるし条件がかなり複雑に見えるので飛ばした。

Fを通して戻ってきた。包除でできそう。3の倍数を数えるのは簡単。3で割ればいい。まず3で割ったあまりをもとめてそれを引いてから割れば求まる。3が含まれるとかも、10^100以下で3が含まれない個数は簡単だろうし、3種類の数字を含むというのも包除でなんとかなるだろうと思っていた。しかし書こうとしてみるとできない。ましてや条件を組み合わせたものなどできる気がしない。改めて問題を見てみると、普通に桁DPでできる。カス（また桁DPとかいうつまらん解法の問題を出したのか期待して損した）。

3の倍数かについては、3で割ったあまりを状態として持てばいい。3が含まれるかは、含まれるかどうか2通りの状態を持てばいい（あとで必要ないことに気づいた）。3種類の数字については、使った数字の集合2^10通りの状態を持てばいい。自分のブログから「桁DPでn以下の非負整数の個数を求める」コードを持ってきて、遷移コードを追加する。次の桁にdを追加したら3で割ったあまりはどうなるかなどを計算してそこへ配るDP。サンプルが合わず、000123に含まれる数字は4種類ではなく3種類としなければならないことに気づく。下からやってるのでけっこう難しかったが、集合に含まれた0を、0以外の数字が追加されたときに初めて認証するという2通りの状態を追加することでいけた。それでもサンプルが合わず時間切れ。元のコードがllだったのをmintに直し忘れていたのが原因だった。

F - Sjeltzer?

xとyの間。どうすればまとめて計算できるかと思っていたが、素直に6次元だと考えると超立方体の中の総和だから単に累積和だ。高速ゼータ変換すればいい。ただ、実装がきつい。6重ループを書けばいけるのだろうがそれは選択肢にない。2進のときの高速ゼータ変換のコードを持ってきて10進に改造する。やはり高次元は想像しづらいので、できるはずなのにコードが書けないという混乱。それでも、6周するうち1周目と2周目を丁寧に合わせてでっちあげていく。累積和ができたのであとはクエリに答えるだけ。まず幅が0以下のものははじく。超立方体の中の総和は、適当に包除すれば合うはずでここはまあ（理解度はともかく）気楽だった。サンプルが合わず、包除の符号を使い忘れたのと、Sから読むとき添え字をi,j間違えてたひどいミス。計算量は11^6*2^6*6で10^8くらいなので大丈夫と思ってたけど今計算したら6.8*10^8くらいで思ったよりでかいな。と思ったら計算式が間違っていて、11^6*6+3*10^5*2^6*6だから10^8程度だ。こんなんでACしてるんだからな。

ARC136のDで似たことをやっていたらしい。ブログを見るとよくわからんけど当時の自分のがちゃんと考えてそう。