SRM446 Div1

For RITZを微音量で聴きながら参戦しました。
そろそろ500が解けるようになりたい・・・。

250

• 隣の面に移るときの処理をどうするか、ちょっと悩みました。
  • 辛うじて全パターン打ち込もうとする直前に気付きました。
• 真ん中にいるときにRedを返してた以外にはバグも無く、すっきり。

500

• 一番得点の高い辺をひたすら往復するのが最適では？
  • その辺に行って帰る時の時間や得点も考慮するとそうとは限らない
  • そもそも有向グラフなので往復できない。代わりに適当な閉路を探さないと。
  • ぐぬぬ。

• とりあえず stepsPerSecond ステップちょうどでできる最適な移動を求めよう。
  • これはDPで簡単。
• ここからどうしよう。timeLimit以下なら何秒でもOKなので、行列の timeLimt 乗ではマズい。
  • ぐぬぬ。

• ・・・！
• 最適解は単純な閉路をできるだけぐるぐるしたものであるはず & 閉路の長さはノード数 = 50以下なのだから、最適解は timeLimit - 50 秒以上使っているはずでは？
  • 50秒以下の場合もあり得る。これは後で気付きました。
• timeLimit - 50秒後の状態を行列べき乗で求めて、あとは1回ずつ行列掛けながらtimeLimit秒後まで調べればいい！はず！
  • 自信とかあんまり無いけど、実装開始！

• 間に合いませんでした。
  • さすがに10分では無理です。
  • ぐぬぬ。

Challenge Phase

• まずは250がみんなと同じであることを確認して安心する。
• timeLimitちょうどでなくてもいいことを読み落としてる人が結構いる気がする。
  • 落とそうと思いましたが、そもそも入力が作りにくくて間に合いませんでした。
  • System Test通ってる人も半分ぐらいいましたが、一か八かランダム爆撃してみても良かったのかもしれません。
  • ぐぬぬ。

System Test

• 250はつつがなく通りました。
• 1284 -> 1376
  • はいすこあ こうしん！