Pの競プロ記

競技プログラミングに関することを書きます。

ARC #010 C 積み上げパズル

概要


問題文はこちら
http://arc010.contest.atcoder.jp/tasks/arc010_3

1次元のパズル的なやつがあって高得点狙いましょう!みたいな問題です。
(問題文が読みやすいのでそちらを参考にしてください)


解法


動的計画法(DP)で解くことができます。

まずこの問題を全探索で解こうとすると、ブロックを置く・置かないの2択の処理を5000回しないといけないのでいくら時間があっても足りません。

int dp[現在のブロック][積まれているブロックの色の種類(bitで管理)][直前の色]
で解くことができます。

ここで注意しないといけないことがあります。
(私も最初ハマっていたのですが)上の配列をdp[5000][(1 << 10)][11]のように用意するとメモリが足りません。

配列を再利用しましょう!!
⇒ int dp[2][(1 << 10)][11]

これでループを回してやればよいです。

そしてもう一つ注意すべき点、得点がマイナスの可能性もあるので配列は最初にマイナスの値で初期化しないといけません。


C++Java両方で書いたので参考程度に(やっている事は同じです)


ソースコード


C++バージョン

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

#define REP(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rep(i,n) REP(i,0,n)

static const int INF = 50000000;

int n,m,Y,Z;
map<char, int> c;
int p[10];
char b[5000];
int dp[2][(1 << 10)][11];

int solve(){
  rep(i,2) rep(j,(1<<m)) rep(k,m+1) dp[i][j][k] = -INF;
  dp[0][0][m] = 0;

  for(int i = 0; i < n; i++){
    int next = (i + 1) % 2;
    int now = i % 2;
    
    for(int j = 0; j < (1 << m); j++){
      for(int k = 0; k <= m; k++){
        dp[next][j][k] = -INF;
      }
    }
    
    for(int j = 0; j < (1 << m); j++){
      for(int k = 0; k <= m; k++){
        if(dp[now][j][k] == -INF) continue;
        
        dp[next][j][k] = max(dp[next][j][k], dp[now][j][k]);
        int cc = c[b[i]];
        int bonus = p[cc] + ((cc == k) ? Y : 0);
        dp[next][j | (1 << cc)][cc] = max(dp[next][j | (1 << cc)][cc], dp[now][j][k] + bonus);
      }
    }
  }
  
  int ans = -INF;
  for(int j = 0; j < (1 << m); j++){
    for(int k = 0; k <= m; k++){
      if(j == ((1 << m) - 1)) dp[n % 2][j][k] += Z;
      ans = max(ans, dp[n % 2][j][k]);
    }
  }

  return ans;
}

int main(){
  cin >> n >> m >> Y >> Z;
  
  rep(i,m){
    char cc;
    cin >> cc >> p[i];
    c[cc] = i;
  }
  
  rep(i,n) cin >> b[i];
  
  cout << solve() << endl;
  
  return 0;
}

Javaバージョン

import java.util.*;

public class C {
    final int INF = 5000000;
    
    void run(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int Y = sc.nextInt();
        int Z = sc.nextInt();
        
        Map<Character, Integer> c = new HashMap<Character, Integer>();
        int[] p = new int[m];
        char[] b = new char[n];
        
        for(int i = 0; i < m; i++){
            String cc = sc.next();
            p[i] = sc.nextInt();
            
            c.put(cc.charAt(0),i);
        }
        
        String str = sc.next();
        for(int i = 0; i < n; i++){
            b[i] = str.charAt(i);
        }
        
        int[][][] dp = new int[2][(1 << m)][m + 1];
        
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < (1 << m); j++){
                for(int k = 0; k <= m; k++){
                    dp[i][j][k] = -INF;
                }
            }
        }

        dp[0][0][m] = 0;
       
        for(int i = 0; i < n; i++){
            int next = (i + 1) % 2;
            int now = i % 2;
            
            for(int j = 0; j < (1 << m); j++){
                for(int k = 0; k <= m; k++){
                    dp[next][j][k] = -INF;
                }
            }
            
            for(int j = 0; j < (1 << m); j++){
                for(int k = 0; k <= m; k++){
                    if(dp[now][j][k] == -INF) continue;
                    
                    dp[next][j][k] = Math.max(dp[next][j][k], dp[now][j][k]);
                    int cc = c.get(b[i]);
                    int bonus = p[cc] + ((cc == k) ? Y : 0);
                    dp[next][j | (1 << cc)][cc] = Math.max(dp[next][j | (1 << cc)][cc], dp[now][j][k] + bonus);
                }
            }
        }

        int ans = -INF;
        for(int j = 0; j < (1 << m); j++){
            for(int k = 0; k <= m; k++){
                if(j == ((1 << m) - 1)) dp[n % 2][j][k] += Z;
                ans = Math.max(ans, dp[n % 2][j][k]);
            }
        }
                    
        System.out.println(ans);
    }
    
    public static void main(String[] args){
        new C().run();
    }
}