No.2683 Two Sheets
自力AC。
縦と横を独立に考えられると思ったが、コンテスト中は、そのまま（縦の期待値）*（横の期待値）になる気がし、答えが合わず混乱。
落ち着いて見ると、重なっている部分が長方形になるので、そこを縦*横で計算できると気付いた。
これがすんなり解けないのは、やっぱり確率/期待値が苦手なのかなぁ。
No.2684 折々の色
自力AC。
難しくはないけど、同じカードを二枚重ねる場合などに注意が必要ですね。
No.2685 Cell Proliferation (Easy)
自力AC。
これは簡単でした。シンプルな二乗のDPでOK。
No.2686 商品券の使い道
解説AC。
高速ゼータ変換について何も覚えていなかった。
部分集合に関してのDPを考えれば結構自然な考え方に見えた。
高速ゼータ変換は（他次元）立方体における累積和を考えている、というのも覚えておきたい。それが身に着いていれば、高速ゼータ変換を忘れたとしても、どんなDPを考えれば良いか？ と思考すれば思いつけるはず。
0 件のコメント:
コメントを投稿