AとCの二問しか解けず。
コンテスト後のツイート
C 最大値が実現可能。大きい方からN/2個を+1他を-1として累積和を考える
— titia (@titia_til) April 9, 2022
D https://t.co/l2OtXL0oan を見に行き、そのコードを使って解こうとしたが3WAが取れず終了。
B - 01 Generation
解法ツイートを見てAC。
コンテスト中は、実験メインで考えていたものの、「後ろから見る」という方針も一応考慮したのだが……。
後ろから見ていくと、二つ操作ある操作のうち、二つ目、「末尾の0を除く」という操作を優先して行い、その後、「先頭の0を取り除いてflip」する、という操作が最適だと分かる。
いや、言われてすぐピンとは来なかったのだが、「先頭の0を取り除いてflip」だけを行うとすると、これはAの先頭の0, 1, 0, 1,...がどれだけ続いているかだけで決まってしまうので、この操作を行う合間に、末尾はできるだけ取り除いた方が良い、となる。
「操作に優先順位があるのでは？」と思い至れば、そんなに難しくなかった気もするが、コンテスト中は全く考えなかった……。
実験したら、長さNのとき作れるPの種類数がフィボナッチ数になると分かって、そこから考察しようとしてしまった。いや、多分本当は、それを手がかりに解くこともできるんだろうけど、漸化式とか導けなかったんだよね。
いまだになぜフィボナッチ数になるのか分かっていません。
D - Differ by K bits
「基底」というキーワードを元にAC。
この問題の方法（もしくは、グレイコード）で、K=1のときのときは作れる。それを改造すればKが他の値のときも解けそうなのだが、xorする値を、1(K=1)→7（K=3）のように隣りのbitを立てていくように変更するのでは上手くいかない。
時間もなかったし、そこで困ってしまったのだが、何故上手くいかないのか？ と考えるのが大切だった。
先の問題で上手くいくのは、(1<<i)たちが基底をなすからである。先の方法では、NとKのgcdが1でないとき、基底とならない。
では、K個bitが立っているものたちで基底を取れれば、xorを取る値をそれらに変更することで構成できる。
0 件のコメント:
コメントを投稿