Google Code Jam 2022 Round 1B : B. Controlled Inflation

Round1とはいえ、2問目の割には簡単？
https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000accfdb

問題

変数xの初期値は0である。
ここで、N個の整数列が与えられる。各整数列はP個の値を持つ。

1つずつ整数列を処理して行くことを考える。
xに対し値を1ずつ加減算していき、今処理中の数列中の値について、xが全要素に対する値に1度でも到達したタイミングで、その処理を終えることができ、次の数列に処理を移す。

xの加減算の順番を任意に選べるとき、全整数列を処理し終わるまでにかかるxの加減算回数の総数の最小値を求めよ。

解法

各数列、最大値と最小値だけ考えればよい。
先にどちらに到達し、次にどちらに到達するかを総当たりして最小値を求めて行こう。

int N,P;
int X[1010][1010];

ll from[2];
ll S[2],T[2];
ll to[2];


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>P;
	S[0]=S[1]=0;
	from[0]=from[1]=0;
	FOR(y,N) {
		T[0]=1LL<<60;
		T[1]=0;
		FOR(x,P) {
			cin>>i;
			T[0]=min(T[0],(ll)i);
			T[1]=max(T[1],(ll)i);
		}
		
		to[0]=min(from[0]+abs(S[0]-T[1])+abs(T[1]-T[0]),from[1]+abs(S[1]-T[1])+abs(T[1]-T[0]));
		to[1]=min(from[0]+abs(S[0]-T[0])+abs(T[1]-T[0]),from[1]+abs(S[1]-T[0])+abs(T[1]-T[0]));
		swap(from,to);
		swap(S,T);
	}
	
	
	cout<<"Case #"<<_loop<<": "<<min(from[0],from[1])<<endl;
}

まとめ

1AのBよりだいぶ簡単と思ったけど、AC数は倍は離れてないんだな。