きままにものづくり

日々の気付いたことなんかを書いてます。

SRM580Div1

結果: 0 pt
Easyでつまづいてしまい全然解けなかった。
習得したアルゴリズムに当てはめようとして、失敗した感じ。
アルゴリズムを身につけるのはとても大切だけど、中途半端な理解だと柔軟に思考できなくなってしまう。

EelAndRabbit

セグメントツリー、bitDP、グラフ理論で考えてみたけど全然解答にたどり着かなかった。
セグメントツリーは、空間計算量がO(l+t) (1 \le l,t \le 10^9) なので無理だと判断した。
bitDPは、時間計算量がO(2^n) (1 \le n \le 50)なので無理だと判断した。
その後、グラフ理論で考えてみて、完全グラフを形成していれば同時にうなぎを確保できることに気づいた。この方法で頑張って考えてみたけどダメだった。

この問題の解答はかなりシンプルなので、気付きたかった。

広告を非表示にする