kojingharangの日記

D.

22:59 |

• 1〜Nのカードが順不同でおいてある。
• 任意のカード集合の位置を固定したまま机を叩くと、残りのカードが順不同にシャッフルされる。
• カードを抑える、机をたたく以外のことはできない。
• カードを昇順にソートしたい。
• 平均何回机を叩けばソートできるか？？ただし誤差は 1-e6 以内とする。

• なにこれ

• sample input, output を見ると、２枚のカードを固定しないでシャッフルすると平均２回でソートできるとなっている。ほう。
• 確率を計算しようと試みる。1*1/2 + 2*1/2*1/2 + 3*1/2*1/2*1/2 + ... と無限に足すと、...わかんないけど 2 に近づくようだ。
• では、「任意の２枚を入れ替える操作だけができるとして、初期状態から最小何手でソートされた状態になるか？」という問題を解けばいいんじゃね
• sample output と同じ結果になったので small 提出→incorrect
• ちょっとバグってたので再提出→incorrect

• (.....................)

• 諦める。

• 問題の解説を見たところ、「正しい位置にないカードだけを１回シャッフルすると平均１枚のカードが正しい位置に移動する」という性質が成り立つようで、
• 正しい位置にないカードの枚数に ".000000" を付けて出力すれば正解となるらしい。

（反省点）

• こういう、「サンプルみたいなシンプルなケースで考えてみて、なんか成り立ちそうな性質を思いついて、それをざっくりでもいいから証明してコードを書く」みたいなのが苦手。
• どう反省すべきか不明だが、もっと賢くなれということかorz

（以下、間違ってますが掲載）

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int n;
		int ans=0;
		cin>>n;
		VI d(n);
		REP(i, n)
		{
			cin>>d[i];
		}
		cout<<d<<endl;
		int ans2=0;
		REP(i, n)
		{
			if(i+1!=d[i]) ans2++;
		}
		REP(i, n)
		{
			if(i+1!=d[i])
			{
				int ti=-1;
				FOR(j, i+1, n) { if(d[j]==i+1) { ti=j; break; } }
				swap(d[i], d[ti]);
				ans+=2;
				//cout<<d<<endl;
			}
		}
		//cout<<d<<endl;
		cout<<"Case #"<<t+1<<": "<<ans<<".000000 "<<ans2<<endl;
	}
	return 0;
}

ツイートする