回答編集履歴

5

文章校正、これで多分完結

2017/11/11 13:15

投稿

miyabi-sun
miyabi-sun

スコア21158

test CHANGED
@@ -40,79 +40,65 @@
40
40
 
41
41
 
42
42
 
43
- 作業者は1回ハサミを入れる度に倍の人数が投入出来るようになるわけだけど、
43
+ 作業者は1回ハサミを入れる度に倍の人数(1, 2, 4, 8...)が投入出来るようになるわけだね。
44
44
 
45
- まず1cm単位切り分け必要がある。
45
+ も5人ならどうすの?
46
46
 
47
- この時点で単なる/2すれば良いじゃんという話にならない。
48
-
49
-
50
-
51
- 次に、作業担当者は倍々(1, 2, 4, 8...)になるんだけど、5人ならどうするの?
52
-
53
- 2回ハサミ入れたら3回目は4人で、1人余ってる状態だよね?
47
+ 2回ハサミ入れたらは4人で、1人余ってる状態になるから…
54
48
 
55
49
  もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
56
50
 
57
51
 
58
52
 
59
- なので、最初条件で関数を回す。
53
+ うーん……再帰分割に注力というロジックならいけるか?
54
+
55
+ 引数は下記の3個
60
56
 
61
57
 
62
58
 
63
59
  - 経過時間: 0秒
64
60
 
65
- - 担当人数: (自分含めて)5人
61
+ - 担当人数: (自分含めて)5人 ← でもハサミを入れられるのは自分だけ
66
62
 
67
63
  - 棒の長さ: 100cm
68
64
 
69
65
 
70
66
 
71
- 担当人数が5人なので100/(5 / 2の小数点切り捨て)の位置にハサミを作り
67
+ 担当人数が5人なので`(100 * (5 / 2).floor / 5).ceil`の位置にハサミをいれて棒を分断
72
68
 
73
- 下記2つの配列を作成して再帰し、受取った経過時間秒数のMAXを返させる。
69
+ 下記2つの配列を作成してそれぞれ再帰関数にかける。
74
70
 
71
+ そして受け取った経過時間秒数のMAXを返させる。
72
+
75
- (配列の中身は経過時間, 担当人数, 棒の長さの順)
73
+ (二回目以降は配列っぽく記載、経過時間, 担当人数, 棒の長さの順)
76
74
 
77
75
 
78
76
 
79
- - [1, 2, 40]
77
+ - [1, 2, 40] -> [[2, 1, 20], [2, 1, 20]]
80
78
 
81
- - [1, 3, 60]
79
+ - [1, 3, 60] -> [[2, 1, 20], [2, 2, 40]]
82
80
 
83
81
 
84
82
 
85
83
  次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る
86
84
 
87
-
88
-
89
- - [2, 1, 20]
90
-
91
- - [2, 1, 20]
92
-
93
- - [2, 1, 20]
94
-
95
- - [2, 2, 40]
96
-
97
-
98
-
99
85
  担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい
100
86
 
101
87
 
102
88
 
103
- - 2 + (20 - 1) = 21s
89
+ - [2, 1, 20] -> 2 + (20 - 1) = 21s
104
90
 
105
- - 2 + (20 - 1) = 21s
91
+ - [2, 1, 20] -> 2 + (20 - 1) = 21s
106
92
 
107
- - 2 + (20 - 1) = 21s
93
+ - [2, 1, 20] -> 2 + (20 - 1) = 21s
108
94
 
109
- - [3, 1, 20] -> 3 + (20 - 1) = 22s
95
+ - [2, 2, 40] -> [[3, 1, 20], [3, 1, 20]] -> [22s, 22s] -> 22s
110
-
111
- - [3, 1, 20] -> 3 + (20 - 1) = 22s
112
96
 
113
97
 
114
98
 
115
99
  お、これなら確かに再帰で書けるね。
100
+
101
+ もし待ち作業担当者がまだ居る状態で棒が1cmになってしまったら今の経過時間をそのまま返せば良い。
116
102
 
117
103
 
118
104
 
@@ -122,13 +108,19 @@
122
108
 
123
109
  でも、持ち替えNGとは書いてないんだよね。
124
110
 
125
- なら毎一番長い順に棒を持たせて半分に刻めばいか。
111
+ なら毎一番長い順から順番担当者に半分にカットさせてくと、
126
112
 
127
- 最終的に2cmの棒きれが大量に出来最短秒数で完了することが確定するわけだ
113
+ 最終的に2cmの棒きれが50個弱出来るから2cmの棒きれ50個弱を5人皆がそれぞれ手にって半分にカットしていく光景見れるわけだ
128
114
 
129
115
 
130
116
 
117
+ でもそうなると、5人揃うまでに3秒かかるから、`1 + 2 + 4 = 7回`ハサミを入れることが可能。
118
+
119
+ 100cmの棒きれは99回ハサミを入れれば1cm毎になるので、後92回ハサミを入れればバラバラになる。
120
+
131
- でもそうなると、3秒で7回刻んで93cm、後は3秒+((93 - 1)cm/5人)の小数点以下切り上げで答えが出てしまう。
121
+ つまり`3秒+ (92回 / 5人).ceil`で答えが出てしまう。
122
+
123
+
132
124
 
133
125
  なんてことだ……やはり再帰は不要だったのだ!
134
126
 

4

追加条件を再帰で解きました。

2017/11/11 13:15

投稿

miyabi-sun
miyabi-sun

スコア21158

test CHANGED
@@ -54,7 +54,69 @@
54
54
 
55
55
  もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
56
56
 
57
+
58
+
59
+ なので、最初はこの条件で関数を回す。
60
+
61
+
62
+
63
+ - 経過時間: 0秒
64
+
65
+ - 担当人数: (自分含めて)5人
66
+
67
+ - 棒の長さ: 100cm
68
+
69
+
70
+
71
+ 担当人数が5人なので100/(5 / 2の小数点切り捨て)の位置にハサミを作り、
72
+
73
+ 下記2つの配列を作成して再帰し、受け取った経過時間秒数のMAXを返させる。
74
+
75
+ (配列の中身は経過時間, 担当人数, 棒の長さの順)
76
+
77
+
78
+
79
+ - [1, 2, 40]
80
+
81
+ - [1, 3, 60]
82
+
83
+
84
+
85
+ 次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る
86
+
87
+
88
+
89
+ - [2, 1, 20]
90
+
91
+ - [2, 1, 20]
92
+
93
+ - [2, 1, 20]
94
+
95
+ - [2, 2, 40]
96
+
97
+
98
+
99
+ 担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい
100
+
101
+
102
+
103
+ - 2 + (20 - 1) = 21s
104
+
105
+ - 2 + (20 - 1) = 21s
106
+
107
+ - 2 + (20 - 1) = 21s
108
+
109
+ - [3, 1, 20] -> 3 + (20 - 1) = 22s
110
+
111
+ - [3, 1, 20] -> 3 + (20 - 1) = 22s
112
+
113
+
114
+
57
- これだと再帰では解ないね。
115
+ お、これなら確かに再帰でね。
116
+
117
+
118
+
119
+ ---
58
120
 
59
121
 
60
122
 

3

結論が出てしまった…

2017/11/11 12:34

投稿

miyabi-sun
miyabi-sun

スコア21158

test CHANGED
@@ -58,14 +58,18 @@
58
58
 
59
59
 
60
60
 
61
- でも、持ち替えNGとは書いてないから再帰で綺麗に書けるね。
61
+ でも、持ち替えNGとは書いてないんだよね。
62
62
 
63
- 皆が適当に半分の長さに刻んで、人より棒切れの方が多くった長い順に棒を持たせて半分に刻めばいいか。
63
+ なら毎回一番長い順に棒を持たせて半分に刻めばいいか。
64
64
 
65
- そうこうしている内、大量の2cmの棒きれが出来て、最短秒数で完了することが確定するわけだし。
65
+ 最終的に2cmの棒きれが大量に出来て、最短秒数で完了することが確定するわけだし。
66
66
 
67
67
 
68
68
 
69
- やり取りしながら11いく光景は非常にシュールだけど…
69
+ でもると、3で7回刻んで93cm、後は3秒+((93 - 1)cm/5人)の小数点以下り上げで答えが出しまう。
70
70
 
71
+ なんてことだ……やはり再帰は不要だったのだ!
72
+
71
- 実際にやると大量配列をソートしまくりになから速度は間違いなくでなさそう。
73
+ あ、でもでも3秒で7回刻むロジックは再帰で書くが一番スッキリすね!
74
+
75
+ そこかよ!って感じで正直微妙だけど…

2

ちょっとだけ修正

2017/11/11 09:03

投稿

miyabi-sun
miyabi-sun

スコア21158

test CHANGED
@@ -58,12 +58,14 @@
58
58
 
59
59
 
60
60
 
61
+ でも、持ち替えNGとは書いてないから再帰で綺麗に書けるね。
62
+
61
- でも、皆が適当に半分の長さに刻んで、人より棒切れの方が多くなったら、長い順に棒を持たせて半分に刻めばいいか。
63
+ 皆が適当に半分の長さに刻んで、人より棒切れの方が多くなったら、長い順に棒を持たせて半分に刻めばいいか。
62
64
 
63
65
  そうこうしている内に、大量の2cmの棒きれが出来て、最短秒数で完了することが確定するわけだし。
64
66
 
65
67
 
66
68
 
67
- こうすれば再帰でいけそうだね。
69
+ そんなやり取りしながら1秒に1回切ってく光景は非常にシュールだど…
68
70
 
69
- そんなやり取りし1秒に1回切っていく光景は非常にシュールだけど…
71
+ 実際にると大量の配列をソートしまくるか速度は間違でなさそう。

1

ロジックを考え直した

2017/11/11 08:54

投稿

miyabi-sun
miyabi-sun

スコア21158

test CHANGED
@@ -26,7 +26,7 @@
26
26
 
27
27
  でもまぁ、これだと再帰使う意味ないし、
28
28
 
29
- 下記のように言い換えてみたら問題としては納得出来るけど、再帰の例として出す問題としてはおかしいね。
29
+ 下記のように言い換えてみたら問題としては納得出来るんだけど
30
30
 
31
31
 
32
32
 
@@ -36,7 +36,7 @@
36
36
 
37
37
 
38
38
 
39
- その場合はかなり複雑だし、再帰関数の問題じゃないよね。
39
+ これかなり複雑だね。
40
40
 
41
41
 
42
42
 
@@ -52,12 +52,18 @@
52
52
 
53
53
  2回ハサミ入れたら3回目は4人で、1人余ってる状態だよね?
54
54
 
55
- もし100cmを5人で担当するなら、3回ハサミを入れた時点で18cmが2本、19cmが3本にるよう割り振らければらない。
55
+ もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗5等分にはできない。
56
56
 
57
- 19cmが5本5人の担当者にった時点で後18秒必要ってのは誰の目にも明らかだし
57
+ これだと再帰は解けいね
58
58
 
59
59
 
60
60
 
61
- まぁ解けるちゃ解けるか。
61
+ でも、皆が適当に半分の長さに刻んで、人より棒切れの方が多くなたら、長い順に棒を持たせて半分に刻めばいいか。
62
62
 
63
+ そうこうしている内に、大量の2cmの棒きれが出来て、最短秒数で完了することが確定するわけだし。
64
+
65
+
66
+
63
- 再帰じゃないけ。。
67
+ こうすれば再帰いけそうだね
68
+
69
+ そんなやり取りしながら1秒に1回切っていく光景は非常にシュールだけど…