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

torus711 のアレ

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

TopCoder, Single Round Match 642, Division 2, Level 1 : ForgetfulAddition

問題概要

 Alice は,2 つの正整数 a, b からなる数式 a + b をコンピュータに入力しようとしたが,'+' キーが壊れていて数字のみが入力されてしまった.彼女が入力した(数字のみからなる)文字列 expression が与えられる.元の数式 a + b の値として有り得るものの内,最大のものを求めよ.
 |expression| \leq 8

解法

 題意より,expression は,2 つの文字列 S_1, S_2 によって S_1 + S_2 と表されます(ここで演算 + は文字列の連結を表す).このとき,S_1, S_2 のそれぞれが表す整数値の和が,Alice が入力しようとした数式の値になります.
 制約より,expression を 2 つの文字列に分割する方法は高々 7 通りしかありません.従って,expression の分割を全通り試し,そのそれぞれについて数式の値を計算する処理はごく短時間で完了します.従って,この方法で問題を解くことができます.

コード

template < typename T = int > using LIM = numeric_limits< T >;

template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; };

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

class ForgetfulAddition
{
public:
	int minNumber( string expression )
	{
		const int L = expression.size();

		int res = LIM<>::max();
		REP( i, 1, L )
		{
			res = min( res, fromString< int >( expression.substr( 0, i ) ) + fromString< int >( expression.substr( i ) ) );
		}
		return res;
	}
};