hotpepsiの練習帳

TCO16 Algorithm Round 2A

19:32

https://competitiveprogramming.info/topcoder/srm/round/16736/div/1

Easy (400) LCMGCD

問題

• 2^a×3^bの数からなる配列がある
• 任意の2つの要素を選び、その要素を削除する
• 2つの要素のGCDかLCMを求め、配列に追加する
• 配列の要素が1つになるまで繰り返したとき、値をtにできるかどうかを求める

方針

• GCDはmin,LCDはmaxを取るのとほぼ等しい
• Failed System Test
• 乱択でもいけるらしい
• 10万回くらい試行すればsystem testは通る
• https://github.com/firewood/topcoder/blob/master/tco_2016/LCMGCD.cpp
• 2軸のmin/maxのため、x・yそれぞれで大・等・小の3通り、計9通りにわける
• xとyどちらも等しい状態に遷移できるか探索すれば良いっぽい

結果

x-- +1 50pt rating 1410 -> 1543 (+133)

変則400点。写経ボーナスをもらった。

http://togetter.com/li/974447