TopCoder Open 2010 Round 2

惨敗すぎて泣きそう……
ぜんっぜんまともに問題が解けるようにならない。

Result

133.30 / System Test Failed / Unopend
0撃墜0ミス
133.30 640位


1576->1517

Easy SnowPlow

問題

n個の都市が双方向に通行可能な道路でつながれている。
各都市と都市の道路の車線の数が与えられる。これらは最初全て雪で覆われていて、除雪車でこの雪を取り除きたい。
全ての雪を取り除くために道路を行き来する最低回数を求めよ。

  • 除雪車は上り下りの両車線を全て除雪する必要がある。
  • 除雪車は除雪し終えた道路を通ることも可能である。
  • 全ての雪を取り除くのが不可能の場合-1を返せ。
試行錯誤

うげーRound 2の問題ってこんなに難しいの??
全然方針が見えない。


頂点の次数の偶奇で場合わけとかだろうか。それともフローとか費用流とか??
DPだろうか。でもサイクルがありうるからツリーDPはできない。

などと変なことを考え出してかなりの時間深みにはまる。
オイラー閉路っぽさを判定すればいいんだけど行き来できる道路ってどうなるんだろう。。。


あ、あれ……?これ、両側k車線じゃなくて、片側がk車線ずつか!
どんな場合でも一筆書きできんじゃねーのか……


そのようだorz


最初の都市からから全エッジが通れるかDFSして、通れたら全部の車線数を足したものを返せばいい。。。


orz.送信。これはおわたぽい。

Medium RepresentableNumbers

問題

整数Aの各桁が全て奇数のとき、Aを"totally odd"と呼ぶことにする。
更に、"totally odd"の数二つの和で表現できる数を"representable"と呼ぶ。


与えられた数xに対し、x以上で最小のrepresentableな数を求めよ。
x≦10^8を満たす。

試行錯誤

繰り上がりがなければ全部偶数になるよな。。。
ってことは奇数が出てくるところで繰り上がりでー??


0と1が出てきてもおかしい。
0と1以外の奇数はそれ以下の桁で帳尻を合わせることができるが、0と1は特別っぽい。


どうなるんだ・・・?
0,1の次は奇数じゃないといけない感じ?
書いてみる。あれ、最後のサンプルがおかしい。10102222がOKだと・・・
2個目の1の次が0???何と何足してるんだこれ。


総当りで求めるプログラムを書く。
あー999+11で1010か。ってことは0,1の上に1000とか2000とかが来る場合もOKなんだろうか。
時間ないー!!もうこの方針で書こう。
終了3分前に書き終える。送信。

Hard

Unopened.

Challenge Phase

現在480位付近。1個くらい撃墜できればまだ可能性はある。


落とせそうなのを必死こいて探す。
500の方針みんなは全然違う。。。総当りで生成してよかったのかこれ。


hosさん作問の解でかなり似たやつあったじゃねーかよ!!
ちっとは学習しろよこのゴミが!!!


あれ、みんな全然チャレンジしないなー。あ、ぼくの嘘解法にチャレンジしてる人がいる。嘘解法生き残ったwwww


落とせぬまま終了。うーん、システムテストで奇蹟がおきることを祈ろう。

System Test

Failed. ですよねー。
ぼくのTCOはこうして終了してしまった。