SRM528

翌朝も仕事だったけど構わず参加した今年最後のSRM。

• -

250. Cut

問題：決められた切断回数以内で10cmのうなぎをなるべくたくさん作る

• 最大で長さ10mのうなぎ…ごくり。

• とりあえず、長さが10の倍数のうなぎはお得
  • (length/10-1)回の切断で、10cmのうなぎがlength/10個(?)得られる
  • (length/10-1)回切断しないとお得にならない。
  • なので、中でも短いうなぎほどお得度高い

• 長さが10の倍数のうなぎを短いものを最初に切断→他のうなぎを切断 でよさそう。
• さっくり書いてみたところ、既に提出してる人が何人かいてビビった。
• サンプルはソートしなくても全部通るっぽかったので、それだけテストして提出。

500. SPartition

問題：文字列sから2つの部分列を同一になるように取る取り方は何通り？

• サンプルの答えが2べきの数ばかりだったので、ちょっと反応した。
• が、すぐに答えが2べきの数じゃないケースを思いついたので忘れることに。

• よく見たら文字列長が40しかないので、結果の文字列は2^20通りしかない。
• sからoとxの数は決まるので、調べなきゃいけないのは最大でもC(20, 10)通りしかない。
  • 作る文字列を決めれば、O(n^2)のDPでパターン数は求められる。
  • 作れうる文字列全通りについて、パターン数足しあわせれば良いのでは。

• 計算時間がやや不安だったものの、とりあえず組んでみることに。
  • |s|=40のケースで1.7sくらいだった
  • チキンなので、そのケースを1.4sくらいに高速化してから提出した。

1000. ColorfulCookie

問題：いろんな色のクッキーがいっぱいある。ある色のクッキーをC1枚と別の色のクッキーをC2枚を取る操作を繰り返した時、クッキーは最大何枚取れる？

• 珍しくMediumがスムーズに解けて時間余ったので見てみた。
• 2分探索説とフロー説が脳内を駆け巡っていたものの、残念ながら解けず。
• フロー説にかけた時間が長かった時点で詰んでた(´・ω・｀)

Challenge Phase

• ぼんやり見てたら、250でやたらチャレンジが成功してたので、便乗して見てみた。
• そしたら、ソートしてない人がいたので美味しくいただいた

• -

結果：AC / AC / -- ，+50, 630.99pt, 38位
レーティング：2374 -> 2426

Highestを更新し、良い感じに2011年を終えることができました。
翌日は短時間の睡眠で会社+飲み会をこなし若干キツかったですが、後悔も反省もしていない。