オーダーを極める思考法：最強最速アルゴリズマー養成講座（2/3 ページ）

[高橋直大，ITmedia]

SRM443 Mediumの問題

Problem Statement

You are playing a game where you initially have A zeros and B ones. Your goal is to end up with all ones. In each move, you must choose exactly K of the numbers and flip their values （zeros change to ones, and vice-versa）. You can choose any K numbers each time, regardless of their current values or whether you have flipped them before. Return the minimal number of moves required to win the game, or -1 if it is impossible.

Constraints

- A will be between 0 and 100,000, inclusive.

- B will be between 0 and 100,000, inclusive.

- K will be between 1 and 100,000, inclusive.

　ざっと意訳すると、以下のように読み取れます。

A個の0とB個の1がある。これをK個同時に反転させる作業を繰り返して、全部1にしたい。A、B、Kが与えられる時、反転させる回数の最小値を求めよ。ただし、できない場合は-1を返せ。A、B、Kはそれぞれ100,000以下とし、Kは1以上とする。

　これだけだと分かりにくいので、問題を理解しやすいようにしたいと思います。

　表が0、裏が1のカードがA＋B枚あり、0が見えているものがA枚、1が見えているものがB枚とします。例えば、A＝5、B＝3、K＝3とします。これを図に表すと、下図のように、0が5枚、1が3枚見えています。

　ここで、K＝3なので、例えば下図のように、3枚ずつ反転させることを3回繰り返すことによって 、すべてを1にすることができます。このように、0の枚数（＝A）、1の枚数（＝B）、同時にひっくり返す枚数（＝K）が与えられたときに、ひっくり返すターン数の最小値を求めるのが今回の問題です。

　この問題は、Medium問題の中でもかなり難しい問題です。これが競技時間内に解ける方は、RedCoderを目指せるレベルだと思います。できなくて当然、といった部分もありますが、この連載をお読みになっている皆さまは、ぜひ、問題に挑戦してみてほしいと思います。解けるかどうかにかかわらず、記事を読む前に一度問題について考えていれば、ほかの考えに触れたときの印象がまるで違ってきますので、理解もかなり深まるはずです。数学の問題集の答えだけ見ていても問題が解けるようにならないのと同じで、一度解いてみることが非常に大切です。

　今回は、問題に挑戦しやすいように、TopCoder形式でのテンプレートを用意しました。本番中に試せる7つのサンプルと、本番終了後に行われるシステムテストから厳選して3つのケースを自動で試してくれるものを、C++／C#／Javaの3言語で用意しました（問題はSRM443 Medium）。すべてのテストで2秒以内にPASSEDと出力されればだいたい間違いなく成功ですので、ぜひともチャレンジしてみてください（厳密なシステムテストを行いたい場合は、TopCoderのサイトにユーザー登録した上、Arena上のPractice Roomから行うことが可能です。Practice Roomの使い方については別の回で改めて解説したいと思います）。

サンプルコードのダウンロードはこちらから