SRM358 に挑戦。
250 点問題。いかにケアレスミスをしないか?を問われる問題。で、見事にミスをしてしまいました。しかも、2 つも。 5 分の休憩時間中に、自分の誤りに気がついたんですけど、ときすでに遅し。なぜか、自分は、250 点問題のミスに、休憩時間中に気付くパターンが多いような。他人へのチャレンジ・ケースを考えているうちに、自分のミスに気付かされるといういつものパターン。
500 点問題。苦手な整数問題。最大サイズが 50 なので、探索できっこないと思い込む。なにかクレバーなアイデアがあるはずと思いつつ、しかし、時間内に思いつく自信がなかったため、早めにパスして、1000 点問題へ。
1000 点問題．500 点問題よりは取り組みやすそうに思えたので、今回は、ずっとこれに取り組んでいました。まったく同じ鮫をのぞいてしまえば、グラフは DAG(directed acyclic graph)になるので、まったく同じ鮫をどのように扱うか考えていました。結局提出まで至らず時間切れ。後で、コードを振り返ってみると、全体としての方針は間違っていなかったんですけど(DAG にしてマッチング問題に帰着)、前半部分で、「同じ鮫をひとつにまとめてしまっても大丈夫なはずだ」という、致命的な勘違いをしていました。なぜ、そう思ったのだろう。。。
ほとんどのひとは、MaxFlow で解いていますね。なるほど。
System Test の結果です． ( Room Statistics )
チャレンジも 2 つ失敗して、結局スコア-50 で終わるという過去最低の結果に。レーティングも 2040->1856 とものの見事な低下っぷり。この悔しさが、次回へのモチベーションにつながるんですけどね。