SRM 508 div1

盛岡から参戦。

250

• 変な問題。
  • どうせ幅優先探索したら間に合うんじゃね？
  • 一応厳密に計算。めんどくさい、ダイクストラにするか？
  • ダイクストラめんどくさい。やっぱりBFSで間に合いそうなので実装。サブミット。とても遅い…。

500

• 足し算とORを一致させる問題。
  • 各数値のANDが0の場合は明らかに大丈夫。他の場合は？
  • 繰り上がりが起こるから他の場合はだめっぽい。
  • 要するに各数値のANDが0になる組み合わせを求める問題か。てきとうにやって見るが結構むずい。
  • 上の桁から1にするか0にするか決定していくことにする。あと適当にR自体をいじりながらメモ化探索とか？
  • 計算量は大丈夫っぽいので実装。通らない。
  • 一番上のビットを使わない場合の処理が間違っていたので修正してサブミット。思ったより時間食われたなあ。

Challenge Phase

• 250で怪しい人を探す。
  • 怪しい人がいたけど先に落とされた。TLEしそうな人がいたけどコード見てるうちに終了。

結果

oxx 148.16pts 342位 2309→2227。
なぜか500で落ちたと思ったら、計算量(空間使用量)の見積もりが甘くて、最後二つのテストケースでO(60*10*2^10)くらいのメモリを確保してMLEで死んでた。あと、500はともかく250で時間食い過ぎた。