cafelier@SRM

TCO09 Round3

SRM | 02:15 |

TCO09 Round3 の成績・ソース (要ログイン) : AC/-/- : はい今死んだ！今僕のTCO全部死んだよ！って250通った…？

500開く

• 『何やらアメリカの大統領選挙みたいなシステムで、各州を訪問すると勝てる確率がかわる。訪問できる州の数が決まってるときに、過半数得票できる確率を最大化せよ』

• まあDPだよなあ…
  • 州を順番に訪れるか訪れないかで、できるだけ確率最大になるように
  • あと何州訪れられるかで分けて全部覚える
  • あと50*50の2500が最大得票だから、たぶんこれもDPの要素に使う

• とか15分考えたけどすがすがしいほどに何も浮かばなかったのであきらめ
  • 撃墜フェーズでひとのソース見ても初期値が1.0とかの理由がぜんぜん頭に入ってこない

250開く

• 『xy平面上の格子点に木が生えてる。i番目の木を切ると長さh[i]の壁が作れる。できるだけ切る本数少なくて軸平行な長方形で残ってる木を囲うような切り方は』

• 40本
  • 2^40 通りの切り方が。無理
  • 1本ずつ順に切ってく法
    • 外側のボーダーにあるやつを切って範囲を狭める(4通り)
    • or内側の高い木を切って全体を囲う(1通り)、そこで囲いきれるやつだけ調べればいいので再帰探索にならない
  • 4^40通り。だめすぎる

• ぜんぜんわからん。残り40分くらいになった…

• 最終的な壁の4辺の座標は40^4で決まる
  • その切り方でできるかどうかは、4辺の外は全部切ってみて、
  • あとは壁で囲えるようになるまで内側のを高い木から順に切ってく
  • 40^5 log 40。えー大丈夫かこれ。

• 書いた。
• よくわからないtypo多数でぜんぜん通らない。
• 通った。
  • 40の最大ケースで1000ms。まあいいか出しちゃえ。
  • 最大と言っても枝刈りの関係で本当の最悪パターンがわからんけどどうだろう…

• あー少なくとも(40*39/2)^2*40 log 40にしとけばよかった。アホか僕は

1000開く

• 『ループしてる双六を、駒何個か使って同じマスを２度踏まないように全マス踏めるかどうか。駒の数最小化。駒は何周かしてもとの位置に戻ったらゴール。スタートは好きに決めていい』

• さいころは1～6なので、駒はせいぜい6個までしか使わない。それ以上使ってもどっかでぶつかる
  • だからといって50^6の探索空間をどうするんだ…

• グラフにしてみる。
  • 最小閉路分解とかそういうのないでしょうか
  • ググった。あるにはありそうだが難しそう。
  • やっぱ1～6なのを使うんだよなー。

• 点を足したり割ったりしてフローっぽく
  • 無理

• ひとふでがきっぽく、点の次数を数えるとか
  • in==out==1のがあったら前後を縮約を繰り返すなど
  • わからん
  • 死亡

撃墜フェーズ

• 250みんな同じような方針でびっくりした。これでいいのかー
• 木が1本だけ残るパターンの扱いが変な人の撃墜を先を越されまくった。

感想

• ぜんぜん頭の回転が足りなすぎる。
• 突破したかた頑張って下さい！