torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 744, Division 1, Level 1 (Division 2, Level 3), ModularQuadrant

問題概要

 2 次元空間の第一象限(ちゃんと言うと,$\{ ( x, y ) \mid x, y \in \mathbb Z, x \geq 0, y \geq 0 \}$)を考える.これらの点の内,$c_1 \leq x \leq c_2, r_1 \leq y \leq r_2$ を満たす点 $( x, y )$ について,$\max( x, y ) \bmod 3$ の和を求めよ.

解法

 区間を扱いやすくするため,半開区間で考えることにして,以降,$x_1 := c_1, y_1 := r_1, x_2 := c_2 + 1, y_2 := r_2 + 1$ とします.また,$1$ 次元区間を拡張して $2$ 次元(半開)区間を $[ ( a_1, b_1 ), ( a_2, b_2 ) ) := [ a_1, a_2 ) \times [ b_1, b_2 )$ と書きます($X$ 軸,$Y$ 軸のそれぞれについて別々に区間を考えてから共通部分をとったものです).
 問題が問うているのは $[ ( x_1, y_1 ), ( x_2, y_2 ) )$ に関する和ですが,いわゆる $2$ 次元累積和のようにすることで,この問題は $[ ( 0, 0 ), ( x, y ) )$ についての問題に帰着できます.つまり,ある区間に関する答えを求める関数を $S : \mathbb Z ^2 \times \mathbb Z ^2 \mapsto \mathbb Z$ とすると,$$S( [ ( x_1, y_1 ), ( x_2, y_2 ) ) = S( [ ( 0, 0 ), x_2, y_2 ) - S( [ ( 0, 0, x_1, y_2 ) ) - S( [ ( 0, 0, ), ( x_2, y_1 ) ) + S( [ ( 0, 0 ), ( x_1, y_1 ) )$$ で求められます.この式のお気持ちは WUPC 2012 の F 問題の解説(58 ページ目から) に投げます.

$[ ( 0, 0 ), ( x, y ) )$ の場合

 対象の区間が $[ ( 0, 0 ), ( x, y ) )$ の形で書ける場合について考えます.このとき,原点付近の様子を図示してみると,

0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
1 1 2 0 1 2 0 1 2 0 1 2 0 1 2
2 2 2 0 1 2 0 1 2 0 1 2 0 1 2
0 0 0 0 1 2 0 1 2 0 1 2 0 1 2
1 1 1 1 1 2 0 1 2 0 1 2 0 1 2
2 2 2 2 2 2 0 1 2 0 1 2 0 1 2
0 0 0 0 0 0 0 1 2 0 1 2 0 1 2
1 1 1 1 1 1 1 1 2 0 1 2 0 1 2

のようになっています($Y$ 軸を下向きにとっています).この図をぐっと睨むと,原点を含む(極大な)正方形の領域と,それ以外の部分についてそれぞれ特徴的なパターンが視えてきます.つまり,

  • 原点を含む正方形の領域 : 原点からのマンハッタン距離ごとに $0, 1, 2$ を並べたパターン
  • それ以外の部分 : $0, 1, 2$ からなる「縞」模様

です.任意の $( x, y )$ について,対角線に関する対称性から,一般性を損なわずに $y \leq x$ と仮定できるので,以降そのようにします.ちなみに,上で図示したのは $y = 8, x = 15$ の場合です(半開区間であることに注意).このように分割すると,それぞれのパターンごとに別々に答えを求めてから足し合わせることで答えを求めることができます.つまり,$$S( [ ( 0, 0 ), ( x, y ) ) = S( [ ( 0, 0 ), ( y, y ) ] ) + S( [ ( 0, y ), ( x, y ) )$$ です.

原点を含む正方形の領域について

 この部分については,空間を $3 \times 3$ のブロックに分割すると見通しがよくなります.図示すると,

0 1 2 | 0 1 2 | 0 1
1 1 2 | 0 1 2 | 0 1
2 2 2 | 0 1 2 | 0 1
------+-------+----
0 0 0 | 0 1 2 | 0 1
1 1 1 | 1 1 2 | 0 1
2 2 2 | 2 2 2 | 0 1
------+-------+----
0 0 0 | 0 0 0 | 0 1
1 1 1 | 1 1 1 | 1 1

みたいな感じです.これは,対角線を含むブロックとそれ以外に分けて考えることができます.
 着目している正方形領域に完全に含まれているブロックについて,対角線を含むブロックの個数は $\lfloor \frac y 3 \rfloor$ *1で求めることができて,ブロック内の和は $13$ です.それ以外のブロックは,$\lfloor \frac y 3 \rfloor^2$ から対角線を含むブロックの個数を引くことで求められて,それぞれのブロック内の和は $9$ です.なので,あとは算数をすれば和を求めることができます.
 着目領域に部分的に含まれる場合については,$1$ が並んでいる部分だけを処理すればいいのは,ちょっと考えると分かります*2.このようなケースは $y \bmod 3 = 2$ のときに発生して,このときに足される $1$ の個数は $y^2 - 1$ です.
 あとは足すだけで求まります.

原点を含む正方形領域の外側について

 この領域は,$0, 1, 2, 0, 1, 2, \dots$ という列を $y$ 個並べたものと考えることができます.なので,$1$ 次元で和を求めてから $y$ 倍すればよいです.$1$ 次元の場合,$0, 1, 2, 0, 1, 2, \dots$ について,$[ 0, x )$ に関する和を求められれば,累積和のテクニックと同様に答えが求まります.上で述べた正方形領域に含まれる部分はプラスとマイナスでキャンセルされるので気にしなくてよいです.
 $0, 1, 2, 0, 1, 2, \dots x - 1$ の和も $3$ つずつのブロックに分けると考えやすくて,$0, 1, 2$ の並びが $\lfloor \frac x 3 \rfloor$ 個あって,その和は $3$ です.また,$x \bmod 3 = 2$ のときに,ブロックに分けられない $1$ が $1$ つあります.
 これで,あとは足して $y$ 倍するだけです.

まとめと解析

 解法をまとめると,

  1. 原点を含む正方形の領域と,それ以外の領域に分ける
    1. 原点を含む部分について,$3 \times 3$ のブロックに分けてそれぞれ和を求める
    2. それ以外の部分については,$1$ 次元と見做して $3$ つずつの塊に分けて和を求めてから $y$ 倍して求める
  2. 1.1, 1.2 を足す

という流れになります.
 どのステップについても定数回の四則演算と剰余で計算ができるので,計算量としては $O( 1 )$ 時間となります.

コード

using LL = long long;

class ModularQuadrant
{
public:
	LL sum( int r1, int r2, int c1, int c2 )
	{
		++r2, ++c2; // make input half open segment
		return solve( r2, c2 ) - solve( r1, c2 ) - solve( r2, c1 ) + solve( r1, c1 );
	}

	LL solve( int y, int x )
	{
		if ( x < y )
		{
			swap( y, x );
		}

		LL res = 0;

		{
			// { 0 1 2 \\ 1 1 2 \\ 2 2 2 } on diagonal
			const LL diagonals = y / 3;
			res += diagonals * 13;

			// { 0 1 2 \\ 0 1 2 \\ 0 1 2 } ( or, its tranpose ) on other blocks
			const LL blocks = LL( y / 3 ) * ( y / 3 ) - diagonals;
			res += blocks * 9;

			if ( y - diagonals * 3 == 2 )
			{
				res += y * 2 - 1;
			}
		}

		res += ( solve1d( x ) - solve1d( y ) ) * y;

		return res;
	}

	LL solve1d( LL x )
	{
		LL res = 0;

		res += x / 3 * 3;

		if ( x % 3 == 2 )
		{
			++res;
		}

		return res;
	}
};

*1:ガウス記号 : 切り下げ

*2:$0$ は足しても意味がなくて,$2$ が足せるならブロックが完全に含まれるので