回答編集履歴
5
文章校正、これで多分完結
answer
CHANGED
|
@@ -19,51 +19,47 @@
|
|
|
19
19
|
|
|
20
20
|
これかなり複雑だね。
|
|
21
21
|
|
|
22
|
-
作業者は1回ハサミを入れる度に倍の人数が投入出来るようになるわけだ
|
|
22
|
+
作業者は1回ハサミを入れる度に倍の人数(1, 2, 4, 8...)が投入出来るようになるわけだね。
|
|
23
|
-
|
|
23
|
+
でも5人ならどうするの？
|
|
24
|
-
この時点で単なる/2すれば良いじゃんという話にならない。
|
|
25
|
-
|
|
26
|
-
次に、作業担当者は倍々(1, 2, 4, 8...)になるんだけど、5人ならどうするの？
|
|
27
|
-
2回ハサミ入れたら
|
|
24
|
+
2回ハサミ入れたら次は4人で、1人余ってる状態になるから…
|
|
28
25
|
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
|
|
29
26
|
|
|
30
|
-
|
|
27
|
+
うーん……再帰は棒の分割に注力というロジックならいけるか？
|
|
28
|
+
引数は下記の3個
|
|
31
29
|
|
|
32
30
|
- 経過時間: 0秒
|
|
33
|
-
- 担当人数: (自分含めて)5人
|
|
31
|
+
- 担当人数: (自分含めて)5人 ← でもハサミを入れられるのは自分だけ
|
|
34
32
|
- 棒の長さ: 100cm
|
|
35
33
|
|
|
36
|
-
担当人数が5人なので100
|
|
34
|
+
担当人数が5人なので`(100 * (5 / 2).floor / 5).ceil`の位置にハサミをいれて棒を分断、
|
|
35
|
+
下記2つの配列を作成してそれぞれ再帰関数にかける。
|
|
37
|
-
|
|
36
|
+
そして受け取った経過時間秒数のMAXを返させる。
|
|
38
|
-
(配列
|
|
37
|
+
(二回目以降は配列っぽく記載、経過時間, 担当人数, 棒の長さの順)
|
|
39
38
|
|
|
40
|
-
- [1, 2, 40]
|
|
39
|
+
- [1, 2, 40] -> [[2, 1, 20], [2, 1, 20]]
|
|
41
|
-
- [1, 3, 60]
|
|
40
|
+
- [1, 3, 60] -> [[2, 1, 20], [2, 2, 40]]
|
|
42
41
|
|
|
43
42
|
次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る
|
|
44
|
-
|
|
45
|
-
- [2, 1, 20]
|
|
46
|
-
- [2, 1, 20]
|
|
47
|
-
- [2, 1, 20]
|
|
48
|
-
- [2, 2, 40]
|
|
49
|
-
|
|
50
43
|
担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい
|
|
51
44
|
|
|
52
|
-
- 2 + (20 - 1) = 21s
|
|
53
|
-
- 2 + (20 - 1) = 21s
|
|
54
|
-
- 2 + (20 - 1) = 21s
|
|
55
|
-
- [
|
|
45
|
+
- [2, 1, 20] -> 2 + (20 - 1) = 21s
|
|
56
|
-
- [
|
|
46
|
+
- [2, 1, 20] -> 2 + (20 - 1) = 21s
|
|
47
|
+
- [2, 1, 20] -> 2 + (20 - 1) = 21s
|
|
48
|
+
- [2, 2, 40] -> [[3, 1, 20], [3, 1, 20]] -> [22s, 22s] -> 22s
|
|
57
49
|
|
|
58
50
|
お、これなら確かに再帰で書けるね。
|
|
51
|
+
もし待ち作業担当者がまだ居る状態で棒が1cmになってしまったら今の経過時間をそのまま返せば良い。
|
|
59
52
|
|
|
60
53
|
---
|
|
61
54
|
|
|
62
55
|
でも、持ち替えNGとは書いてないんだよね。
|
|
63
|
-
なら毎
|
|
56
|
+
なら毎秒一番長い順から順番に担当者に半分にカットさせていくと、
|
|
64
|
-
最終的に2cmの棒きれが
|
|
57
|
+
最終的に2cmの棒きれが50個弱出来るから、2cmの棒きれ50個弱を5人皆がそれぞれ手にとって半分にカットしていく光景が見れるわけだね。
|
|
65
58
|
|
|
59
|
+
でもそうなると、5人揃うまでに3秒かかるから、`1 + 2 + 4 = 7回`ハサミを入れることが可能。
|
|
60
|
+
100cmの棒きれは99回ハサミを入れれば1cm毎になるので、後92回ハサミを入れればバラバラになる。
|
|
66
|
-
|
|
61
|
+
つまり`3秒+ (92回 / 5人).ceil`で答えが出てしまう。
|
|
62
|
+
|
|
67
63
|
なんてことだ……やはり再帰は不要だったのだ！
|
|
68
64
|
あ、でもでも3秒で7回刻むロジックは再帰で書くのが一番スッキリするね！
|
|
69
65
|
そこかよ！って感じで正直微妙だけど…
|
4
追加条件を再帰で解きました。
answer
CHANGED
|
@@ -26,8 +26,39 @@
|
|
|
26
26
|
次に、作業担当者は倍々(1, 2, 4, 8...)になるんだけど、5人ならどうするの？
|
|
27
27
|
2回ハサミ入れたら3回目は4人で、1人余ってる状態だよね？
|
|
28
28
|
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
|
|
29
|
-
これだと再帰では解けないね。
|
|
30
29
|
|
|
30
|
+
なので、最初はこの条件で関数を回す。
|
|
31
|
+
|
|
32
|
+
- 経過時間: 0秒
|
|
33
|
+
- 担当人数: (自分含めて)5人
|
|
34
|
+
- 棒の長さ: 100cm
|
|
35
|
+
|
|
36
|
+
担当人数が5人なので100/(5 / 2の小数点切り捨て)の位置にハサミを作り、
|
|
37
|
+
下記2つの配列を作成して再帰し、受け取った経過時間秒数のMAXを返させる。
|
|
38
|
+
(配列の中身は経過時間, 担当人数, 棒の長さの順)
|
|
39
|
+
|
|
40
|
+
- [1, 2, 40]
|
|
41
|
+
- [1, 3, 60]
|
|
42
|
+
|
|
43
|
+
次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る
|
|
44
|
+
|
|
45
|
+
- [2, 1, 20]
|
|
46
|
+
- [2, 1, 20]
|
|
47
|
+
- [2, 1, 20]
|
|
48
|
+
- [2, 2, 40]
|
|
49
|
+
|
|
50
|
+
担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい
|
|
51
|
+
|
|
52
|
+
- 2 + (20 - 1) = 21s
|
|
53
|
+
- 2 + (20 - 1) = 21s
|
|
54
|
+
- 2 + (20 - 1) = 21s
|
|
55
|
+
- [3, 1, 20] -> 3 + (20 - 1) = 22s
|
|
56
|
+
- [3, 1, 20] -> 3 + (20 - 1) = 22s
|
|
57
|
+
|
|
58
|
+
お、これなら確かに再帰で書けるね。
|
|
59
|
+
|
|
60
|
+
---
|
|
61
|
+
|
|
31
62
|
でも、持ち替えNGとは書いてないんだよね。
|
|
32
63
|
なら毎回一番長い順に棒を持たせて半分に刻めばいいか。
|
|
33
64
|
最終的に2cmの棒きれが大量に出来て、最短秒数で完了することが確定するわけだし。
|
3
結論が出てしまった…
answer
CHANGED
|
@@ -28,9 +28,11 @@
|
|
|
28
28
|
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
|
|
29
29
|
これだと再帰では解けないね。
|
|
30
30
|
|
|
31
|
-
でも、持ち替えNGとは書いてない
|
|
31
|
+
でも、持ち替えNGとは書いてないんだよね。
|
|
32
|
-
|
|
32
|
+
なら毎回一番長い順に棒を持たせて半分に刻めばいいか。
|
|
33
|
-
|
|
33
|
+
最終的に2cmの棒きれが大量に出来て、最短秒数で完了することが確定するわけだし。
|
|
34
34
|
|
|
35
|
+
でもそうなると、3秒で7回刻んで93cm、後は3秒+((93 - 1)cm/5人)の小数点以下切り上げで答えが出てしまう。
|
|
36
|
+
なんてことだ……やはり再帰は不要だったのだ！
|
|
35
|
-
|
|
37
|
+
あ、でもでも3秒で7回刻むロジックは再帰で書くのが一番スッキリするね！
|
|
36
|
-
|
|
38
|
+
そこかよ！って感じで正直微妙だけど…
|
2
ちょっとだけ修正
answer
CHANGED
|
@@ -28,8 +28,9 @@
|
|
|
28
28
|
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
|
|
29
29
|
これだと再帰では解けないね。
|
|
30
30
|
|
|
31
|
+
でも、持ち替えNGとは書いてないから再帰で綺麗に書けるね。
|
|
31
|
-
|
|
32
|
+
皆が適当に半分の長さに刻んで、人より棒切れの方が多くなったら、長い順に棒を持たせて半分に刻めばいいか。
|
|
32
33
|
そうこうしている内に、大量の2cmの棒きれが出来て、最短秒数で完了することが確定するわけだし。
|
|
33
34
|
|
|
34
|
-
こうすれば再帰でいけそうだね。
|
|
35
|
-
そんなやり取りしながら1秒に1回切っていく光景は非常にシュールだけど…
|
|
35
|
+
そんなやり取りしながら1秒に1回切っていく光景は非常にシュールだけど…
|
|
36
|
+
実際にやると大量の配列をソートしまくりになるから速度は間違いなくでなさそう。
|
1
ロジックを考え直した
answer
CHANGED
|
@@ -12,12 +12,12 @@
|
|
|
12
12
|
---
|
|
13
13
|
|
|
14
14
|
でもまぁ、これだと再帰使う意味ないし、
|
|
15
|
-
下記のように言い換えてみたら問題としては納得出来るけど
|
|
15
|
+
下記のように言い換えてみたら問題としては納得出来るんだけど…
|
|
16
16
|
|
|
17
17
|
> 1人の作業者は1秒に1度のペースでハサミを入れる事ができます。
|
|
18
18
|
m人の作業者で切り分けると最低何秒かかるでしょう？
|
|
19
19
|
|
|
20
|
-
|
|
20
|
+
これかなり複雑だね。
|
|
21
21
|
|
|
22
22
|
作業者は1回ハサミを入れる度に倍の人数が投入出来るようになるわけだけど、
|
|
23
23
|
まず1cm単位で切り分ける必要がある。
|
|
@@ -25,8 +25,11 @@
|
|
|
25
25
|
|
|
26
26
|
次に、作業担当者は倍々(1, 2, 4, 8...)になるんだけど、5人ならどうするの？
|
|
27
27
|
2回ハサミ入れたら3回目は4人で、1人余ってる状態だよね？
|
|
28
|
-
もし100cmを5人で担当するなら
|
|
28
|
+
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。
|
|
29
|
-
|
|
29
|
+
これだと再帰では解けないね。
|
|
30
30
|
|
|
31
|
+
でも、皆が適当に半分の長さに刻んで、人より棒切れの方が多くなったら、長い順に棒を持たせて半分に刻めばいいか。
|
|
31
|
-
|
|
32
|
+
そうこうしている内に、大量の2cmの棒きれが出来て、最短秒数で完了することが確定するわけだし。
|
|
33
|
+
|
|
32
|
-
再帰
|
|
34
|
+
こうすれば再帰でいけそうだね。
|
|
35
|
+
そんなやり取りしながら1秒に1回切っていく光景は非常にシュールだけど…
|