■

去年からアルゴリズムの勉強のためにtopcoderのSRMをたまに解いたり、時間が合えばちょこちょこ参加したりしていました。 今回解いた内容を自分用に記録。

今回解いたのはSRM711 DIV2 250 Easy. 問題文は、「４本の棒の長さについてそれぞれ自然数a,b,c,dが与えられ、1コインを棒製造店に持っていくと1本の棒の長さを-1か+1することが可能である。（この操作は何度でも可能）4本の棒を使って正方形を作るには（つまり4本の棒の長さを同じにする）、何コイン必要か？ただし棒の長さは正であることに注意」といった内容。

※ちなみにtopcoderの問題文は全て英語だが、英語が読めない人（私もです）も、最近のgoogle翻訳では全コピペで十分内容を読み取ることができるので、取り組んでみたいけど英語だからちょっと…と思っている人は最初はそれで問題ないと思います。Let’s try topcoder.

今回の問題、簡単だとタカをくくっていたら、数学の問題として間違えていた…この問題のポイントは、「４つの値のうち、どの値に揃えるか」です。

４つの値の平均値 ( ( a + b + c + d ) / 4 ) の切り捨てor切り上げのいずれかに揃えるのが最小と考え解いたが、これが間違いでした。

（↑図１）

図１のような場合、平均値mに揃えると以下のようになります。（図の平均値の場所はテキトウだけど、とにかくbとcの間の場合）

棒の長さの増減のを行なった回数（最終的なコインの枚数）をsとおくと、a<b<c<dとして、a=0とすると（4値すべてを-aすればよい）、平均値に寄せた場合は、図１よりs = d + (c - b) になります。

（↑図２）

これは平均値でなくともbc間であれば、b,cいずれかの値に揃えた場合（例えばbに揃えた場合、図２）でもs = d + (c - b)になることがわかります。

（↑図３）

ですが図３のようにbc間以外の点に揃えようとすると、d + (c - b) > sとなるのがわかります。揃える値mはb<=m<=cの範囲である必要があるため、b or c（つまり中央値）に揃えるのがコード的にシンプルです。以下、一応サンプルコード。

~~~

coding:utf-8

import numpy as np

class SquareMaking():

def init(self): self = self

def getMinimalPrice(self, a, b, c, d): list_answer = [] abcd = [a, b, c, d] data = np.array(abcd) med = np.median(data) answer = (abs(a - med) + abs(b - med) + abs(c - med) + abs(d - med)) return int(answer)

S = SquareMaking() a = 705451 b = 751563 c = 608515 d = 994713

answer = S.getMinimalPrice(a, b, c, d) print answer

~~~

numpyのmedianで中央値を求めて、abs()で４値と中央値との差の絶対値を全て足し合わせているだけの単純なロジックになります。

直感で平均値という考えが甘かったです。図にすれば一目瞭然でした。。

Easyは確実に解けるように、これからはミスに気をつけよう