ABC311 反省会

全体的な反省

• 考えていた解法はサンプルできちんと試そう

A,B問題

• 今回は特になし。あっさり解けたと思う。

C問題

• 閉路検出の問題。Cに配置されていることを考えると再帰無しでも解けそうだが、あんまり書いたこと再帰で解いた。
• サイクルの部分だけ出力する必要があるので、適当に工夫した。提出

D問題

• 各盤面についてどの方向で移動しているかという情報を記録できるので、幅優先探索すれば良い。提出

E問題

コンテスト中に頑張ったが解けなかった。

考えていたこと

各マスからどの程度伸ばせるかということが判別することができれば、解ける。
ただし、 伸ばせる数　程度の計算量になるので、前計算か高速に答える必要がある。
コンテスト中の方針としては、前計算として、各マスから最も近い穴の座標を、それぞれ独立に累積minで記録して、各マスごとにどこまで伸ばせるかを計算しようとした。が、うまくいかなった。提出
なぜだめだったのかを反省も込めて書いてみる。

コンテスト中の方針は、あるマスから、最も近い穴の座標を記録しておき、それをもとに計算するというものだった。
（モチベーションは,、正方形 を考えるときに、最初に当たりそうな穴の座標をでそれぞれ記録したいという感じ。)
ここで、マスのときに、座標とにそれぞれ穴があるものとする。この時、は右下隅とする正方形は答えの候補となりえるが、はとなってしまい答えを導出できない。
がそれぞれの軸についての上限となってくれることを期待したが、最小値同士だと情報が足りない。 例えば、とに穴があってもとなり、情報が消える。
それぞれの情報をマスの座標を保存すれば解ける気もするが、計算パートが大変そう。
いずれせよ、記録しておく値だけで情報が不足する/答えの導出に足りないという部分には気づくべきだった。

解法

結局累積和と二分探索で解いた。こっちのほうが解法が明確がわかりやすいかも...
コンテスト中にひらめきたい解法だった。

#include <bits/stdc++.h>

using namespace std;
using Int = long long;

template<class F,class T>
auto  maximize(T imin,T imax,F &f){
    while(imax - imin > 1){
        T mid = imin + (imax - imin)/2;
        if(f(mid)) imin = mid;
        else imax = mid;
    }
    return imin;
}

template <class T>
class Cumulative2DSum {
    // query[sx,gx),[sy,gy)
public:
    vector<vector<T>>sum;
    T e;
    Cumulative2DSum(vector<vector<T>>&v,T e) {
        // W is x, H is y
        int W = v.front().size();
        int H = v.size();
        ++H , ++W;
        sum = vector<vector<T>>(H,vector<T>(W,e));
        
        for(int i = 0; i < v.size(); ++i){
            for(int j = 0; j < v[i].size(); ++j){
                sum[i + 1][j + 1] +=  v[i][j];
            }
        }
        for(int i = 1; i < sum.size(); ++i){
            for(int j = 1; j < sum[i].size();++j){
                sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }
    }
    T query(int sx,int sy,int gx,int gy){
        return sum[gy][gx] - sum[sy][gx] - sum[gy][sx] + sum[sy][sx];
    }
};

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W, N;
    cin >> H >> W >> N;
    map<pair<int,int>,int>pos;

    vector<vector<Int>>h(H, vector<Int>(W,0));
    for(int i = 0; i < N; ++i){
        int y,x;
        cin >> y >> x; --y; --x;
        h[y][x]++;;
    }
    
    auto csum = Cumulative2DSum<Int>(h, 0LL);
    
    int cx = 0, cy = 0;
    auto f = [&](int mid) {
        if(cx + mid  >= W or cy + mid  >= H) return false;
        return csum.query(cx,cy,cx + mid + 1,cy + mid + 1) == 0;
    };
    
    Int ans = H * W - N;
    for(int y = 0; y < H; ++y){
        for(int x = 0; x < W; ++x){
            if(h[y][x]++) continue;
            cx = x; cy = y;
            Int remu =  maximize(0, 3001,f);
            ans += remu;
        }
    }
    cout << ans << endl;
}