No.2871 Universal Serial Bus
解説AC。
コンテスト後、解こうとしたらWAを量産してしまった。
二つ罠があった。
・全ての場合に確率が0のとき、期待値は無限になる。
期待値の定義を考えれば当たり前で、これに気付かないのはまずい。
・「ケーブルを 180度回転させて上下ひっくり返した状態」は左右も反転する！！
これ。
testcaseを読んだり解説を読んでもしばらく気付かなかった。コンテスト中ACするのは難しかったのでは。
No.2872 Depth of the Parentheses
自力AC。
二次元DPで計算量はKの三乗にはなった。
evilケースどうやるの？
No.2873 Kendall's Tau
自力AC。
「ケンドールの順位相関係数」は初耳でした。
どういうときに使うのかな～と思ったら、順位の相関を計ると知り納得。（名前が「順位相関係数」だから当たり前なのだけど、定義だけ読んだら分からなかった）
0 件のコメント:
コメントを投稿