公式
D - Moving Queen 解説 by hotman78
クイーンがマス \((r_s, c_s)\) 、マス \((r_1,c_1)\) 、マス \((r_2,c_2)\) 、マス \((r_t,c_t)\) の順で動くとします。
以下の条件を満たす時、クイーンはマス \((r_1,c_1)\) からマス \((r_2,c_2)\) に移動できることが分かります。
- マス \((r_1,c_1)\) とマス \((r_2,c_2)\) が同じマスではない
- \(r_1=r_2\) , \(c_1=c_2\) , \(r_1+c_1=r_2+c_2\) , \(r_1-c_1=r_2-c_2\) のいずれか満たす
よって、以下のアルゴリズムを実装することでこの問題を解くことが出来ます
- マス \((r_2,c_2)\) としてあり得るマスに対し、 \(r_2\) , \(c_2\) , \(r_2+c_2\) , \(r_2-c_2\) の各値についてその値をとるマスの数を保存
- 保存したテーブルを元にマス \((r_1, c_1)\) としてあり得るマスについてゴールにたどり着ける\((r_2,c_2)\) の数を数える
また、マス \((r_s, c_s)\) から一回の移動で移動できるマスの数及び、マス \((r_t, c_t)\) に一回で移動できるマスの数は \(\mathcal{O}(H+W)\) であるため、これは時間計算量 \(\mathcal{O}(H+W)\) で計算できます。(簡単のため本解説では\(\mathcal{O}((H+W)\log(H+W))\) の実装例を載せていますが、基数ソート等を用いる事で \(\mathcal{O}(H+W)\) で解くことが出来ます)
注意点として、 マス \((r_1,c_1)\) とマス \((r_2,c_2)\) が同じマスである場合について慎重に取り除く必要があります。
実装例(C++):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
long long r, c;
vector< long long > r_backet, c_backet, rpc_backet, rmc_backet;
set< pair< long long, long long > > s;
void init(int r,int c){
r_backet.resize(r);
c_backet.resize(c);
rpc_backet.resize(r + c);
rmc_backet.resize(r + c);
}
void rec(int p, int q) {
// r, c, r+c, r-c について記録 / 重複削除のため (r,c) も記録
r_backet[p]++;
c_backet[q]++;
rpc_backet[p + q]++;
rmc_backet[p - q + (c - 1)]++;
s.emplace(p, q);
};
long long cnt(int p, int q) {
// r, c, r+c, r-c 方向に移動して到達できるマスの数を計算
long long res = 0;
// r 固定移動
res += r_backet[p];
// c 固定移動
res += c_backet[q];
// // r+c 固定移動
res += rpc_backet[p + q];
// // r-c 固定移動
res += rmc_backet[p - q + (c - 1)];
res -= s.count({p, q}) * 4;
return res;
};
int main() {
cin >> r >> c;
long long rs, cs, rt, ct;
cin >> rs >> cs >> rt >> ct;
// 0-index に変換
rs--;cs--;rt--;ct--;
// 配列サイズの初期化
init(r,c);
long long ans = 0;
// ゴールにr方向移動で到達するマスについて記録
for (int i = 0; i < r; i++) {
if (i == rt) continue;
rec(i, ct);
}
// ゴールにc方向移動で到達するマスについて記録
for (int i = 0; i < c; i++) {
if (i == ct) continue;
rec(rt, i);
}
// ゴールにr plus/c plus、またはr minus/c minus 方向への移動で到達するマスについて記録
for (int i = -max(r, c); i < max(r, c); i++) {
int p = rt + i, q = ct + i;
if (i == 0) continue;
if (0 <= p && p < r && 0 <= q && q < c) {
rec(p, q);
}
}
// ゴールにr plus/c minus、またはr minus/c plus 方向への移動で到達するマスについて記録
for (int i = -max(r, c); i < max(r, c); i++) {
int p = rt + i, q = ct - i;
if (i == 0) continue;
if (0 <= p && p < r && 0 <= q && q < c) {
rec(p, q);
}
}
// スタートからr方向移動で到達するマスについて計算
for (int i = 0; i < r; i++) {
if (i == rs) continue;
ans+=cnt(i, cs);
}
// スタートからc方向移動で到達するマスについて計算
for (int i = 0; i < c; i++) {
if (i == cs) continue;
ans+=cnt(rs, i);
}
// スタートからr plus/c plus 、またはr minus/c minus 方向への移動で到達するマスについて計算
for (int i = -max(r, c); i < max(r, c); i++) {
int p = rs + i, q = cs + i;
if (i == 0) continue;
if (0 <= p && p < r && 0 <= q && q < c) {
ans+=cnt(p, q);
}
}
// スタートからr plus/c minus 、またはr minus/c plus 方向への移動で到達するマスについて計算
for (int i = -max(r, c); i < max(r, c); i++) {
int p = rs + i, q = cs - i;
if (i == 0) continue;
if (0 <= p && p < r && 0 <= q && q < c) {
ans+=cnt(p, q);
}
}
cout << ans << endl;
}
投稿日時:
最終更新: