ABC190 反省と解法 - 文学徒が競プロをするブログ

ABCEの四完。Eを通したのがせめてもの救いだが本当に不甲斐ない。
1300パフォ程度は取ったが、後日自力でDFを解き直すと10分程度であっさり解けてしまった。全完するべきセットだったと強く感じる。大反省......。

全完の目がある得意セットなんて十回に一回あれば良い方だし、失敗した自分が情けない。もっと頑張ろう。

A問題 Very Very Primitive Game

どう考えてもBより難しいと思います。これなに？
とりあえずお気持ちif文を投げたら落ちたので、適当にシミュレーションして通した。こどふぉDiv2のAみがある。

B問題 Magic 3

最易。問題文に答えが書いてあるので、言われたとおりにやります。

C問題 Bowls and Dishes

びっっっっっっっっくりするくらい初見難しかった。ARC111のB問題と若干似ていたので一瞬グラフを書き始めたが、制約をよく見ると $K \leq 16$ で全てを察した。

普通にbit全探索で全部試してAC

D問題 Staircase Sequences

解けなかったやつ。難しいよ～～～～とか言ってたが、今考察ノートを見返すと取り掛かって五分で本質の式変形まで済ませていて笑ってしまった。何でそこから20分以上悩んだ挙句に飛ばすねん。

S = 数列の和, A = 初項, N = 数列の長さとして、等差数列の和の公式を変形すると

$S = \frac{1}{2} N(2A + (N-1))$

$2S = N(2A + (N-1))$

$2S = 2AN + N(N-1)$

こうなる。長さを決め打つとすると初項Aについて解けばいいので

$A = \frac{2S - N(N-1)}{2N}$

こういう形の式になります。
この式が整数解を持てばいいので $2S - N(N-1) % 2N = 0$ になるかNを決め打って確かめればいいことが分かります。ここまでは速かった。

この後、アホなので ${10}^{6}$ くらいまで決め打てばいいかな～とか言いながら愚直にNを1から決め打とうとしたものの、当然 ${10}^{12}$ まで決め打つ必要があるのでダメになり。

サンプルをグッと睨んで入力が12の時の数列の長さを確かめると、24の約数になっていることがわかったので高笑いしながら $2N$ の約数列挙を実装 -> サンプル3が合いません......何もわからない......。になりました。

原因はオーバーフローの見落としでした。真正のアホ。

てっきり $2N$ の約数だけ見ればいいわけではないのだと思ったのがこのやらかしの原因でした。

そこで $2N$ の約数だけ見ればいい根拠を自戒として示しておきます。
上の変形途中の形をグッと睨むと

$2S = N(2A + (N-1))$

となっています。 $(2A + (N-1)) = M$ とすると $2S = N \times M$ です。よってNとMは両方とも $2S$ の約数であることが分かります。決め打ちたい長さはNなので、 $2S$ の約数だけ見ればいいことが示せました。

本当にノートを見返して脱力してしまった。視野が極端に狭くなってしまっていたのが本質的な敗因ですね。
最近数式を用いて思考を整理し、段階的に考察することを意識しているのですが、まだそれらの行為に慣れておらず、いっぱいいっぱいになりながら頑張っているような感覚があります。数式を思考の道具とする習慣を徹底し続けていくことを肝に銘じます。

E問題 Magical Ornament

これが青diffなの、最近の初心者レベルインフレに慣れていたので逆にびっくり。絶対先週のアフィン変換より簡単だから。新規参入者は全員数強東大生なんじゃないかという僕の疑念がまた深まってしまったな......。

問題文の「魔法石 $C_1,C_2, ... ,C_k$ をそれぞれ1個以上含む魔法石の列を作る」と制約の $K \leq 17$ が「bitDPで解くよ～」と宣言してくれています。自己紹介ありがとう。

で、問題文を読んで考えると、隣に置ける数字がそれぞれ決まっているので、数字どうしの関係性をグラフとして考えることができ、数列 $C$ の数字が全て連結でなければならないことがわかります。

更にグラフとして考えるやり方を進めると、 $C_1$ を置いた後に $C_2, C_3, ... , C_k$ を置くのに必要な数字の個数は $C_1$ から $C_2,C_3, ... , C_k$ までの最短距離であることに気づきます。

これで問題は巡回セールスマン問題に帰着され、各辺のコストもわかった状態になったので、bitDPをやっておしまいです。

この「bitDPに必要な重みをグラフの最短距離として求めておく」という考え方は ABC180-Eで既出なのですんなりと出てきました

具体的な実装は、グラフで数字の関係性を持ち、 $K*(K-1)/2$ 回BFSして重みを求めたうえでbitDPというそこそこ面倒なものでしたが、結構すんなり通せて嬉しかったですね。でも青diffではないだろ。

F問題 Shift and Inversions

不甲斐ねえ～～～～～part2.

残り25分あってなんでこれが解けなかったんですか？
誤読しました................

どう誤読したのかというと $b_i = a_{i+k \bmod N}$ を $b_i = (a_i + k) mod N$ に誤読しました。

これだと区間加算更新の区間和取得が出来るデータ構造で解けるんですが、使っていたPCにACLを実行できる環境がなく、そもそも転倒数の詳しいことを忘れており(ゴミ以下のアホ)、アルメリアさんのACLの遅延セグ木の記事を見ながらAtCoderのコードテストで頑張りましたが時間切れとなりました。

ちゃんと誤読せず読むと色々やりようはあるのですが、こういう円環として回すやつは同じものを二つ繋げて並べてしまうのが好きです。

そこでBITなりセグ木なりで適当にやれば解けます。別になくても解けますが、無思考で解けるのでやっちゃいました。

総評

何回自分の愚かさを噛み締めれば気が済むんですか？