TCO10 Online Round 1

TopCoder

GoogleCodeJamが落ち着いたところで、今度はTopCoder Open。
ちょっと眠かったので寝オチだけが心配でしたが…。

  • -

250. EqualizeStrings

問題：文字列s, tそれぞれに，「1文字を選びアルファベット順で1つ進める or 戻す」という操作を加え、sとtを同じ文字列にする。最小のステップ数でできる辞書順最小の文字列は？

  • 1文字ずつ決めていくだけ。233.76pt

500. TwoRegisters

問題：2つのレジスタXとYそれぞれに整数値1が格納されている。2種類の命令X(X:=X+Y)、Y(Y:=X+Y)を使って、Xに値rが入るようにするための最短の命令列は？

  • レジスタXに値rが入る1つ前の状態を考えると、X(r-i) Y(i)で高々r通り。
  • 命令の性質から前の命令では値が大きい側に値が小さい側を足したと分かる。
  • よって、各状態から初期状態まで逆にたどる事で命令列を決定できる。
    • 得られた命令列の中で最短かつ辞書順最小のものを返せば良い。
    • r-iとiが互いに素でない場合は初期状態X(1) Y(1)から生成できない
  • 適当に実装したら最大ケース(r=10^6)でTLEしたので適当に高速化。
  • 間に合いそうだったので提出した。307.30pt

1000. VacationTours

問題：いくつかの観光地を巡るツアーを企画する。異なるツアーに同じ目的地が含まれては行けなくて、旅行会社は「(企画したツアー数)*fee - 各ツアーの経路コストの合計」の利益を得られる。得られる利益の最大値は？

  • 観光地の数が最大49。別にホテルがあって、各ツアーはホテルを起点とする。
  • どう見ても最小費用流ですが、気づいた頃にはタイムアップ。あーあ。
  • practiceでは面倒なのでフローの流量ごとに利益を計算し、そのmaxを取った。
  • -

結果：AC / AC / -- ，541.06pt, 205位
レーティング：1719 -> 1821

1000解きたかったなーと思いつつ、自信なかった500が通ったので安心もしました。
とりあえず次には行けそうなので、また頑張ろうと思います。