最近は、AtCoder Problems を利用して、水Diff以上のRatedの問題をSolverの多い順に解くということをしていました。 とりあえず 100 問解けました。99番の Range Set Query 以外は自力でときました。 Range Set Query も当時コンテスト中に想定解を思いついていたみたいですが、今やってみたら何も思いつかなかったんです。
解けない問題が自力で解けるというのはやっている側からしたらめちゃくちゃ嬉しいことで、自分の力にもなると思います。 ですので極力解法は調べないでじっくり考えようというポリシーでやりました。 今はSolver順に解いていっていますが、じきに問題が難しくなると考えられるので、それが難しくなってくるかもしれません。 今の所そういう場合どうすればいいか考えかねてますが、解法を見るのは少し味気ないというか、せっかくならその問題に もっと向き合いたいと思うわけです。でも飛ばしたら飛ばしたで、いつその問題に触れるのかということにもなります。 でも飛ばさないと他の問題が解けないということにもなるので、そこらへんはちょっとシステム化したいなと思いますね。 程よい考察で解ける問題を解いて、解けなかった問題を解く、というようにできれば理想ですがね。
んで今回は、問題を解けても自分は忘れるので、解いた100問について一言だけでいいので振り返りたい。 難しかった問題や、驚いた問題、自力で解けなかった問題は少し長めに振り返りたい。 衝撃度ランキングみたいなのを貼ってみたい。10問程度。 解いた問題数が100溜まったらまた一言コメントをつける。 難しくなると 50 単位とかでやるかも.
Solver が8893人から 4034 人までの問題でした。
大したことはない。next_permutationで順列を作ってそれぞれ行けるか調べる。
これは面白いと思う。自分は $2019$ で割ったあまりをテーブルにしてDPを作ったが、危険な計算量。 考えてみると、$U_i$ ... $i$ 文字目以降の文字列の整数を $2019$ で割ったあまりというものを作ると $U_i = U_{j+1} \ (1 \leq i \leq j \leq N)$ のときに条件を満たすようだ。
たしかに $U_i - U_{j+1} = 0$ なので、$i$ 文字目から $j$ 文字目の値の $10^{N-j+1}$ 倍の値については 条件を満たす。じゃあ $10$ 倍していったことであまりの数が変わらなかったのか？という疑問が生まれる。 でも、そもそもその $i$ から $j$ までの文字のあまりが $0$ じゃなかった場合というのは、 いくら $10$ 倍しても あまりが $0$ になりえない。これは $2019$ と $10$ が互いに素だからだ。 というのも互いに素ならそれぞれの素因数を全く含まないということになるので、この場合 $10$ をいくら掛けても、$2019$ が約数になることは絶対にないということで説明できると思う。 すると、 $U_i - U_{j+1} = 0$ になるのは、$i$ 文字目から $j$ 文字目までのあまりの値が $0$ でなければ おかしいということになるので、同値であることを説明できる。
同じ値になるようなものを探すことについてはmapを使って、過去に何回その値が出たかということをカウントする ことで $\mathrm{O}(N \log N)$ でいける。
これと同系統の問題は実は この自分のブログ で一回説明している。ABC158の Divisible Substring という問題。
奇数を別の色に変える。偶数を同じ色で塗るというのをdfsでやる。
最も長い丸太の長さ $T$ をあらかじめ決めているなら、その中で最も切る回数を少なくする切り方は、 できるだけ 長さ $T$ の丸太をつくることだろう。 $T$ を大きくすればその分切る回数は単調に減少するため、二分探索ができる。 しかも、今回は小数点以下を切り上げるということなので、整数について調べれば十分。
ちょっといやーな問題。コンプリートする難易度を予め決めればいい。 決めたら、あとは難易度の高い問題を解けばいい。 ただコンプリートするって決めてないやつもあとからコンプリートすることがあるということもあるので、 別に計算に入れなくてもいいけど入れないとなんか気持ち悪いような気がする。
日にちが迫っている方から見ていって、候補をpriority_queueに入れていく。 その中で一番報酬が得られるものを貪欲に選択するという方法を取る。 これはどうやっても最善である。 最善にするために選ばないといけないアルバイトを選ぶときに、 迫っている方からやると、あとから取らなくて済むから最善になるみたいな考えかと。 ちゃんと証明できないー
それか、DPみたいな、小問題化できる性質が貪欲にはあるのかな？ 期限が 1 日しかないならその 1 日の中で取れるものの最大を取るのは最善。 2 日になったとき、その残り 1 日の方に入れられるものは増えないから 明らかに 残り 1 日でも行けるようなものはそっちに入れておけば良いみたいな。
$i < j$ のときに $A_i$ のある bit が 1 のときに、$A_j$ のそのbitは反転する。 今回は別に桁上がりとかはないので、桁ごとに予め 1 の数を調べておいて、 $i$ について反転するか見て、ほかの $j$ の 1 の数というのを高速に求めて計算すれば解ける。
ちょっと難しかった。切るところというのは左から見ていったときにはできるだけ右にというのはわかる。 ただ切ったあとに切ったと認識できるかというところが問題だった。 でも考えてみると、そのようなものは左端が切ったところよりも左にあるから、 それで判断するだけだった。 やり方は右端でソートして左端を見て切ればいいか調べ、切るなら最も右で切るということをする。
知っているのと知らないとではちょっと計算量が変わる。 実はBFSで解ける。queue ではなく dequeを使うことでコスト０のものを先頭に入れるようにする。 すると、dequeの順はコストの小さい順を保つことができるので、BFSが可能。 隣接するところをコスト0にして先頭へ、ワープを使うところをコスト1にして末尾へ。 これで解ける。ダイクストラでも通るんだっけこれ。ちょっと怖いよね。
アンバランスな文字列には必ずある過半数を占める文字 x があったとすると、 "xx" か "xyx" のようなものが含まれる(yはx以外の文字)。 なぜなら、たとえ一番xの数(xcntと呼ぼう)が少ないもの xcnt = (N+1)/2 個だとしても、 まずxが隣接しないようにするために作られるものが、"xyxyxyxyxyx" しかない。 このとき"xyx"になっている。 そして"xx" や "xyx" 自体もアンバランスなので、それだけ探して見つければ終わり。
問題自体は単純なのでやり方さえ見つければACできるけど、ちょっと分かりづらい。 でもこれでとける。 1桁目を見て 奇数だったら 0 にして引く。 これをとっておく。 次に値を-2で割る。そして同じことを繰り返す。 確かに2進数のやり方がそのまま -2 になっただけだ。 確かに現在の1桁目の1をどうにかするには1引くしかない。こうすれば次の桁について貪欲的に 考えられるわけだ。
人 $i$ を見たときに連結している人の数から、友達関係を除いてブロック関係を除くという単純なことを すればいい。まずユニ木に友達関係全部いれて、人 $i$ の接続している集合のサイズを人ごとに入れていく。 そのあと、友達関係の $A_i, B_i$ をそれぞれ答えから引く。 同じく、ブロック関係の $C_i, D_i$ も引く。これで答えを作れる。
逆からやる。全部崩落させて、$M$ 番目の橋から復活させる。 このとき $i$ 番目の橋を復活させると、$A_i$ の属している集合のサイズと $B_i$ の属している集合のサイズ の積だけ不便さが復活する。そのあと $i$ を連結する。 例によってそのような集合を持つデータ構造はユニ木なのでそれで解く。 最初の全崩落の不便さは $_N\mathrm{C}_2 = N(N-1)/2$ っす。
実は $Z_i$ は関係ない。$1$ か $2$ どっちを与えられるにせよ、 隣接した同士の値というのはどちらかが決まれば一意に求まる。 この問題は連結成分の数を出力すれば終わり。
これをグラフのように考える。連結していれば、その中の値はスワップで自由に交換できる。 そこで、その連結成分の中の順列の番号とノードの番号で重複しているものの数を求める。 これを書く連結成分ごとにやると終わる。
ある程度は列と行を独立して考えられる。答えも、爆弾が一番多い列と行のもの以外にはない。 ただ、そのような列と行を選ぶとき、重なる１マスに爆弾があると、重複して数えているので -1しないといけない。そこに気をつけながら答えが-1されるかされないかを慎重に判断しながら やる。
$K$ が小さいので、累積和DPでいもす法のようにやる。
赤い点を一番下のものから見ていって、このときに条件を満たす青い点の中で一番左のものをとっていけばいい。 #000006 の Summer Vacation のような解が成立する。 そのようなものを下の赤い点がとっても、上の赤い点は何も文句ないとおもう。
合成魔法を使うのは一番最初でもコストに影響しない。 それぞれの竹について、Aに合成するか、Bに合成するか, Cに合成するか, 合成しないかの4パターンがある。 そのため予めどれに合成するかを決めて、あとは延長と短縮を適切にして全探索。
$dp_{i, r}$ ... $i$ 桁目までで生成できるあまり $r$ のものの総数を考えると、 各桁でどう $r$ が移動するかを適切に表現するとできる。
最初のデータを正にするか負にするか決めて、足し上げていき、 符号が異なったら、負にしたい場合 $-1$ , 正にしたい場合 $1$ にするようにする。
これも貪欲の一種だと思う。$i$ を走査するとき絶対に処理しないといけないからこうなる。 $-1$ より小さく, $1$ より大きくしても良いんじゃないかと思うかもしれないが、 それはあとに遅延しても操作回数は変わらないから後でやっていい。それに余分なことになることがある。
現在のそれぞれの得票の最小として考えられるものに対して、 $T_i$ , $A_i$ を何回かければ現在のそれぞれの得票数以上になるかを見れば最小で矛盾しない。 そしてそのような得票を新たな値として持つ。
自分はカードを何枚選んだかも持つDPをやったが、実は、$x$ に対して $A$ を引いちゃえば、 総和が $0$ になるかどうかで全部判定できるみたいだった。そして昔はやっていた。ちょっと悲しいね。
左から取り出す数と右から取り出す数を決めたらそのあまりを負の宝石を捨てる(筒に入れる)動作に使う。 すると全通りためせるので、全探索する。 途中で戻しても意味ないのはわかるだろう。
現在の 金貨, 銀貨, 銅貨 の数を持って、そこに遷移する確率を持つDPを考えると解けるみたい。 最後に操作回数と掛け算して解を取り出す。ちょっとdoubleの答えが合うのかが怖い。
切り方が横にすべて寸断するものと、縦に切ってから横に切る。というものを縦横反転させたもののパターンしかない。 これをうまく実装する。大体1/3に切る辺りのところに答えがある。 縦に切ってから横に切るパターンについて想定解は縦に切るところを全部見ていたが、 自分は切る位置が $W/3$ か $W/3+1$ 以外ないと見ていてこれについて求めたらACした。 この解は $\mathrm{O}(1)$ だけど、嘘解法だったりするのだろうか。
操作1, 2, 3 を決めると 操作 4 が決まることがわかるのでこれで全探索。単にやるだけでも通るかな？ とにかく実装が大変。砂糖水の質量が $F$ [g] 以下という制約がめんどくさい。
$l$ を決め打ちすると、どこまで $r$ を伸ばせるかが決まる。つまり $l$ を左端にするときの個数は $r-l+1$ だ。 そして、 $l$ を大きくすると、 $r$ も大きくなるので、尺取りができて、$\mathrm{O}(N)$ となる。 $l$ や $r$ を増やす動作が $\mathrm{O}(1)$ でできるのも重要なところ。
$i$ を小さい方から見るとき、まず $i=1$ は答えがわかる。 $i=2$ は、数字が $A_1$ より大きければ、その色で塗ってしまっていい。 このさきその色で $A_2$ を塗ってしまったことで新たな色を塗らなければならなくなったときも、 実は$A_2$ を違う色で塗ったときと状況が変わらない。ならば同じ色で塗ってしまっていい。
そしてそのようにして色についての現在の状況(各色について塗った数列の最大値)というのが出てくるわけだが、 新たな色が出てきたら、その塗れる色の中で、一番大きい値のものを選んでしまっていい。塗れない場合は新たな色を作る。 これも同じような理由で説明できる。新たに塗っても既存の色で塗った場合とスワップできるし、 他の値の小さいもので塗ったらただ状況が悪くなるだけである。
というようにして、現在の色の状況を逐次保存しておいて、先の述べたような動作を行えばいい。 これはvectorをソートしながら持つと、塗れる色の中で一番大きいものと言うのが二分探索で調べられるので、 調べたところを新たに値を塗りつぶして処理する。$\mathrm{O}(N \log N)$ で終了する。
実は、この問題は、LDS(Longest Decreasing Subsequence) つまり最長減少部分列と同値の解になっている。 解法はそれぞれ色々方法、やれることも違ってくるはずなのに解だけピッタリと合うとはかなり不思議ですよね。 こういうのって双対っていうんだろうか？（にわか）
実はTopCoDeerくんがどんな手を出そうと、最大化の手法に影響を及ぼさない。 単にこっちがパーを出すとグーを出すより $1$ 点増えるだけである。 ということは、グーを $(N+1)/2$ 回出してからパーを出し続ければおわり。 あとは得点がどうなったかをしらべるだけ。
難しかった・・・。中央値の位置を調べるために特に偶数では２つの値が必要なわけだが、 この２つの値それぞれに取りうる範囲があるので、中央値として考えるよりも、 左から $k$ 番目の値の取りうる範囲について一般的に考えてみたい(これは解けてから言えることだけど)
まず、左端で昇順ソートしたものの $k$ 番目の位置からなら $k$ 番目の値はは有り得そう。これを $l$ とでも。
同じく、右端で昇順ソートしたものの $k$ 番目の位置までなら $k$ 番目の値が有り得そう。これを $r$ とでも。
そして実は、その範囲 $[l, r]$ 全てにおいて、$k$ 番目の値はあり得る。
まず $l$ の地点は、左端が $k$ 回カウントされた地点である。
そして $r$ の地点は、右端が $k$ 回カウントされた地点である。
よく考えると、$l$ と $r$ の間に $k$ 番目の値がありえない範囲があるとしたら、
どの範囲にも入っていない( $[A_i, B_i]$ に含まれない)ところということになるが、
そのようなところは、すでに右端が $k$ 回カウントされていることになる。
すると仮定が矛盾しているので、$l$ から $r$ まで使えなきゃおかしい。これで証明できる。
ちなみに、 $l$ , $r$ の中である範囲に含まれているところは適切に位置を交換することですべて $k$ 番目の値にできる。 これもわかってないとさっきのを証明できないけど。
答えは、まず奇数では $k = (N+1)/2$ にして $r-l+1$ だろう。
そして偶数では、
$k=N/2$ のほうで出たものを $l_1, r_1$, $k=N/2+1$ の方で出たものを $l_2, r_2$ とすると、
取りうる平均値は、$(l_1+l_2)/2$ から $(r_1+r_2)/2$ までで、すべて $1/2$ 単位で取れる。
そのため答えは、$(r_1+r_2)-(l_1+l_2) + 1$ となるだろう。
この $l$ から $r$ まですべて $k$ 番目の値として含まれるということが非自明で、 最初は範囲がかなりバラけると思っていたから、$N$ が偶数のとき $\mathrm{O}(N^2)$ じゃないかと思った。 でもここまで考察できれば、連続していることに気づくのも時間はかからないのかなー？
まず木の辺の中で一番重みの少ないところに関してはその辺をつなぐ頂点同士以外に $f$ がその重みになることはない。 そのような辺を Unionfind でつなげてみる。これがすでに計算済みという証拠になる。 つぎに、その次に小さい辺...と見ていく。このとき、つながっている頂点を $u, v$ とすると、 $u$ の連結成分と $v$ の連結成分をまたぐもの同士の最短パスの重みの最大値がその辺の重みになる。 したがって、 ($u$ の連結成分の大きさ) と ($u$ の連結成分の大きさ) の積に重みを掛けたもので計算できる。 そしてまた $u$ と $v$ をuniteする。というのを $N-1$ 回に渡ってやれば答えが求まる。
私は、それぞれのケーキの美味しさの合計が $X$ 以上になるものの数を二分探索でしらべて、 $K$ 以下の数が出る $X$ の最小値をしらべて、まずそのような条件を満たすものをソートして並べて、 最後にケーキの選び方が $K$ になるまで $X-1$ を入れまくることでACしたが、 そんな事をしなくても、美味しさの大きい順にそれぞれケーキを並べて(その並びをそれぞれ $a, b, c$ という数列で表すとする)、 最初は $a_1+b_1+c_1$ を選んでおいて、このときに priority_queue に $a_2+b_1+c_1$ と $a_1+b_2+c_1$ と $a_1+b_1+c_2$ を 入れて、その最大を選んでいく。そうしたらまた選んだものの近傍を入れるというふうにするだけで良かったみたい。 たしかにこれ $ \mathrm{O} (K \log K)$ で終わるじゃんとなった。
ある位置からある文字が出てくる一番左の位置がどこかをとっておく。 これを $t$ に対して位置を動かしていくと、OK. 何回 $s$ をループ( $loop$ )したかを数えて 最終的な位置を $pos$ とすると $|s|*loop + pos$ が答えになる。
$a_i$ に関しては、素数でかつ、 $5$ で割ったあまりが $1$ になるものを集めてきてその数列を出力すればいい。 $55555$ までの数字の中でしっかりそれは $N$ 個以上見つかる。
もちろんDPで調べて解けるが、やりすぎ。 実は、数列を $201$ 個みつけてくれば、どれか $200$ で割ったあまりがダブる。これを鳩の巣原理というらしい。 $N \geq 8$ なら、先頭 $8$ 個の中の数字を使うか使わないかで合計 $255$ 個の数列が出来上がるので、 答えは間違いなく "Yes" であるし、ダブったら数列を出力するだけ。 ダブったら数列を出力するだけなのは、 $N < 8$ でも同じ。なかったら "No" .
個人的に一番ビックリしている。考えてみればたしかにそうだよなとなった。だいたいそうか。
二次元累積和。添字は左端と右端。 具体的には $L_i, R_i$ があるとき、$L_i$ 以下である左端と $R_i$ 以上である右端の部分をすべて $+1$ したい。 これは２次元配列にするとき、ちょうど正方形になるので、正方形に足すようにいもす法を利用すれば終わり。良問。
これは答えに合うように計算を合わせていくとちょっと大変になる。大変だった。 この場合桁DPというのを使うと楽にやれる。
今回の場合、 $dp_{i, j, k}$ ... $i$ 番目の数字を処理していて、 $j$ 個だけ $0$ じゃない数を入れてきたとする。 $k=0$ ならすでに現在の桁をどれだけ大きくしようと問題ないようになっているようなもの、 $k=1$ ならずっとありえる最大値をとってきた状態(つまり$N$のその桁の値よりも大きいと$N$より大きくなってしまう) を保持する。 このときのありうる通りの数を考える。
桁DPは、$N$ を超えないようにするやり方をみつけるのに、 $2$ 倍配列を用意するので十分なので、 そこまで複雑にならずにDPできると言える？
いやーな二分探索。何進法でやるかを決めて $M$ 以下かどうか。というか大体は二分探索しなくても間に合うと思う。 例えば、 $X$ の長さが短いとなかなか $M$ を超えづらいので値が大きくなる。 まず $|X| = 1$ なら何進法でもずっと値は変わらないので、その値が$M$以下かどうか調べる。 ほかのパターンはオーバーフローに気をつけながら何進数まで行けるか調べて頑張る。 オーバーフローに気をつけながら。オーバーフローの判断って一回値をdouble にして LLINF よりでかいか試せば いいかな。
$dp_{bit}$ ... 現在宝箱が $bit$ 開いているときの費用の最小値を考える。 それぞれ $M$ 個の鍵について遷移を書いて最小を求めていけばいい。 特にひねりもないbitDP。今だったらどのくらいのDiffなんだろう。
$A_iB_i$ は数列 $A$ の最小公倍数である。これをどう求めるか。 $A_i$ を素因数分解して、それぞれの素数が何回掛けられたかを持っておく。 これの掛けられた各最大値が、最小公倍数の素因数になる。 これを Modint を使ってかけて、あとは、$A_i$ で割ったものを $B_i$ として出力する。 ライブラリがないと逆元を求める必要があり面倒。
最大値は、綺麗さの合計の符号と、美味しさの合計の符号と、人気度の合計の符号が一意に定まったまま出てくるので、 ３つの合計が、最終的にどっちの符号になるのかというのを先に決めてしまって、 その中であるケーキの合計値が大きい順に食べるということを調べて、一番大きいものを出力すればいい。 ８通りしかないので $\mathrm{O}(N \log N)$ である。
$a$ の要素すべてを $2$ で割ったものを $b$ とすると、半公倍数の定義は
$X = b_k \times (2p+1)$ を満たす負でない整数 $p$ が存在する
と置き換えられる。つまり $a$ の半公倍数は $b$ について奇数でかけられていないといけない。
そのような $b$ は、$b_i$ と $b_j$ があって、それぞれの末尾ビットの位置がずれていると半公倍数は存在しない。 そういうものは、それぞれ公倍数をとったときにどちらかが偶数をかけることになるからである。 ということはすべて末尾ビットの位置が同じものについて見ればいい。このとき $b$ の最小公倍数と $a$ の最小半公倍数は一致する。 そしてその $b$ の最小公倍数の奇数倍のものが半公倍数になる。これを $M$ 以下までになるように個数を計算すればOK.
発想は思いつきやすいが、詰めるのが難しい。特に末尾ビットの部分とか。
$x$ でソートしたものと $y$ でソートしたものを用意する。 そして、それぞれの隣接した頂点同士の辺以外は見なくていい。 隣接してないものを選んでも、隣接したもの同士でつなげていけば結局そのコストで繋げられるからといえば なんとなくわかるか。実際はminを取るので小さくなることがあるが、そのときはもう片方のほうを見ると同コストかそれ以下で繋げられることがわかる。 辺を選べたらクラスカル法で調べて答えを得る。
$\sum_{X \in S} f(X) = \sum_{X \in S} \max X - \sum_{X \in S} \min X$
というように独立して考えられる。 するとある $A_i$ が ある数列の最大値だったときのパターンの数を列挙するというのを各 $i$ にやって最大値側を。 最小値側も同じようにやると答えが求まる。 これを高速にやるには、$A$ をソートして例えば最大値側だったら、$\sum _{i=1}^{N} ( _{i-1}\mathrm{C}_{K} \times A_i)$ となり、 最小値側だったら、$\sum _{i=1}^{N} ( _{N-i}\mathrm{C}_{K} \times A_i )$ となる。 これを最大値側から最小値側を引き算して答えを得る。
左上からある位置まで行ってある道を通って、右下へ行くということを考える。 このときに、移動できないところを避けるようにして二項係数の積で求めていく。
ある位置に何人も人がいていいので、相対位置だけ考えればいい。そうしたら、この問題をグラフの問題と考えて、 それぞれ進んだり戻ったりして、矛盾がないかを dfs で調べ上げればおわり。
ある隣接するブロック同士が異なる色であるようなとき、そのブロックの間に囲いがあるとする。 この囲いのおける位置は $N-1$ 個だけ存在する。 もし同じ色で塗られている組が $k$ 組だった場合、異なる色で塗られている組が $N-1-k$ 組となるので、 囲いのバリエーションは、$_{N-1}\mathrm{C}_{N-1-k}$ 個だけあるわけである。 その時の塗り方の総数は、 $_{N-1}\mathrm{C}_{N-1-k} \times M \times (M-1)^{N-k-1}$ となり二項係数ライブラリで速くもとまる。 これを $K$ 以下の各 $k$ に対して行ったら終わり。
全探索。適切にフラグを貼っていこう。そこまで変なことにはならないはず。
自分はクイーンの移動を飛ぶと表現して、右に飛んでいるときに状態が1, 下が2, 右下が3になるようなDPをした。 飛んでないときは0. 答えは飛んでなくて $(H,W)$ にいるときに収束される。
bitDPで現在位置と移動した都市のフラグを持ちながらやればOK. ふつうの巡回セールスマン問題。
もちろん座圧。 寺と神社の座標にLLINF, -LLINFを入れておくと楽。 どっちも西にあるか、東にあるか、 あるいは西に行って東に行くか、東に行って西に行くか。 これを丁寧に条件を調べ上げて、最小の移動距離を求める。 $\mathrm{O}(A \log A + B \log B + Q\log AB)$ とかになるのかな。
Warshall Floyd で最短距離を求めてから、順列のあり得るパターンで街の行く順番を決める。 これで解ける。
約数系包除の最たる問題。$\mathrm{gcd}$ が $div$ の倍数であるようなものの総数と言うのはすぐに見つかる。 これは、$(K/div)^N$ となるはず。 これに対して、単純に $div$ をかけたものを足すと、$div$ 以外の $div$ の倍数の $\mathrm{gcd}$ を 持つものも含めて足してしまっている。 もし $div$ を小さい値から見ていくとすると、現在の $div$ で $div$ の倍数に対して足した数を求めておけば、 その後で、あとどのくらい足せば良いのかと言うのがわかっていく。そして全体の答えが求まる。
これも少し誤読していて、文字が異なるならば数字も異なるという制約がないと思ってしまった。 入出力例を見るのでも、誤読は防げることがある。 数字が異なるなら、文字に数字を割り当てるために、文字の並びの順列を作って一つ一つ試せばいい。 アルファベットの種類数が11文字以上あったら絶対に解けない。 10! = 3628800 くらいの計算で済む。
典型的な二分探索。爆発回数 $num$ を決めたらすべての魔物のHPを $B \times num$ だけ減らしておけばいい。 あとは、すべての魔物の体力が減るまで $A-B$ で殴り続ければいい。 倒しきれなかったらng = num, 倒せたらok = numです。
まず $N!$ を素因数分解することを考える。これは単に $2$ から $N$ まで素因数を求めて(cnt[p] みたいなのにカウントする形で)、 それを全部足しあげれば完成する。
ところで、約数が $75$ 個あるような数というのはどういうものかというと、
まず素数 $p$ があるとすると、 $p^{74}$ が該当する。
また、異なる素数 $p_1, p_2$ があって、 ${p_1}^{24} \times {p_2}^{2}$ や ${p_1}^{14} \times {p_2}^{4}$ 。
また、異なる素数 $p_1, p_2, p_3$ があって、 ${p_1}^{4} \times {p_2}^{4} \times {p_3}^{2}$ がある。
これは、ある素数のべき乗 $p^k$ において、約数の持つ数が $k+1$ 個あり、各素数ごとにそれが独立しているためである。 たとえば先に上げた ${p_1}^{4} \times {p_2}^{4} \times {p_3}^{2}$ であれば、$p_1$ に対して $5$ 通り、 $p_2$ に対して $5$ 通り、 $p_3$ に対して $3$ 通りあり、 $5 \times 5 \times 3 = 75$ 通りとなる。
ならば $N!$ に対して、そのような作り方がどの程度あるのかを調べなければならない。 仮に、$N!$ についてある素数 $p$ のべき乗が $74$ 個以上あるようなものを $cnt_{75}$ とよび、 同じような定義で $cnt_{25}, cnt_{15}, cnt_{5}, cnt_{3}$ について定義すると、
まず $p^{74}$ があるような数は $cnt_{75}$ である。
次に ${p_1}^{24} \times {p_2}^{2}$ については、 $cnt_{25} \times (cnt_3 - 1)$ となる。
上の式だが、まず $24$ 乗にできる素数を探す。その後 $2$ 乗にできる素数を探す。このとき、$24$ 乗にできる素数というのは
$2$ 乗にできる素数でもあるので、先に選んだものと同じにならないように $-1$ しないといけない。
同じく ${p_1}^{14} \times {p_2}^{4}$ は、$cnt_{15} \times (cnt_5-1)$ となる。
最後に ${p_1}^4 \times {p_2}^4 \times {p_3}^2$ は、
$$ \frac{cnt_{5}(cnt_{5}-1)}{2}(cnt_{3} - 2)$$ となる。
$p^4$ の因数が２つあるのでこの２つは入れ替えても区別がつかないので /2 するという図式。
これらを足し上げて答えを完成させる。面倒臭すぎるでしょ。計算量は $\mathrm{O}(N\sqrt{N})$ だろうね。最初のところで。 作り方の計算もこんな式で解くんじゃなくてちゃんとコンピュータを使わないとねとは思っている。
まずいちばん最初の状況で完食にかかる最大値を小さくしようとすると、メンバーについて昇順にソート、 食べ物について降順にソートしたもの同士を選ばせれば良い。
この際、チームの成績を $S$ 以下にすることを考えて、あるメンバーの消化コストを減らしたことで順序がおかしくなっても、 順序がおかしくなった時点でその原因のメンバーとスワップして次にそのメンバーの消化コストを減らすという処理に変わるような 動作が可能である。この際 $S$ 以下にするための修行回数というのは一意に定まる。 これは各 $i$ について $A_i \times F_i$ から何回修行すれば $S$ になるかを求めて加算していけばその修行回数になる。 そしてこれは $S$ に対して単調減少であるので、二分探索ができる。修行回数が $K$ 以下になる最小の $S$ を求めればOK.
$A_i = 0$ になるところで区切るような数列を考えると、実は数列ごとに、数列の総和/2はペアを作れる。 この一つの数列を $B$ と呼んでおこう。 サイズは $n$ とでも。
左からペアを作っていくことを考える。$i < n$ であれば、必ず $B_{i+1} \geq 1$ であることがわかる。 これを考えると、まず同じ数字でカードのペアを作り、$1$ 個余ったら右のカードとくっつけるという動作が可能である。 これを一番右までやると、結局 $1$ 個残るか何も残らないかのどちらかになる。これ以上の最善はない。
ということで、各数列のカードの数を調べてそれに対して $1/2$ したものを足し上げて答えとなる。
$1$ 番目の動物と、$2$ 番目の動物の種類を決めれば実はすべての動物の種類がわかるようになっている。 そのため、この $4$ 通りを試して矛盾していないかを確かめて矛盾してないならその種類を出せばいい。 円環状になっているので少し実装が難しいかもしれない。よくバグる。
苦手な問題！最善を尽くすゲーム系の問題。 あと絶対に $A_1 = 1$ を見逃してはならない。特殊な制約は問題の要である。
$dp_n$ ... 現在 $n$ 個石があるときの先手の人の最大の取れる数 というのを考える。 高橋くんは先手なので、$dp_N$ が答えになる。
まず$dp_0 = 0$ である。そして遷移を考える。 $dp_n$ について考えたいとき、まず石を取るという動作があるので、石 $i$ をとるとすると、 $n-A_i$ だけ石があるときの事を考えるわけだ。仮にこれを$prev$ と呼ぼう。 だが、このときの $dp_{prev}$ というのは、相手の値になっている。でも今回は自分の値について考えたいので、 そのときに自分がとっている数というのは、$prev-dp_{prev}$ であるはずだ。なぜなら今回は、$A_1 = 1$ であるため、 必ず石を取りきって終了する。このとき、ある石の個数とったほうのもう片方はとってない方を全部とっていることになるためだ。 そのため、このような$prev-dp_{prev}$ の値に新たに $A_i$ を足した値を $dp_n$ に入れる。 そしてそのような $i$ は複数あるので、
$dp_n = \max\{ (n-A_i)-dp_{n-A_i} + A_i, 1 \leq i \leq K, A_i \leq n\}$
というような遷移ができる。これはどっちも最善を尽くした結果となる。 あとそもそも、$A_i > n$ であるようなものは遷移の段階で配列外なので、あまり制約は気にしなくていい。
構築系の問題はやっぱり苦手だなぁ。ただ、思いついちゃいさえすれば出力するだけというのもある。 入力が少ない場合や入力が関係ない場合に限るけど。 これは、$10000, 20000, ..., 990000$, と、 $100, 200, ..., 9900$ と、 $1, 2, ..., 99$ を用意できれば、 それぞれからとっていくと $10^6$ まですべて網羅できる。これは $297$ 個の数列で $300$ 個以下である。 $1000000$ については数列に入れなくても、 $10000$ と $990000$ を合わせれば作れるからOK.
数字の小さい方から累積和すればOK.累積和するときは $D$ だけ飛ばす。だから合計 $D$ 個の累積和ができるといっていいとおもう。 あとはクエリを $\mathrm{O}(1)$ で処理していけばいい。
根付き木を考える。ルートは適当に $1$ にでも。 木はあるところとあるところのパスがたかだか１こしかないので累積和が可能である。 今回はあとから累積和すると良いようないもす法を考える。
クエリを解析すると、 $a_{e_i}$ と $b_{e_i}$ のどちらかはルートを含む側、含まない側みたいな感じで区別可能だと思う。 含む側を足す場合、単にルートに $x_i$ たして、含まない側のノードに $x_i$ を引けば、含む側だけ足すことができる。 含まない側を足す場合、含まない側のノードに $x_i$ を足すだけでOK.
解説と同じことを言うようだが、連結グラフには $N-1$ 個の辺が含まれているのでこれらはすべて距離 $1$ であるため少なくとも $N(N-1)/2 - (N-1) = (N-1)(N-2)/2$ 個より多い最短距離 $2$ の頂点対は存在しない。 逆にそれ以下だったら、つくれる。 まずあるノードにすべてのノードがくっついているようなグラフを考える。 この最短距離 $2$ の頂点対の数はちょうど $(N-1)(N-2)/2$ になっている。これに対して 真ん中のノードを除く２つのノードに一つ辺を入れると、最短距離 $2$ の頂点対は一つづつ減っていく。 辺を入れる余地は $(N-1)(N-2)/2$ だけ用意されているので、すべての頂点対数のグラフが作れる。 今回は、これが $K$ になるまで辺を入れていけば完成する。
木なので、最善は相手への最短パス上を塗っていくことである。その他はあとから塗ればいい。 うまく白と黒の境界を見つけて、数を調べてどっちが勝者になるかを判定すればいい。
#0061 Stones を解いていると、あーこれもゲームDPだろうとなる。 ゲームDPで大事なのはちゃんとDPの定義を「先攻側が」にしておくことだ。 そうすれば、答えが返ってきたときはちゃんと求めたい先攻の人のものが返ってきてくれる。
今回は、$dp_{i, j}$ ... 座標 $(i, j)$ からゲームを初めて $(H, W)$ でゲームを終わるときの先攻の相対得点の最大値 というようにした。
相対得点は(先攻の得点)-(後攻の得点)というようにしておく。自分が+をとったら +1 される。-をとったら -1 される。 このようにしていけば $dp_{1, 1}$ が正なら高橋くんの勝ち。負なら青木くんの勝ち。０ならドロー。と表現できる。
基底条件と遷移だが、まず基底条件として $dp_{H,W} = 0$ だろう。逆からやっていく。 そして遷移。 $(i, j)$ にいるとき先攻の人は、何がしたいかというと、$(i+1, j)$ に移動したいか $(i, j+1)$ に移動したいかだろう。 移動したところでは後攻の人が得点を最大化させている( $dp_{i+1, j}, dp_{i, j+1}$ のこと)ので、これらの中で どっちに移動したら自分の得点を大きくできるかを考えたい。 まず自分の得点として考えたいので、相手の相対得点は符号が逆になる。そしてそれに対して自分が移動した先のマスの得点を足したい。 すると遷移は、 $$dp_{i,j} = \max{(-dp_{i+1, j} + point_{i+1, j}\ ,\ -dp_{i, j+1} + point_{i, j+1})}$$ となる。なお $point_{i, j}$ は、$A_{i, j}$ が+のとき $1$ で、-のとき $-1$ になるように設定する。 そして答えは $dp_{1,1}$ に返ってくるのでこれの符号を見て答えを出力する。
Stones を解いたあとだったのでアイデアもdp配列も思いついてはいたが、 ちゃんと先攻の人の答えが返ってくるのかと言うのがわからなくて辺に条件分岐させてWAを出していた。 でも $(1, 1)$ から先攻で始めるのは高橋くんだから良いのだ。
あと、ゲームDPは貰うDPのほうがなんか書いててわかりやすい気がする。あくまでも気がするだけど。 自分の番のときに相手の得点について考慮して得点を配っておくっていうのがよくわからないのかもしれない。
専門用語はよくわからないので、ゲームDPとでも名付けておきたい。実際そういう名前かな？
26個 BinaryIndexedTree を持てばいい。それぞれの文字において範囲にあるかどうかを $O(\log N)$ で判断すればいい。定数倍26. オンラインだからMo'sでは解けないか・・・ｗ
$A$ を左から累積和をとった数列を $S$ とすると、$S_r \equiv S_{l-1} \pmod M$ ならよさそう。 このようなものはmapをつかって見つければよいね。$S_0 = 0$ を定義しておこう。
頂点次数 $3$ かつ距離について $3$ より大きいのが呼ばれないのでただそれを愚直に探すだけだが、 調子こいてdfsでやると、最短距離じゃない移動方法でノードにアクセスしてフラグを立てちゃうときがあるので、 WAになる。ああ、でもフラグ建てなければいいのか。BFSなら確実なのでそれでやった。 いまdfsでといてみた。bfsより速いけど、なんか無駄なことしてる気がする・・・
条件が多いったら。まず置くマス $i$ を決め打ちして、シミュレーションすることを考える。 もちろん愚直にやったらだめだが、移動にはループがあるのでそれを使う。 まずループの中で一番山が高いところ、得点の総和が高いところを見つけてそこだけ重要視する。 あくまで $K$ がループ１回はできると仮定すると、 ループの総和が負なら、山の高いところが答え。 ループの総和が正なら、まずできる限りループさせて、最後のループの高い山のところに着目する。 あと、ループが終わったあとの残りの操作についてのシミュレーションでも最大を取る。 そもそもループまで $K$ がない場合は、愚直にやっても $O(N)$ で終わるので問題なし。
したがって $O(N^2)$ でこの問題は解けるが、いやだねぇー
ノートとか使うとやりやすい。まず $N$ が $K$ で割り切れなければずっと $-K$ されて終わる。 割り切れるなら即座に割り切れないところまで落ちる。 まず割り切れないところについては、要は $(N-1)$ だけ進めるやつだけということなるので、 $(N-1)$ の約数が該当する。たとえば $N=7$ だったら $6$ だけ進めるやつを考えたいので、 $K = 2, 3, 6$ などにすると、最終的に $1$ になってくれる。あと、$(N-1)$ の $2$ 以上の約数で絶対 $N$ は割り切れない。 だから $K$ が割り切れる方に入ることもない。
割り切れるものについては $N$ の約数が相当するが、これはそんなに多くないので、それぞれシミュレーションしておわり。 割り切れなくなったら $\mod K$ をかけて問題ない。
やり方は色々あるとは思うけど、自分は何個選ぶか予め決めちゃってそこからあまりを持ったDPをした。 これ $O(N^4)$ なんだよなぁ。でもなんとか間に合う範囲か。
これは書き方が大変なやつと簡単なやつがあって、これはトップダウンに書くとかなり楽にかける。$k$ を 0-indexed にしておく。 まず $k$ のビットが $1$ 立っているだけ2文字ずつ進むという特徴があって、$0$ だったら 1 文字。 これを $k$ を $1/2$ しながら進めていくと、$t$ のほうが $0$ になる場合と $k$ のほうが $0$ になる場合に分岐する。 $t$ の方だったらただ $S_{k+1}$ を読み出して、進んだ量に足せばいい。 $k$ の方だったら、$S$ としては $1$ 文字目確定で、それから $t$ だけ進んでしまえばいい。 まあ文字列の特徴の話はちょっとめんどいのでここでは言わないけど、それを聞けばこの話はわかると思う。
幼稚園ごとの priority_queue とトップの人の priority_queue(反転) を持っておけば変更したところをうまく処理してできる。
体力系を扱う問題は結構二分探索の比率が多いと思う。いもす法をがんばる。
半分全列挙。特になんの変哲もない。解説ページで $i-1$ までの集合を $A_i$ でマージするやり方を知った。 普通に解くと $O(N2^{N/2})$ だが、マージでやると $O(2^{N/2})$ になる。 マージ中にデータを何度も間引けるので、ランダムデータに強くて嬉しい。 ナップザックだともっと嬉しい。詳しくは 労働(Labor) という問題の話を書いてあるので。
それぞれの道路についての連結成分と、鉄道についての連結成分を手に入れるために Unionfind を 2 つ持つのはわかる。 これをどう扱えばいいかということだろう。このときmapに、それぞれのノード $i$ に対して、 (道路網の連結成分の番号, 鉄道網の連結成分の番号) を添え字にして足しあげればいいということがわかった。 これが一致するようなものはどちらも連結していると言える。 うーん、たしかにそうなんだろうけど、なんとなくわかったようなわかってないような。 道路に連結していてかつ、鉄道に連結している、という AND なんだろうなぁ。
テレポーターは最短距離で呼び出せれば、その後その文字については使う必要がなくなる。 そのため、テレポータに乗っていても、すでに使っていれば使う必要がないので $O(HW)$ で解ける。
横に切るパターンを決めてしまえば、あとはホワイトチョコレートが $K$ を超えるたびに切ればいいので $O(2^H HW)$ で解けたはず。
重ならないことに気をつけながらDPをした。解説を見ると Z-Algorithm で解いているようだが、おそらく計算量は変わらない。
$ \max \{ A_j, i+1 \leq j \leq N \} - A_i$ の最大の値のことを考えて、このような $i$ が何個あるかを調べる。 $1$ 個の場合はその $i$ を $1$ 上げるだけで利益が下がってくれるが、複数ある場合はこれらすべてに $1$ 上げる処理をしないといけない。
３つのインデックスを尺取りした。$i$ を左端にして、$X$ と $Y$ がでたとき(もちろん圏外の値が出たら成立しない) の一番左端を $l$, そして圏外の値が出るまでの位置を $r$ とする。 このようにするとき、各インデックスは右にしか動かないようにできるので、各 $i$ についての $r-l+1$ を足しあげればおわり。 実装がかなり疲れる。圏外の値のときの処理とかをやらないといけない。これが面倒。
ある町を始点にするとき、その町の1近傍の町から元の町に戻るような最短距離と元の町からその近傍の町のコストを足したものを最小化すればいい。 これは全点対最短経路を求めておけばよく、$N$ 回ダイクストラを行えばOK.
自分は桁DPでといたが、よくよく考えてみると、うまく貪欲をすれば解ける。ただうまくない貪欲だと嘘解法である。だがACしてしまう。
まず、例のごとくbitごとに考えていいのだが、例によっては上位bitで $X$ の値を大きくしすぎたことで、下位bit で使えなくなり、 最大化できない場合などがある。 だが、あるbit で $X$ を $1$ にできるが $0$ にしたとき、その下位bitから$X$ を自由に選べるという特徴がある。 そのためどのbitまで $K$ と同じ値のとり方をしてある位置で取らないかと言うのを決めて、 その後、下位bitについて値が大きくなる方を選択するという方法を取り、その最大値を取ればOK. 計算量は $O(\log^2 K)$ かと。
最短経路が保存されているとのことなので、都市 $i$ から $j$ に行くとき、$k$ を経由することを考えて、経由したほうが実は短かった場合は、 矛盾しているので -1 と出力する。同じだった場合は、$i$ から $j$ に行く道というのは必要ないのでそれを削除する。 これを長い道からやっていくと最終的には必要なものだけが残る。
矛盾してないなら最短距離がきちんと保存されているはずなので、経由する $k$ だけ考えればACするのかな。 ちょっと証明しきれていない。 でも最短路になってないような部分を経由してしまった場合とかって今思ったが、最終的におかしさが是正されるのかな。 次にそのようなおかしい経路を見ることになるから、結局どこかで矛盾があるかがわかって -1 になる。 矛盾のないデータだったらただただ最短路なので、必要な道だけとればいい。
頂点 $1$ を根とする根付き木を考える。根から値を決めるものとして、まず $K$ 通りが担保される。 このとき、その子となっている頂点同士は色が異ならないといけないので、これに対してすぐ塗るものとして、 $_{K-1} \mathrm{P} _{size} $ 通りだけある( $size$ は子の数)。このように、 現在の位置が経由地になるようなものについてみていく。
次に子に潜って行くわけだが、このとき、自分のノードとその親のノードについてはもうすでに塗ってあるので、 これらの塗り方を取り除いた塗り方というのはまたそのノードの子の数を $size$ と置くと、 $_{K-2} \mathrm{P} _{size} $ 通りだけある。そしてこれを答えに掛け算する。 これを繰り返してやっていくとACする。
これについても少し正当性がわからなくなっているが、もう塗ってしまって、次に塗るところを考えるみたいな。 確かに、順列の考え方も、選んで残りを選ぶみたいなのを繰り返して求めてるよね。 とにかく色が異なればいいのであれば、つまり選ぶ色によって特性などがないのであれば、塗ってしまっても良いのかな。
重みの状態数が少ない。重みをmapとかに入れてdpを解けばACする。 私が作った半分全列挙ナップザックでも、状態数が少ないのでマージしたときの状態数も指数関数にならないので 普通にACできる。状態数が少ないときにはこういうのでも解ける。 まあ半分全列挙の必要はないけど、全列挙ナップザックがあっても汎用性があれなんで。
$dp_{i,j}$ ... $A$ の $i$ 要素までと $B$ の $j$ 要素までについての新たな数列のコストの最小値
これについて考えれば、$A_{i+1}$, $B_{j+1}$ を取り除くときの処理と、どっちも取り除かないときの処理を適切にやっていけば解ける。
予め、動物 $N, 1$ に餌を上げた場合と、動物 $1, 2$ に餌を上げた場合を考えると、終わりの条件がはっきりする。 すると DP ができる。餌を上げてない左端の $i$ について、$i-1, i$ で餌をやるか、$i, i+1$ で餌をやるかということを選択する。
$S$ について二分探索。それぞれの $S$ について頂点 $u$ からdfsを仕掛ければいい。 $S$ の範囲は $4 \times 10^9$ までありえる。自分は昔に解いたときも今回解いたときも $S \leq 2 \times 10^9$ と置いて死んでいた。 ちゃんと考えろｗ
$n$ ターン残ってるときに、$n-1$ ターンやるときの最大の期待値がわかっているなら、 その期待値より目が大きいときだけ、そこで終了したい。 $E_i$ ... 残り $i$ ターンのときの最大の期待値と置くと、 $$\begin{equation*} \begin{cases} E_1 = 3.5 \\ E_i = \frac{6-\lfloor E_{i-1} \rfloor}{6} \frac{6+\lfloor E_{i-1} \rfloor +1}{2} + \frac{\lfloor E_{i-1} \rfloor}{6} E_{i-1} (i > 1) \end{cases} \end{equation*} $$
まあやり方わかってればわざわざ定式化しなくていいか。これは $E_1$ から順に求めていけば終わり
まずは転倒数を求める。ライブラリがあると楽。BinaryIndexedTreeでうまく調べる。 つぎに、先頭にある数を末尾に入れたらどうなるかというと、それより大きい値の数だけ転倒数は上昇するし、小さい値の数だけ転倒数は減少する。 $A$ は順列なので、$N-1-A_0$ だけ上がり、$A_0$ だけ下がる。つまり、$N-1- 2A_0$ だけ上がる。 これが任意の $A_i$ についてもこのときにはそれが先頭に来てるので同じように処理すればこの問題は解ける。
1ループするときにどのくらいアメが増えるのかを考えて一気に計算すればいいが、まあちょっと $K$ の扱いに注意しないといけない。 最大値を求める系よりかは面倒ではないと思う。
典型的なグリッドDPだと思う。i, j, k をもつ。k はその行で何回アイテムを拾ったか。行を超えるたびに0にリセットされる。 変な書き方をするとバグりやすいので注意しよう。
直近 3 文字について何を選択していたかを持つDPをやるといい。あとはその文字たちと、今入れようとしている文字が、 それ自体と、スワップしたものがAGCになるのかを確認する。なかったら遷移。
普通の幅優先に、今進んでいるマスの距離は $3$ で割ったあまりだといくつになるのかというのを保存する。 頂点 $T$ のときにそのあまりが $0$ のものを発見できたら、距離の 1/3 を出力する。
Warshall Floyd をして、各辺についてその辺のコストよりも短い最短経路がある場合は+1する。 どの最短経路にも含まれない理由は、その辺を使うよりも最短経路を使ったほうがどこに行くにも速いからである。
これだけ自力で解けなかった。昔は解いてたんだけどなぁ・・・ 自分はここで Mo's Algorithm というのを知った。 現在見ている $l$ と $r$ というのがあるとすると、それらの$+1, -1$ の移動が、$O(1)$ でできるときなどに使える。 それかつ、すでにデータが完成しているオフラインクエリだとつかえる。
まず $l, r$ のソート方法として、$l$ を平方分割したグループに分けて、そのグループでソートする。 そしてグループが一緒ならば、$r$ を昇順でソートする。
このとき、各グループについてみると、
$l$ の1回の移動が、$O(\sqrt{N})$ で済んでいる。
$r$ のグループの中の移動が $O(N)$ で済んでいる。
そうすると、$l$ の全体の移動は $O(Q \sqrt{N})$ 程度で、 $r$ の全体の移動は $O(N \sqrt{N})$ 程度で済む。 このようにしてクエリを処理すると、$O((N+Q) \sqrt{N})$ で処理できるということだ。なんか魔法みたいだ。 Mo's は言っても、なにか特別なデータ構造を使うわけでもないので、かなり定数倍が早そうである。 今回の $N, Q \leq 5 \times 10^5$ のような大きいケースでも間に合ってくれた。
でも今回はこういうのを使わなくても解ける。これを思いつくべきだったと思う。昔はこれを思いついていた。 $l$ を小さい順に見ることを考える。このとき、$l$ より右にあるものについて、各色の玉が一番左にでてくるところというのを BinaryIndexedTree などで持っておく。 するとこの時点での $r$ のクエリを返すと、ちょうど種類数だけの値を出してくれる。 $l$ が増えるときにすぐにその位置の玉の色について、それより右にある同じ色の玉の一番左のものを出せるようにして、BIT を更新していけば、 任意の範囲(lについてソートしたもの)について、処理することができる。これは多分 $O((N+Q) \log N)$ だと思う。
結構難しかったが、水色 Diff だったのは当時の Mo's の流行り具合などもあったのかな。 当時も頑張って解いたのに、みんな結構通していたことを驚いていたような気がする。
今回は使えない道を逆手に取る。まず全点間の経路については、累積和DPを使うと、うまく解ける。 すべての都市に行けるので、例えばDPが $i$ 日目で現在都市 $u$ にいると言うような情報を持つとき、 一旦全て都市 $1$ のところに遷移させ、それを都市について累積和を取ればいいわけだ。
道が使えないということに対して累積和を対応させると、その部分 dp[i+1][v] に -dp[i][u] させて、 その都市の 1 個先の dp[i+1][v+1] に dp[i][u] を足せばいい。 すると、最終的に累積和してみるとそこだけが足されないということができる。 すると、遷移しないところを作れるのでこの問題は解ける。
色々と多種多様なので、一概にこういう問題があるとは言えないが、まず全探索は多かった。 自明な全探索は単純に実装を頑張るだけなので特に問題はない。問題があるなら、速く解けるかどうかだと思う。
あとは、色んな方法でDPするというやつ。あんまり単純なものはなかった。ただゲームDPなどは典型に入ると思う。あと桁DPとか。 累積和DPもかな？結構多種多様。だけどここらへんは典型かな。
あと、二分探索も結構多い。答えがそのまま二分探索の答えになるものだけじゃなくて、ある値を求めておくと都合がいいときに取得するために 二分探索を用いることもある。結構慣れていたのでここらへんはスムーズだった。
速いシミュレーションもあった。$K \leq 10^{12}$ みたいなやつ。だいたいループができるか、何らかで速く処理できるが、 $K$ の扱い、つまりデータの大小が結構あるので、パターン分けが多くなって面倒だった。再帰とかを使うなら基底条件が多い系は書きやすくなるかも？
ad-hoc? な問題は、結構あったと思うけど、結構単純なものが多い。 Range Set Query みたいに、単純な問題はこれから応用が効くので、こういう基本問題もあるのが嬉しい。 基本の貪欲とかもあったね。スワップできるうんたらかんたら。 逆クエリで UnionFind をするとかも、典型。
なお重要さは記憶に残ったと言い換えてもいい。Happy Birthday! 2 とかは、そんな簡単に解けるのかって面目を食らった。 Stones でゲームDPをよくわからず解いているときとか、756で必死に式を考えるときとか。 Game in Momotetsu World で死ぬほどバグってWAだったりとか。 XXORが嘘解法で昔通してたとか。
割と問題を大事にできたかなーとは思う。結構記憶に残っているものも多いので、いいと思う。
一言コメントって言うつもりだったんだがなぁ・・・ いまhtmlの行数が1000を超えてて、どんだけ書いてるんだよｗという話なんす。 普通に書き終えるのに１週間近く立ってるし・・・これ100問解いたペースと同じなんだよな・・・ そして今どこまで進んでいるかというと#000114あたり？ふむふむ。
ただ、解法を見渡せるものが出来上がったから、自分でまたこのページを見て振り返るかもしれない。 であれば、書いた分意味があったかなとは思っている。
(2023/09/22 06:02)