hotpepsiの練習帳

SRM 552

02:02

Div1 Easy (250) FoxPaintingBalls

問題

• ボールが3角形状に積み上げられている。
• 無色のボールをR、G、Bの3色に塗る。
• 隣り合うボールは異なる色で塗る。
• R、G、Bの塗布可能回数と、塗るボールの段数が与えられる。
• 塗れるセット数を求める。

方針

• なかなか題意がつかめない
• 最初の例が1なのをようやく理解する
• 塗り方じゃなくていくつ作れるかということか(遅い)
• 75分終了
• 3角形状に異なる色に塗るので、最初の2色を決めると全部決まる
• それぞれ同じ数だけ使う場合と、1個目に置いたやつが1個だけ多い場合(=最下段の両端が同じ色)がある
• 後者はNを3で割ると1余る
• 1セットに必要な塗布数T=N*(N+1)/2
• 総塗布可能回数をC=R+G+Bとして、セット数の最大はC÷T個
• 一方、各色は少なくとも(T÷3)=t個ずつ必要
• 答えはmin(min(R,G,B)÷t,C÷T)
• ただしN=1のときはR+G+B
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_552/FoxPaintingBalls.cpp

結果

--- 0pt 237th rating 1233 -> 1251 (+18)

0点なのにレートが上がった。反省しなければ。