Snackdown 2017 Pre-elimination A: Consecutive Snakes

これは良問だなあと思った。

問題概要

原文 → Contest Page | CodeChef

長さ の蛇が数直線上に 匹おり、 番目の蛇の左端の座標は である。つまり、 番目の蛇は区間 にいる。

いま、この蛇たちを以下の条件が成り立つように移動させたい。

• N 匹の蛇すべてについて、区間 の中にいる
• 左から 番目の蛇の右端と 番目の蛇の左端は繋がっている。つまり 番目の蛇が区間 にいるとき、 番目の蛇は におり、 、 番目の蛇は にいる。

ある蛇が から に移動するとき、コストが かかる。全体コストはこのコストを 匹に対して計算した時の総和である。条件が成り立つように移動させた時の全体コストの最小値を出力せよ。

解説

まず、条件より以下のことがわかります。

• 一番左にくる蛇の左端の座標を決定すると、全ての蛇の左端の座標が決まる
• 移動前に左から 番目にいた蛇は、移動後も左から 番目にいたほうが良い

つまり、蛇を座標順にソートしておいて、一番左の蛇がどこにいるか決めてしまえば、コスト計算はできるということです。しかし、制約を見ると一番左の蛇の配置パターンは非常に多いことがわかるので、何か工夫が必要です。そこで、一旦定式化して考えましょう。

一番左の蛇の左端を とします。すると、 番目の蛇の左端は と表せます (0-indexed)。移動前に左から 番目にいた蛇の左端を とすると、全体コストは以下のように書けます。

\begin{align} cost &=& \sum_{i=0}^{N-1} | S_{i} - (x + iL) | \\ &=& \sum_{i=0}^{N-1} | (S_{i} - iL) - x | \\ &=& \sum_{i=0}^{N-1} | T_{i} - x | \end{align}

は の値の設定に関係なく決まるので、定数とみなして良いです。これを新たに とします。

をソートすると、 のような形になります。さて、 を満たす最大の を とすると、全体コストはこのように書けます。

コスト関数は絶対値付きの一次関数を足しあわせた形になっているので凸関数です。よって、 について二分探索して解くことができます。

計算量はソート 、二分探索パートでコスト計算時に upper_bound が必要なため です 。

ソースコード

累積和を 0-indexed にすると配列外参照が起こるので、そこだけ 1-indexed で書いています。

int T, N, L, A, B;
int s[100010];
int t[100010], acc[100010];

int get(int l, int r) {
    l++; r++;
    return acc[r] - acc[l-1];
}

int calc(int x) {
    int idx = upper_bound(t, t+N, x) - t;
    int vl = idx * x - get(0, idx-1);
    int vr = get(idx, N-1) - (N-idx) * x;
    return vl + vr;
}

signed main() {
    scanf("%lld", &T);
    rep(cases, 0, T) {
        scanf("%lld%lld%lld%lld", &N, &L, &A, &B);
        rep(i,0,N) scanf("%lld", &s[i]);
        sort(s, s+N);

        // 累積和は 1-indexed
        rep(i,0,N) t[i] = s[i] - i * L;
        sort(t, t+N);
        rep(i,0,N) acc[i+1] = acc[i] + t[i];

        // A <= x <= B を満たす x で最小を求めよう
        int lb = A - 1, ub = B - N * L;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(calc(mid) < calc(mid+1)) ub = mid;
            else lb = mid;
        }
        cout << calc(ub) << endl;
    }
    return 0;
}

二分探索に落とし込めた時はちょっと感動した。自力で解けてよかった。

競プロをやりはじめてから一年が経ちました

競プロをやりはじめて、今日でちょうど一年です。半年記事 に引き続き、ポエム的なものを書いていきます。

AtCoder Regular Contest 038 B: マス目と駒

ちょっと迷ってしまったので。

問題概要

原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

解説

rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか？ となるような配列を作ります。

あるマス について、この値は以下のように決定できます。

• 1 ターンで行ける範囲に「負け」を表すマスが少なくとも 1 つある場合、勝ち
• 上記に当てはまらない場合 (移動先の候補がない時も含む)、負け

少しわかりにくいと思うので解説すると、 から 1 ターン動いた先で手番が回ってくる人、つまり「相手」が負け確定になるようなマスがある場合、そこに移動することで自分が勝ち確定になります。反対に、そのようなマスが 1 つもない場合は自分が負け確定になります。あとはこれを右下からメモ化再帰で求めていけば良いです。

ソースコード

int h, w;
char board[110][110];

// rec[i][j] := (i, j) から始めたら勝つか負けるか？
int rec[110][110];

int dx[] = {0, 1, 1};
int dy[] = {1, 0, 1};

int solve(int x, int y) {
    int &r = rec[x][y];
    if(r != -1) return r;
    r = 1;
    rep(i,0,3) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx == h || ny == w || board[nx][ny] == '#') continue;
        if(solve(nx, ny) == 1) r = 0;
    }
    return r;
}

signed main() {
    cin >> h >> w;
    rep(i,0,h) rep(j,0,w) cin >> board[i][j];
    memset(rec, -1, sizeof(rec));
    cout << (solve(0, 0) ? "Second" : "First") << endl;
    return 0;
}

先攻か後攻かの情報も保持したほうがいいのかな、とか色々考えていたらすんなり書けませんでした。ゲームの問題はもう少し慣れが必要そうです。