問題（要約）
マンハッタン距離で半径を表される円がたくさんある。それらに被らないように最大の円を作れ。
- 電脳少女プログラミング2088 S問題
考えたこと
1つ目の思いつき
まず初めに思いついたのは、
2次元bool配列を用意してそこに出し、中心と半径を全探索する 方法。
さっそく計算量を考えてみる。
まず前処理としてマップを埋める。だいたい $O(HW)$ ぐらいじゃね、と思った。
次に探索する。これは中心1個ごとにおおよそ$O(HW)$かかり、中心を全探索するには$HW$回かかるから、合計で$O(H^2W^2)$かかる。
よって全体の時間計算量は明らかに$O(H^2W^2)$である。
$H,W<=200$より、最大$O(1,600,000,000)$で、コンピュータの限界だと考えられている秒あたり$O(10^9)$を超えている。
よっておそらくTLE(実行時間超過)が出る。
あとは多分S問題でゴリ押し解法が通るわけない
2つ目の思いつき
でもまだ全探索を諦めたくない。
ここで、$M(縄張りの個数)<=200$に着目する。
どうにかして縄張り1つに対する半径の最大値を$O(1)$で求めることができれば、すべてのマスを全探索しても$O(HWM)$、つまり$O(8,000,000)<10^9$で、十分間に合う解法であることがわかる。
ではどうやって半径の最大値を$O(1)$で求めるか。(多分$O(logN)$の二分探索でも間に合うケド)
ここで半径がマンハッタン距離で表されることを利用する。
円の中心間のマンハッタン距離は、$(x_1,y_1),(x_2, y_2)$とおくと、$d=|x_1-x_2|+|y_1-y_2|$で求められる。
ここで、マンハッタン距離である事を忘れて普通の距離のように扱うと、$max(-1, 中心間の距離-片方の半径)$は最大の半径になる。
だから、これを実装してあげればAC。
※ちなみに、$max()$の左辺を0にしてないのは、そのマス自体が他の円の中に入っている状態をより楽に区別できるようにするため。
伝えたいこと
- 楽な解法がダメそうでもちょっと粘ってみよう！
- まずは無理そうでも計算量を出してみる！いろいろひねってみてそれを改善していこう！
- (競技)プログラミングは、最高のコードを書くことが目的なのではなく、最低限ACできるコードを書くという競技。ACすればOK！これめっちゃ重要！
実装例(AC)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
int main() {
ll h, w, m;
cin >> h >> w >> m;
vl x(m), y(m), r(m);
rep(i, m) cin >> x[i] >> y[i] >> r[i];
for (auto& i : x) i--;
for (auto& i : y) i--;
ll res = -INF;
rep(i, h) {
rep(j, w) {
ll now = INF;
rep(k, m) {
ll dist = abs(i - x[k]) + abs(j - y[k]);
ll remain = dist - r[k] - 1;
chmin(now, remain);
}
chmax(res, now);
}
}
chmax(res, -1LL);
cout << res << endl;
}
さいごに
なにか質問、疑問、感想とかあればコメントへお気軽に。投稿の励みになります。