hotpepsiの練習帳

TCO 2013 Round 2B

00:35

Easy (250) FruitTrees

問題

• 一直線な道路に3種類の木を植える
• 種類ごとに植える間隔が指定される
• 異なる種類の間隔が大きくなるように植えていく
• 間隔の最大値を求める

方針

• GCDかな
• GCDの半分ぽいけど、1/3になってる場合もある
• 適当に場合わけして提出
• Failed System Test
• (終了後)
• GCDが全て同じときはGCDの1/3になる。よく考えたら自明
• そうでない場合、最小同士はGCDの半分だけずらす(最小同士の最大値)
• もう一つについては、反対方向に最小のGCDの半分だけずらす
• このとき、GCDが異なる=周期が一致しないので大丈夫っぽい
• https://github.com/firewood/topcoder/blob/master/tco_2013/FruitTrees.cpp

結果

x-- 0pt 498th/1143 rating 1450 -> 1439 (-11)

探索でも解けるようにしておきたい。