AGC066

Bのみ1完。AGCだった。Aを読んで少し考えて難しいのでBも読んで、「AGCだ~」とにやけた(困りながら)。

A - Adjacent Difference

コストの制約は、マスあたりd/2以下ということ。ということは何か簡単な方法がありそうだが。AB両方読んでどちらもわからず、面白そうなBに集中した。

Bを通して戻ってきた。思ったより難しい。

3 10
0 5 10
0 5 10
0 5 10

このケースが手で解くのも難しい。頑張ったら解けたけど、これができるプログラムを書ける気はしない。左上隅のマスを4にしたらダメそうだけど5から10は大丈夫で、そこから何かを感じとるべきだったのかもしれないが。

どうやっても解けない。最初から解ける見た目だったけど、思ってたのと違う難しさだと気づいたときには残り15分。残り10分になったら体が完全にあきらめていて、その状態でやってもしょうがないのでCやEを読むなどしていた。

(追記)色々な解法ツイートなどを見ていたが、なかなか具体的なものが見えずやる気が出なかった。公式のヒントを頭に入れて布団に入ったらあっさり解けた気がした(ここで初めて腰を入れて考えた)。mod d*2で考えて0とdを市松模様に配置すればいいが、0とdにするコストの和はdなので全部入れ替えれば片方は平均d/2以下になる(すごい)。今実装して実際に書けて、ACした。終わってみれば、最初に感じたイメージのままの解法だった。市松模様は早い段階で見えていたし、そこそこの自由度があるというのも観察からわかっていた。何より、コストがマスあたりd/2になるというのが。わざとらしくそういう設定の問題にしてあるのにそれが見えなかった。本当にAGCの解法って当たり前のことばかりなんだけど、俺はそんなことすら知らないのだ(だからAGCは面白いんだけど)。

B - Decreasing Digit Sums

2倍すると桁和が減っていくものを見つける。とりあえず実験コードを書く。ただし、xを全探索するようなことはしない。入力のNによらずN=50の答えを出力するだけの問題だから、小さいNの答えから類推する感じではないと思った。10^12を2で割っていき桁和を観察する。だんだん増えていくが、減ることもある。2倍して減るやつではなく2で割ってして増えるやつを探すのは、方針としてはよさそう。ここで、1000030000のようにくっつければ10000の桁和と30000の桁和の和が得られると気づく。また、10の冪を2で割っていくと0でない桁が増えていくから、桁和が単調増加でないにせよ増えていく傾向は確実にありそうだと気づく。これで可能性が見えた(同じ傾向のものをたくさん足せば単調増加になりそう)。ただ、「こんな泥臭い実験しないと解けないようなものをAGCで出すか?」というのが気になった。が、他に何も見えないのでこれをやる。10000桁以内という制約があるのでその範囲で(最初10000/50が20くらいだと勘違いしていた)。10^50に何かの整数を掛けたものをいくつか使う。2倍だとすぐ合流してしまうと思ったけど、ずれてるのはそれはそれでいいとあとになって気づいた。20まで試して10以上は2桁に分ける処理が必要だとあとで気づいたり。60桁(10^50に99を掛けると52桁)を100個なら6000桁でOKなので、その範囲でできてくれと思いながら1から99までの99個で試すと最初だけダメ。そこで、1を2回入れることにすると、嬉しいことに狭義単調増加となった。あとはこれを構築して50回2で割ればいい。この部分および検算にGMPを使ったが、あとから考えたら2で割る処理は既に書いてあったので不要ではあった。出力させて、0が思ったより多く連続していて理由がしばらくわからなかったが、何回も2で割って小さくなったので頭に大量の0が付くのだった。GMPの整数をintにキャストする方法がわからず、10で割ったあまりが知りたいので0から9までのintをmpz_classにキャストして等しいか調べる力技を使った(こういうのひねり出すのわりと好き)。結果的にGMPを使ったのは時間の無駄だったが、まあ構築ミスやそもそもの考察ミスなどの可能性は高かったと思うので、悪い立ち回りではなかったはず。

(追記)GMPでint(正確にはlong)に変換するのはget_si()だったね。get_uiはどっかで見かけた記憶があるけど、uiがそういう意味とは思わなかった。