Google Code Jam 2013 Round 1A

遅ればせながら。

結果

ooo-o- 46pts の rank 546 ということで無事 Round1 通過です。どうも TCO より GCJ の方が相性が良い気がします。とりあえず PATH の設定がおかしくて exe 実行時に DLL がないって怒られたり、ブラウザのデフォルトダウンロードパスが gcj2012 になってたりスタートの所で結構いらいらしてましたが通って良かったです。Problem B を short 限定解で割り切ったのが正解だった気がします。テンプレートは前回参照です。なお、Problem Analysis 未読状態です。

Problem A. Bullseye

基本二分探索でやるだけ、ですが単純にやると 64 ビットでオーバーフローするようになってるのが味噌でしょうね。式的には n 個目の円を描くのに必要なインクの量は (r+2n-1)² - (r+2n-2)² = 2r+4n-3 なので c 個目の円まで描くのに必要なインクの量は Σ(2r+4n-3) = 2cr+2c(c+1)-3c = c(2r+2c-1) となります。t ≧ c(2r+2c-1) を満たす最大の c を求めるということで二分探索すればいいわけですが 64 ビットだとオーバーフローしてしまうので、t/c ≧ 2r+2c-1 で計算しています。2r+2c-1 が整数になるので t/c が整数除算(切り捨て)でも > だった場合が = になるだけなので問題有りません。

多倍長をサポートしている言語を使う、GCJ は外部ライブラリの使用も可能なので多倍長ライブラリを使うといった対処もあったのですが面倒だったのでオーソドックスに先に割り算しておく、で対処しました。が、gcc は 4.6 から __int128 をサポートしているようなのでそれを使うのが一番簡単だったかもしれません。

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  ULL r, t;
  cin >> r >> t;

  ULL l_ = 1ULL, r_ = 2000000000ULL;
  REP(i, 50) {
   ULL tt = (l_+r_)/2;
   if(t/tt >= 2*r+2*tt-1) {
    l_ = tt;
   } else {
    r_ = tt;
   }
  }

  cout << "Case #" << casenum+1 << ": " << l_ << endl;
 }

 return 0;
}

Problem B. Manage your Energy

しばらく考えていましたが Large 解は見えなさそうだったので Short 限定解として DP で解きました。大抵 DP の時は memoize 的に書く場合が多いのですが、超正統派な DP なのでループで書いてます。今回 Large 解を出せていませんが、一旦 Short 解を作って通しておいて実績を作り、Large 解を作った時の検証に使う、というのはそれなりに有効な戦略だと思うので 1 つの解で Short/Large 両方というのにはそんなに拘わらなくていいと思っています。

終了後のコメント見ると greedy と言っている人がいました。時間中に考えていたことと合わせると、全 Energy は E+(N-1)R で、最大係数に最長時間を割り当てて、それより後では後ろの係数が大きいところは Energy を消費せずに積む、最大係数より前では前の係数が大きいところでより消費させてその場では Energy を消費させない、みたいにずらしていくことでいける、かも？

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  UI E, R, N; cin >> E >> R >> N;
  vector<UI> v(N); for(auto &i : v) { cin >> i; }
  vector<vector<UI>> t(N, vector<UI>(E+1, 0));
  REP(i, t[N-1].size()) {
   t[N-1][i] = i * v[N-1];
  }
  REP(j_, N-1) {
   UI j = N-2-j_;
   REP(i, t[j].size()) {
    UI temp = 0;
    REP(k, i+1) {
     UI kk = i-k+R;
     if(kk > E) kk = E;
     temp = max(temp, k * v[j] + t[j+1][kk]);
    }
    t[j][i] = temp;
   }
  }
  cout << "Case #" << casenum+1 << ": " << t[0][E] << endl;
 }

 return 0;
}

Problem C. Good Luck

いやー、さすが GCJ。出題者側も果敢に挑戦してくるなーと思ったのがこれ。100%の解ではなく一定率以上の正解であれば良い、という問題。実は Small が 1 つだけど複数回可能で、Large が 1 回のみ、というのに特化した Makefile を書いてたりするので今回割と悲しかったりするわけですが、問題読んだ後で「やってくれる」という感じでテンション上がりました。この調子だと近似解を求める問題とかも早晩出てきそうな感じがします。

Small 1 の方は数字が 2, 3, 4, 5 の 4 種類しかないので 3 か 5 が選ばれた場合には確定、2 と 4 の取り扱いをどうするかです。全ての選択パターンから分布をとって判定、とか可能な元の数字の組み合わせから該当するパターンの生起確率をとる、とかが正道な気がしますがベストな解を求める必要はないので手抜きです。素因数分解して 3 と 5 が確定する部分はまず確定。なお情報が全くないところについてはどの数字でも関係ないのでとりあえず 2 で埋める方針です。2⁶, 2⁵ がある場合は 4 が 2 つあることが確定。2⁴ がある時は 2,2,4 とかも有り得ますけど 4,4 の方が確率が高い(はずな)のでこれも 4 が 2 つ。2³ がある時は 2,2,2 も有り得ますけど以下同文で 4 が 1 つ。2² の時は残り枚数が 1 枚の時は 4 が 1 つで確定。後は、2¹ の場合があれば 4 なし。なければ 4 が 1 つです。少なくともここは最適な戦略じゃない気がします。ただ下表のように分が悪い賭でもない、と思いますが、多分。

	積が2	積が4
2,2	(0,1) (1,0)	(1,1)
2,4	(1,0)	(0,1)

一応、これで一回で通っています。ジャッジが正答率出してくれれば良いのにという意見を見ましたが、自分でジャッジ作って試してみるというのが割と良い戦略だったかもしれないですね。

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  cout << "Case #" << casenum+1 << ":" << endl;
  UI R,N,M,K; cin >> R >> N >> M >> K;
  REP(i, R) {
   vector<UI> pr(K); for(auto &val : pr) { cin >> val; }
   int mc2 = 0, mc3 = 0, mc5 = 0;
   vector<UI> dc2(7);
   for(auto val : pr) {
    int c2 = 0, c3 = 0, c5 = 0;
    while(val % 2 == 0) { ++c2; val /= 2; }
    while(val % 3 == 0) { ++c3; val /= 3; }
    while(val % 5 == 0) { ++c5; val /= 5; }
    ++dc2[c2];
    mc2 = max(mc2, c2);
    mc3 = max(mc3, c3);
    mc5 = max(mc5, c5);
   }
   REP(j, mc3) { cout << 3; }
   REP(j, mc5) { cout << 5; }
   int p2 = 3 - mc3 - mc5;
   int c4 = 0;
   if(dc2[6]) c4 = 3;
   else if(dc2[5]) c4 = 2;
   else if(dc2[4]) c4 = 2; //
   else if(dc2[3]) c4 = 1; //
   else if(dc2[2]) {
    if(p2 == 1) c4 = 1; //
    else if(dc2[1] == 0) c4 = 1;
   }
   REP(j, c4) { cout << 4; }
   REP(j, 3-mc3-mc5-c4) { cout << 2; }
   cout << endl;
  }
 }

 return 0;
}

総評

どうにか今年も T シャツ争奪権を得られました。もらえるといいなぁ。