コンテスト後のツイート
AtCoder Regular Contest 130 AB解いた後、まずCD考えたけど、ふとFを見たらこっちの方が解けそうに見えて、結局解けぬまま終わるというのをやってしまった。
— titia (@titia_til) November 28, 2021
C - Digit Sum Minimization
公式解説は見ずにACしましたが、「繰り上がりの回数を増やせば良い」という本質情報を誰かのツイートで見た後でAC。
「繰り上がりの回数を増やせば良い」ということが分かれば、まあ解ける。Pythonだと多倍長があるので、実際に数字を足して確かめることができるので楽ですね。
コンテスト中は、桁DPかな、と思ったところで飛ばしてしまいました。
「繰り上がりの回数を増やせば良い」は実験したら気付けた気がするので、この問題に集中していたら解けていた気もするけど、本当に実験コードを書こうと思ったかは分からないからなぁ……。
D - Zigzag Tree
解説、解説放送を参照しつつAC。
制約から二乗の木DPは考えたくなる。
二乗の木DPは、「あるノードがルートだったとき、その部分木についての（何らかの）数」を持つDP。そのことが頭にあれば、「自分より小さい数が何個あるか？」を持ってDPすることが思いつける。これで（実際に実装しようとすると頭がこんがらがるけど、ちゃんとやれば）木DPは書ける。
が、これを普通に書くと二乗にならず、累積和による計算量削減が必要になる。これは、式を見て冷静に考えれば分かるのだが、私はかなり悩んでしまった。
木DPパートも計算量削減パートも典型といえば典型で、分かってしまえば難しいものではないし、解かなきゃいけない問題だとは思うけれど、実際にACまでもっていくのは結構困難に感じた。
F - Replace by Average
コンテスト中に、a, $x_1$, $x_2$, ..., b（各$x_i$はaやbより大きい）という列に操作を行った最終結果がどうなるかは分かっていた。
aの方が小さいとし、この列がn+1項とすると、(b-a)/nずつ等差数列のように大きくなっていく。余りはどうなるか？ というと、1ずつbに近い方へと分配される。
たとえば、
・3, 1000, 1000, 1000, 1000, 20
に操作を行うと、
・3, 6, 9, 12, 16, 20
のように、途中までは差が3、それ以降は差が4になって20へたどりつく。
これは実験すれば分かった。
公式解説ではこの証明に分量を割いていて、なかなか難しいが、問題を解くだけならこの結果を導くことができればOKだろう。
こうしてできた結果が凸になることにはコンテスト中に気付いた。が、それを生かすことができず、値の小さい区間に対してこの操作を行う……みたいな方針へ走ってしまった。
そこで凸包を作ろう、と思えたら良かった。
こういうときアルゴリズムの勉強が大事ですね。凸包（convex hull trickやslope trickでも可）の具体的なアルゴリズムやイメージがちゃんと浮かべば、その方針を取れたと思う。
凸包で得られた点たちに対して、その隣同士の点について上記の操作を行うと、かなり答えに近付く。実際、それを20回繰り返すことでACできた。（嘘解法だと思うけど、この回数がlogで抑えられそうな気もするので、もしかすると嘘解法じゃないかも？）
正しい解法は、差が変わる点を適宜加えた（上の例だと、3と20だけでなく12も加える）凸包を作ればOK。
1項目が3、6項目が20ならば商と余りを計算することで、「4項目が12になり、それが今作りたい凸包の候補になる」と分かる。この操作をしながら凸包を作っていけば良い。
0 件のコメント:
コメントを投稿