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

プログラミングのお題 ..

733:デフォルトの名無しさん
15/09/05 08:35:35.11 HkcVe1Bz.net
>>695
>>696
ここは>>620 のとおりお題スレ、ならばお題の批判もありなのでは？

734:デフォルトの名無しさん
15/09/05 08:37:14.95 dxdGb8xg.net
お題が出てそれに対して批判してたらコンテストが成り立たないって話なのにアスペか？

735:デフォルトの名無しさん
15/09/05 08:58:10.81 bk65bvoQ.net
どうしてもお題を批判したいのならここで書かずにチラシの裏にでも書いとけ
皆答えてる奴がいるのに一人だけ暴れるとかキチガイかよ
それに日本語圏では4桁と3桁の間にカンマを入れるのになぜ英語で読むんだ？
頭おかしいのか？

736:デフォルトの名無しさん
15/09/05 09:54:03.65 FYG0oxrb.net
>>703-704
それはQZの思考過程がこうなってるからなんだよ
普通の人が解答を間違えた場合：「済みません間違えました」
QZが解答を間違えた場合：「俺は間違ってない。間違ってるのは出題の方だ」←実際は間違ってばかりいる
自己愛性パーソナリティ障害特有の思考回路
捏造した歴史を信じこんで真実の歴史から目をそむけているどこかの特亜人そっくりですなあ
ニンニクくさー

737:デフォルトの名無しさん
15/09/05 11:36:42.88 u8tdzSFZ.net
>>700
プログラムだけでなく、15Queenの場合の配置の一例を表示して
もらえないでしょうか。

738:デフォルトの名無しさん
15/09/05 11:36:50.97 H3Bu+jcQ.net
荒れてるところすみませんがお題です
Google Code Jamより
URLﾘﾝｸ(code.google.com)
最小スカラー積
次の2つのベクトルが与えられているとします：v1=(x1,x2,...,xn)とv2=(y1,y2,...,yn)
これらのベクトルのスカラー積は１個の数字で、x1y1+x2y2+...+xnynとして計算されます
各々のベクトルの要素は任意に並べ替えても構わないとします
入力ファイルの最初の行は、テストケース数(整数)Tが含まれています
各テストケースは、最初の行は整数nを含んでいます。次の二行は、v1とv2それぞれの座標が与えられます
出力は、各々のテストケースに対して
Case #X: Y
のようになります
ここでXはテストケース番号、Yは与えられたベクトルの全ての順列の最小スカラー積です

739:デフォルトの名無しさん
15/09/05 11:39:13.55 H3Bu+jcQ.net
制限
小さなデータセット
T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000
大きなデータセット
T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000
2種類のデータセットがあるのは、それぞれの得点が異なるからで、どちらを選択されても構いません
例
入力
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
出力
Case #1: -25
Case #2: 6

740:デフォルトの名無しさん
15/09/05 11:43:11.93 iR2NaoHp.net
>>706
横槍だけど、お題はNQueens問題であり、ユニーク解(回転したり反転すると重なる重複解)
を考慮しない置き方の数を求めるものだ
実際の配置を出力すると膨大なデータになり、時間を測定するという題意に背く事になる
この場合時間の測定は必要なくなるだろ
そんなプログラムはどこにでも転がっている

741:デフォルトの名無しさん
15/09/05 11:54:21.61 i6kEld9S.net
ユニーク解と、そうでない解の間に、たとえば4倍したら求まるといった簡単な関係があるんだっけ?
それだったらどちらでも一緒だし、そうでなければユニーク解を求めないとダメでは?
一個求めただけでもいいことにならないか?

742:デフォルトの名無しさん
15/09/05 11:58:23.07 i6kEld9S.net
Ｎクイーン問題(N Queens Problem)
URLﾘﾝｸ(www.ic-net.or.jp)

743:デフォルトの名無しさん
15/09/05 11:59:34.78 iR2NaoHp.net
この粘着具合はまたQZか
URLﾘﾝｸ(deepgreen.game.coocan.jp)
これでも読めや
題意では"ユニーク解は考慮しなくてもよい"となっている
それにケチを付けるんならてめえがユニーク解を考慮したプログラムをまず書いてから言え

744:デフォルトの名無しさん
15/09/05 12:02:22.49 iR2NaoHp.net
>>711
ちゃんと最初に"解の個数を求める"となってるね(・∀・)
ユニーク解を考慮した解の個数を求めるべきならお題にちゃんと「ユニーク解を考慮せよ」
と書いてあるはずだろ
「ユニーク解は考慮しなくてもよい」と書いてあるんだぞ
日本語読めないんでちゅか？

745:デフォルトの名無しさん
15/09/05 12:09:06.35 i6kEld9S.net
>>712
どちらもユニーク解だが。どれも同一と見なすかで解個数が違ってくるからユニークのほうがいいだろ。
鏡像は別で、回転は同一とみなす人をいるかもしれない。

PAA の概要
N=2n の場合、 N x N の N クイーン問題を 4 分割した部品(n x n の部分解)から以下の手順で合成する。
1) A と B から、2 分割した部品（n x 2n の部分解）AB を生成（上半分の合成）
2) C と D から、2 分割した部品（n x 2n の部分解）CD を生成（下半分の合成）
3) AB と CD から全体解を生成
なお、解の生成は unique 解のみに限定し、全数解は式 1 により求める。
高速化実現のポイントは、
・結合処理の高速化（特に、キャッシュミスの削減）
・代表解の判定条件による集合積演算の軽減にある。
URLﾘﾝｸ(deepgreen.game.coocan.jp)

Ｎクイーン問題(N Queens Problem)
ユニーク解から全解への展開
これまでの考察はユニーク解の個数を求めるためのものでした。
全解数を求めるにはユニーク解を求めるための枝刈りを取り除いて全探索する必要があります。
したがって探索時間を犠牲にしてしまうことになります。そこで「ユニーク解の個数から全解数を導いてしまおう」という試みが考えられます。
URLﾘﾝｸ(www.ic-net.or.jp)

746:デフォルトの名無しさん
15/09/05 12:11:11.74 iR2NaoHp.net
>>714
だからそこまでお題に背きたいんだったら改めて"ユニーク解を考慮せよ"という新しいお題を立てろ
もうこれ以上お前と議論しても無駄だ

747:デフォルトの名無しさん
15/09/05 12:11:53.03 i6kEld9S.net
Boardは四角で、ことなる四方向から観察したら直ちに同じ見え方のものが4つあるのは

748:わかる。

749:デフォルトの名無しさん
15/09/05 12:39:53.44 l/Jp8teC.net
お題
オセロの任意の局面・手盤からの最短全滅手を
求める（無い場合は無いと出力）
入力データはキーボードでもテキストファイルでも
可能
最短全滅手はすべての石が黒・白どちらかの色に
なってしまうこと。
局面は、石が連続して置かれているという条件で
あれば不能局面でも可
（ちなみに解答は知らない）

750:デフォルトの名無しさん
15/09/05 12:41:02.73 l/Jp8teC.net
石が連続してというのは
石が連結してという表現のほうが
わかりやすいか....

751:デフォルトの名無しさん
15/09/05 12:47:13.51 a9CPEVg5.net
>>717
お前が全滅すればいいのにな
完全に論破されたからと言ってまず誰も解答が付かない問題を出すとかガキかよ

752:デフォルトの名無しさん
15/09/05 12:54:53.58 nIE3Kuq7.net
>>665 Emacs Lisp
キーワード引数commaの値が689の場合は>>690と同様に動作するようになりました。
(cl-defun f (s &key comma (truncate 0))
(let* ((aaa (let ((x (string-match "[^0]" s))) (if x (substring s x) "0")))
(bbb (length aaa))
(ccc (* (ceiling (/ (float bbb) 4)) 4))
(lll (if (eq comma 689)
(let ((c 0))
(cl-map 'string (lambda (x) x)
(reverse (cl-mapcan #'(lambda (x) (prog1 (if (and (/= x 32) (/= c 0) (= (% c 3) 0)) (list ?, x) (list x)) (unless (= x 32) (incf c))))
(reverse (string-to-list aaa))))))
(format (format "%%%ds" ccc) aaa)))
(mmm (if (eq comma 689)
(split-string (let ((c 0))
(cl-map 'string (lambda (x) x)
(reverse (cl-mapcan #'(lambda (x) (prog1 (if (and (/= c 0) (= (% c 4) 0)) (list 10 x) (list x)) (unless (= x ?,) (incf c))))
(reverse (string-to-list lll)))))) "\n")
(cl-loop for i from 0 below ccc by 4 collect (substring lll i (+ i 4)))))
(fff (mapcar #'(lambda (x) (if (cl-find #x20 x) (remove #x20 x)
(if (string= (remove ?, x) "0000") "" (if (eq comma 689) x (let* ((i (string-match "[^0]" x)) (y (if i (substring x i) x)))
(if (= (length y) 4) (concat (substring y 0 1) (if (eq comma t) "," "") (substring y 1)) y)))))) mmm))
(ggg (reverse fff))
(hhh (cl-subseq ggg truncate))
(iii '("" "万" "億" "兆" "京"))
(jjj (cl-subseq iii truncate))
(kkk (cl-mapcan #'(lambda (a b) (if (string= b "") nil (list a b))) jjj hhh)))
(apply #'concat (reverse kkk))))
f
(f "1234567890" :comma t) "12億3,456万7,890"
(f "1234567890" :comma 689) "1,2億34,56万7,890"

753:デフォルトの名無しさん
15/09/05 15:47:27.36 u8tdzSFZ.net
>>709
私は15Queenの一つの例を求めているだけです、
コンピュータ内で例えば行列の形で配置を求めているならば、
その一例を表示することはできないでしょうか。
たとえば、すべての配置の数を求めた後で、その最後に求めた
配置を表示するということならば、時間はあまり掛からないと思いますが。
プログラムだけを提示されてもその言語を使える環境にないものに
とっては、このプログラムの正しさを検証するてだてがありませんので。

754:デフォルトの名無しさん
15/09/05 15:52:40.59 1TQgpEDy.net
>>721
お前どんだけしつこいんだよ
じゃお前の書いたプログラムには全くバグがないのか
仕事で書いたプログラムに不具合が見つかっても「仕様です」と言って直さないつもりか
この問題は配置を求める問題ではない
「解の個数」さえ求めればそれでいいんだ
ビットマップを使った解法は外人が世界で一番最初に考案したそうなんでこの人に
「あなたのプログラムは本当に正しいのでしょうか。配置を表示できますか。」と質問を
英語で送ってみなよ
URLﾘﾝｸ(jsomers.com)
この人がそうだ
この人の書いたプログラムと本質的には何ら変わらない
もっと速いアルゴリズムもあるが長くなるので端折っただけ
お前を見てるとお前は人に嫌われる達人だなあと心から感心する

755:デフォルトの名無しさん
15/09/05 16:13:25.93 1TQgpEDy.net
>>721
あ、それとお前頭が悪くて人のプログラムを読み解く力がなさそうだから教えといてやるよ
利き筋のみをチェックするのと配置も同時に求めるのは別の問題だ
どう読んだらこのプログラムの中に配置情報まで入っていると思えるのかそちらの方が不思議なんだが
いくらでも配置も覚えておくプログラムは書けるぞ
むしろこのプログラムは利き筋のみチェックして配置を求めるのを省いた分だけ速くなってるのだと

756: 気付けないのかなあ真剣に一度精神科で診てもらう事を検討しろよもう遅いと思うけど

757:デフォルトの名無しさん
15/09/05 17:13:54.12 H2DL4EyO.net
これが噂の炎上学習法か
醜いね

758: ◆QZaw55cn4c
15/09/05 17:25:37.26 bMqKfWg+.net
なりすましに利用されるキャラに成ったとは喜ばしいことだ‥
でも俺じゃないよ

759:デフォルトの名無しさん
15/09/05 18:11:46.68 r36BFiK6.net
>>723
ざっと主張を読むと、>>723は頭いいとおもうけどな
異論あるやついるの？
>>721
このこは、馬鹿というか精神病はいってるいうか、
「云々なだけです」
なんてヤバスギなんだぞ
本人わからんだろうけど

760:デフォルトの名無しさん
15/09/05 18:20:17.60 byXpZJ1D.net
>>721君へ
僕は>>700さんのコードを改竄して配置を表示するようにしてみたよ。
URLﾘﾝｸ(ideone.com)
期待に応えられたかな？？？

761:デフォルトの名無しさん
15/09/05 21:22:45.11 pNQf4xq/.net
>>707
どちらのテストケースも時間が掛かり過ぎるのでもっと小さなデータにしました
データは
URLﾘﾝｸ(pastebin.com)
プログラムは(データを作るプログラムを含んでいます)
URLﾘﾝｸ(ideone.com)
これでこちらの環境ではReleaseモードで700ms前後です
こういうのはやはりC#は苦手なんですかね
すっきり書ける事は書けるんですが
<int>ではなくて<long>になっているのは、intでこれを実行すると大きなデータセットで
オーバーフローが出ちゃうからです
時間が掛かるのは多分順列で天文学的な場合の数になっちゃうからからなあ

762:デフォルトの名無しさん
15/09/05 21:33:50.27 OFlnC1Bs.net
お題：数列を省略して表示してください
数列の範囲 (min, max) と表示数 (disp)、省略の基点 (spot) が以下の範囲内で与えられます。
(0 ＜ min ＜ max), (2 ＜ disp), (min ≦ spot ≦ max)
min 1, max 3, disp 3, spot 1: (1) 2 3
min 1, max 3, disp 3, spot 2: 1 (2) 3
min 1, max 3, disp 3, spot 3: 1 2 (3)
min 1, max 4, disp 3, spot 2: 1 (2) ... 4
min 1, max 4, disp 3, spot 3: 1 ... (3) 4
min 1, max 10, disp 5, spot 1: (1) 2 3 4 ... 10
min 1, max 10, disp 5, spot 2: 1 (2) 3 4 ... 10
min 1, max 10, disp 5, spot 3: 1 2 (3) 4 ... 10
min 1, max 10, disp 5, spot 4: 1 ... 3 (4) 5 ... 10
min 1, max 10, disp 5, spot 5: 1 ... 4 (5) 6 ... 10
min 1, max 10, disp 5, spot 6: 1 ... 5 (6) 7 ... 10
min 1, max 10, disp 5, spot 7: 1 ... 6 (7) 8 ... 10
min 1, max 10, disp 5, spot 8: 1 ... 7 (8) 9 10
min 1, max 10, disp 5, spot 9: 1 ... 7 8 (9) 10
min 1, max 10, disp 5, spot 10: 1 ... 7 8 9 (10)
min 128, max 256, disp 7, spot 192: 128 ... 190 191 (192) 193 194 ... 256
disp が偶数の場合の spot の偏り、
min 1, max 10, disp 4, spot 8: 1 ... 7 (8) ... 10
min 1, max 10, disp 4, spot 9: 1 ... 8 (9) 10
disp が大きい場合の振る舞い、
min 1, max 3, disp 5, spot 3: 1 2 (3)
min 1, max 3, disp 5, spot 3: error. disp out of range
() や ... などの装飾は自由です。

763:デフォルトの名無しさん
15/09/05 21:57:37.63 OFlnC1Bs.net
>>729
(2 ＜ disp) は（0 ＜ disp）でもおｋです

764:デフォルトの名無しさん
15/09/05 22:22:12.08 OFlnC1Bs.net
>>730
やっぱり省略がアレになるので（2 < disp）に訂正します

765:デフォルトの名無しさん
15/09/06 00:53:28.75 3aEa3HTV.net
>>729 Python3
URLﾘﾝｸ(ideone.com)
spotから表示する数を求めていく方法

766:デフォルトの名無しさん
15/09/06 02:03:11.12 labNDWrY.net
NQueenの問題といい、オセロの件といい.QZの自演は凄いな

767:デフォルトの名無しさん
15/09/06 04:26:44.16 3aEa3HTV.net
>>729 OCaml
URLﾘﾝｸ(ideone.com)
>>732と同じアプローチ、ゴリ押しで書き下した

768:デフォルトの名無しさん
15/09/06 06:07:10.46 laHESI+6.net
>>733
QZの自己承認欲求が強すぎるよな
完全に精神的に病気だな
炎上学習法をやるのはQZ一人しかいない

769:デフォルトの名無しさん
15/09/06 08:08:20.90 /Fu+tBiS.net
>>728
ちょっと時間がかか

770:りすぎですね無理にIEnumerable<T>を返してforeachするより http://d.hatena.ne.jp/JAPLJ/20090123/1232716837 こういう奴の方が速いかもしれないんで試してみてくださいちなみにVS2015 C++で>>728のプログラムを書き直したのが http://ideone.com/5bUOrW >>728のデータでこちらで6msしか掛かりませんのでどこかに不自然に時間がかかりすぎていると思いますまたこのプログラムはおっしゃる通りどこかでベクトルの大きさが大きいものが 1個でも入るとそこで引っかかります

771:デフォルトの名無しさん
15/09/06 08:17:25.46 3aEa3HTV.net
>>729 Go
URLﾘﾝｸ(ideone.com)
>>732と同じアプローチ、再代入ましまし

772:デフォルトの名無しさん
15/09/06 08:23:56.62 pZj7Wd8c.net
>>729
汚Haskell
URLﾘﾝｸ(ideone.com)

773:デフォルトの名無しさん
15/09/06 12:29:03.84 RC4omDg7.net
>>707 Java
URLﾘﾝｸ(ideone.com)

774:デフォルトの名無しさん
15/09/06 15:06:47.52 mows7ZZ0.net
>>729 Emacs Lisp
(cl-defun f (min max disp spot &key error)
(when (< (1+ (- max min)) disp)
(if error (error "error. disp out of range") (setq disp (1+ (- max min)))))
(let* ((aaa (let (l) (setq l (cl-adjoin min l)) (setq l (cl-adjoin max l))
(let ((i 0))
(while (< (length l) disp)
(let ((y (let ((x (ceiling (/ (float i) 2)))) (+ spot (if (oddp i) (- x) x)))))
(when (and (<= min y) (<= y max))
(setq l (cl-adjoin (let ((x (ceiling (/ (float i) 2)))) (+ spot (if (oddp i) (- x) x))) l))))
(incf i)))
(sort l (lambda (a b) (< a b)))))
(bbb (let ((p (1- min)))
(cl-loop for n in aaa collect (prog1 (list (if (= n (1+ p)) "" "... ") (format (if (= n spot) "(%d)" "%d") n)) (setq p n)))))
(ccc (cl-reduce (lambda (a b) (concat a " " b)) (mapcar (lambda (x) (concat (nth 0 x) (nth 1 x))) bbb))))
ccc))
f
(f 1 3 3 1) "(1) 2 3"
(f 1 3 3 3) "1 2 (3)"
(f 1 4 3 2) "1 (2) ... 4"
(f 1 4 3 3) "1 ... (3) 4"
(f 1 10 5 1) "(1) 2 3 4 ... 10"
(f 1 10 5 3) "1 2 (3) 4 ... 10"
(f 1 10 5 4) "1 ... 3 (4) 5 ... 10"
(f 1 10 5 10) "1 ... 7 8 9 (10)"
(f 128 256 7 192) "128 ... 190 191 (192) 193 194 ... 256"
(f 1 10 4 8) "1 ... 7 (8) ... 10"
(f 1 10 4 9) "1 ... 8 (9) 10"
(f 1 3 5 3) "1 2 (3)"
(f 1 3 5 3 :error t) "error. out of range"

775:デフォルトの名無しさん
15/09/06 15:25:31.21 XK9v3oN2.net
>>729 GNU Smalltalk
URLﾘﾝｸ(ideone.com)

776:デフォルトの名無しさん
15/09/06 15:53:00.71 XK9v3oN2.net
>>699 GNU Smalltalk
URLﾘﾝｸ(www.ic-net.or.jp) を移植。
ideone.com で N=12 まで。
URLﾘﾝｸ(ideone.com)

777:デフォルトの名無しさん
15/09/06 21:15:29.55 QKeqN0i2.net
>>729
URLﾘﾝｸ(ideone.com)
C++。ギブアップ。細かい仕様が対応できなかった。
表示回りっていつも適当だから、ここまで手の込んだのは無理やったわ。
GOTO使ってるあたりに苦悩を感じてくれ。
算数できなくなってることに絶望した。

778:デフォルトの名無しさん
15/09/06 23:58:23.31 3aEa3HTV.net
>>729 C
URLﾘﾝｸ(ideone.com)
原始的に配列へ詰め込んでソート、文字列の生成は断念した

779:デフォルトの名無しさん
15/09/07 03:04:02.94 QAzFwx2+.net
>>665 C
URLﾘﾝｸ(ideone.com)

780:デフォルトの名無しさん
15/09/07 03:04:53.70 QAzFwx2+.net
>>729 C
URLﾘﾝｸ(ideone.com)

781:デフォルトの名無しさん
15/09/07 03:43:16.07 hx62h88L.net
>>729 C
URLﾘﾝｸ(ideone.com)

782:デフォルトの名無しさん
15/09/08 00:20:53.77 qsWudAV2.net
>>729
省略の基点というのがよくわかりません

783:デフォルトの名無しさん
15/09/08 00:24:13.57 HV2JZhb0.net
>>748
SpotLightを中心点に表示を要求されるのでここを目印にDISP-2個位表示させるのが今回のお題。

784:デフォルトの名無しさん
15/09/08 05:55:05.13 byflMgx0.net
お題
ソート済み配列などに対し、falseを返すまで繰り返し適用することで
重複なく全順列を列挙できる破壊的操作を行う関数 next_permutation を
定義せよ。
文字列 "aaabc" に対する使用例（C++erはネタバレ注意）：URLﾘﾝｸ(ideone.com)
- 標準またはそれに準ずるライブラリに同等機能がある言語の場合は、その使用例を提示するだけでよい。
　もちろん、自力での再実装にこだわってみるのもよい。
- 配列などに対し、その部分のみに適用できるようにはしなくてよい。
- 言語仕様で非破壊操作がしにくい言語の場合は、有限リストやストリーム、
　ジェネレータなどを生成する実装に代えてもよい。

785:デフォルトの名無しさん
15/09/08 07:05:29.36 iUE7XWFn.net
>>750
×非破壊操作がしにくい　→　○破壊操作がしにくい

786:デフォルトの名無しさん
15/09/08 10:54:06.55 n5Qbp6yS.net
>>750 Python3
引数を破壊的変更しないジェネレータ、要素がタプルになるのでfuncで加工する
import itertools
def next_permutations(seq, func=(lambda x: x)):
return map(func, sorted(set(itertools.permutations(seq))))
for a in next_permutations("aaabc", func=''.join):
print(a)

787:デフォルトの名無しさん
15/09/08 12:04:00.18 N3BcRQN+.net
ボードゲーム　スカイゲスト
Miracle Five World Cup ～スカイゲスト
ミラクルファイブ今年に続いて、Othello World Cup 2014 でもミラクルファイブが正式競技として行われることが決まったようですね。
知ってる人は知っている、でもほとんどの人は知らないと思いますが、私、このスカイゲストの世界チャンピオンなんです。
ちなみに日本大会は現在三連覇しています。
で、残念なことに、現状ではネット上でこのスカイゲストをやれる環境が存在してないので、ささやかな興味を持ったとしても、
なかなか実際にプレイするところまでは行かないんですよね。だからそりゃぁ、なかなか普及してません。
そんなわけで(?)、ちょっとこのゲームのルールを軽く説明してみようかと。
URLﾘﾝｸ(www.othello.org)
URLﾘﾝｸ(blog.goo.ne.jp)

スカイゲストAIのアルゴリズム(評価関数編)
オセロの考案者である長谷川五郎氏が考案したボードゲームに、スカイゲスト(SkyGuest、テンゲストも同じルールっぽい)というものがあるのをご存知でしょうか？
大変面白いゲームなのですが、ネット上にこれをプレイできる環境がなかったので、AIを作成しました。
今のところ公開する予定はございませんが、ある程度の強さのものが出来上がったので、アルゴリズムの方を紹介したいと思います。
URLﾘﾝｸ(blog.livedoor.jp)

788:デフォルトの名無しさん
15/09/08 12:19:34.11 JhgINqf8.net
>>750 GNU Smalltalk
URLﾘﾝｸ(ideone.com)

789:デフォルトの名無しさん
15/09/08 12:48:53.12 JhgINqf8.net
>>752
Pythonって、すごくシンプルに書けて格好いいですね。
ただ、この実装だと、多要素だけど要素のほとんどが同じで簡単に返せる場合
（たとえば "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab" とか）
にもかかわらず戻ってこなくなったりしませんか？

790:デフォルトの名無しさん
15/09/08 13:03:12.99 JcPY1iwa.net
>>750
C#
URLﾘﾝｸ(ideone.com)

791:デフォルトの名無しさん
15/09/08 16:46:37.82 HV2JZhb0.net
げ、パーミテーション自作してる人いるの。
すさまじいな。
俺C++の組み込みよく使うけど自作はさっぱりわからんぞ。

792:デフォルトの名無しさん
15/09/08 19:32:53.81 N3BcRQN+.net
パーミテーション=順列か。
順列生成くらいは入門レベルかと。速度は別にして。
どんな経験者だよ。

793:デフォルトの名無しさん
15/09/08 19:52:51.45 HV2JZhb0.net
数学

794:ダメなんですよ。ため息出るわ。

795:デフォルトの名無しさん
15/09/08 19:59:30.98 MMxN10T7.net
俺は数学、足し算なら怖くないな。
ただし演算数、非演算数、ともに二桁以内な

796:デフォルトの名無しさん
15/09/08 20:35:18.17 WO1DF9qJ.net
C++のnext_permutation()アルゴリズムのヘッダを見て真似するのが一番簡単

797:デフォルトの名無しさん
15/09/08 20:59:28.34 MMxN10T7.net
バカにしてたけど
javaやることにした
とりあえずスッキリわかるジャバジャバのKindle版注文した
ん？スレチだな
(*´σｰ｀)ﾍﾍﾍ

798:デフォルトの名無しさん
15/09/09 01:01:53.28 WxXYPcUn.net
N=1 一意解=1 全解=1
N=2 一意解=0 全解=0
N=3 一意解=0 全解=0
N=4 一意解=1 全解=2
N=5 一意解=2 全解=10
N=6 一意解=1 全解=4
N=7 一意解=6 全解=40
N=8 一意解=12 全解=92
N=9 一意解=46 全解=352
N=10 一意解=92 全解=724
N=11 一意解=341 全解=2680
N=12 一意解=1787 全解=14200
N=13 一意解=9233 全解=73712
N=14 一意解=45752 全解=365596
N=15 一意解=285053 全解=2279184

799:デフォルトの名無しさん
15/09/10 00:08:40.35 kopU2pqH.net
GCJはプログラミングコンテスト本が出てるのでProject Eulerで
URLﾘﾝｸ(projecteuler.net)
でも"project euler solutions 99"なんかでぐぐったら駄目ですよ
まあ似たようなコードになると思うけど
2^11と3^7のような指数形式で書かれた2つの数を比較するのは難しくありません
しかし、632382^518062＞519432^525806であるのを確認するのは300万桁を超える
数字を含んでいるのではるかに困難でしょう
base_exp.txt(問題文をクリックしてください)は1000行を含む22KBのテキストで、
それぞれの行に基数と指数が対になっています
どの行の数が最大になるか決定してください
注：ファイル注の最初の二行は上記の例に示されたものです

800:デフォルトの名無しさん
15/09/10 00:10:08.60 kopU2pqH.net
あ、忘れました
お題です

801:デフォルトの名無しさん
15/09/10 00:33:27.38 AxUmdUI6.net
n T U [cost]
1 1 1 (0[msec])
2 0 0 (0[msec])
3 0 0 (0[msec])
4 2 1 (0[msec])
5 10 2 (0[msec])
6 4 1 (0[msec])
7 40 6 (0[msec])
8 92 12 (0[msec])
9 352 46 (0[msec])
10 724 92 (16[msec])
11 2680 341 (0[msec])
12 14200 1787 (94[msec])
13 73712 9233 (499[msec])
14 365596 45752 (3011[msec])
15 2279184 285053 (19843[msec])
16 14772512 1846955 (140806[msec])
ネット回線からの割り込みが多かったので
コストは参考値

802:デフォルトの名無しさん
15/09/10 04:21:19.51 hMjmDO5x.net
>>763
>>766
>>1

803:デフォルトの名無しさん
15/09/10 05:17:03.70 2byHSaL/.net
>>750 Python3
関数の仕様を勘違いしていたのでやりなおし
>>755の指摘を参考に要素に重複があるとき計算を省略する
def next_permutations(iterable):
　　orig = tuple(iterable)
　　def recursive(seq, acc):
　　　　if not seq:
　　　　　　yield acc
　　　　elif orig[:len(acc)] <= acc:
　　　　　　for v in sorted(set(seq)):
　　　　　　　　newseq = seq[:]
　　　　　　　　newseq.remove(v)
　　　　　　　　yield from recursive(newseq, acc+(v,))
　　return recursive(list(iterable), ())
for a in next_permutations("aaabcaaabcaaabc"):
　　print(''.join(a))

804:デフォルトの名無しさん
15/09/10 11:55:20.61 0vTqxZ6A.net
>>768
すばらしい。GNU Smalltalk に移植してみました。（文字列のみ対応の手抜きで恐縮ですが…）
URLﾘﾝｸ(ideone.com)

805:デフォルトの名無しさん
15/09/10 21:31:45.79 AToafzam.net
>>729 c
URLﾘﾝｸ(ideone.com)

806:Fcc

807:デフォルトの名無しさん
15/09/10 22:15:18.95 Q2vaRfqD.net
>>764
モロにカンニングですみませんが
URLﾘﾝｸ(ideone.com)

808:デフォルトの名無しさん
15/09/11 01:59:58.81 0Pjc40Dt.net
>>652 遅ればせながらPerl
use 5.016;
use List::Util 'sum';
say sum grep {$_ % 5 == 0 or $_ % 3 == 0} 1..1000;

809:デフォルトの名無しさん
15/09/11 21:51:13.27 v7E2xSv/.net
手抜きPerl
use 5.016;
sub next_permutations {
　my %h;
　sub fn {
　　my ($l, $p, @r) = @_;
　　defined $p ? map {[$p, @$_]} fn([], @$l, @r) : ([])
　　　,
　　@r ? fn([@$l, $p], @r) : ()
　}
　map {$h{$_} = 1} keys {map {join('', @$_) => 1} fn [], @_};
　keys %h
}
say for next_permutations split '', 'aaabc';

810:デフォルトの名無しさん
15/09/11 22:39:05.52 v7E2xSv/.net
use 5.016;
sub next_permutations {
　sub fn {
　　my ($l, $p, @r) = @_;
　　defined $p ? map {[$p, @$_]} fn([], @$l, @r) : ([])
　　　,
　　@r ? fn([@$l, $p], @r) : ()
　}
　keys {map {join('', @$_) => 1} fn [], @_};
}
say for next_permutations split '', 'aaabc';
これでええやん、つか破壊してないし、過剰仕様
しっか～くｗ

811:デフォルトの名無しさん
15/09/12 14:21:20.66 9MDXYKkO.net
>>774
元の並びがソートされている場合、
保持されている現在の並びを破壊しながらでも
ジェネレータみたいに呼び出される度に次の順列を
重複なく返すアルゴリズムが>750のお題の肝では？

812:デフォルトの名無しさん
15/09/13 19:11:57.62 dr5xNYTR.net
>>775
お題に「生成される順列はソートせずとも辞書順に並ぶこと」って一言いれておけばよかったですね^^;

813:デフォルトの名無しさん
15/09/13 20:57:12.14 bLikZ+wL.net
>>750 OCaml
URLﾘﾝｸ(ideone.com)
引数はリスト限定で破壊的操作はしない、返り値で次の順列を返す

814:デフォルトの名無しさん
15/09/13 22:52:40.22 b32GJr7l.net
>>441 c
URLﾘﾝｸ(ideone.com)
注：肝心な部分（comb, permute）はぐぐったサイトから無断で拝借しました

815:デフォルトの名無しさん
15/09/14 07:17:09.48 aQticbJR.net
>>778
中身が見えない

816:デフォルトの名無しさん
15/09/14 20:25:46.47 Gwz4vSRg.net
>>441 c
URLﾘﾝｸ(ideone.com)
>>778からの変更点：
・いったん全パターンもつのをやっぱやめる
・細部のちょこちょこっとした改善

817:デフォルトの名無しさん
15/09/15 21:30:13.30 jovL9vh0.net
>>775 うっせーな、ハゲっが。
「生成される順列はソートせずとも辞書順に並ぶこと」の意味が
「出力する行がsort済みの順番に並んでいる」順列という意味ならこうか：
use feature qw{:5.16};
use Data::Dump qw(dump);
sub next_permutation {
　defined $_[1] and next_permutation(@_[1..$#_]) or
　　($_[0] lt $_[1]) and
　　do {
　　　do {$i = $_
　　　　　　if $_[0] lt $_[$_]}
　　　　　　　　for 1..$#_;
　　　@_[0, $i] = @_[$i, 0];
　　　@_[1..$#_] = sort @_[1..$#_];
　　　1 }
　}
#@a = split '', 'aaabcaaabcaaabc'; # ←この入力はカラムがsort済みじゃねーしw
@a = split '', 'aaabc';
say join '', @a;
say join '', @a while next_permutation @a;
出力行ごとのカラムもソートされているという制限つきの順列生成なら
中のdoがif産業が一行になるかな。
つか、中のdo forも無名再帰で書くのがホンとは漢つーもんょ。

818:デフォルトの名無しさん
15/09/15 21:35:00.71 jovL9vh0.net
いや、ちょとまて
入力行一行のカラムがソートされてたら、
出力行のカラムもソートされているという制限をつけたら
出力順列は入力と同じたった一行しか存在しない、
ふー危うくひっかかるところだったぜ。
つーことで上の方のほかの人の回答に間違っているのない？

819:デフォルトの名無しさん
15/09/15 21:46:18.62 jovL9vh0.net
やっぱほかの人の解も合ってるかな？
よく見てないけどｗ
'aaabcaaabcaaabc';の入力の並びに目が惑わされたワイ
じゃーな、ハゲっが。

820:デフォルトの名無しさん
15/09/15 22:10:44.77 jovL9vh0.net
>>781 連投ごめんなさい、or式全体を()でくくらないと出力に抜けが起きるバグありあした…orz
修正版：
use feature qw{:5.16};
sub next_permutation {
　defined $_[1] and (next_permutation(@_[1..$#_]) or
　　($_[0] lt $_[1]) and
　　do {
　　　do {$i = $_
　　　　　　if $_[0] lt $_[$_]}
　　　　　　　　for 1..$#_;
　　　@_[0, $i] = @_[$i, 0];
　　　@_[1..$#_] = sort @_[1..$#_];
　　　1 })
　}
#@a = split '', 'aaaaaaaaaaaaaaaabc';
@a = split '', 'aaabc';
say join '', @a;
say join '', @a while next_permutation @a;

821:デフォルトの名無しさん
15/09/16 00:38:04.82 zgtxEZCv.net
>>784
左側の新しい項の入れ替えに移行し右側の並びを一式リセットするためのsortは
reversieでよいはず。これにより並べ替えのオーダーをNloｇNからNに低減できる。
また項を入れかえる対象の要素を検索する繰り返しは、その項より大きくかつ最も小さい
値の要素を探すので、平均行程1/2で打ちって検索の計算量も半減することができる。
それから、もう少しコンパクトかつ可読性ある書き方ができるはず。

822:デフォルトの名無しさん
15/09/16 00:59:37.85 NuZWJDts.net
>>16 c
URLﾘﾝｸ(ideone.com)
カウント版と算出版と両方
カウント版で出した値じっくりながめると
9, 99, 999…っていう値の気配がしたので
それ中心に押したり引いたりしながら算出
なお、理屈はよくわかっていないもよう

823:デフォルトの名無しさん
15/09/16 01:04:42.91 zgtxEZCv.net
use feature qw{:5.16};
sub next_permutation {
　defined $_[1] and (next_permutation(@_[1..$#_]) or
　　($_[0] lt $_[1]) and
　　do {
　　　for (1..$#_)
　　　　{$_[0] lt $_[$_] ? $i = $_ : last}
　　　@_[0, $i] = @_[$i, 0];
　　　@_[1..$#_] = reverse @_[1..$#_];
　　　1 })
　}
#@a = split '', 'aaabc'; # 'aaaaaaaaaaaaaaaabc';
@a = split '', '112334556';
say join '', @a;
say join '', @a while next_permutation @a;
こんな感じな。sortをreverseにしたとき、ぐっと速くなった。

824:デフォルトの名無しさん
15/09/16 05:12:59.25 TSIOTapp.net
>>750 Ruby
URLﾘﾝｸ(ideone.com)

825:デフォルトの名無しさん
15/09/16 07:10:31.01 2Yj1o+46.net
>>750 Go
URLﾘﾝｸ(ideone.com)
Permutationインターフェースを実装すれば他の型でもできる

826:デフォルトの名無しさん
15/09/16 13:06:36.59 fQczy5Yc.net
ruby初心者スレでこちらに書く様に促されたので、
できればrubyかpythonで答えて頂けるとありがたいです。
お題
以下の様な数値群から、重複しない要素を使って任意の数値(例えば2360)に最も近い和を求めるにはどうしたら良いでしょう?
115,135,215,352,358,655,885,925,936,1250,1285,1620,1850

827:デフォルトの名無しさん
15/09/16 14:20:54.79 VfqLXb9I.net
115+135+215+358+655+885=2363

828:デフォルトの名無しさん
15/09/16 14:23:48.16 aL/dguIa.net
>>791
任意の数値のアルゴリズム

829:デフォルトの名無しさん
15/09/16 15:06:27.46 VfqLXb9I.net
データ件数10000件の場合とかだなｗ

830:デフォルトの名無しさん
15/09/16 16:09:16.80 9fL6Ueyi.net
ポテトチップスを、60gの袋詰めする機械では、
9個の秤に、幾らかのポテトチップスが載っていて、
その秤の中から、60g以上で、
最も少ない重さを計算して、袋詰めする
9個の秤の重さの合計を、sum9として、
1個の秤の重さを求めると、残り8個の秤の重さもわかる。
2個の秤の重さを求めると、残り7個の秤の重さもわかる。
3個の秤の重さを求めると、残り6個の秤の重さもわかる。
4個の秤の重さを求めると、残り5個の秤の重さもわかる

831:デフォルトの名無しさん
15/09/16 16:44:57.70 9fL6Ueyi.net
重複を許さない組合せ
Array.combination
13個の数字の合計を、sum13として、
1個の数字を求めると、残り12個の数字の合計もわかる。
2個の数字の合計を求めると、残り11個の数字の合計もわかる。
.
.
6個の数字の合計を求めると、残り7個の数字の合計もわかる
つまり、6個までのすべての組合せを計算すればよい

832:デフォルトの名無しさん
15/09/16 17:54:44.06 slZMIjby.net
>>790
> 以下のような
っていう部分はどう解釈すればいいの？
例に挙がってる程度の数であれば、
総当りでいいんじゃね？
これ↓と同質の問題ならリンク先を参照。
URLﾘﾝｸ(ja.wikipedia.org)

833:デフォルトの名無しさん
15/09/16 18:58:52.94 saSs2l+c.net
>>790 ruby 2.0.0
単に全パターンをチェックした場合
def f789(a, target)
combos = (1..a.size).inject([]) {|r, i| r += a.combination(i).to_a}
min = combos.min_by {|combo| (target - combo.inject(:+)).abs}
[min, min.inject(:+)]
end
p f789([115,135,215,352,358,655,885,925,936,1250,1285,1620,1850], 2360)
↓
[[115, 135, 215, 352, 655, 885], 2357]

834:デフォルトの名無しさん
15/09/16 20:10:54.59 aL/dguIa.net
データの方も任意なんだろう。「ような」が付いてる。

> 以下の様な数値群

835:デフォルトの名無しさん
15/09/16 20:53:50.13 ExTMGHGk.net
>>790
URLﾘﾝｸ(ideone.com)
一応解いたがオセー。最新CPUで1：40かかる。
順列使うくらいなら再起使ったほうが早いな。
コンビネーションほしー。

836:デフォルトの名無しさん
15/09/16 22:16:07.44 JeX5l5vV.net
>>790
データの数が20個程度なら総当りで問題なく解けそうだけど最大数いくつ？

837:デフォルトの名無しさん
15/09/16 22:42:12.73 aL/dguIa.net
これでいいのでは? データがx0, x1, ・・・xN、yに近い和を求めるとして。
y = xnとなるnがあれば終了。
そうでないとき、y > xnとなる最大のnについて、次の値でいいやつを選べはいいのでは?
x(n+1)　//　yより大きくもっとも近い値
cal (y, {x0, ・・・x(n-1)})　//和にxnを含まないときの最良値
cal (y-xn, {x0, ・・・x(n-1)})　//和にxnを含むときの最良値

838:デフォルトの名無しさん
15/09/16 22:53:06.43 aL/dguIa.net
>>801で関数calを作ればいい。
cal(y, vec)とすると、y,かvecが小さくなるので再帰関数で作れるはず。

839:デフォルトの名無しさん
15/09/16 23:59:55.71 JeX5l5vV.net
>>790
URLﾘﾝｸ(ideone.com)
とりあえず何も考えずに総当り
20個だと1秒くらいで出るけど数が増えると死ぬ

840:デフォルトの名無しさん
15/09/17 00:21:00.74 56vB2llc.net
網羅するしかないけど、再計算はしない、大きすぎる・小さすぎる和を検出して無駄なループをさせない点がポイントでは。

841:デフォルトの名無しさん
15/09/17 00:36:51.76 oSu48zpr.net
>>790
URLﾘﾝｸ(ideone.com)
前に書えたやつを軽く修正
全探索解(2^n*n)と、ウソDP解(n*最大重量)
基本python2.xだけど、pypyで実行

842:789
15/09/17 08:46:22.84 aStCI4Gl.net
解答してくださったみなさんありがとうございます。
元々は50程度の数値群で、別にやらなきゃいけない物でもなかったんですが、
プログラミングでやるとしたらどうやるのかなと思ったのですが、
自分では解法が考えつかなかったので書き込んでみました。これから少しずつ見て理解してみます。

843:デフォルトの名無しさん
15/09/17 09:19:36.19 7rI3c1r5.net
>>790 OCaml
URLﾘﾝｸ(ideone.com)
力任せ探索をハッシュテーブルを使ってメモ化

844:名無しさん＠お腹いっぱい。
15/09/17 11:24:35.90 Ref/prt+.net
今度ＰＳ４が値下げするそうなんだけど
ＰＳ４でプログラミングはできるのかな？誰か教えて。
ＣとかRubyとかその他。

845:デフォルトの名無しさん
15/09/17 13:03:14.26 56vB2llc.net
PS4単体でプログラミングできる仕組みはあるのかしらないけど。
PS4で動くソフトの開発は素人でもできるのでは?
PS4で動くコンパイラとかエディタとかキーボードとか揃えばできるとおもうが。

846:デフォルトの名無しさん
15/09/17 13:08:21.98 56vB2llc.net
適当にかいた。ここには契約しないとできない

847:となってる。個人利用でもソニーから開発環境提供してもらわないとムリなのか? PlayStationRソフトウェアの提案・開発・発売をしたい | PlayStation.com https://support.jp.playstation.com/app/answers/detail/a_id/161

848:名無しさん＠お腹いっぱい。
15/09/17 13:18:09.20 Ref/prt+.net
ＰＳ４の使い道があまりないのでＰＣ代わりにプログラミングの勉強に使えないかと
思ったが、やっぱりダメみたいだね。
普通にＷＩＮＤＯＷＳ　ＰＣを使う事にするよ。
回答ありがとう。

849:デフォルトの名無しさん
15/09/17 13:59:14.02 56vB2llc.net
>>806
やってないけど50個は手強いかと。
総当りだと、2^50 = 1125899906842620とおりで普通のPCでは計算終わらないはず。
工夫したとしても手強いはず。

850:デフォルトの名無しさん
15/09/17 14:06:34.37 56vB2llc.net
確実で最初にやるといいと思える計算削減法は。
たとえば101を生成したいとき、101がデータにあるならばそれを使えばよく、それ以下の和で101を生成すべきではないな。
これは事前に検出しておいたほうがよさげ。

851:デフォルトの名無しさん
15/09/17 17:42:20.70 IC3slnA5.net
求める値が10000( > 2360 * 50 / 13)程度なら、>>805これのfunc1で行ける

852:デフォルトの名無しさん
15/09/20 05:58:43.13 vBjKt0IW.net
「Googleの入社試験」より
正の整数 n が与えられたとき、
0からnの間の、すべての整数に使われている、
1の数を返す関数 f があります
例えば、f(1) = 1; f(13) = 6 など。
今、nが2以上で、f(n) = n となる最小のnを求めよ
参考までに、
f(99) = 20; f(999) = 300; f(199,999) = 200,000
答え、n = 199,981

853:デフォルトの名無しさん
15/09/20 08:06:14.95 f/DwOlJx.net
>>815
「10進法表記で」かい？

854:デフォルトの名無しさん
15/09/20 08:25:53.78 g7ao8Sb7.net
>>815
URLﾘﾝｸ(ideone.com)
C++。とりあえず2通り書いてみたけど、どっちも遅い。
片方は並列化すれば多少早くなるはず。片方はデバッグ投げた。コンビネーションほしい。
最近まともに解けてないな・・・。

855:814
15/09/20 08:37:04.35 vBjKt0IW.net
>>816
もちろん、10進数だよ
f(13) = 6
1, 10, 11, 12, 13で、1を6個使っている
11は、2個で数える

856:デフォルトの名無しさん
15/09/20 09:36:23.85 1JwuQWhK.net
入社試験でパソコン使っていいのか？

857:デフォルトの名無しさん
15/09/20 10:45:18.64 7mBXEM/X.net
>>815 OCaml
URLﾘﾝｸ(ideone.com)
最小のnのみ表示、経過はアウトプットしてない

858:デフォルトの名無しさん
15/09/20 12:10:16.54 4gyZNSF5.net
>>815 C
URLﾘﾝｸ(ideone.com)

859:780
15/09/20 13:29:55.06 Ac94krKF.net
>>815
use feature qw{:5.16};
sub f1 { # 0..10**$d - 1 (0..999など)の間にある総和
　my $d = shift;
　my $i = 10**$d;
　my $n = ($i / 10) * $d;
　($i, $n) }
sub f2 { # 0..10**$d *2) (0..2000など)最上位が2になるまでの間にある総和
　my $d = shift;
　my $i = 10**$d * 2;
　my $n = $i / 2 + ($i / 10) * $d;
　($i, $n) }
my $o = 2;
do {
　($i1, $n1) = f1 $o;
　($i2, $n2) = f2 $o;
　say "$o: $i1..$i2, $n1 ~ $n2";
　$o++;
} while $n2 < $i2;
$ perl 7_814_0.pl
2: 100..200, 20 ~ 140
3: 1000..2000, 300 ~ 1600
4: 10000..20000, 4000 ~ 18000
5: 100000..200000, 50000 ~ 200000 ← 解はこの間にある
理屈で考えると、最上位桁が1以外の0,2..9の場合はその値までの文字1の総和は
値に漸近しないので、解は最上位が1となる１xxxx ... 1999...の間にある筈。
上記はそれを確認したコード、この考えに基づき再帰的探査で速やかに見つからないかな…
時間があったらやってみたいが引越しの準備で…、ハゲっが。

860:デフォルトの名無しさん
15/09/20 14:17:21.30 W3KPe91F.net
>>815 c
URLﾘﾝｸ(ideone.com)

861:デフォルトの名無しさん
15/09/20 22:12:07.71 w687FJud.net
>>815 Squeak/Pharo Smalltalk
| g f m |
g := [
　| memo |
　memo := OrderedCollection with: 1.
　[:n |
　　n - memo size timesRepeat: [
　　　memo add: (memo last + ((memo size + 1) asString occurrencesOf: $1))].
　　memo at: n
　]
].
f := g value.
m := 1.
[(m := m + 1) = (f value: m)] whileFalse.
^m "=> 199981 "

862:デフォルトの名無しさん
15/09/20 22:53:09.92 g7ao8Sb7.net
高速化しようとしてthreadいじってみたけど、そっちの闇にのまれて全く進まなかった。Orz
真面目に最後までやって終わってるのかすらわからん・・・。

863:デフォルトの名無しさん
15/09/20 23:01:38.16 D6HrfyQE.net
マンカラ= カラハ = 豆まきゲームのAI作成で。自分が強いのを作るので対戦。

マンカラ ( ボードゲーム ):無料Flashゲーム
URLﾘﾝｸ(www.sousakuba.com)

ゲーム「カラー」の説明
それでは、例題として取り上げるゲーム「カラー (Kalah) 」を説明します。
このゲームはルールこそ単純ですが、展開がスリリングで面白いゲームです。
URLﾘﾝｸ(www.geocities.jp)

864:デフォルトの名無しさん
15/09/20 23:15:14.16 7mBXEM/X.net
>>822の検証をしていたら
9が並んだパターンのnは、1の数え上げが不要なことが分かった
下のPython3のコードはnの桁の数から>>815のf(9...9)の場合の値を出してる
import math
def f_9x(n):
　a = math.floor(math.log10(n))
　return (a+1) * pow(10, a)
f_9x(9) # 1
f_9x(99) # 20
f_9x(999) # 300
f_9x(9999) # 4000
f_9x(99999) # 50000
f_9x(999999) # 600000

865:780
15/09/20 23:55:39.69 Ac94krKF.net
>>827
ｺﾞﾒﾝチャイ
>>822は間違いがあって
× 最上位桁が1以外の0,2..9の場合はその値までの文字1の総和は値に漸近しない
○ ある値における最上位桁から現在着目している桁までの間に1がない場合は
　　その値を右にインクリメントしていっても、文字1の総和は値に漸近しない
たとえば
xxxxxxxxxxooooooooooxxxxxxxxxxx　　　 o　o　　x　o
　　　　　　　　　　　　　　　　　　　　　　　　1…1…2…2
0000000000111111111122222222223…0…1…0…1
0123456789012345678901234567890…0…0…0…0 ←着目している桁
図で書くとxのことろに解はなく、oのところに解がある可能性がある
これ2,3桁なのでちょっと分かりにくいかもしれないけど、桁数が多場合を考えると分かりやすいかも
で、その考えに基づいて速やかに解に近づくようなcodeを書こうと
思ったけど、結構骨が折れてまだ完成しないｗ

866:780
15/09/21 01:39:22.93 jBw1B4c/.net
>>815 Perl
こった解探索ｱﾙｺﾞﾘｽﾞﾑの物はすぐできない感じなので、
愚直に1から探していくﾊﾞｰｼﾞｮﾝをまずは…
use feature qw{:5.16};
($s, $_) = (1, 1);
do {
　$_++;
　$s += (() = /1/g);
} while $s < $_;
say $_;

$ perl 7_814_x.pl
199981

次ページ