概要
赤・緑・青・透過色の四色を扱えるペイントソフトがある。
このペイントソフトはクリップボード機能を備え、任意の位置にクリップボードの内容をペーストできる。
赤・緑・青を貼り付ける場合は上書きされるが、透過色を貼り付ける場合は元の色が残る。
今、クリップボードには既にデータが入っていて、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; } } };