torus711 のアレ

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

Codeforces #223, Division 2, A : Sereja and Dima

概要

 相異なる数が書かれた N 枚のカードを使った、以下のようなゲームをする。

  • プレイヤーは二人で、交互に動く
  • プレイヤーは各ターン、列のどちらかの端にあるカードを一枚取得できる
  • カードが無くなったら終了
  • 取得したカードに書かれた数の総和が得点

今、二人はそのターン複数の選択肢がある場合は常に大きい方を取得する戦略でゲームをする。最終結果を求めよ。

解法

 問題文に書かれた手続きをそのまま実装することで解くことができます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	deque<int> que( ALL( as ) );

	VI res( 2, 0 );
	REP( i, 0, n )
	{
		if ( que.front() < que.back() )
		{
			res[ i % 2 ] += que.back();
			que.pop_back();
		}
		else
		{
			res[ i % 2 ] += que.front();
			que.pop_front();
		}
	}

	cout << res[0] << ' ' << res[1] << endl;

	return 0;
}