Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-29

[][] TopCoder Single Round Match507 Div1 19:38 はてなブックマーク -  TopCoder Single Round Match507 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:11:56.237Passed System Test214.63
5000:57:07.821Challenge Succeeded151.45(再提出1回)
9001:00:14.440Opened0.00
Challenge..0.00

部屋(Room 30) 7位,全体 481位

Rating : 1449 → 1448 (-1)

500の正答率が30%弱で,250点問題の早解き + 500点問題Challengeの回でした.

250 CubeStickers

要約

  様々な色のステッカーが与えられており,それらを立方体の6面に貼る(リストは重複している可能性もある).立方体の1面は1枚ステッカーを貼り,辺を共有する面を異なる色のステッカーを貼りたい.そのような貼り方があるかを判定せよ.

 ステッカーの枚数は6枚以上50枚以下.それぞれのステッカーは文字数10文字以下の色で識別される.

方針

 リスト中に3回以上現れても,1つの色を使える回数は2回(対面を塗る)のみ,そこで色を2回以上,1回のみで分けると,条件を満たす塗り方が出来るのは次のうちのどれかのみ.

2回以上1回
0色6色以上
1色4色以上
2色2色以上
3色0色以上
コード例
class CubeStickers {
public:
  string isPossible(vector <string> s) {
    sort(s.begin(), s.end());
    map<string, int> t;

    for(int i = 0;i < s.size();i++){
      t[s[i]]++;
    }

    s.erase(unique(s.begin(), s.end()), s.end());
    int cnt = 0;
    for(map<string, int>::iterator it = t.begin() ;it!= t.end();it++){
      if(it->second >=2) cnt++;
    } 
    if(cnt >= 3) return "YES";
    if(cnt >= 2 && s.size() >= 4) return "YES";
    if(cnt >= 1 && s.size() >= 5) return "YES";
    if(s.size() >= 6) return "YES";
    return "NO";
  }	
};
分析

 12分はかかり過ぎでした.「uniqueして3色以上あれば良い」「色が6色以上あれば良い」と誤解したままコードを書いた事と,if文の連鎖の部分で構文エラーを出してしまった事が原因です(結局エラーの原因は分からなかった).

500 CubePacking

要約

 1辺の長さが1の立方体Ns個と1辺の長さがLの立方体がNb個ある.これらの立方体達を詰められる直方体の箱のうち,体積が最小のもの達を考える.その体積を答えよ.立方体は斜めに詰めてはならない,つまり,立方体の各辺はの箱の各辺に平行になるように詰める.

 Nsは1以上1000000000以下,Nbは1以上1000000以下,Lは2以上10以下.

方針

 Lが小さい事に注目する.大立方体を一列に積み上げ,その上に小長方形を積めば最悪でも箱に生じる隙間はL * L - 1にまで押さえられる.そこで,(全体の体積)+(0 ~ L * L - 1)の中で立方体達を詰められる体積を調べる.

 体積をひとつ固定する(volとする).volの箱に立方体を詰めるにはまず vol = x * y * z と因数分解できないとならない.問題は各辺の長さの条件. L <= x, y, z <= vol ^ {1/3}の範囲で動き,volは最大2 * 10^{9}程度なので,x, yは最大10^{3} 程度,またzはx, yが決まれば一意に決まるので,探索する必要はない.従って一つの体積 volでの判定は10^{6}程度の計算ですみ,これをL*L回行っても計算は間に合う.

 以上の方針はcafelierさんのコードを参考に書きました.

分析

 自分の場合こういう数学的な問題だとどうにかして数式一発で答えを出せるような方法がないかとを考え,「計算量が間に合えば十分」という考え方になかなかならなかったです.実際提出したコードも答えを何かの下限を求めるのではなく,数式で作っています.

コード例

 下に整形した提出コードと,後で考えて作ったコードを載せます.前者の方針は「立方体に近づけるか大立方体を一列に並べる」でしたが,立方体に近づけるではなく本当に立方体の箱に詰めている点が間違いです.後者は枝狩りをしているといえども全体の体積の2乗のアルゴリズムなのでTLEを起こします.

#include <string>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <cmath>
 
using namespace std;
 
class CubePacking {
public:
 
  int getMinimumVolume(int s, int b, int L) {
    int ans = b * L * L * L;
    int line = s/ (L * L);
    int res = s % (L * L);
 
    int vol = L * L * L * b + s ;
    long long i = 0;
    for(i = 0;;i ++){
      if(i * i * i  >= vol) break; 
    }
    vol = i * i * i; 
    return min(ans + L * L * line + (res == 0 ? 0 : L * L), vol);
  }
};


コード例

(このコードはTLEを起こします)

#include <string>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

class CubePacking {
public:
 
  int getMinimumVolume(int s, int b, int L) {
    ll ans = (ll) pow(10.0, 10);
    const ll vol = L * L * L * b + s ;
    for(ll i = L; i * L * L <= vol; i++){
      for(ll j = i; i * j * L <= vol; j++){
	ll bbox_par_floor = (i / L) * (j / L);
	ll required_height = ( (b + bbox_par_floor -1) / bbox_par_floor ) * L;
	ll required_vol = required_vol * i * j ;

	if(required_vol == vol) 
	  return vol;

	ll candidate = 0;
	if(required_vol >= vol) {
	  candidate = minvol;
	}else{
	  ll res = vol - required_vol;
	  candidate = required_vol + ( (res / i / j) * i * j + (res % (i * j) == 0 ? 0 : i * j) ) ;
	}
	ans = ans < candidate ? ans : candidate;
      }
    }

    return ans;
  }
};