torus711 のアレ

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

SRM 562, Division 1, Level 1 : PastingPaintingDivOne

概要

赤・緑・青・透過色の四色を扱えるペイントソフトがある。
このペイントソフトはクリップボード機能を備え、任意の位置にクリップボードの内容をペーストできる。
赤・緑・青を貼り付ける場合は上書きされるが、透過色を貼り付ける場合は元の色が残る。
今、クリップボードには既にデータが入っていて、T 回ペースト操作をする。
i 回目のペースト操作では、左上の座標は ( i, i ) である。
T 回の操作が終わった後の赤・緑・青のピクセル数を答えよ。

解法

透過色の部分に何色が埋まるかは、右下方向に深さ T だけ見ていけば分かります。
左と上の辺については適当に出現回数を計算して足します。
(表現しにくい……)

コード

typedef long long LL;
typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

typedef vector< long long > VLL;

class PastingPaintingDivOne
{
public:
	int H, W;
	VS clipboard;

	vector<long long> countColors(vector <string> clipboard, int T)
	{
		H = clipboard.size(), W = clipboard[0].size();
		this -> clipboard = clipboard;

		VLL res( 3, 0 );

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				int c, t;

				if ( i == 0 || j == 0 )
				{
					c = toLD( T, 0, i, j, t );

					if ( c == -1 )
					{
						continue;
					}

					res[c] += T - t - 1;
				}

				c = toLD( T, 0, i, j, t );

				if ( c == -1 )
				{
					continue;
				}

				res[c]++;
			}
		}

		return res;
	}

	LL toLD( int T, int t, int i, int j, int &resT )
	{
		if ( H <= i || W <= j || T <= t )
		{
			return -1;
		}

		if ( clipboard[i][j] == '.' )
		{
			return toLD( T, t + 1, i + 1, j + 1, resT );
		}

		resT = t;
		return ctoidx( clipboard[i][j] );
	}

	int ctoidx( char c )
	{
		switch ( c )
		{
			case 'R':
				return 0;
			case 'G':
				return 1;
			case 'B':
				return 2;
		}
	}
};