4653 - Array Game

ACM-ICPC live archive

4653 - Array Game - Asia - Tehran - 2009/2010
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4653

問題概要

長さ無限の1次元グリッドがある。

  • -300から300の間に+ or -の符号が乗っている。最大+,-100個ずつ
  • 同様の区間に数字がある。最大100個値の範囲は-9から9
  • この数字の集合全てを、正負の方向に1ずつ動かすことができる。すべての数字がうごく。
  • 符号の上に数字がのると、数字は消滅し、その数字の分スコアが減少or上昇する。符号は消滅しない。
  • 何回でも動かせる。いつでもやめられる。

実現できる最大スコアを求めよ。

解法

DP
最大右に動かした数　と　最大左に動かした数　が定まれば、消える数字が定まる。
それを状態にしてDP

最初前処理なにもせず、メモ化を適当にしたらTLE.
書き直した。
右or左に動かしたら、どの数字が消滅するかというのを前処理で求めておく。
その情報をもとにDPしたら間に合った。
でも、もっと早く解けてる人がいるから他に解法があるのだろう。

がんばって解けたからうれしい。
配列外参照ではまってたのがなんとも後悔。。。

ソース

#include<algorithm>
#include<cstdio>

#define REP(i,b,n) for(int i=b;i<(int)n;++i)
#define rep(i,n)   REP(i,0,n)
using namespace std;
const int INF = 1000000000;
const int N = 601;

int ope[N], pos[100], value[100], numN, numM, numP;
int dp[N][N];
int rightUsed[N][100];
int leftUsed[N][100];

void init(){
  rep(i, N){
    ope[i] = 0;
    rep(j, N){
      dp[i][j] = -INF;
    }
    rep(j, numN){
      rightUsed[i][j] = leftUsed[i][j] = 0;
    }
  }
  dp[0][0] = 0;
}

bool input(){
  scanf(" %d %d %d ", &numN, &numP, &numM);
  if(numN == 0 && numP == 0 && numM == 0)return false;
  init();
  rep(i, numN){
    scanf(" %d %d ", &pos[i], &value[i]);
    pos[i] += 300;
  }
  rep(i, numP){
    int p;
    scanf(" %d ", &p);
    ope[p+300] = 1;
  }
  rep(i, numM){
    int p;
    scanf(" %d ", &p);
    ope[p+300] = -1;
  }
  return true;
}

void solveUsed(){
  REP(i, 1, N){
    rep(j, numN){
      if(rightUsed[i-1][j] != 0){
        rightUsed[i][j] = rightUsed[i-1][j];
        continue;
      }
      int nowPos = pos[j] + i;
      if(nowPos > N)continue;
      rightUsed[i][j] = ope[nowPos];
    }
  }
  REP(i, 1, N){
    rep(j, numN){
      if(leftUsed[i-1][j] != 0){
        leftUsed[i][j] = leftUsed[i-1][j];
        continue;
      }
      int nowPos = pos[j] - i;
      if(nowPos < 0)continue;
      if(ope[nowPos] != 0){
        leftUsed[i][j] = ope[nowPos];
      }
    }
  }
}

void solve(){
  int ans = 0;
  rep(left, N){
    rep(right, N){
      ans = max(dp[left][right], ans);
      int nextRightScore = dp[left][right];
      int nextLeftScore = dp[left][right];
      rep(i, numN){
        if(rightUsed[right][i] == 0 && leftUsed[left][i] == 0){
          if(right < N-1 && rightUsed[right+1][i] != 0){
            nextRightScore += rightUsed[right+1][i] * value[i];
          }
          if(left < N-1 && leftUsed[left+1][i] != 0){
            nextLeftScore += leftUsed[left+1][i] * value[i];
          }
        }
      }
      if(right < N-1){
        dp[left][right+1] = max(dp[left][right+1], nextRightScore);
      }
      if(left < N-1){
        dp[left+1][right] = max(dp[left+1][right], nextLeftScore);
      }
    }
  }
  printf("%d\n", ans);
}

int main(){
  while(input()){
    solveUsed();
    solve();
  }
  return 0;
}

いつか、さらっと書けるようになりたい。