TopCoder SRM 496

250

平面上に赤と青のインクを直線状に垂らした。赤は横方向、青は縦方向にしか垂らせない。赤と青が重なると緑になる。垂らした後の様子が与えられて、最低何回垂らしたらそうなるか求めよ。

やるだけ

500

ボールがいくつかあり、どれも同じ速度で運動している（向きは違うかもしれない）。ある瞬間写真をとり、いくらか時間が経過したあといくつか余計なボールを加えてまた写真をとった。ボールは衝突しない。最初の写真と後の写真で、ボールの対応は何通り考えられるか。ボールは１箇所に１個だけ。

まず、速度がどれも同じなので、移動前と移動後での距離の差は一定である。この差について全探査を行う（同じ差について２回探索しないように注意）。差の候補は、両方の写真から適当な2つをとってきて差をとれば求まる。
差を固定したとき、対応関係をほどいてやると「直線状なのがいくつか」となるので、それぞれについて場合の数を求め、掛けあわせてやれば場合の数が求まる。

950

文字列がいくつかあって、それらをつなげてハミルトン経路を作る。経路のパスのコストは、それが文字列XとYを結んでいるとき、(Xの長さ)^2+(Yの長さ)^2-(XとYの共通接頭辞の長さA)^2である。端は文字列0,1と決まっている。コストを最小化せよ。

貪欲法でやったら落とされた

結果

950は落とされたけど、250と500は通った

oox 613.5 30位

Rating: 2401 -> 2477