AtCoder が提供しているABC（AtCoder Beginner Contest）269 のF問題をC++で解いてみました。ABC269は、2022年9月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Numbered Checker（Difficulty : 1601）
問題はリンク先をご覧ください。
等差数列の一般項と和の公式を使います。AtCoder Problems による Difficulty は、1601 でした。
解答案
初項 $a_1$、等差 $d$ の等差数列 $a_n$ の一般項は以下となります。
$$a_n = a_1 + (n\;-\;1) d$$
初項 $a_1$ から末項 $a_n$ までの和は以下となります。
$$\sum_{i=1}^n a_i = n \times (a_1 + a_n) / 2$$
これら二つの公式を使って問題を解きます。
C++ プログラム例（ABC269F）
奇数行と偶数行の処理を分けます。
まず、奇数行の処理を解説します。
- c が偶数なら1を加えます。d が偶数なら1を引きます。
- 1行目の0以外の数字は、c が初項、d が末項、等差2の等差数列となります。等差数列の和を求めることにより1行目の和を求めることができます。この和を odd_first_row として記憶しておきます（29、30行目）。
- a が偶数なら1を加えます。b が偶数なら1を引きます。a 行目から b 行目までの2行おきに行の和を求めます。
- 行の和は、初項 odd_first_row、等差 $2 \times M \times$ (行に含まれる数の個数) の等差数列の和と考えることができます。 等差数列の一般項の公式から、a 行目と b 行目のそれぞれの和を求めることができます。odd_first と odd_last として記憶しておきます（43、44行目）。
- a 行目から b 行目までの2行おきの行の和を公式で求めます（47行目）。
偶数行の処理もほぼ同じです（49ー75行目）。998244353 の剰余を求めるため、ACLのmodint を使いました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef modint998244353 mint;
int main()
{
ll n, m;
cin >> n >> m;
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
mint result = 0;
mint c1 = (mint)c;
mint d1 = (mint)d;
if (c % 2 == 0) {
++c1;
}
if (d % 2 == 0) {
--d1;
}
mint odd_n = (d1 - c1) / 2 + 1;
mint odd_first_row = odd_n * (c1 + d1) / 2;
mint a1 = (mint)a;
mint b1 = (mint)b;
if (a % 2 == 0) {
++a1;
}
if (b % 2 == 0) {
--b1;
}
mint odd_first_col = (a1 - 1) / 2 + 1;
mint odd_last_col = (b1 - 1) / 2 + 1;
mint col_odd_dif = 2 * (mint)m * odd_n;
mint odd_first = odd_first_row + (odd_first_col - 1) * col_odd_dif;
mint odd_last = odd_first_row + (odd_last_col - 1) * col_odd_dif;
mint odd_col_n = (b1 - a1) / 2 + 1;
result = odd_col_n * (odd_first + odd_last) / 2;
mint c2 = (mint)(c + m);
mint d2 = (mint)(d + m);
if (c % 2 == 1) {
++c2;
}
if (d % 2 == 1) {
--d2;
}
mint even_n = ((d2 - c2) / 2 + 1);
mint even_first_row = even_n * (c2 + d2) / 2;
mint a2 = (mint)a;
mint b2 = (mint)b;
if (a % 2 == 1) {
++a2;
}
if (b % 2 == 1) {
--b2;
}
mint even_first_col = (a2 - 2) / 2 + 1;
mint even_last_col = (b2 - 2) / 2 + 1;
mint col_even_dif = 2 * (mint)m * even_n;
mint even_first = even_first_row + (even_first_col - 1) * col_even_dif;
mint even_last = even_first_row + (even_last_col - 1) * col_even_dif;
mint even_col_n = (b2 - a2) / 2 + 1;
result += even_col_n * (even_first + even_last) / 2;
cout << result.val() << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
今回は、Python のプログラム紹介を省略します。
最後に
高校の等差数列の公式を久しぶりに思い出しました。実装は重たくなりました。いくつかの処理を関数に分ければ、もう少し簡潔に書けるかもしれません。
ABC269から、このブログで問題とプログラム例を紹介しています。当時解けなかった問題も公式解説などを参考にしながら紹介していきます。
