プログラミングのお題スレ Part11

1 名前：デフォルトの名無しさん mailto:sage [2018/04/24(火) 20:45:14.49 ID:ZY7R7Sru.net] プログラミングのお題スレです。 前スレ プログラミングのお題スレ Part10 https://mevius.5ch.net/test/read.cgi/tech/1514772904/ 【出題と回答例】 1 名前：デフォルトの名無しさん 　　お題：お題本文 2 名前：デフォルトの名無しさん 　　>>1 使用言語 　　回答本文 【ソースコードが長くなったら】 (オンラインでコードを実行できる) https://ideone.com/ codepad.org/ compileonline.com/ rextester.com/runcode https://runnable.com/ https://code.hackerearth.com/ melpon.org/wandbox https://paiza.io/ 宿題は宿題スレがあるのでそちらへ。 231 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 19:28:18.08 ID:bfgs8qRD.net] >>224 >>212 … (ry > {4,3,2,1,0} > => 10.9371 //{0,1,3,4,2} ＿＿＿＿＿＿＿＿＿~ ~ 232 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 19:30:41.81 ID:intU8xfF.net] >>225 あー。ちょっと違うな。崖作らずに山作る感じか。 証明できんけどw 233 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 20:02:43.46 ID:ja0hTifx.net] >>226 「大きい方から順に取って、既存の列の大きい端の外側に配置」を繰り返せばいい 0 1 2 3 4 のときは 4 4, 3 2, 4, 3 2, 4, 3, 1 0, 2, 4, 3, 1 この時の面積は 1/2・sin 72° ・(0*2+2*4+4*3+3*1+1*0) = 10.9371 234 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 20:20:59.85 ID:E/2WxUaU.net] ググったら公式出てきた chaoxuprime.com/posts/2012-08-08-maximize-the-area-of-a-radar-chart.html プログラムでやるなら、数列の前項後項の積和を最大化する方針がいいのかな 235 名前：225 mailto:sage [2018/05/02(水) 20:32:00.70 ID:QUr6vWwN.net] 面倒なので証明しないで全パターンの面積を求めて最大のやつを出すように作ろうかと思ったが、 腹が減ったので飯食ってから考えよう。(というかこうするならほとんど考える必要ないなこれw) 236 名前：211 mailto:sage [2018/05/02(水) 20:37:30.10 ID:lkl981AK.net] 問題思いついた後、ググって>>228見つけたので出題した次第です。 最小化については上手い方法があるんだろうか？ 237 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 20:44:42.35 ID:ja0hTifx.net] >>228 そのπってのが真ん中から左右に配置して行くインデックス列。 でその証明は不完全(*1)だけど結論は合ってる。 (*1) n-1個の時の最大になる列のどこかに n番目の数を挿入すればn個の時の解が得られる、 ということを証明せずに利用している。 小さくするには山谷の数を多くする(小さいのと大きいのがなるべく隣接するように置く) ってことは直感的にわかるんだけど具体的な構成法は考察がいるな 238 名前：デフォルトの名無しさん mailto:sage [2018/05/02(水) 22:20:26.25 ID:hcdKMJ5x.net] >>212 Squeak/Pharo Smalltalk | fn | fn := [:arr | | strm res | strm := arr sorted readStream. res := OrderedCollection withAll: (strm next: 3). [strm atEnd] whileFalse: [ | next foundPos | next := strm next. foundPos := (1 to: res size) detectMax: [:idx | | a1 a2 | (a1 := res at: idx) + (a2 := res atWrap: idx+1) * next - (a1 * a2)]. res add: next afterIndex: foundPos ]. res := res asArray. (res * (2 * Float pi / res size) sin * ({res last}, res allButLast) / 2) sum -> res ]. fn value: #(4 3 2 1 0). "=> 10.937149937394265->#(0 1 3 4 2) " fn value: #(10 0 0 10 10 0 10 10). "=> 141.42135623730948->#(0 10 10 10 10 10 0 0) " fn value: #(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16) "=> 280.6982976397934->#(1 2 4 6 8 10 12 14 16 15 13 11 9 7 5 3) " 239 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 00:37:28.69 ID:hmU6w2gD.net] >>231 最小を目指して, 山谷の数を多くしてみました. (defun f2 (a) (let* ((b (sort (copy-seq a) #'<)) (c (/ (length b) 2)) (d (let ((e (subseq b 0 c))) (apply #'append (mapcar (lambda (x) (let ((y (pop e))) (if y (list x y) (list x)))) (reverse (subseq b c)))))) (h)) (loop for i from 0 below (length d) do (setq h (if (or (= (% i 4) 1) (= (% i 4) 2)) (append h (list (nth i d))) (append (list (nth i d)) h)))) h)) (f2 '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)) (8 10 6 12 4 14 2 16 1 15 3 13 5 11 7 9) (g (f2 '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))) 157.47423241823444 240 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 00:59:37.08 ID:SwM9YWB0.net] >>207 Bash https://ideone.com/ljYBHK エラーには目を瞑ってください 241 名前：デフォルトの名無しさん [2018/05/03(木) 01:32:09.14 .net] >>234 無為に捨てられる何千もの’Hello, World!’がかわいそうすぎね？(´；ω；｀) 242 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 01:32:43.19 ID:rKkc5eBg.net] >>212 Perl5 https://ideone.com/cMJGDR 自力で動的計画法による解法を考えようとしていたけど、 >>228で紹介されたWEBの解法に勝る見込みが無さそうなので 思考を停止してWEBの解法を愚直に実装したものです 243 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 09:34:11.17 ID:dYPbvGoR.net] 【お題】 与えられた整数のリストで、 2つの要素の和が100になるすべての組を列挙せよ。 例： [1, 99, 20] -> [ 244 名前：[1, 99]] [62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40] -> [[40, 60], [-16, 116], [-81, 181]] [100, 0, 100, 0] -> [[0, 100], [0, 100], [0, 100], [0, 100]] [] [ここ壊れてます] 245 名前：デフォルトの名無しさん [2018/05/03(木) 10:12:06.60 ID:6SfrUic2.net] >>237 Rust https://play.rust-lang.org/?gist=29b80b217f269f6ad43a712d52fd595e 246 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 10:13:33.58 ID:ngB6qDho.net] >>237 ruby https://ideone.com/Noq7GJ 247 名前：デフォルトの名無しさん [2018/05/03(木) 10:19:06.64 ID:m6mdbiEz.net] >>237 Ruby。 ary.combination(2).select{|x|x.inject(:+)==100} 248 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 10:45:51.16 ID:uFV+Z8SY.net] >>237 Squeak/Pharo Smalltalk | fn | fn := [:arr | | bag | bag := Bag new. arr combinations: 2 atATimeDo: [:comb | comb sum = 100 ifTrue: [bag add: comb sorted]]. bag asArray ]. fn value: #(1 99 20). "=> #((1 99)) " fn value: #(62 116 181 86 60 98 -16 73 131 16 80 -81 40). "=> #((-81 181) (-16 116) (40 60)) " fn value: #(100 0 100 0). "=> #((0 100) (0 100) (0 100) (0 100)} " 249 名前：デフォルトの名無しさん [2018/05/03(木) 11:34:54.61 .net] >>237 C言語 https://ideone.com/Ohue7U 250 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 13:12:32.47 ID:N6jONgbj.net] >>237 Perl5 use Data::Dump 'dump'; for ([1, 99, 20], [62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40], [100, 0, 100, 0]) { sub c {my $d = shift; my @l = c(@_) if 1 < @_; @l, map{[$d, $_]} @_}; @s = grep{100 == $$_[0]+$$_[1]} c @$_; print dump($_)."\n->".dump(\@s)."\n"; } 実行結果 $ perl 11_236.pl [1, 99, 20] ->[[1, 99]] [62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40] ->[[60, 40], [181, -81], [116, -16]] [100, 0, 100, 0] ->[[100, 0], [0, 100], [100, 0], [100, 0]] ※実行にはperlのData::Dumpモジュールが必要ですが、 　Ideoneのperl 24にはインストールされてないようでした 251 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 13:15:16.16 ID:ngB6qDho.net] >>237 c https://ideone.com/c5I9TG 252 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 14:31:25.30 ID:M52LYEAa.net] >>237 javascript var f = l => { console.log( l.reduce((acc, m, i, ary) => [ ...acc, ...ary.slice(i+1) .filter(n => m + n == 100) .map(n => [m, n]) ], [] ) ) } f([1, 99, 20]) //=> [[1, 99]] f([62, 116, 181, 86, 60, 98, -16, 73, 131, 16, 80, -81, 40]) //=> [[116, -16], [181, -81], [60, 40]] f([100, 0, 100, 0]) //=> [[100, 0], [100, 0], [0, 100], [100, 0]] 253 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 14:55:50.12 ID:cjR1ezGU.net] Smalltalk のメソッドの充実っぷりには毎回感心 254 名前：デフォルトの名無しさん mailto:sage [2018/05/03(木) 18:28:55.09 ID:qi+bYfi0.net] それなりの規模の処理系（GUI付きOSモドキ）をセルフホスティングで構築・維持していると イディオムがイディオムとして認識・共有されやすく、さらにメソッドとしてまとめられやすいのかも たとえばスクリプト言語処理系でしかないGNU Smalltalkはあまり便利メソッドが増える感じがしないので 255 名前：デフォルトの名無しさん [2018/05/04(金) 19:54:42.66 ID:4Zt1BODM.net] お題 10,000個の単純変数に1から10,000の整数を代入する 256 名前：デフォルトの名無しさん mailto:sage [2018/05/04(金) 20:34:39.46 ID:6j9W/G+p.net] >>248 Ruby (1..10000).each{|i|instance_variable_set("@v#{i}", i} 257 名前：デフォルトの名無しさん [2018/05/04(金) 20:41:53.19 ID:LfImqqRO.net] >>248 Common Lisp https://ideone.com/tM8Nve 258 名前：デフォルトの名無しさん [2018/05/04(金) 20:52:57.61 ID:LfImqqRO.net] >>248 Bash ideone だと駄目だった https://ideone.com/FTnIoN 259 名前：デフォルトの名無しさん [2018/05/04(金) 21:16:29.34 ID:sij7cbOA.net] >>248 Perl for(1..10000){eval”\$a$_=$_”} こんなんでいいのか 260 名前：？ [] [ここ壊れてます] 261 名前：デフォルトの名無しさん [2018/05/04(金) 21:23:10.57 ID:sij7cbOA.net] >>251 シェルもperlみたいにeval使えば簡単だと思うよ。その他の言語も同様。 てかこれ、インタープリタの言語にはできてもコンパイルする言語の場合は普通の方法ではできないんじゃないかな。 トリッキーな方法使ってようやっとできるかも知れないって感じじゃないだろうか。 262 名前：デフォルトの名無しさん [2018/05/04(金) 21:49:18.32 .net] Cプリプロセッサでもやろうと思えばできるけど面倒だからやらない 263 名前：デフォルトの名無しさん mailto:sage [2018/05/04(金) 21:57:55.58 ID:mhxe2Hc6.net] お題：パイ生地を折り畳め ただし要素数は二個以上で偶数とする 気が向いた人は逆の操作も実装せよ https://ideone.com/W9woGu 264 名前：デフォルトの名無しさん [2018/05/04(金) 22:02:19.57 ID:sij7cbOA.net] >>255 問題の意味がわからん 265 名前：デフォルトの名無しさん [2018/05/04(金) 23:16:59.35 .net] >>256 分からないときは好きに解釈していいのがこのスレのルール 266 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 00:33:22.15 ID:1BpKS+ks.net] >>255 Perl5 sub f {pop, shift, @_ ? f(@_) : ()} sub g {@_ ? do{my $a = shift; shift, g(@_), $a} : ()} use feature 'say'; sub pai { say "@pai"; @pai = f(@pai); say "@pai"; @pai = g(@pai); say "@pai"; } @pai = qw{1 2 3 4 5 6}; &pai; @pai = qw{a b c d e f}; &pai; 実行結果 $ perl 11_254_1.pl 1 2 3 4 5 6 6 1 5 2 4 3 1 2 3 4 5 6 a b c d e f f a e b d c a b c d e f 267 名前：デフォルトの名無しさん [2018/05/05(土) 01:53:30.67 ID:ia6t0Ogc.net] f, g のような変換関数を作ること自体は簡単な感じがするが、それと「パイ生地の折り畳み」がどう関係するのかがわからんな。 単にここでは折り畳んだらそういう並びになるというルールなだけ？ 268 名前：デフォルトの名無しさん [2018/05/05(土) 01:54:26.33 ID:0a7ZDXtf.net] >>255 Common Lisp https://ideone.com/cabI9c 269 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 02:02:07.19 ID:1dAfhim4.net] 半分に折る->後半部を逆順に 折重ねたまま元の大きさまで伸ばす->前半部に合成 パイ生地の作り方からの連想だとは思う 270 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 02:08:07.54 ID:j/DSqy58.net] >>248 javascript eval('var ' + [...Array(10000)].map((_, i) => `a${i+1}=${i+1}`).join()) >>253の通りやった 271 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 02:13:33.62 ID:1BpKS+ks.net] >>259 分からないと言うことをいろいろ言うつもりは無いけどｍ >>255 のレスの内容とoctaveのコードから考えて 1 2 3 5 6 をパイ生地のように二つに折り畳んだ 1 2 3 6 5 4 を（下を先に選択して）リストで表すと 6 1 5 2 4 3 だということは想像に難くないので、そう解釈して解答を考えた。 gはその逆。誤解はあるかもしれない。 講釈がコードより長くなったけど、 「だけ？」って一体どういういみだよ？ 272 名前：デフォルトの名無しさん [2018/05/05(土) 02:43:53.26 ID:ia6t0Ogc.net] >>263 「パイ生地の折り畳み」という言葉に他の意味がないかってこと。 273 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 07:20:49.47 ID:lTVCLXC3.net] >>255 J l =: -: * -.@(2&|) r =: (# - -:@>:) * 2&| p_fold =: {~((l+r)@i.@#) 折りたたみちょっと面白いね 何度か繰り返し適用すると元に戻る 例えば4つだと p_fold^:3 (1 2 3 4) => 1 2 3 4 と3回適用すると元に戻る (^:n ってのはn回適用するJの仕組み) 同様に p_fold^:5 (1 2 3 4 5 6) =>1 2 3 4 5 6 p_fold^:4 (1 2 3 4 5 6 7 8) => 1 2 3 4 5 6 7 8 p_fold^:9 (1 2 3 4 5 6 7 8 9 10) => 1 2 3 4 5 6 7 8 9 10 274 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 10:31:30.99 ID:5+ZWBL/x.net] >>255 Ruby 条件分岐を使わずにindexのみから求めてみた f=->a{a.size.times.map{|i|a[(i&1)*i-i/2-1]}} g=->a{(s=a.size).times.map{|i|a[~(4*i-2*s+3).abs/2]}} p f[[*1..6]] #=> [6, 1, 5, 2, 4, 3] p g[f[[*1..6]]] #=> [1, 2, 3, 4, 5, 6] 275 名前：デフォルトの名無しさん [2018/05/05(土) 11:51:20.86 .net] >>255 C言語 https://ideone.com/frCiwG 276 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 14:19:41.02 ID:E0VTmDdu.net] >>255 Squeak/Pharo Smalltalk | f g pie | f := [:arr | ((1 to: arr size) collect: [:idx | arr perform: (#(atLast: at:) atWrap: idx) with: (idx / 2) ceiling] ) as: arr species ]. g := [:arr | (((1 to: arr size) select: #even), ((1 to: arr size) select: #odd) reversed collect: [:idx | arr at: idx] ) as: arr species ]. pie := 'abcdefg'. pie := f value: pie. "=> 'gafbecd' " g value: pie. "=> 'abcdefg' " pie := (1 to: 7). pie := f value: pie. "=> #(7 1 6 2 5 3 4) " g value: pie. "=> #(1 2 3 4 5 6 7) " 277 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 16:41:53.04 ID:YacZpoVZ.net] >>255 Squeak/Pharo Smalltalk >>266っぽい方針も入れて書き直し | f g pie | f := [:arr | ((1 to: arr size) collect: [:m | arr atWrap: m * m even asBit - (m // 2)] ) as: arr species ]. g := [:arr | ((2 to: arr size by: 2), (1 to: arr size by: 2) reversed collect: [:idx | arr at: idx] ) as: arr species ]. pie := 'abcdefg'. pie := f value: pie. "=> 'gafbecd' " g value: pie. "=> 'abcdefg' " pie := (1 to: 7). pie := f value: pie. "=> #(7 1 6 2 5 3 4) " g value: pie. "=> #(1 2 3 4 5 6 7) " 278 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 17:07:44.87 ID:ZO4AhgIr.net] >>266ってどういう計算してんの？ 279 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 17:25:53.15 ID:Js8QmTUw.net] お題 N×Mのフィールドが与えられる。各マスの意味は以下の通りとする。 'S'：始点 'G'：終点 '.'：通行可 '#'：通行不可 連続して同じ方向に進むことができないという制約下で、 始点から終点までの最短距離を求めよ。 [example 1] S.... #.... ..#.. ....G => 9 [example 2] S.....G ....... => 12 280 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 17:33:36.44 ID:5+ZWBL/x.net] >>270 配列の長さを L とすると、 f(パイをたたむ)は； i(0 <= i < L)番目の要素を元の配列の (~...~[i / 2]) % L 番目から持ってくればよい (~...~はビット反転を i 回繰り返したもの) g(パイを開く)は； i(0 <= i < L)番目の要素を元の配列の (- 0.5 - |2 * i - L + 1.5|) % L 番目から持ってくればよい 281 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 18:32:03.46 ID:sJdk0i7H.net] [][][] [[[ ] X_[[[ [] ][ [] ][][[[] 282 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 18:51:54.01 ID:c0K4Xq7n.net] 今抱えてる課題 1から100までインクリメントする変数iを用いて 300から1までの実数を100個出力せよ i=1の時は300 i=100の時は1 となる式を考えてちょ(人･ω･)☆ 283 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 19:03:50.73 ID:1st6shTW.net] >>274 300 - (299.0 / 99.0) * (i - 1) 284 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 19:06:07.33 ID:j/DSqy58.net] お題：文字駒を滑らせろ 四方を囲いで被われ駒がこぼれる心配のないM×Nマスのボードがある。 ここに英小文字が印字された正方形の駒が適当に配置されている。(駒のないマスは.(ドット)で表す) 与えられる、ボードを傾ける指示を完遂したときの最終盤面を表示せよ。 指示の方向はU(向かい方向)、D(手前方向)、L(左方向)、R(右方向)の四種類。 例1) solve([ '...', '.a.', '...', ], 'UR') // ↓ // [ // '..a', // '...', // '...', // ] https://jsfiddle.net/en6rd3vk/ ※盤面は文字列の配列にしているが文字の配列の配列など言語で扱いやすいよう好きにしてよい 例2) solve( [".....", ".d.i.", "kmegk", "..tu."], "LRRLLUDRRLRLRRURRRRLLLRULDUDULDLLRDULURULUDLDLU 285 名前：DDL" ) //=> [".....", "gk...", "km...", "dietu"] 暇な人は300×300、指示数50くらいでやってみてください。最適化しないと結構時間かかっちゃうと思いますが。 [] [ここ壊れてます] 286 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 19:17:21.84 ID:c0K4Xq7n.net] >>275 ありがとうございます(^○^) 範囲を等分してiと合わせるだけだったんですね これを思いつかないとは・・・寝てきます(・_・;) 287 名前：デフォルトの名無しさん [2018/05/05(土) 19:38:36.14 ID:ia6t0Ogc.net] >>255 色々な言語で書いてみたが、やってることはほとんど同じ。 それぞれの言語の特徴をあまり生かせてない感じがする。 C https://paiza.io/projects/zsjD__CUc4kIlaDd-nYgQQ Kotlin https://paiza.io/projects/ncCwkTCvQ0IsNcZGbpy_vw Perl https://paiza.io/projects/C9lzimZEAZzk25gjn4NGfw 288 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 20:28:32.99 ID:MmzVJzsz.net] >>271 Ruby 愚直に https://ideone.com/SYfrSu 289 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 20:59:38.12 ID:a4pX7/xy.net] >>271 Squeak/Pharo Smalltalk https://ideone.com/ACAeKW 290 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 22:20:56.64 ID:MmzVJzsz.net] >>276 Ruby 傾ける順番だけ最適化 https://ideone.com/4iIY9g 291 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 22:58:44.12 ID:Js8QmTUw.net] お題 Y円を支払うとき、同種の通貨の枚数を最小化する。 Y=500 => 1 (500*1, 同種の通貨は最大1枚) Y=300 => 2 (2*100+2*50, 同種の通貨は最大2枚) Y=40 => 3 Y=60 => 1 292 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 23:08:19.67 ID:MmzVJzsz.net] >>282 通貨の種類は 1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000？ 293 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 23:19:24.99 ID:Js8QmTUw.net] >>283 それでいいです。任意の種類に対応できたら尚良し 294 名前：デフォルトの名無しさん mailto:sage [2018/05/05(土) 23:53:24.33 ID:gS+4uwRv.net] >>282 => 0 (カード決済または電子マネー決済) 295 名前：デフォルトの名無しさん [2018/05/06(日) 00:22:26.26 .net] >>271 C言語 https://ideone.com/YLAnLJ 296 名前：デフォルトの名無しさん [2018/05/06(日) 01:34:21.80 .net] >>282 C言語 https://ideone.com/RVA3Mk 297 名前：デフォルトの名無しさん [2018/05/06(日) 01:45:52.35 ID:Bse1bLkg.net] >>276 Kotlin https://paiza.io/projects/gVAA38huK6qosFkqbihPTg ボードの内容と傾ける指示は全て標準入力から入力するようにした。 298 名前：デフォルトの名無しさん mailto:sage [2018/05/06(日) 06:45:27.16 ID:lHf8cLJR.net] >>282 Ruby ぴったり払えない時は No Solutions と出力 currency = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000] sums = currency.size.times.map { |i| currency[0..i].sum } [74664, 55998, 37332, 500, 340, 300, 197, 161, 157, 60, 40].each { |yen| print '%d => ' % yen min = currency.zip(sums).reverse_each.map { |c, s| yen -= c * x = [yen/c, -(-yen/s)].min x }.max puts yen.zero? ? min : 'No Solutions' } #=> 74664 => 4 55998 => 3 37332 => 2 500 => 1 340 => 3 300 => 2 197 => 3 161 => 1 157 => 2 60 => 1 40 => 3 299 名前：デフォルトの名無しさん mailto:sage [2018/05/06(日) 08:03:16.30 ID:939GOaZM.net] >>276 一度でも水平垂直の両方に傾けると 座標じゃなくて単に駒の二次元リストでいけると思うから 指示の短縮と合わせて早くできると思うけど どう書けばいいか悩んでる・・・ 300 名前：デフォルトの名無しさん mailto:sage [2018/05/06(日) 08:16:38.56 ID:xMaBOakW.net] >>282 Ruby >>289を修正 currency = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000] samples = [74664, 55998, 37332, 500, 340, 300, 197, 161, 157, 60, 40] cands = currency.zip(currency.reduce([]){|s, e| s << s.last.to_i + e}).reverse_each breakdown = lambda do |yen| 　　x = cands.map{|c, s| yen -= c * x = [yen/c, -(-yen/s)].min; x}.max 　　yen > 0 ? 'No Solution' : x end samples.each{|yen| puts '%d => %s' % [yen, breakdown[yen]]} #=> 74664 => 4 55998 => 3 37332 => 2 500 => 1 340 => 3 300 => 2 197 => 3 161 => 1 157 => 2 60 => 1 40 => 3 301 名前：デフォルトの名無しさん mailto:sage [2018/05/06(日) 19:32:00.34 ID:9CUhRDV/.net] }]] [[《_["[[]]" 〈[]》》 [][][]0,1》》〈〉 [] } } "B,V,0%%%,*1BVLO,SASA1`}}//%\\0,1\"VL"\ 302 名前：デフォルトの名無しさん mailto:sage [2018/05/08(火) 21:21:59.59 ID:qF4LguOP.net] お題：九九の各段の値を合計せよ https://ideone.com/T3TrFG 303 名前：デフォルトの名無しさん mailto:sage [2018/05/08(火) 21:45:36.53 ID:XzXTdruW.net] >>293 @9`*45 304 名前：デフォルトの名無しさん [2018/05/08(火) 21:54:00.37 ID:rppAglGz.net] はっ。それはもしや45の倍数・・・ おや？こんな夜中に誰だ？ 305 名前：デフォルトの名無しさん mailto:sage [2018/05/08(火) 22:14:46.30 ID:8rfWV9vw.net] >>290 それって例えば初期配置が以下のとき(■が駒) □■■□□■ □□■□■□ ■■□■□■ □□■■□□ □■□■□□ ■□■□□■ 最初に例えばULが来ると以下のようになって… ■■■■■■ ■■■■■□ ■■■■□□ ■□□□□□ □□□□□□ □□□□□□ □だけの行、□だけの列はこれからハブいてループ回せるじゃんってことだよね。この例だと下二行。 なるほど命令の最適化ばっかり考えてて全然気づかなかった。 306 名前：デフォルトの名無しさん mailto:sage [2018/05/08(火) 23:30:03.25 ID:y0JbAqkN.net] >>293 Squeak/Pharo Smalltalk (1 to: 9) sum * (1 to: 9) "=> #(45 90 135 180 225 270 315 360 405) " ((1 to: 9) * (Array new: 9 withAll: (1 to: 9))) sum. "=> #(45 90 135 180 225 270 315 360 405) " ついでに全段の合計も ((1 to: 9) sum * (1 to: 9)) sum. "=> 2025 " ((1 to: 9) * (Array new: 9 withAll: (1 to: 9))) sum sum. "=> 2025 " (Matrix rows: 9 columns: 9 tabulate: [:x :y | x * y]) sum. "=> 2025 " ((1 to: 9) asArray +* (Matrix rows:1 columns: 9 contents: (1 to: 9))) sum. "=> 2025 " 307 名前：デフォルトの名無しさん mailto:sage [2018/05/08(火) 23:50:03.66 ID:XzXTdruW.net] >>276 これの最適化したいんだけど誰か大きいボードのサンプルくれないかなあ 308 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 00:00:50.01 ID:yM0yjk1d.net] 激問って未だに更新されてるんだね 309 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 00:58:06.52 ID:NS139TvC.net] >>297 Smalltalk なのに普通だ…いやtabulateが便利そう J 格段の和 +/(*/[)>:i.9 45 90 135 180 225 270 315 360 405 さらに足すと +/+/(*/[)>:i.9 2025 先に,で1次元化してから足せば1文字短く +/,(*/[)>:i.9 2025 310 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 01:51:50.10 ID:bn/AH8fd.net] >>298 すごくでかくなったので分けた。ごめんよjsfiddle... board(1980x1080, 文字列の配列形式) https://jsfiddle.net/eqyuvgm9/ actions(256) https://jsfiddle.net/2j2817rc/ result(1980x1080, 文字列の配列形式) https://jsfiddle.net/uyboko52/ このサンプルでchromeのコンソールで試した結果、 最適化なしでは47.4秒 命令の最適化だけで1.8秒になった >>290も試してみようと思う 311 名前：デフォルトの名無しさん [2018/05/09(水) 01:56:38.20 ID:qkLXPpHd.net] >>293 Kotlin (1..9).forEach { a -> println((1..9).map { it * a }.sum()) } この1行をファイルに入れて kotlinc -script でファイルを指定するとスクリプトとして実行されて計算結果が出力される。 45 90 135 180 225 270 315 360 405 312 名前：デフォルトの名無しさん [2018/05/09(水) 03:24:50.65 .net] >>293 C言語 https://ideone.com/nGbT40 313 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 04:36:36.06 ID:uBL8ccTk.net] >>293 Nim import math const s1 = (sum[int]([1,2,3,4,5,6,7,8,9])) var s=0; for i in 1..9: s+=s1; echo s 314 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 07:39:32.32 ID:LEGAA83e.net] >>301 命令はもう LDRULDRU... で与えた方がいいかもね この256文字?命令も URDLURDLU まで最適化できちゃうわけだし 315 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 14:54:31.24 ID:LEGAA83e.net] >>301 Ruby >>290を意識して最適化してみた https://ideone.com/zwyM7p 2回動かした後、適切に反転させて右下が開くようにしておけば、 abc- ed-- f--- ---- LとRは、 cba- de-- f--- ---- UとDは、 fdc- eb-- a--- ---- と垂直、鉛直方向にそれぞれ反転するだけでいい 最適化された命令は時計回りか反時計回りに回すことになるけど、((駒の数)! + 1)回以内には必ずでループするのでそれも考慮 が、1980x1080には4秒要する模様 316 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 15:06:55.92 ID:FhlfzW8k.net] >>296 マス単位で省けると思う [a....,bcd..,efghi]を[a,bcd,efghi]って表現して これを上に傾けて[acdhi,bfg,e]にする操作はこんなコードで出来る https://ideone.com/i7EmbB 他の方向へは対称性を利用すれば書けるから 今は左下に寄ってるみたいな情報を持ってればいいし その情報で行列表現にも戻せる まあ駒の数が多い場合は大して速くならないけど 317 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 15:13:44.30 ID:LEGAA83e.net] あとは2回目以降どうやって傾けても駒の配置は合同(かその反転)になるから 2回傾けた結果を使って4回目を求めて……ってやればO((駒の数)*log(最適化された命令の長さ))で済みそうだよね 318 名前：デフォルトの名無しさん [2018/05/09(水) 15:37:49.24 ID:FhlfzW8k.net] >>306 面倒なループ書かなくても反転でいけたのか・・・ 数学力が足りなかった 319 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 18:01:06.55 ID:tbbSaefy.net] >>276を>>301のボードで こういう処理はCが速かろうということで何の工夫もないコードを書いてみた アクションの最適化なしで256回動かした場合 MacBook-Pro:tmp$ time ./a.out <data.raw > r.raw real 0m0.638s user 0m0.625s sys 0m0.009s 638ミリ秒 アクションの最適化だけ実装すると MacBook-Pro:tmp$ time ./a.out <data.raw > r.raw real 0m0.045s user 0m0.037s sys 0m0.006s 45ミリ秒 https://ideone.com/bZmXpg 320 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 18:02:18.67 ID:tbbSaefy.net] 補足 256回というのは>>301にある256アクションをそのまま行うということ 321 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 19:18:52.31 ID:tbbSaefy.net] 目先を変えて Apple の GCD を使って8スレッド並列にしてみた 4コアのPCで3倍くらいになった アクションの最適化なし MacBook-Pro:tmp$ time ./c.out <data.raw > rc.raw real 0m0.218s user 0m1.190s sys 0m0.027s 218ミリ秒 アクションの最適化あり MacBook-Pro:tmp$ time ./c.out <data.raw > rc.raw real 0m0.023s user 0m0.058s sys 0m0.008s 23ミリ秒 100回繰り返すと1回あたり18msec程度になる模様 MacBook-Pro:tmp$ time for i in `seq 1 100` ; do ./c.out <data.raw >rc.raw ; done real 0m1.814s user 0m6.659s sys 0m0.589s https://ideone.com/ULrjTi 322 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 21:01:50.08 ID:28IRmfG3.net] やっぱはえ〜ｗ 323 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 21:40:14.20 ID:7NiN2gcq.net] (そして今試してわかったが dispatch_group は >>312のように使いまわさず wait 後破棄してまた create する方が高速、と) 324 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 21:57:48.63 ID:bn/AH8fd.net] スクリプト言語のわりには速いと言われるjsだけど当たり前なのかもしれないが桁違いにぜんぜん敵わんくて糞ワロタｗｗ 325 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 22:18:37.30 ID:7NiN2gcq.net] JS のは配列の初期化や文字列操作関数とかが足引っ張ってるんじゃないだろうか。 毎回メモリアロケートするからキャッシュも効きにくそうだし。 2次元配列に初期値セットしてからコードで操作した方が速い気がする。 326 名前：デフォルトの名無しさん mailto:sage [2018/05/09(水) 22:24:38.34 ID:7NiN2gcq.net] PCの速度差がかなりあるだけかも知れんし後でjs版も計測してみる 327 名前：デフォルトの名無しさん [2018/05/10(木) 08:16:30.90 .net] 各コマの最大可動範囲は最初に定まるし ターンが進むにつれ狭まりもするから それで最適化できん？ 知らんけど 328 名前：デフォルトの名無しさん mailto:sage [2018/05/10(木) 14:34:27.76 ID:qHVZoDSH.net] >>306のやり方だと二回傾けて以降は駒の入れ替えだけでいいから numpyでboard[board!='.']=np.fliplr(board)[np.fliplr(board)!='.']とかやれば速いかな インデックスは毎回計算しなくてもいいけど 329 名前：デフォルトの名無しさん mailto:sage [2018/05/10(木) 16:30:45.02 ID:qHVZoDSH.net] >>319で書いてみたけど 傾きの処理自体はC並みに速い https://ideone.com/NWCyYW 330 名前：デフォルトの名無しさん mailto:sage [2018/05/10(木) 16:47:50.18 ID:Ulb5C2sT.net] そりゃあ numpyの本体はC言語だしなぁ・・・ 331 名前：デフォルトの名無しさん mailto:sage [2018/05/10(木) 17:33:52.68 ID:qHVZoDSH.net] 本当は数値計算みたいにもっと速い命令を使ってくれるかなと期待してたんだけど そういう上手くはいかなかった

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef