SRM 147 DIV2 600

問題を読む為の英単語

単語	意味
male	男
fimale	女
direction	方向
arrange	配列する

問題概要

入力：男の人の数、女の人の数、削除パターンK
出力：男女の並び順
男女の並び順を作る。男女の並びはサークルになっている。
開始位置(先頭)から始めて、K番目の人をサークルから除外していく。
女の人の数分除外したとき、すべて男性(女性無し)となるような
並び順を出力せよ。

例示

5
3
2
Returns: "MFMFMFMM"

5
5
3
Returns: "MFFMMFFMFM"

回答コード(C#)

class PeopleCircle
{
	public string order(int numMales, int numFemales, int K)
	{
		int size = numMales + numFemales;
		int pivod = 0;
		char[] circle = new char[size];
		string ret = "";

		//Initialize
		for(int i=0; i<size; i++){
			circle [i] = 'M';
		}

		for (int i = 0; i < numFemales; i++) {
			for (int j = 0; j < (K-1); j++) {
				pivod = (pivod + 1) % size;
				while (circle [pivod] != 'M') {
					pivod = (pivod + 1) % size;
				}
			}
			circle [pivod] = 'F';
			while (circle [pivod] != 'M') {
				pivod = (pivod + 1) % size;
			}
		}

		for(int i=0; i<size; i++){
			ret += circle [i].ToString ();
		}
		return ret;
	}
}

ひっかかったところ。

ラウンドが進むにつれ、女性が居る場所はカウントしないようにしなければならない。
K=1000のような大きな数字の場合、何度もサークルを回ることになるが、その場合女性をカウントしてはいけなかった。
女性が格納されている配列であることが保証された状態でインクリメントできていなかった。

他の人の回答

あらかじめ、int型のキュー領域と、回答用の配列領域を確保し、
int型のキューには０〜人数の整数値を格納しておく。
回答用の配列領域は'M'で初期化しておく。
そして以下(Java)を実行

for(int i=0; i<numFemales; i++){
   for(int j=0; j<K-1; j++)
      q.add(p.poll());
   ans[q.poll()]='F';
}

K回まわす場合は、int型のキュー領域を
「Dequeue」▶︎ 「Enqueue」を繰り返す。
K回終わったら、int型のキュー領域を「Dequeue」し、
その値が示す回答配列に'F'を入れる。

すごいところは、int型のキュー領域は、常に'M'だけのキューになっており、
K回まわす場合に、'F'であるかを意識しないことである。
ぐぬぬ。