C# と VB.NET の質問掲示板

■No62879 (堀江伸一 さん) に返信

2分割
a | b  => a= b
  p1

3分割
a | b | c => b = a+c = N/2
  p2  p3        p2,p3はp1ではない(p1による２分割が最小であることに矛盾する
　　　　　　　　　　　　　　　　　というかp1は中央なので２分割以外ありえない)


4分割
a | b | c | d   => a+c=b+d=N/2
  p4  p5  p6      p4,p5,p6はp1ではない、かつ２点以上がp2,p3と一致することはない(同様)


たぶんこんな感じのことが成立すると思われる。検証してません。

上記の考え方をそのまま実装してみたところコード実行速度5位メモリ使用量低で正答できました。
ここから先の高速化とかはあまり考えてないので。
もし高速化できそうなところがあったらご指摘ください。


#include<stdio.h>
#include<string.h>

const int A=0;//二人をAさんBさんとする
const int B=1;

void setData(int n){
	int memo[2][5002];//[次にもらうのがAさん＝0　Bさん＝1][Aさんがここまででもらった個数]=最小切断時間
	int next[2][5002];//次の切断箇所の検討
	int cutTimes[10001];//切断時間
	int cutTime,herf=n/2,nowTime;
	int up;

	for(int i=0;i<n-1;i++)scanf("%d",&cutTimes[i]);
	
	memset(memo,127,sizeof(memo));//足される切断秒数は10000なのでオーバーフローしない
	memo[A][1]=0;//計算しやすいようAさんが1個目を取得した状態から始める
	
	for(int turn=0;turn<n-1;turn++){
		memset(next,127,sizeof(next));//ダミーデータ
		cutTime=cutTimes[turn];//切断箇所をずらしていく

		up=turn+1>herf?herf:turn+1;//上限
		for(int k=1;k<=up;k++){
			nowTime=memo[A][k];//Aさん
			
			//切断せずAさんが続けてもらう
			next[A][k+1]=nowTime;
			
			//切断して次はBさんがもらう
			next[B][k]=nowTime+cutTime;
		}
		for(int k=1;k<=up;k++){
			//Bさんの番
			nowTime=memo[B][k];
			//Bさんが続けてもらう
			next[B][k]=next[B][k]>nowTime?nowTime:next[B][k];
			
			//Aさんがもらう
			nowTime+=cutTime;
			next[A][k+1]=next[A][k+1]>nowTime?nowTime:next[A][k+1];
		}
		memcpy(memo,next,sizeof(next));
	}
	nowTime=memo[A][herf]>memo[B][herf]?memo[B][herf]:memo[A][herf];
	
	printf("%d\n",nowTime);
}

int main(){
	int n;
	scanf("%d",&n);
	setData(n);
	while(scanf("%d",&n)!=EOF){
	}
}