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

torus711 のアレ

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

Codeforces #274, Division 1, B ( Division 2, D ) : Long Jumps

問題概要

 特殊な定規で 2 つの長さ x, y を測りたい。定規の全長は l であり、目盛りは n 個ある。i 番目の目盛りの位置は端から a_i のところであり、a_0 = 0, a_{ n - 1 } = l である。この定規である長さ b を「測れる」とは、距離が丁度 b だけ離れた 2 つの目盛りが存在することを言う。
 x, y を測ることができない場合、目盛りを書き足すことによって x, y を測れるようにする。書き足さなければならない目盛りの数の最小値を求め、そのときに目盛りを書き足す位置を全て出力せよ。解が複数ある場合はどれを出力してもよい。

解法

 まず、測定の起点を定規の端にできるので、書き足さなければならない目盛りの数は高々 2 です。また、x, y に関して、a_j - a_i = x ( j < i ) となる i, j が存在すれば x を測るために目盛りを書き足す必要はありません。y についても同様のことが言えます。
 さて、x の為に目盛りを書き足す必要がある場合、その位置の候補は a_i \pm x となる位置です(定規の全長から飛び出さないように注意)。y についても同様に候補を求め、共通する位置があればその点に目盛りを書くことで x, y の両方を測ることができるようになります。そうでない場合は 2 箇所書く必要があるので、適当に 1 点ずつ選んで目盛りを書きます。まとめると、

  • x, y のいずれも初期状態では測れない
    • x, y それぞれを測れる用にするために目盛りを書く位置に共通する点がある
      • →共通 1 点に目盛りを書く
    • 共通する点は無い
      • →適当に 1 点ずつ選んで 2 箇所に目盛りを書く
  • x, y の片方は初期状態で測れる
    • →測れない方を測れるするようにする位置に目盛りを 1 つ書く
  • それ以外
    • →何もしなくてよい

となります。

コード

using VI = vector<int>; using VVI = vector<VI>;

template < typename T > inline void input_n( vector< T > &out ) { copy_n( istream_iterator< T >( cin ), out.size(), out.begin() ); };

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

#define PB( n ) push_back( n )

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

	int n, l, x, y;
	cin >> n >> l >> x >> y;

	VI as( n );
	input_n< int >( as );

	VI xy( { x, y } );
	VVI candidate( 2 );
	REP( i, 0, 2 )
	{
		const int t = xy[i];

		FOR( a, as )
		{
			if ( 0 <= a - t )
			{
				if ( !binary_search( ALL( as ), a - t ) )
				{
					candidate[i].PB( a - t );
				}
				else
				{
					candidate[i].clear();
					break;
				}
			}
			if ( a + t <= l )
			{
				if ( !binary_search( ALL( as ), a + t ) )
				{
					candidate[i].PB( a + t );
				}
				else
				{
					candidate[i].clear();
					break;
				}
			}
		}
	}
	for_each( ALL( candidate ), []( VI &ary ){ sort( ALL( ary ) ); } );

	if ( all_of( ALL( candidate ), mem_fn( &VI::empty ) ) )
	{
		cout << 0 << endl;
	}
	else if ( none_of( ALL( candidate ), mem_fn( &VI::empty ) ) )
	{
		VI intersection;
		set_intersection( ALL( candidate[0] ), ALL( candidate[1] ), back_inserter( intersection ) );

		if ( intersection.empty() )
		{
			cout << 2 << endl;
			REP( i, 0, 2 )
			{
				cout << ( i ? " " : "" ) << candidate[i][0];
			}
			cout << endl;
		}
		else
		{
			cout << 1 << endl;
			cout << intersection[0] << endl;
		}
	}
	else
	{
		cout << 1 << endl;
		FOR( ary, candidate )
		{
			if ( !ary.empty() )
			{
				cout << ary[0] << endl;
			}
		}
	}

	return 0;
}