Problem C. Equal Sums 解き方
実践したソースは このあたり にあります。
問題紹介は こちら です。
以下ネタバレ
個人的には Round 1B の3問の中で一番シンプルな印象を受けました。
十分なメモリと、言語による高速な辞書（連想配列）のサポートがあれば難しくない気がします。（考慮漏れや bad case があるかもしれませんが…）
「全ての組み合せを見つける」とか「合計値が最小の組み合せ」という条件はなく、1組でも見つければよいので、単純にいろんな組み合せを作って合計値を調べていきました。
最初は各々の数字をキーに、その値を連想配列に登録します。
次は2つの数字の組み合せ。合計値をキーに、組み合せを連想配列に登録します。このとき、既に同じキー（合計値）が連想配列にあれば、その組み合せとのペアが「同じ合計値」になります。これが見つかった時点でループを抜けて回答を出力することができます。
同じ合計値が見つからなければ次は3つの数字の組み合せ、その次は4つの数字の組み合せ… という具合に組み合せる数字の個数を増やしていきます。
Analysis にあるように、1012 未満の数字を50個足しても最大で 50×1012。これより 250 の方が大きいので、50個の数字の組み合せパターン数の方が大きくなります（各数字について加える／加えないのどちらかを選択するので 250 通りになります）。つまり、500個の数字のうち任意の50個を取り出して調査すれば必ず同じ合計値になるパターンにたどり着くことができます。言語や環境によっては500個で調べるより有利、、かも?
0 件のコメント:
コメントを投稿