Dまで四完。Eが解けなかったのは、Dで苦戦して頭が働かなかったため、という気もする。
コンテスト後のツイート
D Aを2ベキで分類。奇数が含まれればOK。偶数のみでグループを作る場合、同じ2ベキの人が偶数個いたらそれより大きい2ベキたちとグループを組んでOK（一応証明したつもり）。
— titia (@titia_til) November 23, 2021
E. AmShZ and G.O.A.T.
三個がterribleな場合に帰着されそうというのはそうなのだけど、そこから考察を進められなかった。
badじゃない数列を構築していこう、と考えれば良かった。
a, b, c （a<b<c）がbadじゃないとする。さらにd（>c）を付け加えたいなら、a, c, dの三つがterribleになってはいけないので、d-cがc-a以上にならなくてはいけない。なので、構築できる数列のサイズはlogで抑えられるので、計算量も大きくならない。
これで十分条件も満たしている、というのに気付いていなかったのがマズかった。四個以上の数列がbadになるとき、terribleな三個の数列ができそうだけど、できるならどこにできるのだろう？ という考察ができていなかった。これは気付けなきゃいけなかったなぁ……。
0 件のコメント:
コメントを投稿