torus711 のアレ

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

TopCoder SRM 603, Division 2, Level 1 : MiddleCode

概要

 文字列 s に対し、次のアルゴリズムを適用する。得られる t を求めよ

  1. t := 空文字列とする
  2. s が空でない間、次の処理を繰り返す
    1. s の長さが奇数なら、中央の一文字を t の末尾に付け足して、その文字を s から削除する
    2. s の長さが偶数なら、中央の隣接する二文字の内小さい方を t の末尾に付け足して、その文字を s から削除する

解法

 問題文に記述された通りのアルゴリズムを実装することで解くことができます。再帰で書くとカッコ良くなります。

コード

class MiddleCode
{
public:
	string encode( string s )
	{
		const int L = s.size();

		if ( L <= 0 )
		{
			return "";
		}

		int pos = L / 2;
		if ( !( L % 2 ) )
		{
			const int p1 = L / 2, p2 = p1 - 1;
			pos = s[ p1 ] < s[ p2 ] ? p1 : p2;
		}

		const string res = string( 1, s[ pos ] );
		return res + encode( s.erase( pos, 1 ) );
	}
};