https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0434
解説
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0434/review/5811086/hamayanhamayan/C++14
シミュレーション高速化していく問題となる。
加工後の高さをもっていきながらシミュレーションをしていきたい所ではあるが、盤面が大きすぎる。
なので、加工された部分のみを保持しながらシミュレーションを頑張っていくことにする。
各所、切削をしていくが、その切削によって表面積がどう変化したかという感じで、差分計算をしていくことにする。
初期状態
最初は、全部つるつるの状態なので、6面の表面積を足したものになる。
具体的には2WD + 2DH + 2HWが初期状態となる。
差分計算
切削をしていくが、その際の表面積の変化は周りの高さがどうであるかに依存することになる。
4面あるので、4面について場合分けを書いていってもいいが、実際にはやっていることはさほど変わらず、自分のように
dx, dyを使用して4面を同じコードでさばいていくことにする。
盤面をすべて持つことはできないので、mapで保持することにする。
map<int,map<int,int>>みたいにしてもいいのだが、mapはまあまあ重いので、配列でx座標については配列にして置いている。
中で3択の場合分けをしている
場合分け1: 盤面からはみ出してしまう場合
はみ出す場合は、そちら側は切削した分だけ表面積がなくなってしまうので、ans -= z[i]をしよう。
反対側の表面積があるのでは？と思うかもしれないが、そちらの側面もループであとで考慮するので、
このはみ出す方向に対する表面積としては減るだけ
場合分け2: まだ切削してない部分と面している
この場合は切削した分だけ表面積が増えるので、ans += z[i]すればいい。
場合分け3: 既に切削している部分と面している
この場合はちょっと複雑なのだが、差分計算でよくやる、「現状を消す→処理→現状を足す」ということをすればいい。
現状を消すの部分は、今切削している所と今見ている隣接している所の高さの差が現在生じている表面積になっているので、
ans -= abs(changed[xx][yy] - cur)とする。
これで、切削処理をするので、curがcur - z[i]となる。
それでから現状を足すので、ans += abs(changed[xx][yy] - (cur - z[i]))とする。
注意点
これで最終的にansを答えればいいのだが、オーバーフローに注意。
long longで全体的に計算すること。
ll W, D, H; int C; int x[101010], y[101010]; ll z[101010]; map<int, int> changed[101010]; int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }; //--------------------------------------------------------------------------------------------------- void _main() { cin >> W >> D >> H >> C; rep(i, 0, C) cin >> x[i] >> y[i] >> z[i]; ll ans = 2 * W * D + 2 * D * H + 2 * H * W; rep(i, 0, C) { ll cur = H; if (changed[x[i]].count(y[i])) cur = changed[x[i]][y[i]]; rep(d, 0, 4) { int xx = x[i] + dx[d]; int yy = y[i] + dy[d]; if (0 <= xx && xx < W && 0 <= yy && yy < D) { if (changed[xx].count(yy)) ans -= abs(changed[xx][yy] - cur), ans += abs(changed[xx][yy] - (cur - z[i])); // 場合分け3 else ans += z[i]; // 場合分け2 } else ans -= z[i]; // 場合分け1 } changed[x[i]][y[i]] = cur - z[i]; } cout << ans << endl; }
