Codeforces Round #456 (Div. 2) D - Fishes -

問題文

n × m マスのグリッドにk匹の魚がいる。（それぞれのセルには魚は高々一匹しかいない）
r × r の正方形の網がある。その網をグリッド上に設置したとき、その領域に含まれる魚を得られる。
その網をグリッド上の考えられるすべての場所に設置するとき、得られる魚の平均の数を最大化せよ。

制約

http://codeforces.com/contest/912/problem/D

解法

まず愚直に考えると、全ての座標に魚を置いてみて、その座標を含む領域の数が大きいやつからとってくみたいなことを思いつく。
しかし n m の制約からそれは無理なことが分かる。

そこで含まれる領域の数が多い座標の特徴はなにか考える。少し考えると真ん中に行けばいくほど良いことが分かる。(直感的にも分かる)

考察から、グリッド上の真ん中あたりから座標を決めていくことにする。やり方はいろいろあると思う。
公式の解説では、y座標は m / 2 と m / 2 + 1 、x座標は 1 ~ n に決めて、その座標を含まれる領域の数(グリッドと網の領域のサイズと魚の座標から計算できる)と一緒に multiset に突っ込んで、いいやつから取っていってそれに近い座標もどんどん突っ込んでくみたいなやり方をしていた。(公式解説を見た方が正確)

公式解説
http://codeforces.com/blog/entry/56920

ソースコード

const int N = 100005, M = 350;
int n, m, r, k;

struct Cell {
    int x, y, d, val;
    Cell(int x, int y, int d) : x(x), y(y), d(d) {
        val = (min(m+1, y+r) - max(y, r)) * 1LL * (min(n+1, x+r) - max(x, r));
    }

    bool operator < (const Cell &other) const {
        return val > other.val;
    }
};

multiset<Cell> ms;

double get() {
    for ( int i = 1; i <= n; i++ ) {
        int j = m / 2;
        ms.insert({i, j, 0});
        ms.insert({i, j+1, 1});
    }

    int total = 0;
    Rep(i, k) {
        auto it = *ms.begin();
        total += it.val;

        ms.erase(ms.begin());

        if ( it.d == 1 && it.y < m ) {
            ms.insert({it.x, it.y+1, 1});
        } else if ( it.d == 0 && it.y > 1 ) {
            ms.insert({it.x, it.y-1, 0});
        }
    }

    return (double)total / ((n-r+1) * 1LL * (m-r+1));
}

signed main() {
    cin >> n >> m >> r >> k;
    if ( n > m ) swap(n, m);

    if ( n == 1 && m == 1 ) {
        printf("%.10f\n", 1.0);
    } else {
        printf("%.10f\n", get());
    }

    return 0;
}

反省とか

自分で解いたというより解説を理解しただけ。
コンテスト中はCを読むのがめんどくさすぎてほどんど考えず離脱してしまった。