みなさん、こんにちは。第3回swapコンの振り返りを投稿します。
swapコンの詳細はこちら: https://qiita.com/swapman/items/62e9fedc2a3e39b9d28c
結果としては、A-E,4ペナでした。コードを出す前に一度見直ししないとね...
(A-Eの解説はこちら: https://qiita.com/swapman/items/f878967b70950567b4cd)
この記事では、自分が解けなかったF問題の解説を覚書として残したいと思います。それではいきましょう！
ABC269のリンク: https://atcoder.jp/contests/abc269
【解説を見る前の僕の考察と反省】
ある矩形区間の和を求める問題ですが、大体半分くらいになるなぁと思っていましたが、そこから考察があまり進まず....
二次元累積和を使う感じかなと思いつつも、制約を見て即撤回。結構難しかったです。
【解説を拝見してAC】
まずは、「全てのマス (i,j) について、 i+j が奇数ならそのマスに書かれている数字を 0 に書き換える」を無視して考えましょう。
これを無視すると、ただの二次元累積和の問題です。左上と右上の座標だけを決めてやれば、その矩形区間内の和はO(1)で求まります。この性質を利用しましょう。（ここでは二次元累積和について詳しく説明することはしません。）
グリッド内に同じ性質が存在する場所を見つけることが大事ですね。よく考えるとグリッドの奇数行目と偶数行目で背反にグリッドを分けることができます。奇数行目だけと偶数行目だけでグリッドを再編成することを考えましょう。ここで便宜上奇数行目だけを使ったグリッドをA、偶数行目だけのグリッドをBとします。まずはAについて考えます。Aは左上の値が1で固定され、右下の値もO(1)で求められることに気づけます。
具体的に言うと、Aは1行増えるごとに2M増えて、1列増えるごとに2増加しています。あとは矩形区間の大きさから、右下の値を求めることができます。ここまでできれば、もうほとんど終わりです。AもBもグリッドは等差数列の集合なので、グリッド全体の和は、グリッドの平均値×要素数の式で求められます。Bに関しては、Aとほぼ変わりないですが、左上の値が1の右斜め下の要素になる、すなわちM+2になることに注意すれば、処理を共通化できます。
実装に関しては、コードを見ながら説明します。まずはコードです。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,q;
cin >> n >> m >> q;
auto sumHelper = [&](int x, int y, int val) -> mint {
//再作成したグリッドの右下の値を求める
mint last = (mint)val+((mint)2*m*(x-1))+(mint)(2*(y-1));
//再作成したグリッドの平均
mint ave = (val+last)/2;
//再作成したグリッドの合計値
mint res = ave * x * y;
return res;
};
auto sum = [&](int x, int y) -> mint {
mint res;
//奇数行目
res += sumHelper((x+1)/2, (y+1)/2,1);
//偶数行目
res += sumHelper(x/2, y/2, m+2);
return res;
};
while(q--) {
int a,b,c,d;
cin >> a >> b >> c >> d;
mint ans;
ans += sum(b,d);
ans -= sum(a-1,d);
ans -= sum(b,c-1);
ans += sum(a-1,c-1);
cout << ans.val() << endl;
}
}
main関数の中で二次元累積和をやっています。sumの中でsumHelperを読んで、奇数行目と偶数行目の処理を共通化しています。
sumHelperはグリッドの右下の値を左上の値から求めて、再編成したグリッドの平均値および合計値を計算しています。
当然公式解説のsnukeさんが書いたコードを参考にしているので、その辺はご愛嬌で...
計算量はO(Q)です。これでACできました。
【終わりに】
「性質の違いを見抜いて複雑な問題を背反に簡単な問題に分ける」と言う思考プロセスをスムーズに踏めるようになりたいですね。第3回swapコンの振り返りをすると、しょーもないミスをして10分時間を食ったのは勿体無かったですね。あと、僕の癖としてWAが出た時に焦って、少しだけ直して衝動的に提出する癖があるので、そこを治したいです。無駄にもう1ペナ食うのは馬鹿すぎます。まぁ一応5完なので、復習はできているとしたいですが、さらに上を目指せるように頑張ります。今日はここまでにします。swapコンへの参加、お待ちしております。それでは！