今回も100問解き、300問解けました。 この難易度帯になると、令和ABC初期の青Diff(1900とかもでる)の問題などが増えてきましたね。いい復習になったと思います。 青Diff はそれだけでなく、普通に割と新し目の問題でも青Diffはよく出るようになったと思います。 #000297 の typewriter とか、 #000286 の Average and Median とか、 #000299 Sugoroku 3 とかはかなり教育的な問題じゃないでしょうか。 ABCっぽくていいと思っています。 難易度だけで言うなら、黄 Diff が 3 つ出ましたね。#000245 Active Infants と #000264 桁和 と #000282 No Need ですね。 Active Infants は他の２つが結構古めの問題だったのに対して、 一応令和 ABC の問題でちょっと新し目でした。そして 初ACだったので達成感がありました。あと、No Need は昔嘘解法で通してたのでいい勉強になったと思います。
今回は 99 問自力ACです(解説やコードを見なかった問題数, 自分の知識にないと思ったものは類似する情報を調べるなどして対応した)。 今回自力で行けなかったのは #000226 Coins Respawn でベルマンフォード法の拡張について理解が足りていなくてずっと after contest ケースで WA を出していました。負閉路を見つけたらめちゃくちゃ小さい値でぬりつぶす必要があったみたいです。 あと、自力ではあったものの、理解せずに AC してしまったのが #000212 Strivore です。これも自力 AC とは言えないかも・・・。
あと、実際に最近コンテストに参加してACした新しい問題がこの難易度帯に食い込んできて、問題番号とリストの位置が対応しなくなっちゃいました。 結構解いてきたんだなとおもった。ちょっと見づらくなるけど、仕方ないかなぁとは思っています。
あと思いの外 新 ARC の問題があまりでてこない。ARC のリストを見るとまだまだ水 Diff がかなりある。 やっぱり Solver 数結構少ないのかな。301-400 はどうだろう。もっとでてくるだろうか。
そんなこんなで、10/8から11/6までこの100問を解いたわけです。 今回は ARC の緑 Diff までの問題も解いていたので少し遅くなったが、特にペースは変わってない様子。 むしろ 101-200 のときよりスムーズに解けたと思う。一番むずかしかったのは #000299 Sugoroku 3 だった。。。
Solver が 3264 人から 2513 人までの問題でした。
現在の命令でどっちの変数も値がある場合は、次の命令で使う方に値を移動するといい。 このようにすると、変数の合計の値が $2$ あるだけで最初の命令で詰まない限りは必ず作ることができることがわかる。 ある命令でどちらかの変数にしか値がない場合でも、それを反対側に移動しようが、現在の命令で使われていない位置に一つあるので、 必ず次の命令では動かせることがわかるからだ。
ということはあとは合計が $1$ だけのときに動かせるかを見ればいいがこれは簡単に求まる。 これで後はシミュレーションをすれば解けるわけである。
自分の実装はかなり大変になったが、多分工夫すれば楽にやれると思う。
こういう制約の大きいゲームは、だいたい必勝法がある。相手を必ず負けさせるマス(状態)にそうでないマスから必ず移動させられ、 負けさせるマスにいる場合はそのようなマスに移動できないようになっている場合、 負けさせるマスに最初に Alice がいる場合は必ず負ける(Brown がそのマスに常に誘導してくるため)。 そうでない場合は Alice が勝つ。
そしてかなり非自明なことに、$\mathrm{abs}(X-Y) \leq 1$ のとき必ず負ける状態になるようである。 確かめてみると、まあ確かにそうなっていることがわかる。
これを実際に導出するとなるとこんな具合にやれると思う。 今回の場合、 $X, Y$ が小さい問題なら DP にして表せるので一回最終状態から考えて、ゲームの先手が勝つかどうかのDPを埋めてみるとする。 すると、さっきの負けマスを導出できるので、法則性を見つけて答えを出すというエスパーが考えられる。
かなり勉強になった。状態を表しやすいのなら一回小さい制約で DP をやってみるといい。
一回完全グラフを作ることを考える。すると、現在のノード $i$ について番号の和の値が、 $N(N+1)/2 - i$ になっていることが確かめられる。 この時すべて同じ和の値にするには、番号の小さいノードから順にだんだん結合を消すノードの番号の値を $1$ 小さくしながらやっていく必要がある。
このとき自分のノードを消すみたいなことにならないようにするためには消すのノードの番号と現在のノードの番号の偶奇を異なるようにしながらやればいい ことがわかる。
すると、 $N$ が奇数のときは、ノード $i$ についてノード $(N-1)-i$ との結合を消せば良さそうである。 $N$ が偶数のときは、ノード $i$ についてノード $N-i$ との結合を消すようにする。するとそのようなグラフを形成できる。
$M \geq 2$ であれば、$0$ から $2^M-1$ までの値の XOR を取ると $0$ になることがわかる。これをとりあえず前提にする。 すると、値を $\{K, 2^M-1, ..., 0, K, 0, ..., 2^M-1\}$ というように並べると($K = 0$ のときは $0$ と書いているところが $1$ になるが)、 条件を満たすことがわかる。もちろん $0 \leq K \leq 2^M-1$ である。まあ $K$ を挟んで降順昇順に並べればいい。
$M = 1$ のときは、$K=0$ のとき $\{1, 0, 0, 1\}$ と並べればよく、$K=1$ のときは作れないことがわかる。その他はそもそも作れない。
$M = 0$ のときは、$K=0$ のとき $\{0, 0\}$ と並べればよい。その他は作れない。
$A_i+1 = A_{i+1}$ なら連続して作れる。しかし、$A_i+1 > A_{i+1}$ だと、先に右のものを作ってから左のものを作る必要がでてくる。 あと、 $A_i \geq i$ でもだめだし、 $A_i+1 < A_{i+1}$ でもだめ。 これに気をつけながら、$i$ を左から見る時、$A_{i-1}+1 = A_i$ のときに操作回数 $+1$ をし、 そうでないときその前に作るので操作回数 $+A_i$ をする。すると答えが求まる。
この問題は色をノード、カードをエッジにしたグラフを考えると解ける。 あるノードとノードがエッジでつながっている時、どちらかのノードを選択できるというような感じになる。 このとき、連結成分について考えると、連結成分が木のときはあるノードだけ選ばないようにすると、その他のすべてのノードが選べる。 木でなく、閉路を含んでいる場合(自己ループも含む)は、 その閉路にするためのエッジを取り除いてどちらかを選択するとする。この時それを根にした根付き木を考えると、 すべてのノードを選択できることがわかる。
つまりこの問題は各連結成分が木であるかそうでないかを判定することで答えを導き出すことができる。 木であるかそうでないかというのは、その連結成分の中にあるエッジ数を求めればいいので、これは Unionfind で簡単にやれる。 というような感じで解くことができる。
dp[i][j] ... 現在 $i$ 行目を見ていて、現在位置が $j$ のときの正しいあみだくじの本数 というのを考える。 このとき、どのような遷移が考えられるかと言うと、(左に移動する, 移動しない, 右に移動する) という $3$ パターンがある。 左に移動する場合は、その位置に横線がないといけなくて、かつ、その近くに横線があってはいけない。 すると、現在自由な部分というのは、左右にあり、置き方としては、 (自由なマスが $n$ マスあり、すべて白色とする。この時マスに黒色を塗ることを考え、それが連続しないように配置するパターンは何通りか) について考えればいいことがわかる。これを左右求めて かけ合わせたものを dp[i+1][j-1] に遷移すればいい。
これと同じノリで、移動しない場合と、右に移動する場合についても考えて遷移させればいい。
実はこの自由な部分の色の塗り方はフィボナッチ数列のような dp で求められるので $O(W)$ で求まる。 前計算で求めておく。
するとこの問題の計算量は dp の空間の大きさと一致し、 $O(HW)$ で求められる。 実は $W$ が大きくてもある程度問題ない。
まず、高橋くんのプログラムは最適解を出す。そのため、$M < 0$ は絶対にありえない。 そして、$M=N$ についても青木くんが絶対に $1$ つは区間を取るのでありえない。 $M=N-1$ については、まず最適解が $N$ でなくてはいけなくて、この時すべての区間が排反であるのでありえないことがわかる。 逆に $0 \leq M \leq N-2$ である場合はすべて構成できる。
まずものすごい長い区間を用意する。この区間の中(strictly)に互いに排反な区間を入れる。 すると、この排反な区間の数-1 だけ答えがずれてくることがわかるので、最大 $N-2$ まで答えをずらすことができることがわかる。 入れない区間については、ものすごい長い区間の外に排反に区間を設置すればよい。
$N=1$ のときは、$M=0$ で作れるのでここだけ気をつける。
この問題はまず 2 次元の DP を考えてみて高速化するという方針を取る。 $dp[i][k]$ ... 現在 $i$ まで見たときの $k$ 個要素を選んだときの和の最大値 ということを考える。すると、各 $k$ において、埋められる $i$ は最大 $3$ 個までであるとわかる。
ということは、$k$ に対して配列を $3$ つ持つような dp 配列に変更すればいい。 $dp[k][l = 0,1,2]$ みたいな形にする。 $i = 2 \times k + l $ となっている。 このような DP 配列を更新して解けばよい。答えは $ dp[\lfloor N/2 \rfloor][l] $ の $3$ つの中にある。
チームの総合力を仮に $X$ 以上になるか考えるとすると、各メンバーのパラメータを $X$ 以上かそうでないかという 2 値に変更できる。 仮にこの値を $1, 0$ としておく。 この際に、 メンバーを $3$ 人選んだときにすべてのパラメータが $1$ になるようにすればいいということから、 $dp[i][k][b]$ ... 現在 $i$ 番目の人まで見たときの $k$ 人選んだとき、各パラメータの集合 $b$ になっているというパターンが 存在するか という dp を解けばいいことになる。 $b$ は bit で管理する。答えは $dp[N][3][2^5-1]$ が true かそうでないかということになる。
例によって $X$ についての答えが true になるときそれより低い値も true になるという単調性があるので 二分探索で解くと、二分探索の調べる最大値を $Y$ とおくと、 $O(N \log Y)$ 程度で解けることがわかる。
想定解だとパラメータの種類が高々 $32$ 通りしかなくなるため圧縮して $3$ 重ループを回すという方法がとられているようである。
ある $i$ を部分列の左端、 $j$ を部分列の右端にするとき、 $A_i \leq A_j$ という条件さえ満たされていればいいので、 この条件を満たす時、パターンは $2^{j-i-1}$ 通りだけあることわかる。
このことを整理すると、ある $i$ を見ている時、条件を満たす $j (i < j)$ についての答えの累積和がすぐに手に入れられれば 速く解けそうということになるわけである。
これはどのようにするかと言うと、 $A_i$ の大きい方から見ながら、処理した後に位置 $i$ に累積和を更新するというような ことを考えるといい。更新クエリも速く処理しないといけないので、Binary Indexed Tree が適任である。
ところで、パターンが $2^{j-i-1}$ 通りあるというのを足し上げるためにはどうしたらいいかということが問題である。 これを解決するためには、単に Binary Indexed Tree の配列の $i$ 番目の値に $2^i$ を add すればいいことがわかる。 このようにすると、まず $i$ より大きい $j$ についての累積和を求めた後、 $2^{i+1}$ で割ってあげれば、 条件を満たす $j$ について $2^{j-i-1}$ の値が取り出せるようになる。
というのを適切に実装すれば解ける。 一応、$i$ を小さい順に見ながら $j < i, A_j \leq A_i$ であるような物を見つけるという実装でもいいが、 この場合は、$A$ における座標圧縮が必要になる。
これは答えがわからないでACしちゃった問題。だが、コンテストをやっていた当時はちゃんとわかって通していたみたいである。
こういう問題を解くときは、$|S| + K$ 個の中から文字を置くということを考えたほうが良い。 このとき文字列がダブらないように置くためにはどうすればいいかということを考えるのがかなり難しい。 文字がダブる条件は、$S_i$ が置いてあるところのすぐ隣などに(厳密に言うとその文字が $S_{i+1}$ の右や $S_{i-1}$ の左にある、 あるいはそれ自体であるととれないようなところにあるものに)同じ文字が置かれている場合が該当する。 このとき、どれを $S_i$ にしたらいいかということでパターンがダブっていることがわかる。
そのためそのような同じ文字について「必ず $S_i$ はそのなかで左端にある」という条件を追加すると、ダブらず計算できることがわかる。
それを満たすやり方は、「$S_{i-1}$ と $S_i$ の間の文字には $S_i$ と同じ文字を含まない」 というような物を数え上げるというようなものになる。 そしてこれは $S_{|S|}$ より右にある文字が何個あるかということが決まればパターンが簡単に数え上げられる。 この数を仮に $k$ と置いてみる。すると、 $S_{|S|}$ より左にある自由な文字についてはそれぞれの文字について何を選ぶかというパターンが $25^{K-k}$ 通りある。 そしてその中でその位置を自由に選べるので、 $_{(|S|-1)+(K-k)} \mathrm{C} _{|S|-1}$ 通りあることがわかる ($S_{|S|}$ については一番右になければならない)。 そして右にある文字についてはすべて自由に選べるので $26^k$ 通りあることがわかり、これらをかけ合わせれば $k$ についての答えが 出る。 そのため、すべての $k$ についてこれを足しあげれば答えが求まるというわけである。
AC したときは、よくわからない包除原理を用いて解いていた。 逆に $k$ 個ダブっているときのことを考えた。つまり $S_i$ より左にあるものの同じ文字が $k$ 個あるという状況である。 そしてそうでないものは適当に設置することを考える。 すると、まず適当に設置するものとして $26^{K-k} \times _{|S|+K} \mathrm{C} _{K-k}$ 通りあり、 ダブっているものの位置として、 $_{(|S|-1)+k} \mathrm{C} _{k}$ 通りあることがわかる。 これを $k$ が偶数の時足し上げて、 $k$ が奇数のとき引いていくと、答えが求まる。
置くやり方として考えてみても、$S_{i-1}$ と $S_i$ との間に $S_i$ と同じ文字を含まないという条件がダブらない条件である という考えに持っていくのはかなり難しいと思った。
当時は DP を高速化する方針を考えていたみたい。かなり頭がいい。いやこうやって考えるべきだったかなぁ。
まず整数の遷移をグラフのように捉えると funcitinal graph であることがわかる。 この functional graph の閉路の中に整数 $i$ があるのであれば、そのようなゲームはすべて高橋くんが勝つことがわかる。 なぜなら青木くんがどのような $K_i$ を指定しても $K_i$ 回動いたところに $i$ があるような位置は閉路内に存在するからである。 逆に $i$ が閉路に含まれていない場合は青木くんがものすごい大きい値を指定すれば絶対に $i$ にならないので青木くんが勝つ。
よってこの問題はあるノードが閉路に含まれているかを考えればいいので、SCC などを使って(SCC でやる場合は自己ループにも気をつける) 解けばいい。あるいは入次数 0 のノードを取り除いていく方針でもいい。
逆から考えるといい。例えば $A_K = 2$ が与えられた時、その $1$ 個前の状況としてありえるものは、 $2$ 人いるか、 $3$ 人いるかというものになる。 一般化すると、あるゲーム $i$ が終わったときに $D$ という人数になっている場合、 ゲームが始まる前にいた人数は $D$ から $D+A_i-1$ になるということがわかる。
これを突き詰めて考えると、$i$ 番目のゲームが開始してから $N$ 番目のゲームまでやるときの 子どもたちの人数の最小の値と、最大の値を取っておけば、最終的に $1$ 番目のゲームからやったときのものが出そうである。
$i+1$ の状態から $i$ に遷移するためには、まず、$i$ のゲームが終わる時 $A_i$ の倍数になっていないといけないため、 $i+1$ のときの max と min の間の数字で、 $A_i$ の倍数として一番大きいものと、小さいものを用意し、 小さいものについてはそのままにして、大きいものについて $A_i-1$ を加算するようにする。 このようにすると、 $i$ についての答えが求まることになる。
ただし、max, min の中の値で $A_i$ の倍数のものが存在しない場合、最後 $2$ 人で終わるようなものがないことがわかる。
ABC319 の感想の方でも書いた。最近解いた問題でもぶつかったら解くようにしている。
$1 \leq P_i \leq 8$ であるので、$1, 2, 3, 4, 5, 6, 7, 8$ の最小公倍数である $840$ 通りしか ある時刻からスタートしたときのかかる時間のパターンがない。
これは単純に時刻が $840$ 経ったらバス停の状態のパターンが繰り返されるので、 いったん $q_i$ に $\bmod 840$ したものを考えてそのときのかかる時間を考えればいいことがわかる。 そのような状態を $840$ 通り保存しておけばいい。
$dp[i][j]$ ... 現在 $i$ にいるときに $i$ までの $T=$ "ABC" の 部分文字列として $T_j$ までを採用したときの総数 というものを考える。この時、$T_j = S_i$ であるか $S_i =$'?' であるときに 部分文字列として採用するかしないかというパターンを取る遷移ができる。 すると、最終的に $dp[|S|][3]$ には ABC 数の和が求まることになる。 $S_i=$'?' のときは $dp[i-1][j]$ から $dp[i][j]$ への遷移が $3$ 倍になる。
主客転倒的な考えだとしてもこの dp は暗に $i$ の累積和(のようなもの)を取っているので発想として結びつきづらい。 確かに遷移は簡単になるが、少し思いつきづらい形になっているように思える。
自分はこの dp が当初思いつかなかったので、'B' か '?' の文字列に着目して、それより左にある 'A' か '?' について、 それより右にある 'C' か '?' についてのパターンを求めるという主客転倒の方法をとった。 これは少し式が難しくなるので、計算量を下げるために Wolfram Alpha を使って |S| とかの計算量によらない式を出した。
単に確率に対して dp をすればいい。unordered_map などを使う。 $1$ が出たときの遷移が面倒くさそうだが、結局のこりの $2, 3, 4, 5, 6$ の目が出てくることになるので、 それぞれ $2, 3, 4, 5, 6$ の目が出る確率を $1/5$ と捉えて問題ない。 初項 $a=1/6$, 公比 $r=1/6$ に対する無限等比級数と捉えてもいい。これも結局 $1/5$ である。
これも ABC323 の感想で書いたが、もう少しスマートな解法があるようだ。
$p_t$ ... 時刻 $t$ においてちょうど曲が再生された確率というものを考える。 すると、$t$ で $1$ 番目の曲が再生された確率というのは $p_t/N$ であることがわかる。 そのため、この $p$ を求め、あとは、$X-T_1+1 \leq t \leq X$ の $t$ において $p_t/N$ を足しあげればいい。
うーん、確率ってなんなんだろう。ある $t$ における確率という概念がよくわからない。 どこのどういう意味での確率になっているのかが、すごい曖昧で、これで解けそうな感じはあるが、厳密に理解できていない。 確率というか、寄与している量なのかな。
魔法石をノードにして考えて、隣り合わせにできる組をエッジとして考える。 この時、辿らなければいけないノードをたどったときの距離 + 1 がそのパスについての魔法石の個数となる。
今回は、$C_i$ から $C_j$ までの距離というものを BFS で求めておくと、単に求めたい魔法石のみ考えればよくなる。 するとノード数は $17$ 個になる。
すると、$dp[S][u]$ ... 現在 $u$ にいるときに、 $S$ だけすでにたどったときの距離の最小値 という bitDP に落とし込めるのでこれを解いて答えを +1 すると求めたいものが出る。
例えば横の長さを $k$ とすると、縦の長さは必ず $k+1$ になる。 まず $1$ 行目に $1, 2, 3, ..., k$ という数字を入れると、その下の行についてこれらの数字が一つずつ入ってないといけないので、 $1$ 列目の $2$ 行目からの値は $1, 2, 3, ..., k$ という値になる。これで $k$ までの数字は使ってはいけない。 これをやっていくと、最終的にできるものは $k(k+1)/2$ までの数字を使ったものとなる。 横に新たな数字を書き込み, 縦にそれと同じ数字を書き込むというようなやり方になる。これ以外はできない。
そのため、$N$ は $k(k+1)/2$ の値でなくては駄目で、この条件を満たしていれば、上のような構成方法で作っていけばいい。 問題欄に書かれている $k$ は縦の長さとしているが、横の長さとしても+-1 違うだけである。
あと、 $1$ 列目に $1, 2, 3, ..., k$ を書くといったが、別にそうでなくてもいいのだが、 結局 $1$ 列目に全部書き込んだときのことだけ考えればよいということがわかる。
ABC322 の感想でも書いたおなじみの問題。 回転と平行移動したものを全部作ってそれぞれパターンを作っておく。 後はこれを $3$ つ組合せて実際に当てはめて作れるかどうかを試せばいい。 後述する #000227 Ideal Sheet よりかは割とヤバいケースとかがなくてやりやすい。
虐殺で有名な問題。これは単にある $y$ について $x$ の範囲を見てそれの整数の場所の数を調べればいいのだが、 これを double 型で解こうとすると、引き算のときに精度を超えてしまうことがあり、 ちゃんと計算ができない。そこで、int 型に直して、各座標を $10^4$ 倍すれば、精度の問題は解消されるが、 ここで、最初の入力についてしっかり丸めて int 型に直してあげないとおかしい値になってしまうことがあり、 ここも気をつける必要がある。解説に書いてある round 関数を使うのが一番いい。 おかしくなりやすいのは、$X, Y$ が負の時が挙げられる。というか、負の値のあまりとか、そういう値が出てくるときは 細心の注意を払わないとバグりやすいので本当に気をつけるべき。正の値にならないんだよなぁ。
平方根を求めるときも double がでてくるので、もしこれが怖いなら、二分探索とかで整数を調べるのが良さそう。
こういう問題は、最も近い同じ値にエッジを張って DP をすると、数え上げができる。 なぜなら、遠い値にある同じ値の操作は近い値の操作を何回かやることで実現できるからである。 そのようにすると、数列がダブることもなく、異なる数列を数え上げることができる。
ルークの位置として重要なものは $4$ つである。 位置を $(x, y)$ とすると、 $x = x_2, y \neq y_2$ であるパターンと、 $x \neq x_2, y = y_2$ のパターン、 $x \neq x_2, y \neq y_2$ と、$x = x_2, y = y_2$ の $4$ パターンである。
そしてこれは操作を $k$ 回行ったときのその場所にいるのが何通りあるかが $k-1$ 回のときの値を使って計算できる。 その為これはそれをシミュレーションして解けばいい。
あとこの問題は、$K$ 回の操作が同じ遷移によって起こるので行列累乗が使えて $O(\log K)$ で解くことも可能である。
総和が要素の数と等しくなるという問題を解くときは、それぞれの要素について $-1$ しておくことで、 総和が $0$ になるという問題を解くことと同じになる。 その為これは要素の数によらず要素の和を $K$ で割ったあまりが $0$ になる ものを見ればいいだけになる。
ただし、気をつけなければならないのは、要素の数が $K$ 個以上になる場合は絶対に作ることができないので、 map を使った数え上げをやるときは要素が $K$ 個以上になるようなものを削除しながらやっていく必要がある。
これはすべての辺の重みの符号を変更し、それを Bellman-Ford 法で最短路問題を解けば解けるのだが、 例によって負閉路が見つかったときの処理が難しい。実際に頂点 $N$ を更新できるのかというところなのだが、 これは負閉路が見つかり次第、そこのコストをものすごく小さくして、それで $N$ まで持っていけば解くことができる。
コストをものすごく小さくしないと、閉路なしの答えがかなり小さかった場合に更新されない可能性があるので 注意しないといけない。これは少し解法を見てしまった。
この問題は実装方法によってはとんでもないことになる、計算しすぎて TLE する可能性もある問題である。 おそらくイージーな実装方法は、まずシートの $A, B, X$ について 上下左右で '#' を含まない行や列(つまり関係ないところ)を削除 しておくということをしておく。そのあとシート $A$, $B$ を組合せたら、組合せたものをさっきの削除の操作をしておいて、 それと $X$ が等しいかを見ればかなり実装が楽になる。
とにかく左上の位置をちゃんと合わせる必要があるので、このような操作をしておけば、かなり楽になるわけだ。
逆にこれをしないとかなり多様なコーナーケースがあるので苦しむ羽目に合う。計算量も大変なことになる。 さっきの操作をしておくだけで 1000ms とかが 2ms とかになるのでかなり違う。
まず、$A$ はどこかの要素を一つでも決めると、一意に定まることがわかる。 そして、 $A$ は $A_{i+2} - A_{i}$ が一定という制約があるので、奇数番目の数列の要素が上昇する場合、 偶数番目の数列の要素が減少するというような関係になっている。
また、ラッキーナンバーの数の最大値の候補としては、$A$ のどこかの要素に $X_i$ があるみたいなものしか無いので、 そのような候補は $O(NM)$ だけある。先程の $A$ の決まり方の法則を利用しながら候補になるものを当てはめれば、 それぞれ $O(\log N)$ 程度($A_0 = 0$ のときの結果を 2 つ(奇数数列と偶数数列)の map のキーにとっておくとよい) で調べられることがわかるので、時間内に調べられる。
というふうに実装したが、想定解だと、候補について差分が $(-1)^{i-1} \times (X_j - B_i)$ ( $B_i$ は $A_0=0$ としたときの $A$ と示す) とでてくるので、その中で一番多く出てきた差分の数が そのままラッキーナンバーを含む最大値になるというものである。こっちの方が計算量が少し小さくなる。 どの差分でやると、一番一致するのかということがわかるようである。
これは割と方針が考えやすいと思う。まず一回美味しさが大きい順にとっておく。 この時、一つずつ種類を増やしていって、その時の最大値を取るように選んでいくようにする。という感じになる。 そのため、現在取っているものの中で同じ種類のものが $2$ つ以上あるものについて minHeap などに入れておき、 種類を増やすときにその minHeap から取り出す。そのあと、種類が増えるものの中で最大の物を入れるようにする。 というように適切に実装すれば時間内に解ける。
まず、$R-B=K$ であるものと $R-B=-K$ であるものの答えが変わらないことに着目すると、 $K \leftarrow \mathrm{abs}(K)$ と更新していい。そのため $R \geq B$ の場合のみを考えるだけで済む。 これで考えていく。
まず赤を何回通過したなら良いのかということを考えたい。 これは、通過した辺の個数を $L$ とすると、$L-R=B$ であるので、$R-(L-R) = K$ より、 $R = (K+L)/2$ となる。
また、ある辺について、通った回数が $B_i$ だとすると、 その辺を赤に塗ったときに $B_i$ だけ通過する回数が増えることになる。
というふうに整理すると、各辺について部分和 DP が使えることがわかる。 これは $O(NR)$ で実装でき、in-place に DP の遷移を行えるので、空間計算量も問題ない。 $N \leq 1000, R \leq 10^5$ であるので問題ない。
通過した辺の列挙の実装は自分は根付き木を使って lca を求めて親に遷移するようにしてみたが、 普通に深さ優先探索でも問題ないと思う。
これは DP 配列に Segment Tree を乗せれば解ける。遷移が DP 配列に置いて 差の絶対値が $K$ 以下のものを すべて遷移しないといけないので、これを Range Max Query で処理すれば良い。
木に対して LIS を求めるときは、DFS でやるとき、LIS の配列を $1$ 個前に戻すような処理を考えておくと、 適切に実装できる。関数ごとに今やった操作を覚えておけば、逆操作も簡単に求まるが、 vector の位置を持つためにイテレータを持ってしまうと、vector の配列の中身が色々変化した後に イテレータの意味が変わってきちゃう場合があるようなので、ちゃんと int 型の位置として持っておく必要があるようだ。
$A, B$ があまり大きくないのを利用すると、最大でも偏りとしてありえる値が $12800$ 程度である。 そしてこれは負もありえるので、 $25600$ 通り偏りが存在している。 ある位置に対する偏りのありえる値の集合を持つことを考えると、配列のサイズが、 $80 \times 80 \times 25600 = 163840000$ 程度であるがこれは bitset で小さくするか行だけ持つなどの対処で小さくできる。
遷移自体もこの程度の量であるが、 bitset で高速化すると割とましな計算量になって通る。
答えはもちろん、$(H, W)$ についての更新された集合を見て、もっとも偏りが小さいものを見るだけである。
これは美味しさと香り高さの二次元ベクトルで管理するとよい。このとき内積が $0$ であるものが仲が悪いものになるので、 ちょうど直角であるようなものが該当する。また今回は逆の向きになっているものをすべて同じ向きにして考えられる。 すると、すべてのベクトルを第一象限と第二象限に持ってこれる。
そしてこの時、ある角度を持つベクトルの集合と、それと直角になっているベクトルの集合をペアにして考える。 このとき、ある角度を持つベクトルの数を $a$ として、直角になっているベクトルの数を $b$ とすると、 この中でベクトルを選ぼうとすると、 $2^a + 2^b - 1$ 通りあることがわかる。 そしてこれは他のベクトルたちと独立して考えられるので、各角度のベクトルにたいしても同じように何通りあるかを求めて、 かけ合わせれば答えになる。
また、どうやって直角かを高速に判定するかというと、ある角度のベクトルをできるだけ正規化することを考える。 これはベクトルが $(a, b)$ だとすると、それぞれの要素を $\mathrm{gcd}(a, b)$ で割ると良い。 直角のものは、$(-b, a)$ にある( $(a, b)$ を第一象限だとすると( $1$ 番目の要素を $x$ 座標と考えると) )。 これを map などに入れて頑張ってペアを作ると良い。実装が少し大変である。
各道路工事について、ある人が座標 $0$ を出発したときにどの時刻に出発するとその道路工事が塞ぐのかということを考える。 これは $[S_i-X_i, T_i-X_i)$ が該当する。このように考えれば、ある時刻のときに塞がれる道路工事の中で一番座標が小さいもの がその出発した時刻の答えになるわけである。
そしてこれは意味のある時刻を座標圧縮して、時刻の小さい順からシミュレーションすれば 現在座標が一番小さいものを高速に求められる。 $D_i$ を小さい方から見ていって、そこまでの時刻で起こったことを適切に処理する。区間に入ったときに multiset などに $X$ 座標を入れて区間が終わったときにそれを削除するようなシミュレーションである。 これを $D_i$ まで求めて、multiset の一番小さい要素を出力。そして $i+1$ についてもシミュレーションの続きをやっていけば 高速に求まる。
例によって $X$ と $Y$ を独立して考える。 とりあえず $X$ について求めてみる。
これはよくある主客転倒のテクニックで、今回はある２つの駒の距離が $D$ であるようなものの総数を求めて $D$ を掛けたものをそれぞれ足しあげればよい。 これはまず、$X$ 座標のペアとして、 $M-D$ 個存在し、そして $Y$ 座標の選べるものとして、 $N^2$ 存在し、 かつ、他の駒についてその座標以外すべて選べるので、$\binom{NM-2}{K-2}$ だけ存在している。 この総数に $D$ を掛けたものが距離が $D$ のものについての答えである。 これを各 $D$ について求めれば $X$ 座標についての答えが完成する。
$Y$ 座標も同じように考えればいいので、２つを足し合わせて答えにすれば、この問題を解くことができる。 今回の $N, M$ の制約も小さいので、普通に二項係数ライブラリを使って解けばいい。
小さい数字ができるだけ書き込まれないようにすることを考えたいので、 一番小さい数字を木の葉に書き込むと、$1$ 回より多く辺に書き込まれることはなくなる。 一番小さい数字は必ず $1$ 回は辺に書き込まれるので、これが適切であるといえ、貪欲にこれを解けばいい。
書き込まれたノードと書き込まれるエッジについてはもう考える必要がなくなるので、これを取り除いた後の木について考え、 その葉っぱに小さい数字を書き込んでいくと、最終的にエッジに書き込まれる数字の和は最大になる。
構成方法は色々他にもある。根付き木を考えて根に一番大きい値を入れて、その子に順序よく大きい値を入れていくと、 結局辺に書き込まれる値は $c$ の総和の一番大きい値を引いたものになるようだ。
ある $i$ を集合に必ず入れる時、 $A_j \leq A_i (i \neq j)$ であるような $j$ すべてについての $B_j$ の部分和 DP を解けばその後 $B_i$ を入れたときの $A_i$ 以下の値すべてを着目すると、その時の条件を満たす ものの個数が出る。 ただ、$A_i = A_j$ であるようなものについてはこの通りにやるとダブる要素があるので、 何かしら順序を持って、順序が先にあるものは後にあるものを含まないようにやるとダブらずに済む。
これを愚直にやると、 $O(N^2 A_{max})$ くらいになるが、部分和 DP の配列は $A$ が小さい順にやると使い回せるので、 $O(N A_{max})$ 程度に収まる。
まず、あまるパンの長さについては、そのような長さの配るパンがあると考えても同じである。
パンを切るということを考えるよりパンをくっつけるということを考えたほうが良い。 パンをくっつけるときにその２つのパンの合計の長さだけコストがかかることになる。
この時、最終的にくっつけた結果を考えると、各パンについてそのパンが何回コストに寄与するのかということがわかるはず である。この時一番寄与する回数の多い物が一番小さい値になっていれば最適である。 これを実現するためには、貪欲に小さいパン同士をつなぎ合わせるということをすると良い。 そしてつなぎ合わせたパンはその長さの新たなパンとして置いておき、また新たな問題を解けばいい。
あまりちゃんと説明できていないが、これはハフマン符号化をするときのアルゴリズムと全く同じで、 まあ覚えていたので解けたという感じである。ちゃんとした証明は解説ページに書いてある。
この問題は、min が $m$ であるような区間の数を調べるという方針が良い。 これを $m$ が小さいほうからやると、$m$ の処理が終わるたびに壁のようなものができる。 壁を超えると $m$ より min が小さくなってしまうという印である。
これを適切に張っていけばどこからどこまでの区間が条件を満たすのかがわかるので、 それを数え上げて問題に答えることができる。
$p_{i, j, k}$ ... 高橋くんが 地点 $i$ , 青木くんが地点 $j$ にいるとき、$k=0$ のとき高橋くんが次にサイコロを振る , $k=1$ のとき青木くんが次にサイコロを振るときの確率
みたいなものを取っておくと、遷移は簡単にでき、$p_{N, i, 1}$ に答えが求まる。
とりあえず、桁の重みがあるとややこしいので、$A_i = 10^{N-i+1} \times S_i \bmod 7$ としておくと 単純に $A_i$ を選んだときの和が $7$ の倍数か見ればいいだけになるので楽になる(剰余を取る和なら $0$ かどうか)。
まず、$X$ の末尾が 'A' であり、その連続した 'A' について一つでも $A_i \neq 0$ であるようなものがあれば必ず 青木くんが勝つ。あと、$A_i = 0$ しか連続していない場合は無いものと見ていい。とりあえずこれらを省いておく。 実装時には省かずに済むが説明のため。
この時、末尾が 'T' のときだけ考えればいいが、末尾から連続する 'T' について考えてみる。 この 'T' の先頭の前、青木くんのターンが終わるまでにどのような値が作れていたら、最後に $7$ の倍数にできるのか ということを考えると、末尾から $\bmod 7$ の部分和問題を解くことで、どの値が作れていたら必ず勝つのかがわかる。
このときその前にあった青木くんのターンについて考えてみると、逆にその値を作れないようにするには その青木くんのターンが始まる前にどの値になっていればいいかという問題になる。 というように考えるとこれはそれぞれの都合のいい値にならないようにするような再帰的な解き方ができる。
具体的には部分和の集合を表すビットとして、 "0000001" を持っておく(現在 $7$ の倍数が作りたいので $0$ ビット目が $1$ )。 このとき高橋くんの $A_i$ について後ろから見るわけだが、現在の bit から $A_i$ だけ循環右シフトしたものを or するという 処理にて、部分和のあり得る集合を埋めていく。もし "1111111" になったなら、どのような値を青木くんが持ってきても 最終的に $7$ の倍数にすることができるので高橋くんが勝つといった感じである。
そして青木くんのターンになった時、この bit を反転する。そして同じように部分和問題を解く。 このとき "1111111" になったなら、どのような値を高橋くんが持ってきても次に高橋くんに渡すときに 高橋くんの都合のいい値にできないということがわかるので青木くんが勝つ。
というように後ろから求め、一番最初のターンが青木くんだった場合は、現在の bit の $0$ ビット目が $1$ であれば、 総和 $0$ の状態から青木くんが勝つように作れるということがわかるので青木くんが勝ち、そうでない場合は負ける。 最初のターンが高橋くんだった場合は、同じように bit の $0$ ビット目が $1$ であるとき高橋くんが勝ち、 そうでない場合は負ける。というような条件になる。
再帰的に解くのはゲーム問題ではよくあるが、集合を持つというやり方が面白いなと思った。
$N$ 頂点 $N$ 辺であるのでこのグラフは一つの閉路を含むグラフになっている。 このとき、それぞれ閉路の頂点を根とした木に分解することができる (閉路の頂点から閉路を構成していない頂点をすべてくっつけるような木)。 今回の問題である、単純パスが一意に定まるという条件は、どちらの頂点も同じ木に属しているかということと同値になる。
これは閉路を検出して、実際に木を構成して色を塗ればよく、 閉路の検出は BFS などで、次数管理して見つけ、あとは、その閉路を構成する頂点から木を作るのを DFS などでやれば色を塗れる。 後は適切にクエリ処理すれば良い。
今から入れるじゃがいもの位置を $N$ で割ったあまりが同じならすべて同じ重さで箱に入ることがわかるうえ、 次に行く位置も変わらないので、$N$ 回程度シミュレーションすれば遷移において閉路ができることがわかる。 その閉路に入ってしまえば同じ事を何回も繰り返すだけであるので、その閉路に入る位置からの操作回数は その閉路の長さのあまりとして考えても同じになるので、予めその時の入っているじゃがいもの個数を取っておける。
そのため、それを求めたら後は辻褄の合うように出力すれば良い。 閉路に入るまでに閉路に含まないノードがあるので、ややシミュレーションが面倒くさくなっている。
重要な考察として、一番活発度の高い幼児は左端か右端に移動すると最適であるということである。 ある二人の幼児で活発度の高い方を端にやらなかったときと比較するとたしかにそうなっていることがわかる。
するとこの問題は、活発度の大きい幼児から左端にやるか右端にやるかを決める DP になる。 この時持っているキーとして、$i$, $l$ を持つ、$i$ 番目の大きい幼児まで決定し、$l$ まで左端を詰めた というように定義する。すると、 $r$ は $i$ と $l$ から出るので DP が可能になる。
この問題は部分木について考えられるようにすると楽に処理できる。 ある $r$ を部分木の根として、$r$ を経由するようなものの頂点の組を調べることとする。 これは、$r$ の左の部分木を $a$, 右の部分木を $b$ とすると、$a$ の方からのパスの長さと $b$ の方からの パスの長さについて変更できる分だけ $2^{D-2}$ 通り存在することがわかる。 最後に $r$ 自体がパスの端点になっているパターンを考え、これは十分深さが存在するときに $2^D$ 通りあることがわかる。 これは $O(1)$ で処理できる。
これを各部分木に対してやれば良い。同じ深さの部分木は同じ答えになるので 部分木の答えに $2^d$ ($d$ は部分木の根の深さ) を掛けて各深さに対して足し上げる。
例によって、主客転倒のテクニックが使われる。ある部分和で $S$ を達成した時、 その添字の一番小さいものと大きいものを $l, r$ とすると、$l \times (N-r+1) $ 個 $f$ に存在していることがわかる。 そのため、これをどうやって DP するかと言うと、dp の現在部分和が $0$ であるようなときに値を足すことを考えて、 このときに $l$ の重みをいれておく。また、$S$ に到達する際に $(N-r+1)$ の重みを掛けて足すということをする。
すると、$dp[S]$ に求めたい値が入ることになる。
一旦、数字をノードとして、ペアになるもの同士をつなげるようにグラフを作ってみると、 このグラフは木になっていることがわかる。 このグラフが木の構造を持つことから親が一つだけ存在し、これはその数字よりも小さいものになっている。
このことを考えると、一番大きい値のペアとなるものというのは一つしか存在しないことがわかる。 そして大きい値から順にペアを貪欲に取っていくと最適であることが言える(詳しくは解説)ので、 そのように取っていくのをシミュレーションすればこの問題は解ける。
木の構造がかなり面白い。稚拙な表現だが綺麗だと思う。
最初に解いたときは、頂点 $i$ についてのすべての $j$ の $\mathrm{dist}$ の和をそれぞれ求めることで その和を $1/2$ したものを出力できるようにした。 まず、部分木に対する答えというのは適切に bit ごとに $0$ の個数と $1$ の個数を保存しておけば、 後から答えを復元できる。
この答えの部分に当たるデータ構造はモノイドの構造を持つので全方位木DP が使え、 すると、すべての頂点を根としたときの答えが出るので、それらを足し上げて答えにすればいい。 答えを modulo 内で $2$ を割る必要があるが、これは答えを足し上げているときに $\mathrm{mod}$ の $2$ 倍で 割ったあまりを求めながら演算することで解決できる。 この解法はかなり重く、1768ms もかかる。
想定解はもっと賢く、全方位木DPを使う必要がなく定数倍が軽い。 まず根付き木を仮定し、木の根を $r$ と置くと、 $\mathrm{dist}(i, j) = \mathrm{dist}(r, i) \oplus \mathrm{dist}(r, j)$ であることがわかる。 このとき、$r$ について 各 bit の $0$ と $1$ の個数が求まっている時、 答えがその bit で $0$ であるものと、$1$ であるもののペアになっているものの個数ということになるので、 そのような答えというのは、 ($0$ の個数) $\times$ ($1$ の個数) ということになり、これを各 bit で足しあげれば 答えが求まる。 この解法は 286ms で通っている。
実装を高速化せよ、的な問題。 まず手続きのループは最大でも $H+W$ 回より多くは回らないことがわかる。 とりあえずこのループは回すとしたら、あとは手続きを $O(H+W)$ 回程度でやれれば良さそうである。 色がすべて同じかというのは、その行か列の残りのクッキーの枚数と、色別のクッキーの枚数を持っておけば どれかがそのクッキーの枚数と一致する場合にわかる。 そのため、これを発見したらその行か列に実際に塗りつぶすような処理を行うようにして、 逐次進めていけばいい。塗りつぶす処理は全体のループで結局 $O(HW)$ 程度しか回らないし、 条件の判定も $26$ の定数倍があるがループごとに $O(H+W)$ である。つまり $O((H+W)^2)$ となる。・・・はず。
この問題は、完全グラフであると考え、エッジ $(i, j)$ のコストに ${A_i}^{A_j} + {A_j}^{A_i} \bmod M$ がついている と考えると、その中から一番エッジの得点が高い木を探し出す問題に帰着できる。 コストの計算は適当に繰り返し二乗法などで求めておく。
するとこの問題は、最大全域木を求めればいいことがわかり、これは最小全域木と同様の方法で、コストが高い順に 木の集合を作るようなクラスカル法を使えばいいことがわかり、この問題を解くことができる。
典型的な包除原理の問題。普通包除原理を使うときは、今回の問題でいうと、どの位置が $A_i = B_i$ であるかというような 使い方になり、計算量は爆発するが、今回の場合、$A_i = B_i$ であるものの $i$ の数が同じであればすべて答えが変わらないことを利用すると、そのような組合せをすべてまとめることができる。
すると今回の答えは、 $$ \displaystyle \sum_{k=0}^{N} (-1)^k \binom{N}{k} {}_{M}\mathrm{P}_{k} (_{M-k}\mathrm{P}_{N-k})^2$$ とまとめられる。 $\binom{N}{k}$ が一致している個数でまとめた量で、順列についてはその場合における答えを表している。
まず、$1, N$ は上の段に行くときに必ず消えるので作れない。 逆にそうでない時すべて作れることを示せる。 ある $x$ を一番上に遷移させたいときは $2$ 段目のときに真ん中と、その横が同じ値になるように工夫すると、 真ん中の中央値は常に $x$ になるので上まで遷移する。
これを作るには、'x' より小さいものを 'y', 大きいものを 'z' とすると、真ん中に $x$ を置くとして、 "zyxz" とおくか、"yzxy" とおけばよい。 これは $N \geq 3$ で必ず作れる. $N=2$ のときは $x=2$ のときだけ考えればいいので、 $(1, 2, 3)$ と置けばok.
これは ABC325 の問題なのでそこでも書いてある。 まず基本の考察として現在印字しなければならないものの中で一番範囲から出るのが早いものを優先して印字するということが 必要である。
また、この問題は座標がかなり大きいので、座標圧縮を使いながら主要となる点のみを考えることにして、 それまでを一気にシミュレーションすると解ける。
この問題は集合をノードとした幅優先探索で解くような解法が思いつくが、案の定普通にエッジを貼るとヤバいので どうにかしないといけない。
そこで、$M$ 個の超頂点を用意する。これは数字を表すノードで、その数字を含む集合ノードに接続される。 これを双方向に接続する。 このようにすると、そのようなエッジ数は $10^6$ 個で収まることがわかる(制約から)。 超頂点から出るほうか入る方のコストを $0$ にしてもう一方を $1$ にすることで集合から集合への移動がコスト $1$ で あることを表現できる。このようにすると 01BFS によって解くことができる。
$S$ をすべてノードにしてしまうような変な解き方を最初してしまった。まあそれでもいいと思うけど。
やや変に解いたので、変に違う技術が手に入った。この問題は想定解としてはまず $1$ から $N$ への最短距離の 一つのパスを保存しておく。この辺の数が $N$ 個以下であることに着目する。 すると、辺 $i$ が通れないとき、もしそのパスに含まれていた場合、BFS で再計算する。 そうでない場合は最短距離は変更されない。
このようにすると、再計算する回数は $N$ 回以下であるので $O(NM)$ ですべての答えが求まることがわかる。
変に曲解して考えた私は、最短距離のすべてのルートを持たないとと思ってしまった。 この時、答えが変化するのはそのような最短距離の DAG の橋の部分であることがわかった。 橋の数は $N$ 個以下であるのでこれでも解ける。 そのためその DAG を求めてから、その DAG の橋を探すために LowLink を学習した。 LowLink はグラフの橋と関節点を求めるのを $O(|V|+|E|)$ でやるアルゴリズムである。
変な解き方かもしれないが、一応説明。 たとえば ABEDCBACDE みたいな $T$ が与えられた時、 $i=2$ を見てみると、答えだということがわかる。$S$ は ABCDE である。
この時、文字列を半分に分けてみて、 ABEDC と BACDE を見てみる。 このとき、ちょうど AB が BA に反転し、 EDC が CDE に反転したものと見ることができる。 つまり、２つに分けたときに２つを反転すると一致するようなものを探したいのだが、 これは、BACDE を反転した EDCAB を見て、更にこれを連結し、 EDCABEDCAB であるようなものを作成するとよい。 このとき部分文字列に ABEDC が含まれることがわかる。 そして、新たに連結した側である EDC を反転すると、CDE とでき、ABCDE と復元できる。
そしてこの位置を探すためには ABEDCEDCABEDCAB という文字列について最大共通接頭辞を見て、 $N+1$ 文字目からの最大共通接頭辞のどこかが $N$ 以上であれば答えを復元するような形になる。 これは結局 Z_algorithm で解くことができ $O(N)$ である。
この問題は、逆にあるノードとノードがつながっているときに、 それによって連結成分がいくつ減るのかということを考えると解ける。 あるノード $u, v(u < v)$ が直接つながっている時、$L \leq u$ かつ $v \leq R$ のときに 連結成分が一つ減るというように考えることができる。
そのため、そのような $(L, R)$ の数は、$u \times (N-v-1)$ であるので、 これを何もつながっていないときの答えである $N(N+1)(N+2)/6$ から逐次エッジごとに引いていくと答えが出る。
主客転倒の一種であるがかなり思いつくのが難しいと思う。 自分はこれが思いつかなかったので、$L \rightarrow L+1$ にするときに $L$ の答えを再利用しながら解いた。
もしこれを DP 配列にしてみると、ただの二項係数になっているが、普通に計算するのはもちろん時間がかかりすぎる。 しかし、実は行についてまとめて計算できる。 $$ \displaystyle \sum_{j=0}^{W} \binom{i+j}{j} = \binom{i+W+1}{W} $$ という計算式が使える。 そのため、この問題の答えは、 $$ \displaystyle \sum_{i=r_1}^{r_2} \left( \binom{i+c_2+1}{c_2} - \binom{i+c_1}{c_1-1} \right) $$ となる。 経路について思いを馳せるとまとめられるところがわかり、うまく考察が進むのではないかと思う。
あみだくじ系の問題を解いたことがある人なら馴染みがあると思うが、 ある位置である index 2 つを swap するものを挿入したのならば、 最終的な結果は元の答えと比較してその index 2 つのみが入れ替わったものになるというものだ。 今回の問題である、swap してたところを swap しないという動作も同様である。
そのため、今回の問題はすべて swap したときの結果を用意しておいて、 $i$ 回目の操作の時何を swap していたのかという情報がわかれば、 そこだけ index を swap することで、各クエリに $O(1)$ で答えられる。
まず $Y < X$ のときは答えは $X-Y$ になるのでこれを省いておく。 $X \leq Y$ のときのことを考える。
このとき、$Y$ から $X$ にするための逆操作を考えると、$Y$ が偶数のときは愚直に $1$ ずつ減らして $X$ にするか、 $1/2$ するかという二択しか無い。もし $Y+2$ や $Y-2$ にしてから $1/2$ するにしても それは $Y$ を $1/2$ してから $1$ 増やすか $1$ 減らすかという操作のほうが操作回数が小さいからである。 同様に $Y$ が奇数のときも 愚直に $1$ 減らして $X$ にするか、 $Y+1$ にして $1/2$ するか $Y-1$ にして $1/2$ するかしか無い。
この状態数を考えると、実はそこまで大きくならないので高速に解けることがわかる。再帰で解く。 もし操作の途中で $Y < X$ になったら $X-Y$ を答えに足す。常に $|X-Y|$ の答えを考慮すること。
辺を取り除くという考えより、辺を使用して木を形成するという考えの方がよい。 そしてこのような木は必ず生成できる。 まず根に適当な数字を置いておく。そして次のノードに移動するときに辺の数字が置いた数字と同じならば それとは異なる適当な数字を置く。異なるのならばその辺の数字をそのノードに書く。というふうにやる。 このようにやれば必ずすべてのノードに数字を書けるのでこれを dfs で実装すれば良い。
先に魔法を唱える回数 $k$ を決める。 すると、あるスライム $i$ を最終的に飼うことを考える時それを作るための最小コストは $\min(A_j, i-k \leq j \leq i)$ となるはずである( $A_{i-N} = A_{i}$ として考えておく)。 これを $k$ を増やすときにうまく min を伝播させるなどして全体の sum を求めればこの問題を解ける。 $O(N^2)$ である。
この問題は、$b$ 進数が $2$ 桁のときの $f$ がまとめて求まることから $2$ 桁のときの計算を速くして解く問題である。 まず、$3$ 桁以上のときはそもそも $b$ が $\sqrt{n}$ 以下であるので全探索する。
$2$ 桁のとき、値は $n = pb + q$ によって表せる。かつ、$p+q = s$ であるので、 $n = pb + (s-p)$ となり、 $\displaystyle b = \frac{n-s}{p} + 1$ となる。 つまり、 $n-s$ が $p$ で割り切れるときに $b$ が整数になり条件を満たすことがわかるので、 $p$ を $2$ 桁の範囲であるところで全探索して最小の $b$ を見つければ良い。 $\displaystyle 1 \leq p \leq \lceil \sqrt{n} \rceil - 1$ であるようだ。
実装のやり方次第でかなり汚くなってしまうので注意。しっかりと立式すると綺麗に解ける(なお上の求め方は解説を参照した)。
まず $2^n \leq L$ である最大の $n$ について、$0$ から $2^n - 1$ までを網羅するグラフを作ることを考える。 これは $n+1$ 個のノードを用意して、リストのようにエッジを張り、順に $2^n, 2^{n-1}, ..., 1$ と張る。 また、もう一つリストのように $0, 0, 0, ..., 0$ を張る。 すると、そのようなグラフは生成できる。 そしてこのようなグラフを生成すると、$2^m, m < n$ であるような大きさの総和の集合を自由に追加できる。 例えば、$0$ から $15$ までを網羅するグラフを生成した後、これに $8$ 追加して、 $0$ から $23$ までにするには、 ノード $1$ から $n-2$ のところへ $16$ の重みの辺を張れば良い。するとそこのノードから $8$ 通り生成されるので $16$ から $23$ までの総和を網羅できるといった感じだ。
そのため、$L$ の $1$ の立っている bit に合わせて適切に辺を張れば、$M \leq 60$ で辺を生成できることがわかる。
まず、グラフに閉路が存在しない場合、必ず分解できることがわかる。 次に長さが偶数である閉路について考える。この場合、番号を閉路について $0, 1, 0, 1, ...$ と振っていけば必ず分解できる。 しかし長さが奇数の閉路については、どのようにやっても最後が隣接しないので分解できない。 そのためこの問題は長さが奇数の閉路が存在しない二部グラフであるかということの判定をすれば分解できるか判定できる。
次にそのようなグラフの $k$ の最大の大きさだが、これはグラフの直径 + 1 になる。 ある頂点から幅優先探索して一番長いところをすべて求めていけば求まる。 幅優先のコストそのものが集合の添字になっていることが確認できる。
これは単に街と宝箱を集合に持って現在位置を持つ bitDP をすれば解ける。 宝箱をとった数だけスピードの上昇の具合がわかるので、 そのときに他の行ってない街や宝箱に向かうときの遷移を適切に実装すればいい。
これは #000254 Printing Machine と全く同じ解法である。 どのボールを先に処理したら良いかというと、右端が一番左にあるものからやるのが最適である。 これを座標圧縮して適切に実装する。
$2$ 番目に大きい値が $X$ であるような $(L, R)$ がいくつあるのかということを考えたい。 これは $X$ があるところから $X$ より大きい値を $1$ つ含んだときの数を求めればいい。 このような数は、左に $1$ 個含み右に $0$ 個含むときのパターンと、左に $0$ 個含み、右に $1$ 個含むときのパターンを それぞれ足し上げる必要がある。この時、$X$ より大きい値の index を set などでとっておくと、そのパターンを楽に計算できる。 $X$ を大きい順にやれば、 $O(N \log N)$ で解くことができる。
この問題はちゃんと読むと任意の位置から文字をとったときの通りの数を求める問題であるので 実は $S$ の順序によらない。したがって、ある文字が何個あるかということが大事になる。
この時文字ごとに見て、 $dp[c][s]$ ... $c$ までの文字を見て、現在の文字列の長さが $s$ のときの文字列の種類数 ということを考える。ある文字を $k$ 個追加するときには、もともと文字列の長さが $s$ だったとすると、 $k$ 個追加するときに考えられる通りは $\binom{s+k}{k}$ 通りだけある。 そのため、$dp[c+1][s+k]$ に $dp[c][s] \times \binom{s+k}{k}$ を追加すると良い。
$i$ ごとに各 $s$ に 文字 $c$ の文字数分 $c_i$ の遷移を考えるので、$O(N^2)$ となる。 $N$ 個の値が $26$ の入れ物に分散しているだけなので、$26$ は定数倍にならない。
かなり面白かった。解き方は色々とある。
自分が解いた方法として、まず赤を塗る方法を $2^N$ 通り考えておく。この時 緑と青で他の頂点を塗らないといけないわけだが、 これは赤の頂点を取り除いたグラフにおいて、二部グラフ判定をすれば塗れるかどうかがわかる。 またこの塗り方は連結成分ごとに $2$ 通りある。その為これをかけ合わせる。 これは $O(N+M)$ でできるので $O(2^N (N+M))$ で解くことができる。
想定解は、単純に dfs で全探索をしていた。しかし、塗る順序を工夫することで重複を無くすようにしていた。 ある連結成分についてある頂点から preorder に塗る順序を決めておく。 そしてその順序に塗るようにすると、重複無しで塗ることが可能になる。
なお、間に合う理由としては、$2$ 個目以降の塗り方はそれぞれ $2$ 通り以下にしかならないからである(どこかが塗られているので)。
今までに選んだ状態と直前に選んだものを持ちながらゲームDPをすれば解ける。 自分の番にて、ある文字を選んだときに相手がどうあっても負けているような物を探してあった場合はそこから見たら勝っている と判断するような感じで解く。 $O(2^N N^2)$ である。再帰で解いた。
ABC326 の感想でも書いている。 よくある重実装。行について next_permutation してパターンを作ったほうがやりやすいと思う。 後は文字一致を正確に実装する。
自分が解いた方法は、とりあえず $1$ の倍数になるものを考慮しないで $2$ の倍数以上で作るようなDPを考えた。 $\mathrm{DP}[i][S]$ ... $i$ まで整数列を作り、$A_i = S$ であるようなものの総数という感じ。 このようにするときに、整数列のサイズは $O(\log M)$ 程度になるので小さい。 遷移については、$S$ の倍数についてすべて見るので、$i$ についての遷移が調和級数になり $O(M \log M)$ で済む。 したがって $O(N + M \log^2 M)$ である。
このような数列を作り上げたら、後はそのような数列について $1$ を散りばめることを考える。 ある作った数列のサイズが $i$ だったならば、 それに対して $1$ をサイズ $N$ になるまで散りばめるので、 そのような散りばめ方は、$\binom{N}{i}$ 個だけ存在している($N$ 個の数列の中に $i$ 個の作った数列を任意の位置に入れるため)。 そのためできた DP 配列のすべての要素について $\binom{N}{i}$ を掛けて総和を出力すれば良い。
想定解は、$1 \leq i \leq M$ であるすべての $i$ について素因数分解したものを用意して、 $A$ の末尾が $i$ になるようなすべての数列を考える。 このとき、ある素数 $p$ の使われる数を $c$ だとすると、この $c$ 個を $N$ 個の数列の中に 掛けておかないといけない。同じところにかけても良い。 するとこのような通りの数は、重複組合せであり、$\binom{N+c-1}{c}$ を計算すると素数 $p$ についてもとまる。 そしてこれを各素数に掛け合わせると $i$ についての答えが出ることになる。 すると、$O(N + M \log M)$ になるかな。ただ定数倍が重いイメージ。 横着すれば $O(N + M \sqrt{M})$ とかだと思う。素因数分解を特に工夫せずに独立して求める場合。
よく考えてみると、この問題は相対的な位置だけが重要であるので、最初に平日にするところはどこでも良いことがわかる。 そのため曜日 $1$ を平日としてみる。この時 DP が可能になる。
$\mathrm{DP}[i]$ ... 曜日 $i$ を平日にして、曜日 $2$ から $i-1$ までの平日を適切に選んだときの最大の生産量 というようなものを求めておくと、これ以上先の曜日に平日を入れないとしたら、$\mathrm{DP}[i]$ に $i$ から曜日 $1$ までの間の生産量を足したものが $i$ についての答えになる。 これを $i$ についてすべて求めて最大値を出せばそれが答えになる。 DP の遷移に $O(N)$ かかり $O(N^2)$ で求まる。
よくある拡張 Dijkstra である。今回は都市 $t$ に行くだけであったら銀貨は $2500$ 個より多くは使わないはずである。 そのため現在の都市 $i$ と現在の銀貨 $S$ を持ってダイクストラすれば十分間に合う時間で解ける。
範囲を持ってシミュレーションすればよい。 最初にものすごく大きな区間を用意して、各所各所で max や min をとっていくと範囲が潰れていく。 そして最終的にできたものは、結局最後まで普通に足せるのを保てたものになっていて、 ということは、その sum を引いたものが一番最初から関数を通すときの潰れない範囲になっている。
範囲外にあるような $x$ は範囲のうち近い方の値をシミュレーションしたものと同じになる。 そのため 区間の $L, R$ が求まったならば、clamp(x, L, R) + sum が答えになる。
主客転倒を考えるとうまく求まる。ある散らかってないマスが光るような通りが何通りあるのかということを計算する。 このとき、そのマスの十字のマスの中で一つより多く照明があり、その他のマスを任意とすると、 そのマスの十字のマスの個数を $X$ とすると、$(2^X - 1) \times 2^{K-X}$ だけ存在することがわかる。 そのため十字のマスの個数を適切に高速に求められる工夫ができれば、各マスについて数え上げて高速に答えを出せる。 ちょっと累積和がめんどくさい。
想定解だと、まず平方数を $S^2$ とすると $x^2 - y = S^2$ になっていればよく、 これは $x^2 - S^2 = y \rightarrow (x+S)(x-S) = y$ であるので、 これを $pq = y$ と置くとすると、$p \geq q, pq = y \leq N, p \equiv q \pmod{2}$ であるような $p, q$ を探せば良くなり、 これは $q$ を全探索することで、条件を満たす $y$ を見つけられる。 同じ $y$ がでてきても、$p$ が異なれば $x$ が異なることになるのでこれで全列挙ができる。
自分は当初 $x^2$ の増える差分に着目しながら、二分探索を駆使して解いたが、すごい汚い解法になった。
ABC326 の感想でも書いた。 まずある整数にたどり着く確率 $p_i$ を求めておく。 すると、$A_i$ は $p_i$ だけ寄与することがわかるので、これを掛けて合わせて出力すれば良い。 $p_i$ は単純に DP で求まる。累積和を使う。
エスパーしてみると $(N+1)/N$ だけ $p_i$ が掛けられていくようだ。
オイラーツアーのように頂点をたどっていけば、移動する回数は $2(N-1)$ 回以下で済むのでこれを 適切に実装すれば良い。
$i$ 以外の部分和が DP 配列として今求まっていると仮定する。 この時、$i$ を処理すると何かの部分和が $K$ 以上になるとき、これは必要なカードで、 逆に何もまたがなかった場合、不必要なカードということになる。
そのため、このような部分和の DP 配列を作りたいが、まず $K$ 以上になるかどうかという情報しか必要ないので $K$ 未満の配列だけ持っておけば良い。 ただこれでも、 $i$ を省いた部分和 DP 配列を作るには愚直にやると $O(N^2 K)$ かかってくるので、どうにか早くしたい。 そこで、$1$ から部分和を取る DP 配列 $L$ と、 $N$ から部分和を取る DP 配列 $R$ を用意する。 このようにしたときに、 $L[i-1]$ と $R[i+1]$ に着目する。 この配列を組み合わせると時間がかかるが今回必要な情報は、 $K$ 以上になるかどうかであるので、 $L[i-1]$ の部分和と $R[i+1]$ の部分和を組合せたときに $K$ 以下で一番大きくなる値を見つければいいだけである。 すると、これは尺取りの要領でスライドしていけばいいので、 $O(NK)$ で求まる。
$a_i$ の小さい順に実は単調性があるらしく、二分探索でも解けるようだ。 あと、間違える確率があるが戻す DP で全体から戻してもよい (通りが爆発するので $\bmod p$ を取ることで対処するため低確率だが間違える)。
ABC321 の感想で書いたが、戻す DP は $i$ の小さい方から見て、 $\mathrm{DP}[i+x]$ を $\mathrm{DP}[i]$ で引くと完成するようだ。 絶対に $x$ を使ってないところからみると、そこから使ったものの個数がわかるからである。 それが $\mathrm{DP}[i+x]$ に存在しているのでそれを消す感じである。
最大値が変化するところはその値が入っているということがわかるので、 このときもう片方がそれより小さい値が入っている場合 $0$ 通りが確定する。
逆に最大値が更新されていないような場所( $i$ とする)では、$1$ から $\min{(T_i, A_i)}$ の範疇で自由に選べるので その通りを掛けていけば良い。
色々と解法があると思うが、$K \times K$ の領域ですべて考えられないかと考える。 ただループしている領域は $2K \times 2K$ であるので、座標 $(x \bmod 2K, y \bmod 2K)$ を考える時、 $x \geq K, y < K$ か $x < K, y \geq K$ のときに $c$ を反転させて、 $(x \bmod K, y \bmod K)$ の領域に押し込むと同じ答えになることがわかる。
チェックのバリエーションは黒色の部分の左上の位置をどこにやるかということで決まり、 これを全探索したい。そのため、押し込んだ座標についての $2$ 次元累積和を取ってあげて、 ある領域を黒にしたらいくつの願いを叶えられるかと、白にしたらいくつの願いが叶えられるかを $O(1)$ で求められる ようにしておくとこの問題が解ける。 ちょっと重実装である。重実装と言うか頭が壊れると言うか。
どっちも二分探索すると楽に解けることが知られている。 まず平均値の方は平均値の最大値は $X$ 以上かという問題を解くことにする。 すると、$A_i - X$ について値を最大化する DP を解き、答えが $0$ 以上かどうかで判断できる。
中央値については、中央値の最大値は $X$ 以上かという問題について解く。 これは結局、ある $n$ 個の整数を取ってきた時に $X$ 以上の値の個数が $\lfloor n/2 \rfloor + 1$ 以上であるようなものが存在する場合はそのような命題が解ける。 そしてこれは $X$ 未満の $A_i$ を $-1$ , $X$ 以上の $A_i$ を 1 としたときの DP を解き、 これが $1$ 以上である場合にそのように判断できることになる。
実装を頑張る問題。と言うほどでもないが。たとえば $(1, x)$ に石を置いた場合、 これから $(1, y) (x < y)$ に石を置く命令がでても $(1, x)$ に石を置いたときの白に置き替わるマスの数分だけ置き換えることができる。
そうすると、$(1, y)$ についての増分が確定するので小さい問題だけ考慮しながら計算していけばよく、 同じようなノリで実装すると、ちゃんと求められる。
説明になってない気がするがまあこれでもいいや。
こういう問題はある $X$ 以上の幸福度の握手を行ってみることを考えると、 その握手の回数が $M$ 以上であるような $X$ の最大値に着目すると、 $M$ 回目の握手は $X$ の幸福度を持つことがわかる。
そしてその $X$ を決めてシミュレーションすると、$X$ 以上のすべての握手の幸福度の総和と握手回数が $O(N)$ でわかるので(尺取りを使う)、 $M$ 回に調整するには $X$ を超えた分だけ減らせばいいのでこれで最大の幸福度が求まる。
例によって最初の $X$ を探すのに二分探索をするので、 $O(N \log N)$ で解ける。
永続 stack と言うらしい。まあ、データの挿入の様子を木として表現すると、 データをさかのぼりたいときは木の親を見ていけば良いわけである。
セーブ時は現在の頂点の位置を保存しておけばよい。
まあ、缶切りが不要なやつを一回大きい順に $M$ 個選んでから、 多く開けられるオープナーを何個使うかで適宜缶切りが必要な缶に入れ替えていくようなことをすると ACできる。
まず $a$ の $\max$ と $\min$ の差が $2$ 以上あることは絶対に無いので取り除く。
差が $0$ の時を考えると、各猫がそれぞれユニークな色の帽子をかぶっているパターンと、 各猫がそれぞれユニークでない色の帽子をかぶっているパターンが考えられる。 とりあえず $a$ の値を $A$ と置いておこう。 ユニークな色の帽子をかぶっているパターンは、その性質上、$A = N-1$ である必要がある。 逆にユニークな色じゃない場合は必ずその色が $2$ 色以上なければならないので、 $A \leq \lfloor N/2 \rfloor$ である必要があることがわかる。
差が $1$ の時を考える($A$ を小さい方、 $B$ を大きい方とする)と、 $a_i = A$ である方は自分の色がユニークであり、$a_i = B$ である方はユニークでないということになる。 そして全体の色は $B$ 色あるとわかる。 すると、 $A_i = A$ の数( $C_A$ とする)だけ色が消費されるので $B \leq C_A$ の場合はまずありえない。 そうでない場合は、いま後 $B - C_A$ 色残っているが、この時、ユニークな色じゃない猫が $N-C_A$ 残っている。 これについて考えるときは差が $0$ のときのユニークじゃない色について考えるのと同じであるので、 $B-C_A \leq \lfloor (N-C_A)/2 \rfloor$ について見ると良い。
$M \leq 10$ であるので、最大でも $10$ 個先の都市にしか移動しない。 ということは、$k$ が通れなくなっても代替のパスを探すには $k-M+1$ から $k-1$ あたりで $k$ を超えるような辺を探してそこからのパスを見つければ良さそうである。
頂点 $1$ からの最短路 DP と頂点 $N$ からの最短路 DP の配列を作れば、 先のような辺を見つけることでその辺を使ったパスが構成できて十分速い。 $O(NM^2)$ かな？
とりあえず $a_i = 30000 \times i + 1, b_i = 30000 \times (N-i+1) + 1$ としておく。 いますべての $a_i+b_i$ が同じであり、まだ第三条件を満たせていないが これに対して $a_{p_i}$ に $a_{p_i} + i$ を代入すると、 $i \leq 20000$ より $a$ の大小関係を変えずに第三条件を満たせる。
まず、行ける範囲の広がり方について考察する。 $2$ 回の移動をしてもとの位置あたりに戻ってくることを考える。 すると、左側と右側に $D-C$ だけ範囲が広がるということがわかる。 そのため、 $A$ から $B$ に移動するために $D$ でできるだけ近くまで移動して、 そこから偶数回行って戻るを繰り返すときの範囲の広がり方を計算すれば $B$ に行けるかどうかが判定できる。実は $O(1)$ である。
主客転倒を考え、$A_i \neq A_j$ であるような数列の個数を探すことになるが、 このパターンも $O(N^2)$ あるので、速く計算しないといけない。
このとき、 逆に $A_i = A_j$ のものを探して全体から引くことを考える。 全体の求め方も少し難しいが累積和を駆使しながらうまくやると行ける。 そして同じものに対しては、あり得る数列の数が少ない方(左端及び右端の方)から順にそれより内部にあるものを 計算するような形で求めることができる。よくわからない言い回しだけど、実装もそれなりに難しい。 Diff = 1485 とは思えない。
同じものを求めるという方針で考えるよりも実はもっとスマートな計算方法があった。 これは実装が楽で Diff が 1485 でもいま納得した。 $i, N-i+1$ を $i$ の小さい順に同時に見ながらやっていく方法で、$i \leq j \leq N-i+1$ である $j$ について 考える。 このとき、 $A_i, A_{N-i+1}$ のそれぞれについてその値と異なる値の数が実は求まり、 それに対して $i$ でかけたもの (それぞれに対しそのような数列の数は $i$ 個であるため) を足し上げる。 なお $A_i \neq A_{N-i+1}$ の場合は重複して計算しているため、 $i$ を引いておく。
$A_i$ と異なる値の数はその範囲に置ける $A_i$ と同じ数をその範囲から引いたものになっている。
よくわからない解説になった。
基本的にクラスカル法を思い浮かべながらやっていく。 そのため、$C_i$ が小さい方から見ていくことになるが、このときに頂点を結ぶと、 連結成分数が $\mathrm{gcd}(N, A_i)$ になることがわかる。 異なる連結成分の頂点は隣接して並ぶような感じになっていて、これから頂点数を $\mathrm{gcd}(N, A_i)$ と見て 考えても問題ないような構造になっている。
そのため、頂点数が $1$ になるまで頂点をつなげるようにすると、この問題を解くことができる。 $1$ にならなかった場合は $-1$ である。
重複する部分を取り除くために包除原理が使える。
答えとしては、$f(T)$ を集合 $T$ に含まれる要素の文字列で共通して使える文字の数とすると $$ \displaystyle \sum_{T \subseteq \{1, 2, ..., N\}, T \neq \{\}} (-1)^{|T|-1} \times f(T)^M $$ となる。 今回はベン図のそれぞれの丸を正の部分にしたかったので、$(-1)^{|T|-1}$ となっている。
一回すべてのスポーツを選ぶことにしたときに、このとき最も多く参加しているスポーツについて考える。 このスポーツを削除しない限りはそれより最も多く参加しているスポーツの参加人数が小さくなることがないので、 そのスポーツを削除する。これを $M$ 回繰り返して参加人数の一番小さかった場合を求めると正答になる。
二分探索で考えるとわかりやすくて、ある参加人数 $X$ 以下になるまでスポーツを削除するような方針を 効率的にやると実は二分探索が必要なくなるような感じだ。
期待値の式をしっかりかければそこまで難しくはない。あとはこれをもとにDPするだけ。 ある位置 $i$ から $N$ に行くまでの操作回数の期待値を $E[i]$ とする。 このとき $E[i]$ について立式すると、 $$ E[N] = 0$$ $$ E[i] = \left( \frac{1}{A_i + 1} \sum_{j=0}^{A_i} E[i+j] \right) + 1$$ となっているはずである。
例によって $j=0$ のときが厄介であるので式変形する。 $$ E[i] = \frac{1}{A_i+1} E[i] + \left( \frac{1}{A_i+1} \sum_{j=1}^{A_i} E[i+j] \right) + 1 $$ $$ \frac{A_i}{A_i+1} E[i] = \left( \frac{1}{A_i+1} \sum_{j=1}^{A_i} E[i+j] \right) + 1$$ $$ E[i] = \frac{1}{A_i} \sum_{j=1}^{A_i} E[i+j] + \frac{A_i+1}{A_i} $$
このようになれば、もう求まる形になっている。 期待値の総和を求めるフェーズがあるのでこれを累積和で高速化して解くことが可能になる。
期待値の立式について慣れていないとかなり難しい問題で、変に DP しても解けないようになっている。 この式を出すためにも色々記事を漁ったり EDPC の Sushi を解いてみたりとか色々やった。 ただ、やり方を慣れられれば、慣例に沿って解くだけになると思う。
期待値 DP という名称よりかは、期待値を立式すると漸化式が出てくるので DP をすると解けるといったほうが 正確かもしれない。 逆から解くものだというよりかは、正確に立式すると逆から解くような構造になるといったほうが正しいか。
まずすべての区間は持つことができる。この中から作れば良いわけである。 最上位ビットの方から $K$ 個 $1$ を取ってこれるかを考えれば良い。 取ってこれる場合は $1$ を取ってこれるものの集合のみを考え、次の bit を見ていけば良い。
前回と大体同じ行数になった。感想なので説明を省けるところが多くなったのか。
新しい問題もあったが、新しい問題は基本的に Diff は水青の境界くらいだった。 昔の 2019, 2020 年くらいの問題だと結構 Diff が高い青もでていた。 ABC の問題が多かったのでかなり勉強になる問題が多かったと思う。 かなり良い順序で出題されている。
ただ、みんな問題が難しくなっているので、重要か重要でないかと分ける意味がよくわからなくなってきた。
もう、記憶に残った問題という意味でいいかな。
良い出題順序で教育的な問題が出るので、かなり助かっている。最近解いている問題が、 前に解いた問題で学んだことで活かされることがよくある。 Solver 順というやり方はかなり良いのかもしれない。
書くのに１ヶ月かかった。おかげで #000386 まで進んでいる。 もうもはや同列で書き込んでいくものと見ても差し支えないよなぁ。 とりあえずARCのやつまだ書いてないので書こう。
(2023/12/05 18:27)