一問も解けず青に落ちた。
コンテスト後のツイート
AtCoder Grand Contest 066 一問も解けなかったらどうしようという不安がなかったわけではないけど、本当に一問も解けませんでした!
— titia (@titia_til) March 31, 2024
A (i+j)%2で分ける方針を主に考えたが失敗。あとは色々な貪欲とか投げた。
B 頑張って探索したがN=19までしか作れず。
A - Adjacent Difference
解説AC。
・市松模様に分ける
・片方を0, もう片方をd (mod 2*d)にする
どちらも考えたはずなのに、一次元でも上手くいかない気がして捨ててしまった。上手くいかなかったのは、mod 2*dで良いと明示的に考えられていなかったのと、例で計算するのが下手だったせいか。
ただ、公式解説の、これで良いという証明は自分には思いつきにくいものだった。これを思い付ける数学的証明能力があれば解けていたかもしれないので、そこを反省しよう。
B - Decreasing Digit Sums
解説AC。
5ベキに注目するのは全く考えなかった。N=3となる小さい数として625にはちょっと着目したけどそこから考察を進められなかった。
単純にその数のNの値を考えるのではなく、二倍していったときに桁和がどう変化するかに着目するのが大事だったのですね。
答えを直接求める実験をするのではなく、ちょっと一般化したような内容で実験をするというのはしばしば必要となる手法。直接答えを求める実験しかせず何も情報を得られず失敗したことは結構記憶にある。そのあたりが反省点か。
なお、コンテスト中は、あるSにx*2ベキを文字列として足したものを繋げていってNが大きくなるものを探すような実験をしていた。（これでN=19まで見つけられた）
この実験コードの2ベキの部分を5ベキに変えたら（理由はよく分かっていないが）N=51のものが見つかった。
0 件のコメント:
コメントを投稿