t8m8-mem8

競プロとか、学んだことを書いていきます。

ICPC 2016 国内予選 参加記

Hutari. というチームで出場した。結果は4完で38位。
うちのチームは問題を分担せずにAから順番に解いていく方針をとった。

問題↓
http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html

A

ソートして隣同士を全部見ていく。

B

適当に数をカウントしていく。

C

mからエラトステネスの篩をする。
バグらせて時間を持っていかれた。しかも1WAでペナルティ。

D

区間DP。twitterを見る限り2回に分けてDPをした人が多いっぽい。僕は1回のDPで解く解法をとった。

dp[l][r] = [l, r]で取り除ける最大のブロック数 とすると、ある区間[l, r]について
abs(w[l] - w[r]) <= 1 かつ [l+1, r-1]のブロックが全て取り除ける(dp[l+1][r-1] = r - l -1)とき、[l, r]のブロックは全て取り除けるのでdp[l][r] = r - l + 1。
そうでないとき、l<=i<=rなiについて[l, i]と[i+1, r]の2つの区間に分割して和をとった値の最大値となるので、dp[l][r] = max(dp[l][i] + dp[i+1][r])。
最終的に求めるべき答えはdp[0][n-1]。

import java.util.*;

public class D {

    static final Scanner in = new Scanner(System.in);

    static int[][] dp;
    static int[] w;
    static int n;

    static int rec(int l , int r) {
        if (dp[l][r] != -1) return dp[l][r];
        if (l+1 == r) {
            if (Math.abs(w[l] - w[r]) <= 1) return 2;
            else return 0;
        }
        if (l >= r) {
            return 0;
        }

        if (Math.abs(w[l] - w[r]) <= 1) {
            int len = rec(l+1, r-1);
            if (len == r - l -1) {
                return dp[l][r] = r - l + 1;
            }
        }

        int res = 0;

        for (int i=l; i<r; i++) {
            res = Math.max(res, rec(l, i) + rec(i+1, r));
        }

        return dp[l][r] = res;
    }

    static boolean solve() {
        n = in.nextInt();
        if (n == 0) return false;

        w = new int[n];
        for (int i=0; i<n; i++) {
            w[i] = in.nextInt();
        }

        dp = new int[n][n];
        for (int i=0; i<n; i++) {
            Arrays.fill(dp[i], -1);
        }

        System.out.println(rec(0, n-1));
        return true;
    }

    public static void main(String[] args) {
        while(solve());
        in.close();
    }
}

緊張した〜...。