Typical DP Contest J - ボール

問題記録 AtCoder TDPC

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball

問題概要

一次元の座標xiにN個の目標物が設置されている。座標xを狙ってボールを投げると等確率でx-1, x, x+1のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだとき、すべての目標物を倒すために必要なボール投げ回数の期待値を求めよ。

1 <= N <= 16

0 <= xi <= 15

解法

座標の範囲が狭いので、座標xiに目標物がある/ないの状態をbit列で表せばbitDPができる。遷移がよくわからんが、雰囲気で以下のようにやったら通ってしまった。

  1. 狙う座標の周囲3マスに全部目標物があるとき
    • どれか1個が倒れた状態に1/3で遷移 + 1 (1回投げれば必ず1個は倒れるので)
  2. 周囲2マスに目標物があるとき
    • どちらか1個が倒れた状態に1/2で遷移 + 1.5 (どちらか2つにボールが行くのは2/3なので、その逆数）
  3. 周囲1マスに目標物があるとき
    • その1個が倒れた状態に1/1で遷移 + 3 （1/3の逆数）

通した後もモヤモヤしてたが以下の記事を読んだらすべてが腑に落ちた。

http://pekempey.hatenablog.com/entry/2016/02/05/002257

自己遷移を含む場合（この問題でいうところの何もないところにボールを投げてしまうケース）、遷移を数式で表して式変形するというテクが使えるというのが重要ポイントだったっぽい。

感想

期待値DPの基本的な流れは 期待値(次の状態) × 遷移確率 で、「次の状態」が自己遷移になっている場合には式を立てて解く、という感じで理解しておけばいいんだろうか。

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto N = readln.chomp.to!int;
    auto X = readln.split.map!(to!int).array;


    auto mem = new real[](1 << 16);
    mem.fill(-1);

    real dfs(int mask) {
        if (mem[mask] >= 0)
            return mem[mask];
        if (mask == 0)
            return 0;

        real ret = 1L << 59;

        foreach (i; 1..15) {
            int b = (mask & (0b111 << (i - 1))) >> (i - 1);
            int nmask = mask & ~(0b111 << (i - 1));
            real tmp = 1L << 59;
            
            if (b == 0b111) {
                tmp =
                    dfs(nmask | (0b011 << (i - 1))) / 3 +
                    dfs(nmask | (0b101 << (i - 1))) / 3 +
                    dfs(nmask | (0b110 << (i - 1))) / 3 + 1;
            } else if (b == 0b011) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b010 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b101) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b110) {
                tmp =
                    dfs(nmask | (0b010 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b.popcnt == 1) {
                tmp = dfs(nmask) + 3.0L;
            }
            
            ret = min(ret, tmp);
        }

        mem[mask] = ret;
        return ret;
    }

    
    int mask = 0;
    foreach (x; X)
        mask |= (1 << x);
    writefln("%.9f", dfs(mask));
}