Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2276-f33b41e7
この記事にトラックバックする(FC2ブログユーザー)

SRM552 DIV1 EASY/DIV2 MEDIUM - FoxPaintingBalls (この記事を編集する[管理者用])

Source

TopCoder SRM552 DIV1 EASY (250pt)
TopCoder SRM552 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

問題文の図のようにボールを並べてN段の三角形を作りたい.
触れているボール通しは違う色でなければならない.
色は3色で,赤のボールの数がR個,緑がG個,青がB個使える.
最大で何個の三角形を作れるかを求める問題.
Nは10^9以下,R, G, Bは10^18以下.

解法

最初の2段は全部違う色でなくてはいけないし,後はボールの色は一意に定まってしまう.
結局は,全部だいたい同じ数だけボールが必要となる.
もうちょっと正確に言うなら,
 N mod 3 = 1の時,必要なボールの数はN(N+1)/3 = 3M+1となって,ある一色はM+1個,他の2色はM個必要
 その他の時,N(N+1)/3 = 3Mとなっと,全てのボールがM個必要
となる.

・解法1 (本番に書いたもの)
R >= G >= Bとする.(ソートする)
1個の三角形を作るのに必要なボールの数をそれぞれ a, b, c (a ≥ b ≥ c) とする.
答えは,
 min( floor(B/c), floor( (G+B)/(b+c) ), floor( (R+G+B)/(a+b+c) ) )
となる.(ボトルネックになる場所を全部調べる)
この問題では,実は,
 min( floor(B/c), floor( (R+G+B)/(a+b+c) ) )
で良い.(b=cであるから)

・解法2
N mod 3が1でないとき,答えは min(R,G,B) / Mとなる.(M = N(N+1)/6は三角形1個作るのに,それぞれの色の必要なボールの数)
N mod 3 = 1のとき,二分探索する.
K個作れるかためには,R-KM, G-KM, B-KMが負にならず,和 (R+G+B-3KM) がK以上でなければいけない.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define ll long long

class FoxPaintingBalls {
public:
ll theMax(ll R, ll G, ll B, int N__) {
  ll i, k, arr[3];
  ll sum = R + G + B, one;
  ll N = N__;
  ll res, tmp;

  one = N * (N+1) / 2;
  res = sum / one;

  arr[0] = R; arr[1] = G; arr[2] = B;
  sort(arr, arr+3);

  one = (N * (N+1) / 2) / 3;
  if(one){
    tmp = arr[0] / one;
    if(res > tmp) res = tmp;
  }

  printf("%lld\n",res);

  one = ((N * (N+1) / 2) / 3) + ((N * (N+1) / 2 + 1) / 3);
  if(one){
    tmp = (arr[0] + arr[1]) / one;
    if(res > tmp) res = tmp;
  }

  printf("%lld\n",res);

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2276-f33b41e7
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。