yukicoder : No.2482 Sandglasses

気付いてしまえばすんなり。
https://yukicoder.me/problems/no/2482

問題

N個の砂時計があり、それぞれAB両パーツにある砂の量が与えられる。
各砂時計は以下のようにひっくり返す。

• すべての砂が下のパーツに移動したら、その瞬間にひっくり返す
• 2つの砂時計が、同じ時間にA側のパーツに同じ量の砂がある瞬間があったら、両砂時計を同時にひっくり返す。

時間T経過後の各砂時計のパーツAの砂の量を求めよ。

解法

この動作はいわゆるantである。
2つ目の条件を無視すると、各砂時計は、前者の条件でのみひっくり返るため、時間T後のパーツAの砂の量はO(1)で計算できる。

ここに2つ目の条件を加えると、砂時計同士のパーツAの砂の量の大小関係は変わらないことがわかる。
そこで、1つ目の条件だけ考えて各砂時計のパーツAの砂の量を求めた後、最初のパーツAの砂の量の大小関係に基づき、砂時計の並べ替えを行えばよい。

int N,K,T;
int A[202020];
int B[202020];
int C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>T;
	FOR(i,N) {
		cin>>s;
		A[i]=s=="A";
	}
	vector<pair<int,int>> V;
	FOR(i,N) {
		cin>>B[i];
		V.push_back({B[i],i});
		x=B[i]+(A[i]?-T:T);
		x%=2*K;
		if(x<0) x+=2*K;
		B[i]=(x>K)?(2*K-x):x;
	}
	sort(ALL(V));
	sort(B,B+N);
	FOR(i,N) {
		C[V[i].second]=B[i];
	}
	FOR(i,N) cout<<C[i]<<" ";
	cout<<endl;
	
	
}

まとめ

これはすんなり思いついたね。