|
uchinyan |
|
#25128：
LENさん、興味深く読ませて頂きました。お見事です。 スモークマンさん、この解法ならば、徴収を開始する人を特定できそうです。その意味で、私の解法より優れていると思います。 ただ、ちょっと細かい点を補足しておいた方がいいかもしれません。 ＞#25112 ＞500円所有者＝”+1”， ＞1000円所有者＝”-1”， ＞輪の任意の開始位置をi=0とおき（f(0)=0)、そこから時計回りに進むとき、 ＞所有者に遭うごとに、iを1インクリメントし、 ここらは、i を、受付さんが徴収を開始した後の状態、と考えた方がいいように思います。 i = 0 は、徴収を開始する前の状態、いわゆる初期状態ですね、i = k は、k 番目の人から徴収した後の状態、です。 ＞500円所有者ならば、f(i)=f(i-1)+1, ＞1000円所有者ならば、f(i)=f(i-1)-1とする。 ＞開始位置に戻ると、f(2n)=0=f(0)になる。 「開始位置に戻ると」は、「徴収をし終わった状態では」、ということです。 ＞上の関数f(i)は、iの初期値0と終値間2nにおいて、最大値と最小値をもつ。 これは、f(i) が有限個の整数の集合なので、明らか。 ＞よって、f(i)が最小になる位置から始めれば、 正確には、「f(i)が最小になる状態の次の人から始めれば、」かな。 要するに、f(m) = 最小値 として、m+1 から開始する、ということです。 ＞釣り銭が不足することはありません。 すべての i に対して f(i) >= 最小値 = f(m)、なので、g(i) = f(i+m) - f(m) とすれば、g(0) = 0 で、g(i) >= 0 です。 なお、時計回りか反時計回りかは、問題の本質とは関係ないですね。 徴収を開始する人を特定するには、与えられた実際の並びに対して、f(i) を計算して最小値を求めればいいわけです。 最小値を与える i が一意でない場合もありますが、その場合にはそのどれをとっても OK です。 ただし、f(i) の取り方に、取り敢えずどの人から開始するかの任意性があります。 しかしこの任意性は、f(0) = 0 の与え方のズレだけなので、グラフ的にいうと軸方向の平行移動だけなので、座標の入れ方の任意性に過ぎず、 どの f を用いても、最小値の特定は同じで、それに対応する人の特定も、座標のズレを考慮すれば、同じです。 要は、a が500玉を持っていることを [a,+] と書くとして、[a,+], [b,-], [c,-], [d,+], [e,-], [f,+] となっていたとして、 a から始めると、f(i) は、0 (= f(0)), 1, 0, -1, 0, -1, 0 なので、最小値を与えるのは i = 3 or 5 ですが、これは、c 又は e で、 b から始めると、f(i) は、0 (= f(0)), -1, -2, -1, -2, -1, 0 なので、最小値を与えるのは i = 2 or 4 ですが、これは、やはり、c 又は e です。 つまり、どちらで計算しても、開始する人は、d 又は f に特定できます。 これでうまくいくのでは？ |
|
ネコの住む家
5月21日（土） 11:50:41
MAIL:uchi@sco.bekkoame.ne.jp 25129 |