AtCoder Grand Contest 025 C - Interval Game

AtCoder 競技プログラミング

これ難しくないですか

問題

C - Interval Game

感想

本番中B問題で動転しすぎていてちゃんと考察できずに終わってしまった問題。

第一印象で左右に振り回せばよさそうなのはわかりますが、それをどうすればいいのか詰めるのがむつかしそうだなとか考えていました。



さて。gameについて考えていくと。

  • 同じ方向に移動するのは意味がない

ということがわかります。(後者の区間のみを選べばよくなるので)
そのため、やはりジグザグて移動させることになりますが、

  • 高橋君が右に移動するときは必ず区間の左端で、高橋君が左に移動するときは必ず区間の右端で止まる

とかわかりますね。(それ以上動く必要がないので)

そうするとある移動に注目したとき、その距離は
左に移動するときは(移動先の区間のｌ) - (移動元の区間のｒ)
右に移動するときは(移動元の区間のｌ) - (移動先の区間のｒ)
となります。

また各区間について、ｌまたはｒが二回づつ登場するので、移動元移動先関係なしにそれぞれの区間について、ｌを使うかｒを使うかを考えればよさそうです。
ここまで整理できると、ある程度キレイに解けそうです。便宜上、原点を区間として入れときましょう。
(これ実は突飛で微妙な感じするけれど)LRそれぞれについてソートしてあげると上手くいきますね。

原点を入れるのは最初と最後の行動を上手く考慮したいから、ソートするのは距離が大きい順にとっていきたいから試しにやってみる、くらいの気持ちですかね。

同じ区間のｌ、ｒが両方採用される、移動しないでいいはずの区間が採用される時は距離が負の値をとるので、順番に計算していって極大値を出せばよさそう。(これ難しい)

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int main(){
	int n;cin >> n;
	vector<ll> L(n+1);
	vector<ll> R(n+1);
	
	REP(i,n)cin >> L[i] >> R[i];
	
	sort(ALL(R));
	sort(ALL(L),greater<ll>());
	
	DBG(SHOW1d(R,R.size()););
	DBG(SHOW1d(L,L.size()););
	
	ll ans = 0;
	ll tmp = 0;
	REP(i,n+1){
		tmp += 2 *(L[i] - R[i]);
		ans = max(ans,tmp);
	}
	
	cout << ans << endl;
	return 0;
}

これ、シミュレーションしてもできそうだから頑張ればそれでも通せると思いますが、つらそう。