yukicoder : No.335 門松宝くじ

年初めは門松列問題だろうと思ってたけど、まさか４問来るとは。
http://yukicoder.me/problems/936

問題

「門松宝くじ」は以下のような宝くじである。

• 宝くじ券の番号は、1～NのPermutationの形で構成されている。
• 宝くじの当選発表では、2つの異なる番号が等確率で自動的に選択される。券の持ち主はあと１つの数字を任意に選択できる。計３つの選択された数値が宝くじ券番号の数列上で門松列を成す並び順であるとき、当選賞金は３値の最大値となる。

M枚の宝くじ券の番号が与えられる。
当選金額の期待値が最大となるのは何枚目の券か。

解法

実際に各宝くじ券の期待値を求めよう。
自動的に選択される2つの番号を総当たりし、それぞれの場合に賞金が最大となる３つ目の値を求めよう。
自動的に選ばれた２値をx,y(xが数列中で前にある)とする。
xの手前にある数値の集合をL、xとyの間にある数値の集合をM、yの後にある数値の集合をRとする(LLLLLxMMMMMyRRRRRみたいな配置)

L,M,Rからそれぞれ賞金額が最高となる３値目をどう選べばよいか考えよう。

• Lから選ぶケース
  • x＜yなら、L中の最大値zがxより大きいならmax(y,z)が候補
  • x＞yなら、L中の最小値zがxより小さいならxが候補
• Mから選ぶケース
  • L中の最大値zがmax(x,y)より大きいならzが候補
  • L中の最小値zがmin(x,y)より小さいならmax(x,y)が候補
• Rから選ぶケース
  • x＞yなら、R中の最大値zがyより大きいならmax(x,z)が候補
  • x＜yなら、R中の最小値zがyより小さいならyが候補

あとはyを少しずつずらしながらL,M,Rを管理しつつ、上の最大値を求めよう。

int N,M;
int A[1010];
ll ma=0;
int best=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		FOR(x,N) cin>>A[x];
		ll tot=0;
		
		FOR(x,N) {
			set<int> L,M,R;
			FOR(y,x) L.insert(A[y]);
			for(y=x+1;y<N;y++) R.insert(A[y]);
			for(y=x+1;y<N;y++) {
				int sc=0;
				
				R.erase(A[y]);
				if(L.size()) {
					if(A[x]<A[y] && *L.rbegin()>A[x]) sc=max(A[y],*L.rbegin());
					if(A[x]>A[y] && *L.begin()<A[x])  sc=max(sc,A[x]);
				}
				if(M.size()) {
					if(*M.rbegin()>max(A[x],A[y]))    sc=max(sc,*M.rbegin());
					if(*M.begin()<min(A[x],A[y]))     sc=max(sc,max(A[x],A[y]));
				}
				if(R.size()) {
					if(A[x]>A[y] && *R.rbegin()>A[y]) sc=max(sc,max(A[x],*R.rbegin()));
					if(A[x]<A[y] && *R.begin()<A[y])  sc=max(sc,A[y]);
				}
				
				tot+=sc;
				M.insert(A[y]);
			}
		}
		
		if(tot>ma) ma=tot,best=i;
	}
	cout<<best<<endl;
}

まとめ

お年玉はありませんか？