hotpepsiの練習帳

SRM 536 Div2

22:26

練習

Easy (250) BinaryPolynomialDivTwo

問題

• P(x) = a[0] * x^0 + a[1] * x^1 + ... + a[n] * x^nという多項式がある
• a[i]は0か1のいずれかである
• xとして0か1のいずれかを与える
• a[n]は必ず1が与えられる
• x^0は1である
• P(x) mod 2が0の場合がいくつかを求める

方針

• x=0の場合、和はa[0]
• x=1の場合は、全部の和 mod 2
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/BinaryPolynomialDivTwo.cpp

Medium (500) RollingDiceDivTwo

問題

• 面の数が不明なサイコロがx個ある
• それぞれの面の数は1から9のいずれかであり、出目の確率は等しい
• n回サイコロを振った出目が与えられる
• 面の数の合計の最小値を求める

方針

• 各試行をソート
• 各試行のi番目の試行のうちの最大値を保持
• 最大値を合計
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/RollingDiceDivTwo.cpp

Hard (1000) MergersDivTwo

問題

• n個の会社があり、それぞれの利益が配列で与えられる。
• 会社を合併すると、新会社の利益は、各社の利益の総和÷社数となる。
• 合併には少なくともk社必要で、最終的には1社になる。
• 最終的にできる会社の利益の最大値を求める。

方針

• ソートするとか基本部分はdiv1easyと同じ
• k社ずつ合併できる場合は最大回数を選べばよい
• そうでない場合つまり(n-1)%(k-1)がゼロでない場合は、この余りを何回目に配分するかの判断が必要
• まず全試行だけど最適解でないとわかったら打ち切るメモ化っぽいのを書いた
• 次に、i番目からj個併合した最大値を保持するようにしたDPで書いた。このほうがシンプル
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/MergersDivTwo.cpp

感想

easyとhardのクラス名が交換されているというのがしゃれがきいている。

easyは長文なので読解&早解きの会。

mediumの正答率は97%だったようでchallenge phaseは暇だったと思われる。

hardはdiv1 easyの制約条件が違うだけなのだがだいぶ難しい。DP書く練習になった。