TopCoderOpen Round 1

今日も残念の日。

250: EqualizeStrings

書くだけ。スピードレースだなぁ。
焦って書いたらコストの計算が無茶苦茶だった。
- もうちょっと冷静になれないものかなぁ。
submit.
いつもより簡単な250だ。まだRound 1だし、今日も簡単なセットなんだろうな。

500: TwoRegisters

と言った側から全然わからん。
O(n²)のDPはもちろんダメ。
1 から r ではなく、r から 1 に持っていく方針はどうだろうか？
- レジスタYの値が分からないので簡単にはならないし、むしろ辞書順最小が余計にやり辛くなるなぁ。
"XYXYXYXYXYXY..." ってやればフィボナッチ数で増えてくので、最大ケースでも数十文字で出来ることは分かるけど...。
...
...!
全！探！索！
- と思ったけど、1,000,000を越える最初のフィボナッチ数は30項目ぐらいなので間に合わない。
- ぐぬぬ...
とはいえ、これって枝狩りに使えませんかね？
- とりあえず書いてみよう。
...
...バグった。
...
...!
- だから手元で実行するなら毎回初期化が必要だってあれほど前回学んだのに！ばか！ばか！
まずはノー枝狩りで実行。
- やっぱりちょっと大きな値を入れると帰ってこない。
既に見つかった最適解とと同じ長さになるまで、効率がよさそうな "XYXYXY..." を続けたとしても、rに届かないなら打ち切り。
- 200,000ぐらいまでは出るようになった。けどまだ足りない...。
...
うーん。悩む。
反復深化にしてみたらどうだろう？
- 反復深化は得意ではない・・・というか、速くなった記憶があんまりないのだけど。
- 変更箇所少ないし、やっちゃえ。
1,000,000出てきた。0.3秒未満。すげぇ。
- (フィボナッチ数 + 1)なんかは最悪ケースになりそうだ。試してみよう。
  - 0.9秒未満。
もしかしてこれっていけるのでは。
覚悟を決めてsubmit!
まさかこれが想定解法ってことはないだろうけどなぁ...。

1000: VacationTours

さすがに残り時間で解けるとは思わないので、問題の把握だけ。
- いやACRushが950点ぐらいで出してるので、頑張れば解けるのか？
  - 同室の rem (赤い人) が出してなかったので、やっぱり諦めました。
でもなんとなく Dilworth's Theorem っぽい？
- ってことは最大流？
  - でも重み付き？
    - ってことは最小費用流？
まぁ1人しか出してないし、とりあえず忘れよう。

Challenge Phase

500で探索してる人がいたので、最悪っぽいケースを投げ込む。失敗。
- って、あれ？よく見ると逆方向に探索？どういうこと？
いつの間にか自分の500も落ちてる...。
- でも一度防衛したみたいで、ちょっとニヤリとした。
一つ撃墜できれば通過出来そうだったけど、撃墜できずに終了。

System Test

oxx -25.0 196.34
challenge失敗がなければ通過していた、とかだったら死にたくなってたのだけど、どうやら250が遅かったおかげでどちらにせよ通過できなかったみたい。
- よかった。
  - よくないよ。