概要

\(M\) 個のコマを追加するごとに、既に他のコマの効きがあるマスを考慮しながら、あなたのコマを置けるマスを減らしたくなった場合の解法です。

\(i\) 番目までのコマを置いた段階での答えを求めたい場合にも適用できます。

方針

あなたがコマを置けるマスの個数を \(N^2\) で初期化します。

\(i\) 番目のコマを置くとき、\(j\) \((j < i)\) 番目のコマが \(i\) 番目のコマのマスに効いてるかどうか、またその方向を考慮し、コマの効きがまだない方向のマスの個数を数えて、置けるマスの個数から引きます。このとき、既にコマの効きがあってマスを引いてしまう場合があります。

ここで、コマ \(j\) \((j < i)\) とコマ \(j\) からの効きの方向、コマ \(i\) からの効きの方向を固定すれば、同じ方向の場合を除いて、交点は一意に定まります。交点の分だけコマを置けるマスの個数に足すことになりますが、今度は足しすぎに注意で、setなどを用いて重複を省く必要があります。

交点は連立方程式を立てて求めることができ、今回は逆行列を用いました。

参考

CodeQUEEN2023決勝のD問題が似た問題になっています。コマの効きの方向ごとのマスを数え上げるところや、直線の交点を求める具体的な式変形はこちらのユーザ解説に書いています。(ネタバレ注意です)

https://atcoder.jp/contests/codequeen2023-final-open/editorial/6941

実装例

https://atcoder.jp/contests/abc377/submissions/59193824

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0;i<n;i++)
ll dx[4] = {1, 0, 1, 1};
ll dy[4] = {0, 1, 1, -1};

int main() {
    ll n, m; cin >> n >> m;
    ll ans = n * n;
    vector<ll> a(m), b(m);
    rep(i, m) {
        cin >> a[i] >> b[i];

        set<pair<ll, ll>> seen; // 被ったマス

        rep(j, i) rep(k, 4) { // (a[i], b[i])自体に他のコマが効いてる場合
            ll vx = a[j] - a[i];
            ll vy = b[j] - b[i];
            if(vx * dy[k] == vy * dx[k]) { 
                seen.insert({a[i], b[i]});
                seen.insert({k, -1});
            }
        }

        // 他のコマが効いてない直線それぞれについて引く
        if(!seen.count({a[i], b[i]})) ans --;
        if(!seen.count({0, -1})) ans -= n - 1; // たて
        if(!seen.count({1, -1})) ans -= n - 1; // よこ
        if(!seen.count({2, -1})) ans -= min(n - a[i], n - b[i]) + min(a[i] - 1, b[i] - 1); // ななめ1
        if(!seen.count({3, -1})) ans -= min(n - a[i], b[i] - 1) + min(a[i] - 1, n - b[i]); // ななめ2
        
        // i番目より前にコマの効きがあったマスは引きすぎなので戻す
        rep(j, i) rep(k1, 4) if(!seen.count({k1, -1})) rep(k2, 4) if(k1 != k2) {
            ll D = dx[k1] * dy[k2] - dx[k2] * dy[k1]; // 行列式
            ll vx = a[j] - a[i];
            ll vy = b[j] - b[i];

            ll dis1 = dy[k2] * vx - dx[k2] * vy; // 逆行列
            ll dis2 = - dy[k1] * vx + dx[k1] * vy; 
            if(dis1 % D or dis2 % D) continue; // (k1 != k2より、方向が違うので D != 0)
            dis1 /= D;  
            dis2 /= D;
            ll x = a[i] + dx[k1] * dis1; // 直線の交点
            ll y = b[i] + dy[k1] * dis1;
            if(x <= 0 or x > n or y <= 0 or y > n) continue; 
            if(!seen.count({x, y})) {
                seen.insert({x, y});
                ans ++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}