読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

TCO17 Algorithm Round 1A

タイトル, なんて書くのがいいんだろう.

oo- +0/-1 586.85 points 148th.

Easy(250) PingPongQueue

TopCoder Statistics - Problem Statement

問題概要

 {M(2 \le M \le 50)} 人の技術力を表す配列  {skills_i(1 \le skills_i \le 50)} が与えられる. 技術力は相異なる.

ある  {2} 人が試合すると技術力が高い方が勝利する.

まず,  {1} 回目の試合では  {1} 番目と  {2} 番目の人が試合する. 残りの人々は待ち行列を形成している. 以降以下の操作を繰り返した時,  {K(1 \le K \le 1000)} 回目の試合の敗者と勝者を求めよ.

  1. 試合をする
  2. 試合に負けた人は待ち行列の最後尾につく
  3. 試合に勝った人が連続して  {N(1 \le N \le 100)} 回勝っていれば, 待ち行列の最後尾につく
  4.  {2} 人より少ない間, 待ち行列の先頭から場に移動する

解法

はい. えいする.

 {O(M + K)}.

ソース

#include<bits/stdc++.h>
 
using namespace std;
 
class PingPongQueue
{
public:
  vector<int> whoPlaysNext(vector<int> skills, int N, int K)
  {
    queue< int > que;
    for(int i = 0; i < skills.size(); i++) que.push(skills[i]);
    
    int now1 = que.front(); que.pop();
    int now2 = que.front(); que.pop();
    int a = 0, b = 0;
    
    for(int i = 0; i < K - 1; i++) {
      if(now1 < now2) swap(now1, now2), swap(a, b);
      
      b = 0;
      que.push(now2);
      now2 = -1;
      
      if(++a == N){
        a = 0;
        que.push(now1);
        now1 = -1;
      }
 
      if(now1 == -1) now1 = que.front(), que.pop();
      if(now2 == -1) now2 = que.front(), que.pop();
    }
    
    return {min(now1, now2), max(now1, now2)};
  }
};

Med(500) CheeseSlicing

TopCoder Statistics - Problem Statement

問題概要

サンドイッチにチーズをはさみたい.  {A \times B \times C(1 \le A, B, C \le 100)} の直方体のチーズがある.

以下の条件を満たすカットを何度か行える.

  • カットは 1 つのチーズを 2 つに分割する
  • カットは軸と平行
  • 分割後の 2 つのチーズの辺は整数長をもつ

パンの上にチーズを置く時, 最短の辺が垂直になるように回転される.  {(X, Y, Z) (X \ge Y \ge Z)} のチーズが置かれる時, 表面積は  {X \times Y}, 厚さは  {Z} となる.

置かれるチーズの厚さは  {S(1 \le S \le 10)} 以上である必要がある.

上手くカットしたときに, 置かれるチーズの総表面積の最大値を求めよ.

解法

 {O(N^4)} のDPであれば正当性を考えなくても実装できるのでする.

dp[x][y][z] :=  {(x, y, z)} のチーズの部品が取りうる総表面積の最大値とする.

遷移は,  {x, y, z} を任意長に切ればよい.

ソース

なんか  {x, y, z} のソートをするときに毎回 vector でえいしてたら TLE だったので悲しい気持ちになってたが, 普通に int p[3]; をするだけでよい.

#include<bits/stdc++.h>
 
using namespace std;
 
int dp[102][102][102];
int p[3];
 
class CheeseSlicing
{
public:
  int S;
  
  int rec(int x, int y, int z)
  {
    p[0] = x, p[1] = y, p[2] = z;
    sort(p, p + 3);
    x = p[0], y = p[1], z = p[2];
    if(x < S) return(0);
    if(~dp[x][y][z]) return(dp[x][y][z]);
    int ret = y * z;
    for(int i = 1; i < x; i++) {
      ret = max(ret, rec(i, y, z) + rec(x - i, y, z));
    }
    for(int i = 1; i < y; i++) {
      ret = max(ret, rec(x, i, z) + rec(x, y - i, z));
    }
    for(int i = 1; i < z; i++) {
      ret = max(ret, rec(x, y, i) + rec(x, y, z - i));
    }
    return(dp[x][y][z] = ret);
  }
  
  int totalArea(int A, int B, int C, int _S)
  {
    S = _S;
    memset(dp, -1, sizeof(dp));
    return(rec(A, B, C));
  }
};