D - 壊れた電車 CODE FESTIVAL 2015 予選A 日本語

D - 壊れた電車

問題概略　

N個の車両があり、M人の人がばらばらの車両にいる。

人は隣の車両に一分で移動できる。すべての車両を見て回るのにかかる最小の時間をもとめよ

制約

N(1≦N≦109),$M(1\leqq M\leqq {10}^5,M\leqq N)$ 

• $N\leqq 100$ を満たすデータセットに正解した場合は、$20$ 点が与えられる。
• $N\leqq 500,000$ を満たすデータセットに正解した場合は、上記とは別に $60$ 点が与えられる。
• 追加の制約のないデータセットに正解した場合は、上記とは別に $20$ 点が与えられる。

部分解法

N<=100

動的計画法を使う。

i人までの人が左からj個をt分で埋めている時、i+1番目の人が左からk個までを埋めるのに何分掛かるか。同時進行なので、より掛かる方が全体の経過時間。

i,j,kで100の3乗で間に合う。

類題

D - ぬいぐるみの整理 (Plush Toys)

public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        M = sc.nextInt();
        if (N > 100) return;
        int[] x = sc.nextIntArray(M);
        int[][] dp = new int[M + 1][N + 1];
        fill(dp, INF);
        dp[0][0] = 0;
        //i人の整備士でj両目までを点検する最短
        for (int i = 0; i < M; i++)
        {
            //k個まで埋めたい
            for (int k = 0; k < N + 1; k++)
            {
                //すでにj個埋まっている
                for (int j = 0; j < x[i] + 1; j++)
                {
                    if (i == 0 && j == 1) break;
                    int l = upper0(x[i] - j - 1);
                    int r = upper0(k - x[i]);
                    int nowt = Math.min(l * 2 + r, l + 2 * r);
                    int past = i - 1 >= 0 ? dp[i][j] : 0;
                    int t = Main.max(nowt, past);
 
                    dp[i + 1][k] = Math.min(dp[i + 1][k], t);
                    if (i + 2 <= M) dp[i + 2][k] = dp[i + 1][k];
                }
            }
        }
 
 
        System.out.println(dp[M][N]);
 
    }
 
    public static int upper0(int a)
    {
        if (a < 0) return 0;
        return a;
    }

満点解法

実は左右に移動する際、隣の人を超えた範囲を塗る場合は考えなくて良い

なぜなら

       |

--------->

   <----------------

は

-----     |--->  

<--|     --------------

と、途中で二人が折り返した場合と同じであるため（蟻の問題チック）

よって、左端を塗れる人は左端の人しかいない。つまり、時間制限が決まっていれば端から順番にどこまで塗れるかが、一意に決められる。

よって、時間について二分探索＋貪欲でとけるなぁ

類題

public class Main
{
    static StringBuilder sb = new StringBuilder();
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 123456789;
    static long LINF = 123456789123456789L;
    static long MINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y4 = {0, 1, 0, -1};
    static int[] x4 = {1, 0, -1, 0};
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] F;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;
 
    static int N, M, K;
    static int[] A;
    static int[] x;
 
    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        M = sc.nextInt();
        x = sc.nextIntArray(M);
        long res = binarysearch( LINF,-1);
        System.out.println(res);
    }
 
    public static boolean solve(long t)
    {
        //何個埋めたか
        long fin = 0;
        for (int i = 0; i < M; i++)
        {
            if (fin >= N) return true;
            fin = (fin >= x[i] ? x[i] - 1 : fin);
            long l = upper0(x[i] - fin - 1);
            long r = Math.max(t - l * 2, (t - l) / 2);
            if (l > t) return false;
            fin += (long) (l + r + 1);
        }
        return fin >= N;
    }
 
    //条件を満たす最大値、あるいは最小値を求める
    static long binarysearch(long ok, long ng)
    {
        //int ok = 0; //解が存在する
        //int ng = N; //解が存在しない
        while (Math.abs(ok - ng) > 1)
        {
            long mid;
            if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
            else mid = ok + (ng - ok) / 2;
            if (solve(mid))
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        return ok;
    }
 
    public static int upper0(int a)
    {
        if (a < 0) return 0;
        return a;
    }
 
    public static long upper0(long a)
    {
        if (a < 0) return 0;
        return a;
    }

バイト (id:baitop) 0分前