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参戦中にここまで持って来れるものか...
- レッドコーダーならやるのだろうなぁ