読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 656, Division 2, Level 1 : CorruptedMessage

問題概要

 英小文字の内 1 種類の文字からなる文字列 s を送ったが,伝送途中で丁度 k 文字が異なる文字に変わってしまった.sk が与えられるので,元の文字列として考えられるものを 1 つ復元せよ.1 つ以上存在することは保証される.
 |s| \leq 50

解法

 L := |s| とします.
 元の文字列として考えられるのは,1 種類の文字からなる L 文字の文字列です.これは 26 種類しか無いので,簡単に列挙できます.26 種類の候補それぞれに対して妥当性の判定をすることができれば,答えを探すことができます.
 1 種類の文字からなる文字列 t ( |t| = L ) をもってきたとき,t が元の文字列で有り得る場合とは,題意より,t から丁度 k 文字を変更することで s にできる場合です.t が 1 種の文字 c からなることを考えると,s に含まれる,c ではない文字の個数が k に等しい場合であると言えます.言い換えると,s に含まれる c の個数を L から引いた値が k に等しければ,その文字列は元の文字列として妥当なものであると分かります.このことを調べるためには,各文字が s に含まれる個数だけが分かれば十分で,これは予め数えておくことができます.
 s に各文字が含まれる個数を調べることは,文字列を 1 回走査すればできるので,O( L ) 時間です.調べなければならない文字列は高々定数個であり,それぞれの文字列に対する妥当性判定も定数時間なので,この部分は O( 1 ) 時間です.また,return する文字列を生成するところで O( L ) 時間かかります.従って,処理の全体は O( L ) 時間で完了します.

コード

using VI = vector< int >;

#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

class CorruptedMessage
{
public:
	string reconstructMessage( string s, int k )
	{
		int L = SZ( s );

		VI counts( 26 );
		for_each( ALL( s ), [&]( const char c ){ ++counts[ c - 'a' ]; } );

		for ( char c = 'a'; c <= 'z'; ++c )
		{
			if ( L - counts[ c - 'a' ] == k )
			{
				return string( L, c );
			}
		}
		return "";
	}
};