TopCoder SRM 430 DIV1
練習のため過去の解けなかった500点問題を解いていたが、だいたい解き方が分かっている状態で書いてもなかなか通るものができなくてへこんでいる中のSRM。
システムのトラブルで開始時間が数分遅れた。運営の皆さんお疲れ様です。
Coding Phase
- 250点問題
- 整数xとkが与えられるので、
x+y=x|y
となるyのうち小さい方からk番目のものを求める問題。ようは足したときにbitの繰り上がりが起きなければよい。xの二進表現でビットが0のところを下から順にkのビットで埋めていく。
提出した直後に、計算途中でintがオーバーフローしていることに気づいて再提出… - 500点問題
- 都市どうしに友好都市の関係を作る。友好都市どうしは一定の距離以上離れてないといけないし、一つの都市が持てる友好都市の数は限られている。友好都市の組が最大になるパターンを求める問題。
上手い方法が思いつかなかったので、都市数が最大10だから単純な探索でいけるかも…と書いてみた。サンプルは通るのだけど、大きい入力で実行時間オーバーでした。やっぱりか。 - 1000点問題
- intermissionのときに問題文を読んだだけ。
Challenge Phase
250でオーバーフローしている人を見つけたので即Challenge。
他にも何人かいたようだが、読めなかったり先を越されたりで取れたのは一つだけ。
System-Testing Phase
250は確保。