回答編集履歴
3
さらに修正
test
CHANGED
|
@@ -1,8 +1,8 @@
|
|
|
1
1
|
**一次不定方程式**の考え方を使うのが1番速いと思います。
|
|
2
2
|
|
|
3
|
-
xグループ参加し、それに対して必要なバスがy台としたときに、空席がr席とすると、
|
|
3
|
+
xグループ参加し、それに対して必要なバスがy台としたときに、空席がr席(0≦r<M)とすると、
|
|
4
4
|
|
|
5
|
-
My-Nx=r (
|
|
5
|
+
My-Nx=r (A)
|
|
6
6
|
|
|
7
7
|
という関係が成り立つことになります。
|
|
8
8
|
|
|
@@ -10,37 +10,45 @@
|
|
|
10
10
|
|
|
11
11
|
|
|
12
12
|
|
|
13
|
-
あるr
|
|
13
|
+
ある値がrとして取りうるか否かは、
|
|
14
14
|
|
|
15
|
-
|
|
15
|
+
方程式(A)を満たす整数x,y(**整数解**)が存在するか否か、と同義になります。
|
|
16
16
|
|
|
17
|
+
例えばN=6,M=4の場合、
|
|
18
|
+
|
|
19
|
+
- r=3、つまり4y-6x=3を満たす整数x,yは存在しません。(左辺は偶数、右辺は奇数のため)
|
|
20
|
+
|
|
21
|
+
つまり、「空席が3つ」という状況は起こりえません。
|
|
22
|
+
|
|
23
|
+
- r=2、つまり4y-6x=2は、x=1,y=2や、x=3,y=5などが解になります。
|
|
24
|
+
|
|
25
|
+
これらの状況で、「空席が2つ」になります。
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
x,yについての方程式(A)は、
|
|
30
|
+
|
|
17
|
-
**rが「MとNの最大公約数」の倍数である場合、またその場合に限
|
|
31
|
+
**rが「MとNの最大公約数」の倍数である場合に、またその場合に限り整数解をもつ**ことが知られています。
|
|
32
|
+
|
|
33
|
+
→[一次不定方程式ax+by=cの整数解 - 高校数学の美しい物語](https://mathtrain.jp/axbyc)
|
|
34
|
+
|
|
35
|
+
(厳密には、この問題においてx,yは自然数である必要がありますが、
|
|
36
|
+
|
|
37
|
+
M>0,N>0であれば自然数解をもつことが保証されます。)
|
|
18
38
|
|
|
19
39
|
|
|
20
40
|
|
|
21
41
|
以下、「MとNの最大公約数」をgとします。
|
|
22
42
|
|
|
23
|
-
|
|
24
|
-
|
|
25
|
-
例えばN=6,M=4の場合、g=2なので、
|
|
26
|
-
|
|
27
|
-
- r=3、つまり4y-6x=3を満たす整数x,yは存在しません。(左辺は偶数、右辺は奇数)
|
|
28
|
-
|
|
29
|
-
つまり、「空席が3つ」という状況は起こりえません。
|
|
30
|
-
|
|
31
|
-
- r=2、つまり4y-6x=2は、x=1,y=2や、x=3,y=5などが解になります。
|
|
32
|
-
|
|
33
|
-
これらの状況で、「空席が2つ」が起こりえます。
|
|
34
|
-
|
|
35
|
-
|
|
36
|
-
|
|
37
43
|
Mはgの倍数であるため、M = kgとなる自然数kが存在します。
|
|
38
44
|
|
|
39
|
-
|
|
45
|
+
(A)が整数解をもつためにrとして取りうる値は、
|
|
46
|
+
|
|
47
|
+
0≦r<Mの範囲内にあるgの倍数、すなわち
|
|
40
48
|
|
|
41
49
|
0, g, 2g, ... , (k-1)g
|
|
42
50
|
|
|
43
|
-
であり、このうち最大は
|
|
51
|
+
のk個であり、このうち最大は
|
|
44
52
|
|
|
45
53
|
(k-1)g = kg - g = M - g
|
|
46
54
|
|
2
整合性がとれていなかったので、全体的に回答を修正
test
CHANGED
|
@@ -1,47 +1,51 @@
|
|
|
1
1
|
**一次不定方程式**の考え方を使うのが1番速いと思います。
|
|
2
2
|
|
|
3
|
-
xグループ参加し、それに対して
|
|
3
|
+
xグループ参加し、それに対して必要なバスがy台としたときに、空席がr席とすると、
|
|
4
4
|
|
|
5
|
-
Nx
|
|
5
|
+
My-Nx=r (0≦r<M)
|
|
6
6
|
|
|
7
|
-
|
|
7
|
+
という関係が成り立つことになります。
|
|
8
8
|
|
|
9
|
+
このrとして取りうる値のうち、最大の値を求めるのがこの問題の趣旨となります。
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
9
|
-
あ
|
|
13
|
+
あるrが空席の数として成立するか否かは、この方程式を満たす整数x,yが存在するか否か、と同義になります。
|
|
10
14
|
|
|
11
15
|
このx,yについての方程式が、x,yともに整数となる解を持つのは、
|
|
12
16
|
|
|
13
|
-
**rが「N
|
|
17
|
+
**rが「MとNの最大公約数」の倍数である場合、またその場合に限る**ことが知られています。
|
|
14
18
|
|
|
15
19
|
|
|
16
20
|
|
|
17
|
-
以下、「N
|
|
21
|
+
以下、「MとNの最大公約数」をgとします。
|
|
18
22
|
|
|
19
23
|
|
|
20
24
|
|
|
21
25
|
例えばN=6,M=4の場合、g=2なので、
|
|
22
26
|
|
|
23
|
-
- r=
|
|
27
|
+
- r=3、つまり4y-6x=3を満たす整数x,yは存在しません。(左辺は偶数、右辺は奇数)
|
|
24
28
|
|
|
25
|
-
つまり、「
|
|
29
|
+
つまり、「空席が3つ」という状況は起こりえません。
|
|
26
30
|
|
|
27
|
-
- r=2、つまり6x
|
|
31
|
+
- r=2、つまり4y-6x=2は、x=1,y=2や、x=3,y=5などが解になります。
|
|
32
|
+
|
|
33
|
+
これらの状況で、「空席が2つ」が起こりえます。
|
|
28
34
|
|
|
29
35
|
|
|
30
36
|
|
|
31
|
-
|
|
37
|
+
Mはgの倍数であるため、M = kgとなる自然数kが存在します。
|
|
32
38
|
|
|
33
|
-
|
|
39
|
+
0≦r<Mを加味して考えると、rとして取りうる値は
|
|
34
40
|
|
|
35
|
-
|
|
41
|
+
0, g, 2g, ... , (k-1)g
|
|
36
42
|
|
|
37
|
-
|
|
43
|
+
であり、このうち最大は
|
|
38
44
|
|
|
39
|
-
|
|
45
|
+
(k-1)g = kg - g = M - g
|
|
40
46
|
|
|
47
|
+
となります。
|
|
41
48
|
|
|
42
|
-
|
|
43
|
-
になります。g=Mの場合の空席の最大値0も、M-g=M-Mと表すことができるため、
|
|
44
|
-
|
|
45
|
-
**
|
|
49
|
+
つまり、**求める空席の最大値はM - g**で表せることになります。
|
|
46
50
|
|
|
47
51
|
gは、ユークリッドの互除法により高速に求められるので、総当たりのループより速く解決できます。
|
1
手直し
test
CHANGED
|
@@ -4,22 +4,44 @@
|
|
|
4
4
|
|
|
5
5
|
Nx-My=r (0≦r<M)
|
|
6
6
|
|
|
7
|
-
で定められるあまり人数r人が最小になるケースを考えることになります。
|
|
7
|
+
で定められるあまり人数r人が最小になるケースを考えることになります。
|
|
8
8
|
|
|
9
|
-
|
|
9
|
+
あまり人数が少ないほど、空席が多くなりますから。（ただし、あまり0人の場合は空席0）
|
|
10
10
|
|
|
11
|
-
|
|
11
|
+
このx,yについての方程式が、x,yともに整数となる解を持つのは、
|
|
12
12
|
|
|
13
|
-
|
|
13
|
+
**rが「NとMの最大公約数」の倍数である場合、またその場合に限る**ことが知られています。
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
17
|
-
|
|
17
|
+
以下、「NとMの最大公約数」をgとします。
|
|
18
|
-
|
|
19
|
-
- そうでないとき、空席M-(NとMの最大公約数)
|
|
20
18
|
|
|
21
19
|
|
|
22
20
|
|
|
23
|
-
|
|
21
|
+
例えばN=6,M=4の場合、g=2なので、
|
|
24
22
|
|
|
23
|
+
- r=1、つまり6x-4y=1を満たす整数x,yは存在しません。
|
|
24
|
+
|
|
25
|
+
つまり、「余りが1人」という状況は起こりえません。
|
|
26
|
+
|
|
27
|
+
- r=2、つまり6x-4y=2は、x=1,y=1や、x=3,y=4などが解になります。
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
gがMを超えることはないので、0≦r<Mを加味して考えると、
|
|
32
|
+
|
|
33
|
+
|g|整数解をもつためのrの最小値|空席の最大値|
|
|
34
|
+
|
|
35
|
+
|:--|--:|--:|
|
|
36
|
+
|
|
37
|
+
|M|0|0|
|
|
38
|
+
|
|
39
|
+
|M以外|g|M-g|
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
になります。g=Mの場合の空席の最大値0も、M-g=M-Mと表すことができるため、
|
|
44
|
+
|
|
45
|
+
**いずれの場合も、空席の最大値はM-g**で表せることになります。
|
|
46
|
+
|
|
25
|
-
|
|
47
|
+
gは、ユークリッドの互除法により高速に求められるので、総当たりのループより速く解決できます。
|