hotpepsiの練習帳

SRM 600

greedy | 01:10

Div1 Easy (250) ORSolitaire

問題

• 数値の配列が与えられる
• 初期値を0として、配列の要素をORしてgoalにする
• 要素をいくつ削除したらgoalにできなくなるかを求める

方針

• bit単位で考える
• goalに含まれないbitが立っている要素は無視する
• 取り除く最小値 = 各bitの出現数の最小値が答え
• Failed System Test
• 書き直し
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_600/ORSolitaire.cpp

Div2 Easy (250) TheShuttles

問題

• N箇所の拠点と、それぞれの社員数が与えられる
• それぞれの拠点について、全員を運べる台数を用意する
• 全てのシャトルの座席数は同じである
• シャトル1台のコストはbaseCost＋seatCost×座席数である
• コストの最小値を求める

方針

• 全ての座席数を試す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_600/TheShuttles.cpp

結果

x-- 0pt 889th/1007 rating 1420 -> 1297 (-123)

ビットのループを、小ネタで

for (int b = 1; b > 0; b *= 2)

と書いたらTLEで死んだ。

Visual C++では停止するが、GCCだと条件が常に真と見なされて無限ループになっていた。

条件は色々あるようだ。

https://twitter.com/hirose_golf/status/435034777968603136

for(int i = 715827882; i >= 0; i *= 3)は無限ループするが

for(int i = 715827883; i >= 0; i *= 3)は無限ループしなかったり。

C言語むずかしい。

http://togetter.com/li/602581