ACM問題 #10465 Homer Simpson は一次不定式を解くもの。問題の記述に曖昧性はあるものの、ためになる良問のひとつ。

<問題の説明>
 2種類のハンバーガーをそれぞれM, N 分で食べ切ることができる。与えられた T 分ちょうどの時間に、最多何個のハンバーガーを食べ切ることができるか。また、どうしても時間が余ってしまうなら、余った時間を飲み物にすると良いが、飲む時間は最小にして欲しい。

 入力パラメータ  整数 M, N, T ( 0 < M, N, T < 10000 )
 出力値       K (食べたハンバーガーの個数、K >= 0)、t (飲み物の飲む時間。飲む時間がなければ出力不要)。

<例を考える>
 理解を助けるために、例を考えてみる。
 例えば、M=3、N=5、T=54の場合、18*M = 18*3 = 54 なので、K=18が解答になる。Nの値がMより大きいので、18が最大値であることが理解できよう。
 また、M=3、N=4、T=5の場合、ちょうど5分間でハンバーガーを食べ切ることはできないが、飲む時間をいれて調整すると解答が存在する。つまり、飲む時間を最小限の1分にすれば、ちょうどハンバーガー1個食べ切ることができるから、K=1、t=1 がその解答。

<問題の整理>
 ハンバーガー云々のストーリーが先にあって問題作られたのか、数学的モデルに無理やりストーリーを書きあげたのかは、出題者に聞かないと判らないが、 一次不定式の解き方が問われている。つまり、

  Mx + Ny = T
  x >= 0、y >= 0

を満たす整数解 x、y を求め、解があれば、x+y を最大にするということだ。
 もし、解 x、y がなければ、解があるまで、Tを減らすこと。減らした時間を飲む時間に当てる。勿論、減らす量を最小限に止めるべきだ。

<拡張剰余定理>
 整数 M, N の最大公約数を D=gcd(M, N) とすると、 1次不定式 Mx + Ny = D を満たす整数解 x, y は必ず存在する。詳細はここで省略するが、以下の関数は一組の X、Y 及び D を算出する。(関数では、入力引数の変数名に a, b を使うが、ここでいう M, N と考えてOK。)

int extended_gcd(int a, int b, int *x, int *y)
{
int d;
if (b == 0) { *x = 1; *y = 0; return a; } d = extended_gcd(b, a%b, y, x); *y -= a / b * (*x); return d; }

 また、証明は省略するが、問題の入力パラメータ T がDの倍数、つまり、T がMとNの最大公約数 D の倍数であれば、取りあえず整数解 x, y が見つかる(ただし、非負整数である保証はないので、我々の求める x, y でない可能性もある。)
 T がDの倍数でなければ、整数解が存在しない。飲む時間 t をいれて調整することが必要
 ⇒ t = T % D

 上記の拡張剰余定理で見つかった一組の整数解 x, y を元に、一般解を組み立てると以下になる。

<一次不定式の一般解>
 D = gcd(M, N) とし、 X, Y は不定式 MX + NY = D を満たすものとすると、

 Mx + Ny = T (ただし、T は Dの倍数でないときには、Dの倍数になるように値を減らす)の一般整数解 x, y は、

 x = (T/D)*X – (N/D)*S
 y = (T/D)*Y + (M/D)*S

で与えられる。 ただし、S は任意の整数。なお、(T/D) はC言語でいうところの割算。

<非負整数解にするには>
 x, y の値は、本問題では、ゼロ以上の非負整数でないといけないので、S の変域をここで求める。

 (N/D)*S <= (T/D)*X
 (M/D)*S >= -(T/D)*Y

 -(T/D)*Y / (M/D) <= S <= (T/D)*X / (N/D)

細かい記述は敢えてここで避けておくが、Sの変域の両端を整数値 Smin, Smax とすると、

 Smin = -(T/D)*Y / (M/D)
 Smax = (T/D)*X / (N/D)

となる。はずだが、慎重に計算して欲しい。
 1.4 <= S <= 4.5 では、Smin = 2 (切り上げ), Smax = 4 (正数の切り下げ=C言語の割算)
 -4.5 <= S <= -1.4 では、Smin = -4(負数の切り上げ=C言語の割算), Smax = -2 (切り下げ)

 また、x+y の値は x + y = (T/D)*X + (T/D)*Y + ((M/D – (N/D))*S で与えられるので、
 M >= N であれば、 S = Smax を取れば、 x + y は最大になり、
 M < N であれば、  S = Smin とすれば、 x + y は最大になる。

<話はまだ終わらない>
 一見すると解答は出たようだが、実は Smin と Smax は計算できない場合がある。つまり、Smin > Smax になってしまったりすることがある。その場合では、TをDの値分ずつ減らし、繰り返し計算すれば、必ず条件を満たす Smin, Smax が見つかる。

<解答プログラム> p10465.c

最後に、テストデータを掲載しておく。

<テスト用入力データ>
4 4 10
1 7 10
2 3 6
11 2 13
2 5 25
3 4 5
5 3 5
4 5 7
9 7 62
2 5 6
45 23 91
5 9 19
4 6 42
3 7 10
12 56 71
50 51 103
20 30 7
100 8 1
123 12 21

<対応する出力結果>
2 2
10
3
2
11
1 1
1
1 2
8
3
3
3
10
2
2 3
2 1
0 7
0 1
1 9

Comments are closed.

Post Navigation