Hatena::Grouptopcoder

blu_rayの日記

2012-01-06

Codeforces Round #100

| 04:12

x-x---

0完。眠いときはやめたほうがいい。

A. New Year Table

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const double PI =  3.141592653589793;
const double Eps = 1e-8;
int n, R, r;

void solve() {
  if (n == 1) {
    if (R >= r) { puts("YES"); return; }
    puts("NO"); return;
  }

  if (R/2.0 < r) { puts("NO"); return; }
  
  double tan_ = r / sqrt((double)R*R - 2.0*R*r);
  double need = atan(tan_) * 180.0 / PI * 2 * n;
  if (360.0 + Eps > need) { puts("YES"); return; }
  puts("NO");
}

皿の直径がテーブルの半径より大きい時は多分複数枚置けないと思うので"NO"にして、あとは一枚あたりに必要な角度だしてn枚分数えたときに360°に収まるか愚直にみる。

B. New Year Cards

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int N, pl[302][302];

void solve() {
  vector<int> ret(N+2, -1);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      int cur = -1;
      rep(k,N) {
        if (pl[0][k] <= i && j != pl[0][k]) { cur = pl[0][k]; break; }
      }
      if (cur == -1) continue;
      if (ret[j] == -1) { ret[j] = cur; continue; }
      if (find(pl[j], pl[j]+N, cur) < find(pl[j], pl[j]+N, ret[j])) {
        ret[j] = cur;
      }
    }
  }
  rep(i,N) { if(i) putchar(' '); printf("%d", ret[i+1]); } puts("");
}

Aと比べて問題文長すぎ。

年賀メールを受信する毎に手札が増えていって、相手毎に送信すべき年賀メールを選択して、優先度が高い場合は更新するようにする。findの実装よく知らないけど多分要素数に比例して、結局全体でO(N^3)?

C. New Year Snowmen

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
typedef pair<int,int> P;

int N, r[100002];

void solve() {
  map<int,int> m;
  priority_queue<P> q;

  rep(i,N) { if (m.count(r[i])) ++m[r[i]]; else m.insert(make_pair(r[i],1)); }
  foreach(m,i) q.push(P(i->second, i->first));

  vector<int> v;
  vector<vector<int> > ret;
  vector<P> temp;
  while(!q.empty()) {
    P p = q.top(); q.pop();
    v.push_back(p.second);
    --p.first;
    temp.push_back(p);
    if(v.size() == 3) {
      sort(v.begin(), v.end(), greater<int>());
      ret.push_back(v);
      rep(i,3) if(temp[i].first > 0) q.push(temp[i]);
      temp.clear();
      v.clear();
    }
  }
  
  printf("%d\n", ret.size());
  rep(i,ret.size()) {
    rep(j,3) {
      if(j) putchar(' '); printf("%d",ret[i][j]);
    }
    puts("");
  }
}

priority queue.本番中はvector<P>とか使ってTLEた。

D. New Year Contest

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int Inf = 1<<28;
int N, a[102], dp[102][800], pl[102][800];

void solve() {
  rep(i,N+1) rep(j,750) { dp[i][j] = -Inf; pl[i][j] = -Inf; }
  sort(a, a+N);
  dp[0][0] = 0;
  pl[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 720 ; ++j) {
      dp[i+1][j] = dp[i][j];
      pl[i+1][j] = pl[i][j];
      if (j-a[i] >= 0) {
        if(dp[i+1][j] < dp[i][j-a[i]] + 1) {
          dp[i+1][j] = dp[i][j-a[i]] + 1;
          pl[i+1][j] = pl[i][j-a[i]];
          if(j > 350) pl[i+1][j] += j-350;
        }
      } 
    }
  }
  
  int ret = 0, penal = 0;
  rep(i,711) if (dp[N][i] > ret) { ret = dp[N][i], penal = pl[N][i]; }
  //if (penal >= 350) penal -= 350;
  printf("%d %d\n",ret,penal);
}

終わった後始めて読み始める。problems tagにdpがあったのでなんとなくそれっぽく書いてみたけどpenalty timeが合わない。同じくtagにsortingがあったからsortしてみたら通った。ていうかこんな変なことしなくてもsortしてやるだけにしてみても大体同じだと思って書いたら通った。

int N, a[102];

void solve() {
  sort(a, a+N);
  int ret = 0, cur = 10, penal = 0;
  rep(i,N) {
    if (cur + a[i] > 720) break;
    ++ret;
    cur += a[i];
    if (cur > 360) { penal += cur - 360; }
  }
  printf("%d %d\n", ret, penal);
}

rate

1423(-80)