TCO17 Algorithm Round 1A - ei1333の日記

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

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

Easy(250) PingPongQueue

問題概要

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

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

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

試合をする
試合に負けた人は待ち行列の最後尾につく
試合に勝った人が連続して ${N(1 \le N \le 100)}$ 回勝っていれば, 待ち行列の最後尾につく
${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));
  }
};