2022年5月18日水曜日

yukicoder contest 343

 Aを解いて睡魔に襲われてしまったけど、Bは(厳密な証明はできなくても)見てすぐ分からなくちゃいけない問題でした。


No.1935 Water Simulation

 周期性がある。

 それを厳密に求めなくてもいずれ周期4になりそうな見た目をしているので、適当な回数シミュレーションすればACできる。
 いつ頃周期4になるか、抑える方法はないのだろうか?

No.1936 Rational Approximation

 ACはしたが、証明はちゃんと追えていない。
 なかなか驚きの結果でした。

 ACするだけなら、実験して性質を見つけるのが一番だと思う。
 ファレイ数列を知っているとACしやすかったらしい。

No.1937 Various Tournament

 解説AC。

 あまり考えずに解説を見たら分割統治と書いてあったのでその方針でAC。
 でもまあやることはDPくらいしかないから、自力でやったとしても方針に困ることはなさそう。

 ただ、実装に苦労し、書いている途中、分割統治でない方が書きやすいのでは? という気持ちになった。実際、bitDPなど解いている人もいるようなので、そういうした方が良かったか。
 なんとかACしたけど、上手く書けなかった。

0 件のコメント:

コメントを投稿