プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2016/12/01(木) 16:58:30.97

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part8©2ch.net
http://echo.2ch.net/test/read.cgi/tech/1444216746/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

**デフォルトの名無しさん** · 2017/07/06(木) 00:52:46.56

>>321
あれ、変だな
>>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？
同様に"3328"、"3364"は最短19秒だけど>>318だと20になった

**318** · 2017/07/06(木) 01:20:52.00

>>322
同じコードをideoneに張りなおして3324を入力して実行してみました。
http://ideone.com/vXrTp8

ソースを一箇所編集しています。

31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出

の繰り返し回数上限判定地を10から20に増やしています。

3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。
3364も20が10回繰り返した後19が出て続きます。

お手数おかけしますが
一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして
評価してください。

**318** · 2017/07/06(木) 01:35:51.32

>>323
3324と3364の解を見ていて気が付いた点があります。

一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、
3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため
解として表示されています。
これは、3324の15や3364が4桁しかないので、
最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を
解として表示していることによります。

>>318の一定回数繰り返したら収束とみなすという判定方法は、
ニュートン法のような数値計算では有効ですが、
>>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz

**デフォルトの名無しさん** · 2017/07/06(木) 01:53:08.89

3324を拡張した887654329は閾値どれくらい増やせば対応できるんですかね

**318** · 2017/07/06(木) 02:06:40.59

>>325
延々探索を続けないと解に至らないかもしれない入力については
定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。
887654329がそういったカテゴリーに属する入力かというと
ﾁｮｯﾄ分からない。
なので適切な閾値はこれだと断言しにくいです。
さーせん

**デフォルトの名無しさん** · 2017/07/06(木) 21:08:21.84

>>326
結局>>321は大嘘だったし、閾値20の>>323にしたところで
例えば"14432"は最短にならないし
閾値が決められないならその解法はやはり駄目だな

**318** · 2017/07/06(木) 22:03:39.91

>>327
閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、
計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。

**318** · 2017/07/06(木) 22:08:34.07

見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。
それによって20で打ち切るようなやり方を改善できればいいんだけれども…
それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して
とけなくなる

**デフォルトの名無しさん** · 2017/07/06(木) 23:01:53.78

>>328
閾値20で打ち切るのは枝切りじゃないという主張のようだけど
打ち切るという動作は枝切り以外の何物でもない

>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
というのも嘘

**318** · 2017/07/06(木) 23:19:13.87

>>330
絡むね。そんな暇あったらコードでも書けばいいのにｗ

閾値20でその入力については解の探査を止めて
別の枝に移らず次の入力データに移るのはどちらかといえば中断で、
枝かりではないでしょ。

>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。
にかいてあるでしょうに。

>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
>というのも嘘

これは10回の打ち切りの緩和を書きもらしたんだよ。

何が狙いで、こだわって絡んでくるやらねぇ。

**318** · 2017/07/06(木) 23:37:37.26

「打ち切る」という言葉を

>318
>…
>同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
>最短値に収束したと見なし、探索を打ち切ることによって短時間で
>解を出力できるようにした。打ち切り上限は10をハードコードしてあるが

では「その入力に対する求解を中断する」ところで使い、

>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。

では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの
ところで使ったのが誤解を招いてしまったのかな…

**デフォルトの名無しさん** · 2017/07/07(金) 04:22:27.25

3次の動的計画法ってどんだけメモリ食うんや？

**デフォルトの名無しさん** · 2017/07/08(土) 03:20:24.48

お題：　自然数Nの平方根を整数部含めて(1000*N)桁求めたとき、出現する0の個数を数える
たとえば、N = 4の時ルート4を4000桁（整数部1桁＋小数部3999桁）求めたとき、出現する0の個数は3999個

N = 3 => ?
N = 5 => ?
N = 7 => ?

**デフォルトの名無しさん** · 2017/07/08(土) 03:22:50.68

ブロックチェインの新手のコイン発掘か？

**デフォルトの名無しさん** · 2017/07/08(土) 03:59:02.35

>>334 Ruby
require 'bigdecimal'
[3, 4, 5, 7].each{|i|
n = 1000*i - 1
puts "N = %i => %i"%[i, ("%.#{n}f"%BigDecimal(i).sqrt(n)).count(?0)]
}

N = 3 => 2956
N = 4 => 3999
N = 5 => 4956
N = 7 => 6954

**デフォルトの名無しさん** · 2017/07/08(土) 04:25:25.94

>>336はミス。0がこんなに多いわけがない

require 'bigdecimal'
[3, 5, 7].each{|i|
n = 1000*i - 1
puts "N = %i => %i"%[i, BigDecimal(i).sqrt(n).floor(n).to_s(?F).count(?0)]
}

N = 3 => 309
N = 5 => 492
N = 7 => 738

**デフォルトの名無しさん** · 2017/07/08(土) 07:13:48.73

>>337
N = 5の場合が間違ってると思う
多分、丸めモードの関係か、精度が足りてないと思われる

**デフォルトの名無しさん** · 2017/07/08(土) 09:51:11.17

>>334 C++

#include <iostream>
#include <string>
#include "gmpxx.h"
int main () {
int sq_me;
while( std::cin >> sq_me ){
int prec = 1000*sq_me, cnt = 0;
mpf_class sq_out = sqrt( mpf_class(sq_me, prec*4) );
mp_exp_t exp;
auto str = sq_out.get_str( exp,10,prec );
for( auto it=str.begin(); it!=str.end(); it++ ) if( *it=='0' ) ++cnt;
std::cout << "N = " << sq_me << " => " << cnt+prec-str.length() << '\n';
}
}

N = 3 => 309
N = 5 => 493
N = 7 => 738
N = 11 => 1079
N = 13 => 1305
N = 17 => 1664
N = 19 => 1875
N = 23 => 2265
N = 29 => 2911
N = 31 => 3113
N = 37 => 3795
N = 41 => 4095
N = 43 => 4312
N = 47 => 4798
N = 53 => 5340

**デフォルトの名無しさん** · 2017/07/08(土) 11:54:07.74

>>334 Squeak/Pharo Smalltalk

| sqrt |
sqrt := [:n :m |
　"ref. https://xar.sh/post/67066374255/ "
　| a b |
　a := 5 * n. b := 5.
　[:exit | [
　　a >= b ifTrue: [a := a - b. b := b + 10] ifFalse: [
　　　b log > m ifTrue: [exit value] ifFalse: [
　　　　a := a * 100. b := b // 10 * 100 + (b \\ 10)
　　　]
　　]
　] repeat] valueWithExit.
　b
].

#(3 5 7) collect: [:i | i -> (((sqrt value: i value: i*1000) asString first: i*1000) occurrencesOf: $0)]

"=> {3->309 . 5->493 . 7->738}"

**デフォルトの名無しさん** · 2017/07/08(土) 12:18:57.24

>>339
N = 29とN=41の場合が間違ってる可能性？　それ以外は正しい模様
N = 29 => 2912、N = 41 => 4094 じゃなかろうか

>>340
合ってる

**デフォルトの名無しさん** · 2017/07/08(土) 12:48:13.59

>>334 Perl5
http://ideone.com/fAyh2l

**デフォルトの名無しさん** · 2017/07/08(土) 13:10:39.20

>>334 Perl5
http://ideone.com/cMBD8o

>>342 をもう少しすっきり書けたので差し替え。

**デフォルトの名無しさん** · 2017/07/08(土) 13:31:31.09

>>341
> N = 29 => 2912、N = 41 => 4094 じゃなかろうか

それが正しいようです
GNU MPだとどうしても最後の桁は四捨五入?されるようで
任意のNに対して正確な答えを出すのは面倒なので修正は断念

**デフォルトの名無しさん** · 2017/07/09(日) 10:26:36.71

結局バイナリーツリーになっちゃったなぁ。むずかし。

**デフォルトの名無しさん** · 2017/07/09(日) 10:55:01.51

>>344
考え直したら面倒じゃなかった

>>334 C++
http://codepad.org/k0Sq8Fqo

N=10000くらいまでなら現実的な時間で計算出来そうだ

**デフォルトの名無しさん** · 2017/07/09(日) 11:25:12.20

N=100000, 1億桁のくらいなら現実的な時間で出来る

丸めは切り捨て？四捨五入？

**デフォルトの名無しさん** · 2017/07/09(日) 11:33:40.13

ルートの計算は速い
整数のルートは特に速い

**346** · 2017/07/09(日) 12:21:20.78

>>347
GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので
floor() であらかじめ切り捨ててから get_str() した

**デフォルトの名無しさん** · 2017/07/09(日) 12:57:37.64

ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか?
連続するゼロの個数の最大だろ?
無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。

**デフォルトの名無しさん** · 2017/07/09(日) 13:14:46.15

最大って何の話しとるんや

**デフォルトの名無しさん** · 2017/07/09(日) 13:28:51.97

もとめる桁数のほうに上限があったのか、それを見逃してた。

**デフォルトの名無しさん** · 2017/07/09(日) 13:45:03.68

連続する個数でもないぞw

**デフォルトの名無しさん** · 2017/07/09(日) 13:51:59.10

どっちも間違えたな、ゼロの総数だったか。

**デフォルトの名無しさん** · 2017/07/09(日) 19:14:37.92

>>349
floorを行った後の結果に誤差は無い
という検証は出来てるの？
何もしてないなら、それはたまたま偶然当たったっていうだけだぞ

ていうか、君には聞いてない
出題者の意図を聞いてる

**デフォルトの名無しさん** · 2017/07/11(火) 15:16:56.21

√2でなるべく長い0の連続をみつけるは?

**デフォルトの名無しさん** · 2017/07/11(火) 15:49:47.43

>>355
君には向いて無いよ

◆QZaw55cn4c · 2017/07/11(火) 16:29:49.99

>>355
>floorを行った後の結果に誤差は無い
>という検証は出来てるの？

ぱっとみ当然だと思うんだが

>>356
何桁求めるか指定しないと意味がないのでは？

◆QZaw55cn4c · 2017/07/11(火) 16:35:18.57

>>358
ん、考え直した
10進に変換した結果にて 99999 とかが末尾にあるようでは、余分の計算はしないといけないね

**デフォルトの名無しさん** · 2017/07/11(火) 18:55:08.87

[][Tebla][]

}

000-"Yob*RtStrike"[%Kil\]MO,fla>%$9999VLTS

001-GYORLith"0\R"/"ESUBA"%$%

HADO-"EM","L","O","NU"###END

**デフォルトの名無しさん** · 2017/07/14(金) 06:57:35.22

>>296
http://ideone.com/VzYVY9
C++。解けた気がする。
状態をメモ化してみた。
何で動いてるのか自分でもよくわからない。
暇だったので解いてみた。

**デフォルトの名無しさん** · 2017/07/14(金) 07:42:51.88

あー多倍長精度演算ほしー。もちろん標準で。

◆QZaw55cn4c · 2017/07/14(金) 07:55:58.80

>>362
私も欲しかったので作ってしまった、今 >>334 を奮闘中

**デフォルトの名無しさん** · 2017/07/14(金) 07:56:52.78

>>363
それはすごいな。
後々破棄するようなものを作るモチベーションが出てこないよ。

**デフォルトの名無しさん** · 2017/07/14(金) 07:57:44.37

>>364
書き捨てに慣れてしまったんだ‥

**デフォルトの名無しさん** · 2017/07/14(金) 07:59:21.83

>>365
あはは・・・。
コード書き捨てるのは良いけど、道具書き捨てるのは俺には向いてないわ。
なので、標準待ち。

**デフォルトの名無しさん** · 2017/07/14(金) 09:33:33.04

boostという任意倍長の計算Libraryがあります。
C++では使えるそうです。

**デフォルトの名無しさん** · 2017/07/14(金) 09:38:45.73

>>367
Boostも良いんだけどね。残念なことにあれは実験環境で準標準って扱いなんだよなぁ。
あれから取り入れられるライブラリも多いんだけど、標準じゃないからね。
残念なことに。

**デフォルトの名無しさん** · 2017/07/14(金) 12:49:16.12

まあ標準ライブラリしか使わない縛りをしたければ好きにすればいいんじゃない？

**デフォルトの名無しさん** · 2017/07/14(金) 14:27:07.19

車輪の再発明

**デフォルトの名無しさん** · 2017/07/14(金) 14:31:43.15

競プロみたいな相手方の環境使う物だと標準と準標準の差はでかい
自分の環境なら導入すればいいだけだが

◆QZaw55cn4c · 2017/07/14(金) 18:52:31.62

>>370
個体発生は系統発生を繰り返す

**デフォルトの名無しさん** · 2017/07/15(土) 12:42:06.98

>>361
厳密解を出しているのなら、チャレンジ
(わかって近似値解狙いなら気にしないで)

"14432" と "887654329"

両方とも既出の"貪欲つぶし"(?)数列

"14432"は 20秒 (ゼロインデック順で02341)
"887654329"は 80秒(同123456708)でいける。

**デフォルトの名無しさん** · 2017/07/15(土) 14:59:21.20

>>373
http://ideone.com/cBzPSj
C++。それ解くとほかの問題が解けなくなる。
厳密解のつもりだったが、ちょっと自分の領分超えてるなぁ。
うまくいかないものだ。
真実が奥の方にあると貪欲法は弱いな。Orz

**デフォルトの名無しさん** · 2017/07/16(日) 16:33:07.01

お題：
自分用多倍長整数演算関数

…って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの
制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。

**デフォルトの名無しさん** · 2017/07/16(日) 18:30:49.57

多倍長整数演算がサポートされている言語を使う

終わり

◆QZaw55cn4c · 2017/07/16(日) 18:54:09.85

>>375
C++98 http://codepad.org/hUObVCsR
オートボクシング等はなく便利にはできていない．

**デフォルトの名無しさん** · 2017/07/16(日) 20:34:05.63

掛け算の実装がキモだろう。
ここがボトルネックになるはず。
ここができると円周率とか、ルート計算も高速化できるはず。

◆QZaw55cn4c · 2017/07/16(日) 20:36:24.09

>>378
うん，FFTを使うそうだが‥いまいちよくわからない

**375** · 2017/07/16(日) 20:41:46.81

>>376
仕事で言語を選べる立場になってみたいものだわ。
この言語でやってってののは多々あるけど…orz

>>377
Karatsuba-Ofman法を目指してごーごー

**デフォルトの名無しさん** · 2017/07/17(月) 22:48:25.95

>>296
手計算で計算出来るレベルにまで計算量を減らせた
もちろん数学的な裏付け付きで
ある条件を見たせば一瞬で求まる

"123456789123456789" > 98秒
残念ながら、これだけはその条件を満たしてない

**デフォルトの名無しさん** · 2017/07/18(火) 06:37:17.84

>>381
22とか2323もその条件を満たしてない感じ？

**デフォルトの名無しさん** · 2017/07/18(火) 07:37:05.09

22 は微妙
2323 は大丈夫

**デフォルトの名無しさん** · 2017/07/18(火) 07:41:44.22

まだコードになってないんで、
コードになったらアップします

寿司を食べる時間 < レーンの回転周期
という前提をつけちゃおうと思ったけど、
つけない方が良さそうですね

寿司を食べる時間がレーンの回転周期の整数倍の寿司は
ちょっと特別な処理が必要

**デフォルトの名無しさん** · 2017/07/18(火) 08:01:32.43

整数倍の寿司が無いもので
条件に当てはまらない最小は
2222
かな

**デフォルトの名無しさん** · 2017/07/18(火) 08:49:51.93

>>334 SageMath
ttps://sagecell.sagemath.org/?q=brdclf

普通に(？)多桁のisqrt()なので何の捻りも無し。

**386** · 2017/07/18(火) 09:39:56.20

>>339
つ mpz_sqrt()

**デフォルトの名無しさん** · 2017/07/19(水) 18:12:29.37

>>296
>>373
http://ideone.com/B9vl8l
C++。結局、i7-6700のmem2G使って7分で解けた。
どうしようもない位遅いな。
でも一応題意には添えたと思う。
もう見たくない・・・。Orz

高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。
よくわからんけど、数学で頑張ってる人に期待だ。

**386** · 2017/07/20(木) 01:57:16.81

100のべき乗に変更
ttp://sagecell.sagemath.org/?q=mciykc

**デフォルトの名無しさん** · 2017/07/21(金) 15:21:18.13

>>296
http://ideone.com/mXPglY
C++。試しに再起化してみたら処理速度倍になった。
自分の環境では3分ちょいで解ける。
相変わらずメモリ馬鹿食いするけど。
もう俺には無理。

俺の中では終了でーす。Orz

**デフォルトの名無しさん** · 2017/07/22(土) 08:54:36.28

>>388
数学で頑張ってる人だけど、
もうちょっとまって

>>296の問題だけなら簡単だけど、
まだ全体を解明できてない

というか、忙しくて>>381から進んでない

**デフォルトの名無しさん** · 2017/07/22(土) 08:55:28.19

このスレが無くならないうちに解明します

**デフォルトの名無しさん** · 2017/07/22(土) 10:43:30.03

>>391
wktkデス！
コード見るのが好きなのでぜひ完走していただけたらと思います。

**デフォルトの名無しさん** · 2017/07/23(日) 11:26:56.94

>>375
のほかの実装はでてこないねぇ‥

**デフォルトの名無しさん** · 2017/07/23(日) 12:53:55.68

>>394
使えるコードにするためには、規模がでかくなりすぎるから

**デフォルトの名無しさん** · 2017/07/23(日) 14:15:20.13

C/C++ で最長1000行ぐらいとみて、2日ぐらいあれば、とりあえず動く
土日で仕上がってくるんじゃないかと期待してたんだが

**デフォルトの名無しさん** · 2017/07/23(日) 14:18:11.58

速度が考えられてないコードなんて実用にはならないよ

**デフォルトの名無しさん** · 2017/07/23(日) 14:21:31.79

ていうか、
コードに対する条件とか
サポートする機能とか
条件が無さすぎる

**デフォルトの名無しさん** · 2017/07/23(日) 14:24:57.75

速度‥か‥

どうしてもローテートとかキャリーフラグとかを使いたいから、これはアセンブラの領域になるね
よくみかけるアセンブラ中毒者が今頃爪を研いでいるのだろうか？

**デフォルトの名無しさん** · 2017/07/23(日) 14:25:42.29

>>398
そこは「自分用」だから自由に決めていいんでないかい？

**デフォルトの名無しさん** · 2017/07/23(日) 14:49:34.77

>>394

当日に >>305 で >>390 より10倍以上早いのがでているだろう。
しかも計算量まで書いてある

**デフォルトの名無しさん** · 2017/07/23(日) 14:53:19.94

>>401
お題が違うのでは？

**デフォルトの名無しさん** · 2017/07/23(日) 15:05:28.62

>>402 >>394
確かに違った、すいません。

c++多倍長なら、karatsubaにも対応して300行くらいの以下をパクって使うのも一案

http://sites.google.com/site/indy256/algo_cpp/bigint

**デフォルトの名無しさん** · 2017/07/23(日) 15:09:21.91

>>403
base 10進ならば、表示（operator<<) が楽でいいね、なるほど、それは思いつかなかった

**デフォルトの名無しさん** · 2017/07/23(日) 16:51:44.88

>>399
通常、
処理時間のほとんどが乗算
乗算のほとんどがFFT
アセンブラの出番は当分先

**デフォルトの名無しさん** · 2017/07/23(日) 16:52:43.21

FFTのライブラリをどこからか持ってくるのでもいいけど、
それなら素直に多倍長ライブラリを持ってくれば
ってことになる

**デフォルトの名無しさん** · 2017/07/23(日) 16:54:07.19

今は浮動小数点演算が速いので、
カラツバの出番はあまりない

**デフォルトの名無しさん** · 2017/07/23(日) 18:50:17.74

基数を10のべき乗にするとか(printf()的なものが簡単だから)、乗算はunsigned shortやintとの
乗算に限るとか、除算無しとかいうのは…

プログラムの本体に組み込まれてしまって、再利用可能なライブラリの形で括りだされてる事の
方が少ないかｗ

**デフォルトの名無しさん** · 2017/07/24(月) 00:48:44.80

>>6-285 SageMath
ttp://sagecell.sagemath.org/?q=veftjc

**デフォルトの名無しさん** · 2017/07/24(月) 18:24:00.06

>>408
裁定ラインとしては、乗算は Bigint×Bigint、および除算の実装ですかね、でも足し算の回数での乗算や引き算の回数での除算は嫌ですね

**デフォルトの名無しさん** · 2017/07/24(月) 18:58:12.05

お題：お題スレ3の>>170をファレイ数列を使って解く。
http://peace.2ch.net/test/read.cgi/tech/1390525149/170

**デフォルトの名無しさん** · 2017/07/24(月) 19:10:35.21

>>411 Ruby
def farey_sequence(n)
(1..n-1).map{|i| 1r*i/n}
end

def ans_411(m)
(2..m).map{|i| farey_sequence(i)}.flatten.uniq.sort
end

ans_411 3 #=> [(1/3), (1/2), (2/3)]
ans_411 5 #=> [(1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5)]

**デフォルトの名無しさん** · 2017/07/24(月) 19:11:05.16

>>296
超高速版が出来ました！
http://ideone.com/FrRkof

一皿9秒が上限であれば、計算オーダーはn
関数自体は何秒でも大丈夫です

コードだけじゃ意味がわからないでしょうけど、とりあえずコードだけ
あまりテストしてないので、バグってたらごめんなさい

**デフォルトの名無しさん** · 2017/07/24(月) 23:00:47.69

オーダーnは凄いな

**デフォルトの名無しさん** · 2017/07/25(火) 05:40:32.49

>>413
うーんわからん。
俺の思考とは別系統かな。
ホントに0秒で解けてるし、素晴らしい。
素直に賞賛。

**デフォルトの名無しさん** · 2017/07/25(火) 11:52:16.57

回転寿しの問題は、部分的な最短経路が全体の最短経路にならないんだよな
だが最短時間はレーン長の2倍程度の再帰回数で出る
そのあと数十億回再帰して総当たりしてもそれより短くならない
最後の皿から逆方向に探索してもおそらく同じ状況

**デフォルトの名無しさん** · 2017/07/25(火) 11:56:47.84

例えば、”122” は最短時間6だが、1周目で2番目の要素”2”をパスしないとそうならない

**411** · 2017/07/26(水) 19:54:35.63

>>412
ファレイ数列の中間数(mediant)を再帰的に生成すると、uniqもsortも要らないのだけど、
mが3や5だと大差無いかｗ

**デフォルトの名無しさん** · 2017/07/26(水) 20:50:49.45

>>411
リンク先が見えません
問題文をもう一回書いてください

**デフォルトの名無しさん** · 2017/07/26(水) 20:52:34.29

と思ったら見れました

ファレイ数列を使って何かを解くわけじゃなくて、
ファレイ数列を求める問題？

**411** · 2017/07/26(水) 23:20:07.89

>>420
元の問題はそういうもの(＝ファレイ数列の両端(0/1と1/1)無し版を求める問題)と
解釈してますです。