kmjp's blog

競技プログラミング参加記です

TopCoder SRM 710 Div1 Easy ReverseMancala

参加者の正答率が非常に低かった今回、何気に一発AC出たので本番参加しておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14544

問題

N個のスロットが円周上に並んでおり、それぞれS[i]個ずつ石が並んでいる。
この状態で、以下のいずれかの処理を任意に繰り返す。

  • 処理A : 空でないスロットを1つ選び、すべての石を回収する。そして時計回りにスロットを回りながら、手持ちが空になるまで1つずつ石をスロットに入れていく。
  • 処理B : 空でないスロットを1つ選ぶ。そこから、スロット内の石を1つ拾い、反時計回りに1つずつ移動する。途中で空のスロットに到達したら、すべての石をそこに入れる。

上記処理を用いて、各スロットの石の個数がT[i]個になるようにせよ。

解法

処理Aと処理Bは逆の処理であることがわかる。
スロットのある状態をUとする。S→Uに処理Aだけで到達可能であり、同様にT→Uも処理Aだけで到達可能とする。
処理Bを用いて、T→Uの手順を逆にたどればU→Tに到達可能である。
よってS→U→Tという遷移が可能となる。

あとは、そのようなUを作ればよいだけである。
実はこの問題はDiv2 Mediumと同じで、ある1個のスロットにすべての石を集めるという手順は容易に求まる。
集める先以外のスロットに対し、処理Aを繰り返すだけでよい。

class ReverseMancala {
	public:
	int N;
	
	vector <int> findMoves(vector <int> S, vector <int> T) {
		int N=S.size();
		vector<int> R,R2;
		int tot=accumulate(ALL(S),0);
		int i;
		
		while(S[0]!=tot) {
			for(i=1;i<N;i++) if(S[i]) {
				R.push_back(i);
				int v=S[i];
				S[i]=0;
				int j=(i+1)%N;
				while(v) S[j]++, v--, j=(j+1)%N;
			}
		}
		
		while(T[0]!=tot) {
			for(i=1;i<N;i++) if(T[i]) {
				R2.push_back((i+T[i])%N+N);
				int v=T[i];
				T[i]=0;
				int j=(i+1)%N;
				while(v) T[j]++, v--, j=(j+1)%N;
			}
		}
		while(R2.size()) R.push_back(R2.back()),R2.pop_back();
		return R;
	}
}

まとめ

450ptのMediumでもよかったかもね。