SRM 552 Div II

Single Round Match 552 Round 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15174

250に10分。500に1時間ほどかけ、完成しなかった。合計227.00点。レートは何故か、1095から1123へ。緑コーダー。Room 68

Problem Status Points
250 FoxAndFlowerShopDivTwo System Test Passed 227.00
550 FoxPaintingBalls Opened 0.00
1000 FoxPlusMinus Unopened
  • 250に10分。227.00点
  • 500に1時間ほどかけ、完成しなかった
    • また500が解けなかった...
  • 次回の目標
    • 2問通す

FoxAndFlowerShopDivTwo

http://community.topcoder.com/stat?c=problem_statement&pm=12148&rd=15174

10分。227.00点

  • 以下の4つの面積を求め、一番大きいものを返す

実装は以下(システムテスト済)。

class FoxAndFlowerShopDivTwo {
public:
  int theMaxFlowers(std::vector<std::string> flowers, int r, int c) {
    int h = flowers.size(), w = flowers[0].size();

    int a =          count(flowers, 0,     w - 1,     0, r - 1);
        a = std::max(count(flowers, c + 1, w - 1,     0, h - 1), a);
        a = std::max(count(flowers, 0,     w - 1, r + 1, h - 1), a);
        a = std::max(count(flowers, 0,     c - 1,     0, h - 1), a);

    return a;
  };

private:
  int count(const std::vector<std::string>& flowers, int l, int r, int t, int b) const {
    int c = 0;
    
    for (int j = t; j <= b; j ++)
      for (int i = l; i <= r; i ++)
	if (flowers[j][i] == 'F')
	  c ++;

    return c;
  };
};
  • 少し焦っていたようだ
    • そのためか、count関数の実装が変だ
    • 普段心がけていることを守っていない
  • 二重ループを使って行列を操作するときは、iが行、jが列を表すよう心がけている
    for (int i = t; i <= b; i ++)
      for (int j = l; j <= r; j ++)
	if (flowers[i][j] == 'F')
	  c ++;
  • 以前はiを外側の反復、jを内側の反復に使うようにしていた
  for (int i = 0; i < h; i ++)          // 行に対する反復
    for (int j = 0; j < w; j ++)        // 列に対する反復
      // ここではa{i,j}に対して処理をする

  for (int i = 0; i < w; i ++)          // 列に対する反復
    for (int j = 0; j < h; j ++)        // 行に対する反復
      // ここではa{j,i}に対して処理をする...
  • iが行、jが列を常に示すように実装するようにしてからミスが激減した
  for (int i = 0; i < h; i ++)          // 行に対する反復
    for (int j = 0; j < w; j ++)        // 列に対する反復
      // ここではa{i,j}に対して処理をする

  for (int j = 0; j < w; j ++)          // 列に対する反復(列なのでjを使う)
    for (int i = 0; i < h; i ++)        // 行に対する反復(行なのでiを使う)
      // ここでもa{i,j}に対して処理をする!
  • 考えている途中で実装を始めかけたが、我慢した
    • 意外とよかった
    • しかし、時間が多少かかった(ように感じた)。また予想以上の気力を必要とした
    • 焦っていた要因でもありそうだ
      • 最後まで考えてから実装を始める練習の必要性を感じた

FoxPaintingBalls

http://community.topcoder.com/stat?c=problem_statement&pm=12146&rd=15174

1時間かけ、時間切れ。

  • まず、紙に以下を書き出した


  • Nの大きさからRGBの数を算出するシミュレータを書いた
    • 今考えると、Nが大きいとき(Nは最大109を取る)はこの計算でほとんどの時間を使ってしまう
  long long r = 0, g = 0, b = 0;

  for (int i = 1; i <= N; i ++)
    switch (i % 3) {
    case 1:
      r += i / 3 + 1;
      g += i / 3;
      b += i / 3;
      break;
    case 2:
      r += i / 3;
      g += i / 3 + 1;
      b += i / 3 + 1;
      break;
    case 0:
      r += i / 3;
      g += i / 3;
      b += i / 3;
      break;
    default:
      break;
    }
  • 図をよく眺めると、各ボールの数はずっと簡単に求まることが分かる
    • 初めに使ったボールの総数は変則的に変化する
    • これはボールの合計から求めることができる
  • Nから等比数列を作って合計を出す
    • 合計は3で割り切れるか、3で割って1余るか
  • 合計は以下のように算出することができる


  • ここから、各ボールの数を算出する
    • ボールの合計をnとすると


  • これを実装する
    • 上述のシミュレータがいらなくなってしまった
  long long n = (long long)N * (N + 1) / 2;

  long long r, g, b;

  r = g = b = n / 3;

  if (n % 3 == 1)
    r ++;
  • ここまでで一つの三角形が使う各ボールの数が分かった
    • ここからは与えられた各ボールの数と求めた各ボールの数から三角形がどのくらい作れるかを考える
  • SRM中はこちらもシミュレータとして実装し始めてしまった
  • rはgやbよりも大きいときがある
    • そのため、そのときに一番残っているボールからrを引く戦略を取った
  std::vector<long long> RGB;
  
  RGB.push_back(R);
  RGB.push_back(G);
  RGB.push_back(B);

  for (long long c = 0; true; c ++) {
    std::sort(RALL(RGB));

    if (RGB[0] < r || RGB[1] < g || RGB[2] < b)
      return c;

    RGB[0] -= r;
    RGB[1] -= g;
    RGB[2] -= b;
  }
  • 結構好きな実装
    • ちょっと違うけど、メトロポリス法を用いたサンプリング手法のようだ
  • 好きな実装ではあったが、テストケースの5番のような大きな値に対して解けない
    • そのため、予めざっくり計算する実装を幾つか行うが答えが合わず、時間が切れた
  • SRM後に考察を続けた
    • r、gおよびbが等しいとき、つまり1からNまでの合計が3で割り切れるときは以下の式で求まることに気付く


  • また、r、gおよびbは等しくn / 3であるため、以下とすることができる
    • ここではn / 3が整数であることに注意


  • r、gおよびbが等しくない場合が難しかった
    • 1日ほど考えた
  • 図に書いてみる
    • 考えたいのは、以下のようにRGBの数が異なるアンバランスな場合だ


  • 実際にはありえないが、挙動を見るためにnを4とする
  • 1個目の三角形を作ろう
    • G、BよりRが多い
    • Rをより多く選択しよう
  • Rをより多く取り、1個目の三角形を作った後の残りは


  • 2個目の三角形を作ろう
    • 今だG、BよりRが多い
    • 今回もRをより多く選択しよう
  • Rをより多く取り、2個目の三角形を作った後の残りは


  • この状態で選択すべきボールは何だろう?
    • RかGだ
    • とりあえずRをより多く選択しよう
  • Rを取り、3個目の三角形を作った後の残りは


  • ではこの状態で選択すべきボールは何だろう?
    • 迷わずGを取ろう
  • Gを取り、4個目の三角形を作った後の残りは


  • 次は?
    • やはりRかGだ
    • ここでもとりあえずRをより多く選択しよう
  • Rを取り、5個目の三角形を作った後の残りは


  • もう取れるボールが4個ない
    • ここで終了
  • この作図をしていて、作れる三角形の数は一番少ないボールの数によって抑えられてしまうこと気付いた
    • さきほどの式を部分的に再掲する
      • 書き方を変えている


  • この式を条件として書き直してみる
  • 「1つの三角形を作るのに、」
    • 「RGBそれぞれfloor(n / 3)個のボールが必要であり、」
    • 「さらに、RGB何れか1個のボールが必要」
  • 1つ目の条件から、作り得る三角形の数を式にする


  • ここからは他の抑えかたを考察する
    • 先ほどの抑えかたが起こらないように、min(R, G, B)が十分大きい例を考える


  • まず、はみ出しているボールを何とかしてしまいたい。
    • 直感的に問題がシンプルになるよう感じる
  • はみ出しているボールの総数をcとする
    • この図の場合、cは6
    • cの式は考えない
      • 理由はすぐ分かる


  • c個の三角形を作ると、c × n分のボールが消費される


  • つまり、全体で以下のボールが残る
    • R、G、Bそれぞれが均等に残っていることに注意しよう


  • 残ったボールから作れる三角形の数を求める


  • つまり、全体で作れる三角形の数は以下となる


  • 床関数の中を整理しよう


  • cは整数であるので、床関数から吐き出せる


  • つまり


  • cが消えてなくなってしまった...
  • 全てを考慮すると、求める三角形の数は次のように算出できる
    • 数式的にはここから整理したいところだが、C++の整数演算を加味すると整理しなくてもよい

最終的に行った実装は以下(システムテスト済)。

class FoxPaintingBalls {
public:
  long long theMax(long long R, long long G, long long B, int N) {
    if (N == 1) {
      return R + G + B;
    }
    else {
      long long n = (long long)N * (N + 1) / 2;

      return std::min((R + G + B) / n, std::min(R, std::min(G, B)) / (n / 3));
    }
  };
};
  • すごく短い
    • SRM参戦中にここまで持って来れるものか...
    • レッドコーダーならやるのだろうなぁ