ARC166 で緑Diffが解けていなかったのをきっかけに、ARCの問題に慣れておくという意味合いもあり 緑Diff までの問題をすべて解いてみました。水以上は今進めてる Solver 順に解く方ででてくると思うのでそのときに。
110 問を大体 2 週間かけて埋め終わったわけですが、ARC の問題は難しいですね。 まずどのような問題でも必ず考察は必要で、灰Diff の問題でもそれは変わらないと思います。 ABC と違うところを言うのならば、特別なアルゴリズムの知識がなくても、プログラムがかけてしまうところですね。 ABC の問題では、データ構造をうまく使うだけの問題や最短路問題を解くだけの問題とかでも、緑Diff とかに上がってきます。 これは、単純に典型として知らない人が多いので、その人がふるいに落とされているように見えます。
ARC の問題は、解法が単純になることがかなり多いので、わかりさえすれば誰でも通せるみたいで、 考察が割と必要な問題でも茶や緑にあることがあってかなりこっちとしては難しいなと思えました。 結構、 $O(1)$ で求めてください系の問題が、灰 Diff に結構あって、どこかで計算を間違えないようにビクビクしてやってました。
ABC とは違った意味での複雑性を持った問題がかなり多かったと思いました。ABC は実装方法を考えさせられますが、 ARC は正しい答えを出すためにはどのような条件が必要かというところが場数の必要なところかも知れません。 書いてみるとコード数は少ないのですが。
ちなみに問題に割り振ってる番号ですが、上位 2 桁を種類別にナンバリングするようにしてみました。 水Diff の Solver 順に解く方は 00 で ARC の 緑Diff までのやつが 01 というようになっています。 さすがに9999問を超えることはないでしょう。
ARC らしい。 $2X = A+B$ , $2Y = A-B$ なのでまあうまくやってあげよう。
各部分文字列について A の数と T の数が等しいか、 C の数と G の数が等しいかを見ていけばOKだと思う。 伸ばせば $O(1)$ で計算できるので、それでやろう。
なんか bit とか使ってやると良いのかな。
不変量の典型問題なのかなぁ。まずこれらの処理をしても全体の gcd は変化しない。 全部処理することを考えると、最終的な答えも gcd に落ち着くみたい。
値がすべて同じになる時はそれ自体が gcd になるからかな？ これは面白い問題だと思う。
まあ全探索でしょう。これは ABC でも出る。
連結成分の中の値はおそらく総和が同じならばすべてのパターンを作れると思われる。 連結成分の総和が条件の総和と同じになっていればそこについては可能。 これをすべての連結成分について試せばいい。
グラフが出るだけで Diff が上がっている。
分解して計算。$A, B, C$ も小さいので安心。
こういうのだよ。これが ARC だと思う。やり方としては $a+b$ を決めれば $c+d$ が決まるので、 これを決めた後、 $a+b$ と $c+d$ のそれぞれについてあり得るパターンをかけ合わせるというものなのだが、 この $a+b$ でありうる $a, b$ のパターン数ってどう考えたら良いのか。 $O(1)$ で求まることはわかっているけど、 厳密に計算しづらいのだ。なんか $a$, $b$ に $1$ から $N$ という定義域が敷かれてるし、max とか min とか使うんだきっと！ ってなって多分コンテストでは 10 分くらい溶かす自信がある。
ようは $a$ を決めたときに $b$ がどうなるかでしょう。このとき $b$ がちゃんと定義域に入ってれば良いわけでしょう。 $a+b-1$ が $b$ の最大なので、これと $N$ との min をとる、$a+b-N$ が $b$ の最小なので、これと $1$ との max を取る。 すると、 $\min{(a+b-1, N)} - \max{(a+b-N, 1)} + 1$ という答えがでてくるはず。 このように、めんどくさいのだ。
こういうのは解けるんだよなぁ。考えが割とシンプルだから。 まあ $N, M$ が $P$ の約数のものしか無いので、それだけ全探索すれば良いのでしょう。
自分は stack を持って可能性のあるものを pending にしておくことで実装した。 想定解はただ、新しい文字列を形成するだけでいけるっぽい。fox が末尾にでてきたらすぐに削除。
やりづらい。廊下で移動したほうが速い場合は廊下だけ使うのでシミュレーション。 階段を使いたい場合は、まあこれも廊下でどっちを使うか、だろう。
想定解はかなり単純なグラフになることを見抜いていて、横に並べられるみたい。 複雑な状態からいかに単純にするか、ARC にはよくあるやつだ。
これ、きちんと証明して解いた人どのくらいいるんだろう。長さ $n+1$ の丸太を使って小さい丸太をできるだけ補うのが最善 というのは割と非自明な気がする。
自分が考えたのは、まず大きいものだけ使えばいいということがわかるところから始まり、 では大きいものを $k$ 個使用する時どのように使えばいいのかという話にしてみた。 この時、$n$ よりちいさいものはぴしっとハマるものがあるので、全部それに使う。 この際、残った丸太の総和は当然 $n+1$ になっているが、もちろんこれが最大である。 しかも、丸太はどこも切れていないのでその他の丸太のために使うには最適なものになっている。 そのため $k$ 個使用する時について $n+1$ の丸太は必ず小さい丸太に対して使うことがわかる。
みたいな事を踏まえないと、書けなかった。
あとは二分探索で調べてもいいし、二次方程式を解いてもいい。ただ精度に注意。
最初に解いたときはもっとトリッキーな丸太の切り方をしてみていたが、それでも一応ACできた。 大きいものと小さいものに切り分ける、的な。
winner[j][i] ... 番号 $i$ の人を一番左にした参加者 $2^j$ 人のトーナメントの勝者 というのを作る。そして、winner[j][i + ln] = winner[j][i] ( $l$ は整数) であることがわかるので、 $i$ の添字は $N$ 以上について見なくてもいいことがわかる。
すると、$j$ の小さい順から、対応する式を解いてあげて、最終的に winner[k][0] に答えが返ってくる。
結構楽しい問題。なんか綺麗よね。
$\mathrm{lcm}(2, ..., N) + 1$ が答えになる。まあそうっちゃそうだけど。
条件分岐を頑張る。T="1" なら $2 \times 10^{10}$ , T="0" なら $10^{10}$ , とかいろいろ。 とりあえず $T$ が $2$ 文字以下のものは分岐させておく。
$T$ が $3$ 文字以上なら、"110" か "101" か "011" をつなげてできたような文字になっているかを見る (ぴったりつながってなくてもよい 11011 みたいなのも大丈夫)。 この際、横にスライドすると何個できるのかと言うのを頑張って計算する。 $T$ のサイズと文字列の種類はなにか というのをうまく組合せてやると良い。
まず $1$ を左にやろうとする事を考える。このために $1$ より左にあるものを退けるために $1$ の位置以下のものの スワップは必ずしないといけなくなる。というふうに考えると、次の値をまた左に持っていくときに操作可能かどうかが 判定できることになる。
$10^N$ を $M^2$ で割ったあまりで求めておくと、$M$ でそのまま割ったときに答えになる。 ちょっと割り算するくらいなら、mod の制約を緩めるという方法が使える。
$A = 2L$ のときから条件を満たすものを作れる。 これを $R$ までやることを考えると $1$ から $N$ の総和みたいな式になって、 $(R-2L+1) \times (R-2L+2) / 2$ が答えになる。 こういうのは面倒だなぁとおもった。
座圧して imos をすることで無理やり解いた。 現在の値から足した値というのは先にコスト $2$ を払っておくことで実現できると捉えられる。 現在の値から引いた値はコスト $0$ でok. 現在の値の符号逆転したものの正負に伸ばした値は コスト $1$ 払うことで実現する。 この範囲をうまく imos すると解ける。
全探索して問題ない。
$A$ は何乗するともとの値に戻ってくるかというサイクルを考えて、 $B^C$ はそのサイクルの大きさで割ったあまりを出しておく。 そうしたら、その値を累乗して計算すると解ける。
$0$ 以外は全部もとの値に戻ってくるのが救い。違うところでサイクルができるとかそういうことになってると、 ちょっと実装が厄介な気がする。
できるだけ右のもので条件を満たすものを操作したほうが良い。 右からやって高速にシミュレーションすればいい。
$1$ から $50$ までの素数の数は $15$ 個しか無い。この素数のどれかを使って $Y$ を作るとして、 その中で条件を満たすものの最小を求める。これは bit 全探索でどうにかする。
連結成分の個数を $2$ の累乗したもの -1 が答えである。具体的には閉路を $T$ に含めることになる。 functional graph である。
実は $1$ の数の偶奇が等しくないものが正解した問題の数がどうやっても等しくないものになる。 これが等しくない場合、解いた問題数の偶奇も異なってくる。そのため、ある問題の解答が異なるものにたいして 正解を変化させても、偶奇は変化しないのでどうやっても等しくならない。
$1$ の数の偶奇が等しい場合は、解答が異なるものの数/2 だけ正解を $0$ にすることで同じにできる。
自分は bit を $2$ つ変化させたものが解答が同じになるものになるということを考察して dfs して解いた。 かなり時間がかかる。
まず $C$ については行の差分について同じ値でなければならない。これが同じだった時のことを考える。 $B$ の値をできる限り小さくしておくと、$A$ は大きくなるので便利そうである。 そのため、差分で一番低くなる値を $0$ に調整して $B$ を作成、この際に $A$ を作った時、 $A_i \geq 0$ になるかを見れば良い。いや、どうやっても $A_i \geq 0$ になるようだ。
どのようなやり方でもいいが、$A_i$ については $i$ の素因数のべき乗の最大値 $+1$ を入れておけばいいようだ。 そうすればどの約数でもかぶることはないようにできる。 もし怖いのであれば、普通に約数を列挙して現在のそれらの使ってない値の中で小さいのを入れてもいい。
$N$ が $4$ で割り切れるのなら "Even", そうでなく $2$ で割り切れるのならば "Same", 割り切れないなら "Odd" となる。 素因数分解したときを考えて積を考えると $2$ を何も使わないパターンが約数が奇数になるもので、 $2$ を $1$ 個使うパターンで偶数の約数を同じだけ作れる。 $2$ を $2$ 個使うパターンも作れるなら偶数のもののほうが多くなる。 と言った理由からこういう答えになる。