ARC101 C問題 Candles

問題

C - Candles

解法

自分はひたすらどツボにハマった問題。
初期位置が与えられる配列のindexのどの箇所になるか考え、
そこからプラス・マイナスどちらに行くときも折り返すのは最悪1回のみと考えられる。

そして、折り返す位置さえ決まれば、どのろうそくにアクセスするのかは計算可能。
そのため、折り返す場合、折り返さない場合で場合分けを行い
折り返さない場合：初期位置から一番遠い箇所へのアクセスにかかる時間
折り返す場合：(初期位置から折り返す位置までのアクセスにかかる時間) +折り返した位置から最後にアクセスする場所までにかかる時間
を全探索し、出力する。

アクセスにかかる時間は単純にスタート位置からゴール位置までの距離のため、O(1)で計算できる。
決して間の位置までにかかるアクセス時間を足していくなんてことはしてはいけない。(自分はこれをfor文で回すような実装を最初に行いO(n)になりTLEで死んだ)

#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG 0
#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define VIN(VECTOR,n)\
REP(CNT,n){\
	lli TMP;\
	cin>>TMP;\
	VECTOR.push_back(TMP);\
}
 
lli zettai(lli a){
	if(a>=0)return a;
	else return -a;
}
 
lli minAB(lli a,lli b){
	if(a>=b)return b;
	else return a;
}
 
int main(){
 
	lli n,k;
	lli *x;
 
	cin>>n>>k;
	x = new lli[n];
	REP(i,n){
		cin>>x[i];
	}
	lli ans = 223372036854775807;
	for(lli i=0;i<n-k+1;i++){
		lli now;
		if(x[i]<0 && x[i+k-1] < 0){//両方マイナスパターン
			now = zettai(x[i]);
		}
		else if(x[i]<0 && x[i+k-1]>=0){//片方マイナス片方プラスパターン
			now = minAB(zettai(2*x[i])+zettai(x[i+k-1]),zettai(x[i])+zettai(2*x[i+k-1]));
		}
		else{//両方プラスパターン
			now = zettai(x[i+k-1]);
		}
		if(ans>=now)ans=now;
	}
	cout<<ans<<endl;
 
	return 0;
 
}