SRM487 Div1

250

• 問題を読む。というか図を見ればだいたい何をやりたいか分かるな
  • ちょっと考えると、あるindexを使う方法は2通りしか無いんで2SATに落ちる
  • とりあえずdfsで書いた。サンプルも通った。
  • よく考えるともっと計算量減らせるなあと思いつつ、最大ケースを試したけど大丈夫。しかし、コードをチェックするとメモ化してないけど大丈夫か？
  • メモ化とか一瞬でできるので、メモ化して提出

550

• 期待値を求める問題か。
  • とりあえず、k=1,k=2の場合はいろいろ怪しい。あとlinkageが隣り合ってる場合は明らかに-1
  • それ以外の場合はどうなんの？というか、linkageって情報量増えてんの？
  • 情報量増えてないなら、m/kが答えになるはず。最後のサンプルで試してみたら正しいっぽい。
  • じゃあこの問題ってどんな場合に-1になるかを調べる問題になるのか。
  • k>=3でそんなケースを探してみたけどなかなか作れない。
  • とりあえず提出して、全探索のコードを書くかあ
  • 全探索のコードを書いたら予想通り-1になるケースが見つかった。残り6分で修正は無理です。

Challenge Phase

• 550を提出してる人で同じ間違いをしてる人がいるはず！
  • 開始1分くらいで3人撃墜。

結果

oxx 350.93pts 74位
他の人のコードを見て思ったけど、今回の550は解けるべきですね。