|
uchinyan |
|
(ごめんなさい。最初の説明はゴチャゴチャしていたので，皆さんのも参考にして整理し書き直しました。)
はい，こんにちは。さて，今回の問題は．．． これは直感的に解き方が分かる問題かなぁ。算チャレとしては標準的，ただし常連さんには易，という気がします。 大体こんな感じで。 差の和が最大になるには，できるだけ大きな番号とできるだけ小さな番号とが隣り合えばいいです。 こう考えると一例として次が考えられます。 09 12 07 14 05 16 03 18 01 19 02 17 04 15 06 13 08 11 10 (左端の 09 とつながって円になる。)， この並びの差の和は， (19 - 1) + (18 - 1) + (19 - 2) + (17 - 2) + + (18 - 3) + (16 - 3) + (17 - 4) + (15 - 4) + (16 - 5) + (14 - 5) + (15 - 6) + (13 - 6) + (14 - 7) + (12 - 7) + (13 - 8) + (11 - 8) + (12 - 9) + (10 - 9) + (11 - 10) + (10 - 9) = ((19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11) * 2 + 10) - ((1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) * 2 + 10) = (19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11) * 2 - (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) * 2 = ((19 - 9) + (18 - 8) + (17 - 7) + (16 - 6) + (15 - 5) + (14 - 4) + (13 - 3) + (12 - 2) + (11 - 1)) * 2 = 10 * 9 * 2 = 180， この式の２行目と３行目から分かるように，これが最大値で，中央値の 10 は結果に影響しません。 そこで，中央値の 10 より，大きい数を大，小さい数を小，として， 中央値の 10 以外を 大小大小… の順に自由に並べて中央値の 10 を適当に挟み込むという並べ方， で，最大値 180 になる，と分かります。 つまり，差の和の最大値は 180，になります。 ちなみに，01 〜 18 ならば，同様にして， 09 11 07 13 05 15 03 17 01 18 02 16 04 14 06 12 08 10 (左端の 09 とつながって円になる。)， この並びの差の和が， (18 + 17 + 16 + 15 + 14 + 13 + 12 + 11 + 10) * 2 - (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) * 2， と書けることに注意すると，10 〜 18 を大，1 〜 9 を小，として， 大小大小… の順に自由に並べるという並べ方， で，差の和は最大値になる，と分かります。 以上の話は一般化も容易で，1 〜 n の場合， n が奇数のときは (n + 1)/2 * (n - 1)/2 * 2 = (n^2 - 1)/2， n が偶数のときは n/2 * n/2 * 2 = n^2/2， になります。いわゆるガウス記号を使えばまとめて，[n^2/2]，ですね。 |
|
6月24日（金） 12:57:58
44676 |