水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 103:D - Robot Arms

問題

beta.atcoder.jp

解法

まず,それぞれの到達させたい点と原点の距離の偶奇が一致することを確かめる.一致しなければ,どんなに頑張っても不可能.

それぞれの到達させたい点と原点の距離の偶奇が一致するとき,ロボットの腕の長さを 2^0, 2^1, 2^2, ... , 2^32 と設定すると,全ての奇数を作ることが出来る.偶数の場合は,最後に長さ 1 の腕を付ければよいので同様に考えられる.2の累乗を組み合わせれば全ての奇数が作れることを初めて知った.

解答

beta.atcoder.jp

f:id:babcs2035:20181019202948p:plain