17/11/27 23:36:53.65 bwTh4Bk9.net
>>680
>>696の方法で作ってみました
n=10^10の時に48.3秒くらいです
751:デフォルトの名無しさん
17/11/28 13:09:45.40 IU/PYwM1.net
>>723 はHaswell (4770) 3.4GHz固定での結果で
Skylake (6700K) 定格だと38.4秒でした
ちゃんとCPUも進化してるんですね
752:デフォルトの名無しさん
17/11/28 13:17:18.48 IU/PYwM1.net
>>681
>>690
C++だとどうやって計算してるかが非常に気になります
32bitを越える値同士の乗算(結果が64bitを越える)部分
アセンブラだと
64bit x 64bit ===> 128bit
128bit / 64bit ===> 64bit
等があるのでそれを使っちゃってますが
753:デフォルトの名無しさん
17/11/28 13:20:30.03 IU/PYwM1.net
冪剰余を求めるのに
(a * b) % c
みたいなのがたくさん出てきませんか？
aもbもcも32bitの範囲を微妙に越えてて
754:デフォルトの名無しさん
17/11/28 14:44:32.26 jzUFRHpN.net
誤差部分の間違いが判った。これでよさげだ。
ただし誤差評価を荒くやってはダメそうだが。一番最後の行のところ。
誤差項ありのマクローリン展開は、0<=c<=xが存在して
f(x) = Σ x^k * f(k)(0)/k! (kは0からn-1まで) + x^n * f(n)(c)/n!
f(x) = -log(1-x)のn次導関数は、(n-1)!/(1-x)^n。
このときマクローリン展開は誤差項は x^n / (n*(1-c)^n)
x=1/2ならば、c=1/2のとき最大で、1/n
755:デフォルトの名無しさん
17/11/28 19:45:30.22 jzUFRHpN.net
これが収束速いようだ。
log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)
log((x+1)/(x-1))
= log((1+1/x)/(1-1/x))
= 2 Σ 1/((2n+1)*x^(2n+1))
756:デフォルトの名無しさん
17/11/28 22:18:22.38 7WoPw74F.net
>>728
1/log(2) ≒ 3.32
1/2log(161)+1/2log(49)+1/2log(31) ≒ 0.85
なので、計算に必要な項数は1/4程度
でも、1つの項の計算には時間がかかる
log(1-x)のマクローリン展開に0.5を入れた物は
分母が i * 2^i だから速く計算できるのだ
757:デフォルトの名無しさん
17/11/28 22:20:46.48 7WoPw74F.net
>>727
残りの項を等比数列と見なせば
簡単に誤差の上限が出ます
758:デフォルトの名無しさん
17/11/28 22:47:09.33 7WoPw74F.net
>>724
Haswellで33.96秒に縮まりました
シングルスレッドだと182.54秒で5.3倍
HTTが効くということは、
まだ多少改善の余地がありそう
一番内側のループは
vmulpd
vmulpd
vroundpd
vfmsub213pd
vfmsub132pd
vsubpd
なんと浮動小数点で計算してます
759:デフォルトの名無しさん
17/11/28 22:53:54.93 7WoPw74F.net
n=10000000000の時は
0000010101 でした
出題者さま、合ってます？
また、たまたまですが
n=10000000004では
0101010101
n=10000000005では
1010101010
になります
760:デフォルトの名無しさん
17/11/28 23:30:15.70 9HoDrqB3.net
一番内側のループのコード
URLﾘﾝｸ(fast-uploader.com)
PORT5がガラ空きで、処理のほとんどがPORT0,PORT1
こんなんでもHTTが効く
やっぱり浮動小数点はレイテンシがデカい
AVX512になれば
レジスタの数が倍になるので
8パラにしてレイテンシを隠蔽出来るんだけど
もちろんレジスタ長が倍になる方が大きい
761:デフォルトの名無しさん
17/11/29 13:17:33.09 mHyZby47.net
>>728は後半部分が間違ってるか。log((x+1)/x) = log(1+1/x) の展開を用いるのが正解で。
log(・)の中身を1に近づけた方が収束が早くなるが、
こういった分解 log(2) = 3log(81/80) + 5log(25/24) + 7log(16/15)はどうみつけるのか。
これは数値が(x+1)/x の形だけど、(x+1)/(x-1)の分解もあるのか。こっちだと計算するベキ項が一つ飛ばしにできる。>>728のように。
762:デフォルトの名無しさん
17/11/29 13:34:57.75 8/kTvoZy.net
2 = (81/80)^3 * (25/24)^5 * (16/15)^7
3 と 5 の指数の合計が0になる組み合わせを検索すれば良い
763:デフォルトの名無しさん
17/11/29 13:37:30.83 8/kTvoZy.net
log(81/80) = log(162/160) = log((161+1)/(161-1))
わかってて書いてるんだと思ったが
>>729のlogの中身はこの値
764:デフォルトの名無しさん
17/11/29 13:42:05.17 mHyZby47.net
>>728はそういうことか。みつけたやつのコピペで、そのとき考慮はしてなかった。
765:デフォルトの名無しさん
17/11/29 13:45:31.51 mHyZby47.net
指数も固定でなくていいはずで、
16/15よりかはたとえば1001/1000のほうが1に近いからそういうのはいくらでも見つけられるのかとおもった。
766:デフォルトの名無しさん
17/11/29 14:44:26.09 8/kTvoZy.net
分母分子の素因数の数と同じ項数が必要
例えば素因数が 2, 3, 5, 7 の4種類の場合、
1個差もしくは2個差のペアを4個探す
例えば
126/125
225/224
2401/2400
4375/4374
これらを適当に掛け算して2^nになるようにすると
項が4個の式がみつかる
767:デフォルトの名無しさん
17/11/30 00:31:43.08 H4qIjcIH.net
分母、分子とも 2, 3, 5, 7, 11, 13, 17 のみしか素因数を持たない形の場合、
以下が一番計算する項の数が少ないようです
log(2) = 72*log(126/125)+27*log(225/224)-19*log(2401/2400)+31*log(4375/4374)
768:デフォルトの名無しさん
17/11/30 05:07:54.11 fMs2N0Mh.net
>>740
その数値を検索すると、音楽のコンマというのが出てくる。関係あったり理論があったりするのか。
A.D. Fokker: Unison Vectors and Periodicity Blocks
URLﾘﾝｸ(www.huygens-fokker.org)
List of 7-prime limit accidentals - The?Sagittal?forum
URLﾘﾝｸ(forum.sagittal.org)
769:デフォルトの名無しさん
17/11/30 05:28:17.43 fMs2N0Mh.net
log(2)とは無関係で、単に一個差のやつで適当な素因数分解できるやつに名前がついてるだけ?
An Investigation into the Extraction of Melodic and Harmonic Features from Digital Audio
unit interval name
4375/4374 Ragisma
2401/2400 Breedsma
225/224 Septimal Kleisma
145/144 Difference between 29:16 and 9:5
126/125 Small Septimal Semicomma
121/120 Undecimal Seconds Comma
81/80 Syntonic Comma
URLﾘﾝｸ(scholar.sun.ac.za)
770:デフォルトの名無しさん
17/11/30 11:02:35.16 fMs2N0Mh.net
log2のほうは、分子・分母の素因数分解が似通ってないと成立しないってことで、
音楽のほうは小さい素数に限定して一個差ペアを求めたと理解。
log2のほうは、共通の素数で大きいやつを最初に固定すれば考えれば、よさげかと。
771:片山博文MZ
17/11/30 12:12:48.85 NsMGt5if.net
お題。横x[cm]、縦y[cm]の長方形のステンレスの１枚の板がある。この板からm枚の複数の長方形の部材を切り出す。
部材のサイズは配列で与えられる。
部材のサイズ(縦×横)はそれぞれだいたい決まっているが、1cm程度変わってもよい。
ただし、部材の縦または横が変わるとそれぞれ一点減点となる。
すべての部材を切り出すことができれば、減点がなるべく少ない方法の切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順になるべくたくさん部材を切り出せ。
772:片山博文MZ
17/11/30 12:19:33.84 NsMGt5if.net
テストデータ。
x=10, y=10,
{
{5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5}
}
x=5, y=12
{
{2, 5}, {3, 3}, {2,9}, {3, 2}, {4,3}
}
773:片山博文MZ
17/11/30 12:28:07.36 NsMGt5if.net
部材の縦と横は入れ替わってもよい。
可能ならば、切り出し方法をSVG形式で出力せよ。
774:片山博文MZ
17/11/30 12:51:59.04 NsMGt5if.net
切り出し方法は、
切り出す部材のx座標、y座標、幅、高さ
のリストとして出力せよ。
775:片山博文MZ
17/11/30 12:56:57.25 NsMGt5if.net
切り出しに余裕があるときは、なるべくx座標の大きい方、y座標の大きい方を残すようにせよ。
776:デフォルトの名無しさん
17/11/30 13:08:21.37 tkxPMdZc.net
斜めもOK？
777:デフォルトの名無しさん
17/11/30 13:08:55.87 tkxPMdZc.net
人間用のパズルで、斜めにしないと解けないのとかありそう
778:デフォルトの名無しさん
17/11/30 14:23:24.17 SHLZLl2M.net
問題文の条件が“だいたい”“なるべく”なんて
あいまい表現だらけ
これでプログラミングの問題かよ
779:片山博文MZ
17/11/30 16:18:01.24 NsMGt5if.net
斜めは考えなくてもよい。
訂正。
すべての部材を切り出すことができれば、減点が最小である切り出し方法を出力せよ。
すべての部材を切り出すことができなければ、面積が広い順に切り出せる部材の面積が最大になるよう部材を切り出せ。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。
780:680
17/11/30 17:10:37.24 8ZVWPbH7.net
>>732
そこにある3つとも正解です
当初は L = Σ1/(k*2^k) として
2^n * L の小数部分を愚直に求める方法を想定していました
781:デフォルトの名無しさん
17/11/30 17:26:52.63 r8WkgLop.net
普通に多倍長で計算したら計算量的に終わらないですよね？
n=314159265を求めるのに
冪剰余は使ってますよね？
おそらく私も同じような方法と思います
FMA3命令とOpenMPで高速化してるだけで
782:デフォルトの名無しさん
17/11/30 22:49:50.18 TklDiPhy.net
愚直という言い方は良く割りませんでしたね
仰る通り冪剰余は用います
783:片山博文MZ
17/12/01 14:26:32.50 fw1UFg83.net
再出題。横cx[cm]、縦cy[cm]の長方形または正方形のステンレスの１枚の板がある。この板からm枚の複数の長方形または正方形の部材を切り出す。
m枚の部材のサイズは(縦, 横)の配列で与えられる。
すべての部材を切り出すことができれば、切り出し方法を出力せよ。切り出しが不可能ならば「impossible」と出力せよ。
切り出し方法は、
(部材インデックス、部材の一番左のx座標、部材の一番上のy座標、幅、高さ)
のリストとして出力せよ。斜めの方向の切り出しは考えなくてもよい。
切り出しに余裕があるときは、x座標の大きい方、y座標の大きい方を残すようにせよ。ただし、x軸は右の向き、y軸は下向きとする。
テストデータ。
cx=10, cy=10, m=5, {5, 10}, {2, 2}, {2, 2}, {4, 3}, {6, 5}
cx=5, cy=12, m=5, {2, 5}, {3, 3}, {2, 8}, {3, 2}, {4, 3}
784:デフォルトの名無しさん
17/12/01 17:01:28.13 BqJQPTjH.net
頭の悪そうな文章だな
正方形⊂長方形
ステンレスの板の座標上の位置指定が無い
余裕がある場合の条件の意味が曖昧
785:片山博文MZ
17/12/01 18:41:36.20 fw1UFg83.net
ステンレスの板の左上座標は原点にあるものとする。
切り出しは、可能な限り、座標の小さい方を優先する(「余裕」の意味)。
786:デフォルトの名無しさん
17/12/01 20:32:10.86 9YSaSAW0.net
>>758
相変わらず曖昧な表現
全ての長方形の上辺と左辺がどこかに接していれば良いのか？
そうじゃないのか？
このような条件のを1個だけ見つければ良いのか
すべて見つけるのか
787:片山博文MZ
17/12/01 20:41:14.79 fw1UFg83.net
全ての部材の上辺と左辺が別の部材の辺、もしくは、元の板の端に接していること。
このような条件のをすべて見つけること。
788:片山博文MZ
17/12/01 20:43:57.24 fw1UFg83.net
なんか、工学関係でこのような問題があるらしいが、まだ解決策があるかどうかわからん。これが解ければ、実用化待ったなし。
789:デフォルトの名無しさん
17/12/01 21:15:23.73 9YSaSAW0.net
お題じゃなくて依頼かよ
790:デフォルトの名無しさん
17/12/01 21:19:54.38 9YSaSAW0.net
実用性なら
切り
791:やすさとか余り素材の形状とか そういうのが重要だろうに 問題として中途半端過ぎる
792:デフォルトの名無しさん
17/12/01 21:20:21.36 qVeescqP.net
また片山博文MZ が乞食をやってるのか
793:デフォルトの名無しさん
17/12/01 21:23:07.33 9YSaSAW0.net
普通に考えて、NP問題だろう
794:デフォルトの名無しさん
17/12/01 21:48:16.44 8H4JUlF5.net
なにやら揉めてますね
そろそろうんざりなので次のお題どうぞ
795:デフォルトの名無しさん
17/12/01 23:36:29.58 N1IVcYDB.net
スポーツスケジューリング問題。
796:デフォルトの名無しさん
17/12/03 02:47:12.16 QazTjKaA.net
お題ってこういうのでもいいのかな
a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
このように10個の整数を要素に持つ配列がある（整数の値は不定）
b = エントリーポイント
c = 移動する数量
d = 移動する距離
を与えることにより、配列の要素を移動させるプログラムを作りなさい
ただし配列の右端の要素を一つ移動させると、配列の左端に移動するものとする
例
a = 3, b = 1, c = 5, a = 0124567839
b = 1, c = 3, d = 1, a = 0412356789
b = 7, c = 1, d = 5, a = 1273456890
b = 0, c = 8, d = 1, a = 8012345679
b = 4, c = 5, d = 4, a = 6783901245
b = 9, c = 5, d = 4, a = 5679012384
b = 7, c = 3, d = 1, a = 9123456078
797:デフォルトの名無しさん
17/12/03 02:49:08.83 QazTjKaA.net
>>768
一番上の例は
b = 3, c = 1, d = 5, a = 0124567839
の間違いです
798:デフォルトの名無しさん
17/12/03 09:00:27.20 ucQfMVKf.net
>>768
URLﾘﾝｸ(ideone.com)
C++。なかなか素直な問題なのに邪悪な思念で見ていたため手間取った。
マニュアルを熟知していると簡単かもしれない。
799:デフォルトの名無しさん
17/12/03 09:04:48.71 b0AFqm0g.net
>>768 Ruby
URLﾘﾝｸ(ideone.com)
800:デフォルトの名無しさん
17/12/03 10:14:55.69 ZeeZWfzn.net
>>768
@Mathematica
URLﾘﾝｸ(ideone.com)
801:デフォルトの名無しさん
17/12/03 12:12:41.56 jbLAlLAh.net
>>768
b + c が10を超えることはありますか？
802:デフォルトの名無しさん
17/12/03 12:55:22.10 sC6phLBS.net
>>773訂正
b,c,dが10を越えることはありますか？
803:デフォルトの名無しさん
17/12/03 13:05:23.73 b0AFqm0g.net
>>771はb,c,dが任意の自然数でも大丈夫なようにしておいた
804:デフォルトの名無しさん
17/12/03 13:08:19.92 QazTjKaA.net
みなさんプログラム作るの早いですね
>>774
一応a、b、cの条件は、このようになると思います。
0 <= a <= 9
0 <= b <= 8
0 <= c <= 10 - b - 1
bとcは0では意味がないので、こっちのほうがいいのかな
0 <= a <= 9
1 <= b <= 8
1 <= c <= 10 - b - 1
805:デフォルトの名無しさん
17/12/03 13:12:58.80 QazTjKaA.net
>>776
すみません、間違えました、abcじゃなくてbcdですね
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - b - 1
806:デフォルトの名無しさん
17/12/03 13:34:35.32 QazTjKaA.net
>>777
すみません、訂正の訂正です。dは10-c-1ですorz
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - c - 1
807:デフォルトの名無しさん
17/12/03 17:47:25.64 Gq7SJlPX.net
Linked list 使うと楽そうな感じするな
808:デフォルトの名無しさん
17/12/03 18:26:21.27 QazTjKaA.net
>>770,771
せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね
それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね
>>772
Mathematicaは残念ながら持っていないので検証できませんでした
b = 8 c = 6 d = 2 a = 8901236745
b = 4 c = 3 d = 2 a = 0123784569
b = 4 c = 5 d = 2 a = 8123904567
b = 2 c = 5 d = 2 a = 0178234569
b = 0 c = 5 d = 3 a = 5670123489
b = 9 c = 3 d = 4 a = 3459016782
b = 5 c = 1 d = 7 a = 1253467890
b = 4 c = 6 d = 2 a = 8923014567
b = 6 c = 7 d = 2 a = 8901253467
b = 7 c = 5 d = 4 a = 5789016234
b = 4 c = 2 d = 2 a = 0123674589
b = 6 c = 4 d = 5 a = 4678950123
b = 7 c = 4 d = 4 a = 4789056123
b = 4 c = 5 d = 4 a = 6783901245
b = 8 c = 1 d = 5 a = 1238456790
b = 0 c = 2 d = 6 a = 2345670189
b = 3 c = 7 d = 1 a = 9120345678
b = 9 c = 4 d = 2 a = 4901256783
b = 8 c = 3 d = 6 a = 3456890712
b = 2 c = 5 d = 3 a = 0178923456
809:デフォルトの名無しさん
17/12/03 20:16:05.68 hV+xPFYR.net
>>768
ruby ワンライナー
URLﾘﾝｸ(ideone.com)
810:デフォルトの名無しさん
17/12/03 20:37:58.61 ucQfMVKf.net
>>780
お、あんた偉いな。
出題者でちゃんと答え合わせやってくれる人が稀でレスポンス薄いことが多いんだよ。
ちゃんと動いてよかったよ。
811:デフォルトの名無しさん
17/12/03 20:51:48.60 ucQfMVKf.net
>>774
自分は10超えてもらったら困るなぁ。
10っていうか、配列の要素数だな。
修正はそんなに難しくないけど。
812:デフォルトの名無しさん
17/12/03 23:00:23.32 QazTjKaA.net
>>781
1行プログラムすごいですね
さすがスクリプト言語
>>782
そうなんですか、でもいろいろな言語で回答されるから、出題者も大変かもしれないですね
私は問題の意味すらよく分からないことが多いので、もっぱら見る専ですが
813:デフォルトの名無しさん
17/12/04 02:36:11.06 iGjrIGoV.net
>>768
これでいいのかなあ？
Perl で書いた。
URLﾘﾝｸ(paiza.io)
814:デフォルトの名無しさん
17/12/04 06:47:18.44 Rc7ie/2s.net
>>785
b = 6、 c = 6、 d = 2
のときの動作がおかしいようです
8901452367
となるはずが
0167892345
となっており、移動する"678901"の並びが崩れてしまっています
815:785
17/12/05 02:32:35.27 LDxS5CId.net
>>786
問題勘違いしてました。素直にぐるぐる回すように修正しました。
URLﾘﾝｸ(paiza.io)
下の「入力」タブの方にスペース区切りで b, c, d の値を1行づつ並べて入れてから実行させると「出力」に結果が出ます。
とりあえず >>768 に書いてある値を入力にセットしたところ出力は同じになりました。
816:デフォルトの名無しさん
17/12/05 20:55:13.95 vy+ohhoY.net
>>787
入出力の確認をしただけですが、今回は問題ないようです
paiza使うと簡単に確認できて便利ですね
817:デフォルトの名無しさん
17/12/05 21:48:50.31 32LsMTj+.net
>>768
僕の頭だとどうしても右端から左端に行くときの動きがイメージできないので、解答締め切ったあとでもいいのでちょろっと教えてもらえると嬉しいです
上3つまではわかるけどそこから先がそもそも答えにたどり着けない……
818:デフォルトの名無しさん
17/12/05 23:47:14.24 ynbcQBXQ.net
>>789
ヒント。
(インデックス++)%配列の長さ
を繰り返すとどうなりますか？%は余剰デス。
819:デフォルトの名無しさん
17/12/06 00:25:49.49 gvvJf1Ph.net
>>789
上の３つまでは分かるということなので、３つめのcの値を一つずつ増やしてみると、こんな感じになります
"7"、"78"、"789"、"7890"と並ぶ数値が増えていっているのが分かると思います
c+d の合計は9が最高なので、これ以上cを増やすにはdを減らさなくてはなりません
b = 7 c = 1 d = 5 a = 1273456890
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 3 d = 5 a = 3478956012
b = 7 c = 4 d = 5 a = 4578906123
今度はcを2に固定して、dの値を一つずつ増やすと、こんな感じになります
"78"の並びが一つずつ右へずれていっているのが分かると思います
c+d の合計は9が最高なので、これ以上dを増やすにはcを減らさなくてはなりません
b = 7 c = 2 d = 1 a = 0123456978
b = 7 c = 2 d = 2 a = 8123456907
b = 7 c = 2 d = 3 a = 7823456901
b = 7 c = 2 d = 4 a = 2783456901
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 2 d = 6 a = 2347856901
b = 7 c = 2 d = 7 a = 2345786901
こんな感じで分かるでしょうか？私も自分の頭で考えると混乱しますw
820:デフォルトの名無しさん
17/12/06 00:31:57.65 +0bHqE6f.net
�
821:ｩ分の考え方は、配列の一部を切り取ってパッディングするんだけど、 まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。 すると、配列の後ろにはすでにパディングが終わった数列のができてる。 で切り取って削除して尻尾にくっつける。 で、さっき回した分を戻してやると完成。 という方法で、>>770を解いた。
822:デフォルトの名無しさん
17/12/06 00:32:05.18 +0bHqE6f.net
自分の考え方は、配列の一部を切り取ってパッディングするんだけど、
まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。
すると、配列の後ろにはすでにパディングが終わった数列のができてる。
で切り取って削除して尻尾にくっつける。
で、さっき回した分を戻してやると完成。
という方法で、>>770を解いた。
823:デフォルトの名無しさん
17/12/06 00:32:32.42 +0bHqE6f.net
あちゃー
二重投稿になったある。
そんなに大事でもないのだけど。
824:デフォルトの名無しさん
17/12/06 00:38:22.54 +0bHqE6f.net
C++は比較的不自由な言語なので頭使うのは鍛えられるよ。
パーツが少ないのでほとんど自作しないといけない。
825:デフォルトの名無しさん
17/12/06 00:46:18.89 DokUEpLm.net
コンパイルが必要とかでスクリプト系の言語より
使うことに不便があるかもしれないが、
できるアプリが自由で高速・軽量！
ライブラリもＳＴＬやboost以外にも、探せば便利なのがいっぱい。
826:デフォルトの名無しさん
17/12/06 01:07:01.76 +0bHqE6f.net
よそのライブラリ使うとイデオンで動かないからなぁ。
まぁ、業務ではライセンスに合ったものを使えばいいよ。
827:デフォルトの名無しさん
17/12/06 02:01:03.49 QVT4XBLu.net
>>789
塊が移動すると考えれば良い。
例えば 7, 4, 2 だとすると、 789 と先頭の 0 が移動する塊だ。
で、ちょっと分かり易くするためにこの塊を伏せて * で書くとするとこうなる。
*123456***
それでこの塊を右に一つずらす。その時に1は食われて尻尾から吐き出される。
**234561**
移動量2なのでもう一回右にずらす。すると2が食われて尻尾から吐き出される。
***345612*
それでは * から 7890 に戻してみよう。
8903456127
できあがり。
828:デフォルトの名無しさん
17/12/06 02:58:25.26 +0bHqE6f.net
>>793
これ間違ってるな。
最後尻尾にくっつけるんじゃなくて、適所にインサートだった。
で戻す。
書いた日から時間たってるからすまん。
829:デフォルトの名無しさん
17/12/06 08:41:18.93 obBhCrma.net
>>790
>>791
>>798
ありがとうございます
やっと理解できました
がんばって解いてみます
830:デフォルトの名無しさん
17/12/06 17:48:37.81 T95E7suL.net
log2だけど、これ使うといいらしいよ。分割統治法のBSA法というやつらしい。
2個ずつの積を繰り返すことで計算回数が減らせる。
{{1, a0}, {0, r}}*{{1, a1}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/rであり、
{{1, a0}, {0, r}}*{{1, a1}, {0, r}}*{{1, a2}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/r + a2/r^2。
上の式を実際に計算してみる。
URLﾘﾝｸ(www.wolframalpha.com)
831:デフォルトの名無しさん
17/12/06 21:09:44.45 N+lgs3o9.net
>>801
普通のlog 2の計算には使えても
>>680 には使えないかと
832:デフォルトの名無しさん
17/12/07 00:07:53.25 YC8MWngg.net
>>731 から更に縮まりました
もう誰も興味が無いかも知れませんが
コードいる？
833:デフォルトの名無しさん
17/12/07 09:24:10.80 XIHsqoOR.net
>>801でできるはずだ。やってみる
834:デフォルトの名無しさん
17/12/07 10:09:03.65 DjN/Fbox.net
n=10^10で19.28秒にまで縮めた
n=10^13くらいまでなら�
835:髏Qてる間に終わる >>804 期待してます！
836:デフォルトの名無しさん
17/12/07 15:54:52.13 XIHsqoOR.net
804だけど考えてみたら面倒なんだな。
有理数(整数)で完全に求めてから割り算するのは時間かかりそうだから、
展開も、割り算も、有限で打ち切って求める精度がでるようにするのが普通?
837:デフォルトの名無しさん
17/12/07 18:15:20.36 wGY0QmnN.net
お題
辺の長さが10,000以下の整数である直方体について
すべての面の対角線も整数となるものを全て求める
838:デフォルトの名無しさん
17/12/07 19:52:07.65 5gbe7aWB.net
対角線を出す式を忘れたのだ～。
数学って難しい。
839:デフォルトの名無しさん
17/12/07 20:10:49.23 bwV7uU+3.net
>>807
答えは浮かんだけど、
手元にインタプリタがないので書けない。
840:デフォルトの名無しさん
17/12/07 20:38:16.84 fmQCcJGl.net
>>808
えーと、ほら、三角形の三角形のアレ
841:デフォルトの名無しさん
17/12/07 21:23:21.04 BdlZ1dXv.net
>>805 のソース一式とexeです。
>>680 の回答となります。
URLﾘﾝｸ(fast-uploader.com)
実行ファイルは、拡張子をexe_からexeに変えてください。
OSはWindows 64bit Vista以降
CPUはHaswell以降
で動作します。
842:デフォルトの名無しさん
17/12/07 21:26:37.34 5gbe7aWB.net
作ってみたけど、オッセ―。
なんか数学的にやらないとダメぽ。
>>810
検索したら出てきた。
ただのHYPODだった。
843:デフォルトの名無しさん
17/12/07 21:34:41.35 5gbe7aWB.net
あ～ん。足し算10兆回かかるとかむりげーじゃ。
どうしようかこれ。
844:デフォルトの名無しさん
17/12/07 21:40:02.60 5gbe7aWB.net
>>807
URLﾘﾝｸ(ideone.com)
C++。ギブアップ。遅すぎだ。
デバッグ不完全だからそこを忘れないで。
多分1日かけても終わらないと思う。
845:デフォルトの名無しさん
17/12/07 21:40:16.73 BdlZ1dXv.net
>>807
特に大きな工夫もなく普通に3重ループで出来ましたよ
151個かな
846:デフォルトの名無しさん
17/12/07 21:42:04.13 BdlZ1dXv.net
URLﾘﾝｸ(ideone.com)
847:デフォルトの名無しさん
17/12/07 21:44:43.70 8KQwIEWy.net
>>807 Java
URLﾘﾝｸ(ideone.com)
こうでいいのけ？
848:デフォルトの名無しさん
17/12/07 21:48:20.51 5gbe7aWB.net
ぶ。おれは・・・いったい・・・。
だめだなぁ。才能ないなぁ。
849:デフォルトの名無しさん
17/12/07 22:07:39.64 BdlZ1dXv.net
>>817の意味がわからん
解説よろしく！
850:デフォルトの名無しさん
17/12/07 22:27:00.87 XIHsqoOR.net
>>801のように積へ変換した場合、どれ位の精度・桁数が必要なのか簡単にわからないな。
>>801でやると、誤差ありの巨大な数同士の掛け算になって、その結果誤差が拡大する。
和のままやると、適当に2ベキをかければ、各項の整数部分だけ計算すればよさそうだけど。
>>801は桁を十分にとったとしても、2進10桁以上の部分も計算途中で無視はできないか。
851:デフォルトの名無しさん
17/12/07 22:32:10.24 5gbe7aWB.net
グア。題意勘違いしてた。
直方体の対角線はいらんのか。うおー。
ばかばかー。
852:デフォルトの名無しさん
17/12/07 22:57:05.97 5gbe7aWB.net
>>807
URLﾘﾝｸ(ideone.com)
C++。書き直したら、>>816のパクリ見たくなった。
そしてそれでも遅いとかあかんなー。
うーん。なんでなんだろう・・・。
853:デフォルトの名無しさん
17/12/07 23:06:46.33 BdlZ1dXv.net
>>820
普通に、求めたい精度＋α の精度を保てば十分かと
演算回数はlog(n)のオーダーなので
普通にlog(2)を求める時には使える手法
854:デフォルトの名無しさん
17/12/07 23:06:47.69 8KQwIEWy.net
>>819
URLﾘﾝｸ(ideone.com)
適当にコメント付けた
855:デフォルトの名無しさん
17/12/07 23:18:28.32 8ACt5G91.net
物体は表面だけでなく無
856:数の内面を有するという考えは絶対に存在する 一方で全てを表面でしかとらえない人の存在も否定できない
857:デフォルトの名無しさん
17/12/07 23:24:59.96 BdlZ1dXv.net
このポエムをどうプログラミングしろと？
858:デフォルトの名無しさん
17/12/08 03:20:08.11 JkPU7Xcj.net
>>807 Ruby
URLﾘﾝｸ(ideone.com)
20秒程かかってしまう
859:デフォルトの名無しさん
17/12/08 12:45:22.72 lX5lg0SB.net
log2は>>801でもできそうだ。
積の先頭ほど精度が必要で、無視できる上限・下限を積の位置で可変にするか、
最初の積の計算で必要な精度をすべてに適用するかでいけそう。
860:デフォルトの名無しさん
17/12/08 14:42:05.63 3hyL4NRS.net
>>817
これパクってstd::bitset<10001>でやったら動かないかな
nextSetBitだけ作れば動きそう
861:デフォルトの名無しさん
17/12/08 17:20:05.13 qoqqt6pE.net
>>829
やってみた
いろいろ怪しいが速度は強烈に速いな
URLﾘﾝｸ(ideone.com)
862:デフォルトの名無しさん
17/12/09 00:08:31.54 NdkcUgXa.net
>>828
時間的に無理だろって話
863:デフォルトの名無しさん
17/12/09 02:59:25.21 C21Kkp0z.net
>>807
これでいいかな？
Kotlin で書いた。しかしpaiza.ioの制限なのか、何故か import kotlin.math.* がエラーだったので java.lang.Math の関数を使っている。
URLﾘﾝｸ(paiza.io)
864:デフォルトの名無しさん
17/12/09 09:05:25.04 WAlxvB4a.net
お題
10,000以下の三角形数をもとめる
865:デフォルトの名無しさん
17/12/09 09:42:44.72 HfcuYzyJ.net
>>833
三角数だよね？
.js
URLﾘﾝｸ(ideone.com)
866:デフォルトの名無しさん
17/12/09 10:35:24.71 PLdtTEIG.net
>>833 ruby
i,j=0,-1;p i while(i+=j+=1)<10000
867:デフォルトの名無しさん
17/12/09 21:40:06.26 PLdtTEIG.net
>>833 Brainf**k ワンライナー(笑)
URLﾘﾝｸ(ideone.com)
遅すぎて8bitまでしか計算できなかった
868:デフォルトの名無しさん
17/12/09 23:46:47.87 3TNSAl29.net
ideone.comはたいして最適化しないBrainf**k処理系だからな
869:デフォルトの名無しさん
17/12/10 00:50:34.10 J0bkBqjd.net
>>833
1+2+3+... だよね? じゃあこうだ。
perl -e '$i=0;$n=1;while(($i+=$n)<=10000){print"$i\n";++$n}'
870:デフォルトの名無しさん
17/12/10 00:52:24.37 J0bkBqjd.net
>>833
while じゃなくて for にするとこう。
perl -e 'for($i=0,$n=1;($i+=$n)<=10000;++$n){print"$i\n"}'
871:デフォルトの名無しさん
17/12/10 08:00:18.20 uc7Ht429.net
>833 R
cat(cumsum(0:140))
872:デフォルトの名無しさん
17/12/10 09:05:44.08 gZDGKqrG.net
>>801は精度管理の手間を考えたら、そのまま級数計算するのと大差ないと諦めたが。
こうすれば割り算の小数計算がほぼでないからいいのでは? 既に実装済?
an = 1/n、r = 2として、Σ an/r^n を定数C倍したやつの整数部分の取り出し。
C*anを再びanとおく。
Σ an/r^n
= a2/r^2 + a4/r^4 +・・・+ aN(2)/r^N(2) (添え字は2の倍数を動く)
+ a3/r^3 + a9/r^9 + a15/r^15 + ・・・+ aN(3)/r^N(3)
+ ap/r^p + ・・・+ aq/r^q + ・・・ (pは素数、qはp未満の数で割り切れないpの倍数)
= 1/N(2)r^N(2) * ( N(2)*a2*r^(N(2)-2) + ・・・ + N(2)*aN(2) ) + ・・
この分子部分は、各項、整数でそのまま計算しても>>801でも速くなるはず。
873:デフォルトの名無しさん
17/12/10 21:52:17.18 gZDGKqrG.net
>>841は添え字に被りが出ていて間違えてた。
874:デフォルトの名無しさん
17/12/10 22:07:36.99 XvO3Mos9.net
やってみて時間教えて
875:
876:デフォルトの名無しさん
17/12/10 22:08:42.09 XvO3Mos9.net
>>805 >>811 を抜ける？
877:デフォルトの名無しさん
17/12/10 22:22:45.57 gZDGKqrG.net
秒数ではCPU依存するから正確に比較できない。
掛ける2だけのループを10^10回するだけでも19秒では終わらない。
無料のideone codepadなどの実行可能時間以内にできる範囲とか、
ベースとなる簡単なコード、関数の何倍時間がかかるかなどだと比較できるけど。
878:デフォルトの名無しさん
17/12/10 22:36:08.95 3sNoocWL.net
演算回数の見積りは？
879:35歳
17/12/11 02:10:45.96 OsSLt9Cy.net
Bronze取りました
880:35歳
17/12/11 02:11:34.08 OsSLt9Cy.net
Bronze取りました
881:デフォルトの名無しさん
17/12/11 04:58:28.24 zs4BBX0s.net
くだらん話かも知れんけど
竹内関数のメモ化
URLﾘﾝｸ(ideone.com)
これはC++によるものだけど、C++や他の言語でもっと高速に書く方法はあるか？
882:デフォルトの名無しさん
17/12/11 05:19:34.19 zs4BBX0s.net
あ、ちなみにideoneの結果は間違っている
多分スタックオーバーフローしている
100, 50, 0の場合は答えは100
883:デフォルトの名無しさん
17/12/11 05:38:23.74 pBTqvDfH.net
>>849
constexprにすれば実行時はほぼ計算無しにできると思う。
コンパイル時間半端ないけど。
884:デフォルトの名無しさん
17/12/11 05:45:19.55 pBTqvDfH.net
ところで、いくらメモ化してても5回しか呼ばれないってことがあるのか？って気はする。
885:デフォルトの名無しさん
17/12/11 07:04:34.34 pBTqvDfH.net
URLﾘﾝｸ(ideone.com)
竹内関数constexprにしてみた。
ウチの環境だとこの辺のパラメータが限界っぽいかな。
100,50,0だとメモリ使い切るらしい。
886:デフォルトの名無しさん
17/12/11 07:09:30.00 pBTqvDfH.net
あら、コンパイルエラーになっちゃった。
VCだと通ったんだけど。もちろんステップ数とか設定はいじってるが。
887:デフォルトの名無しさん
17/12/11 08:32:22.37 gAGFZ0s2.net
>>849
こんなのとか？
たらいを回すならHaskella
2006年04月07日 22:09
URLﾘﾝｸ(blog.livedoor.jp)
888:デフォルトの名無しさん
17/12/11 12:03:51.37 uZdMj4Ux.net
お題
6つの辺の長さが 与えられた4面体の体積を求める
889:デフォルトの名無しさん
17/12/11 13:07:53.63 iSg/oyC4.net
お題
8つの辺の長さが与えられた超5面体の体積を求める
890:デフォルトの名無しさん
17/12/11 14:29:31.82 hKbhSguL.net
お題
与えられた自然数を高々四個の四角数(平方数)の和で表せ
891:デフォルトの名無しさん
17/12/11 14:35:19.85 k7Z6O4lr.net
>>856 Ruby
URLﾘﾝｸ(ideone.com)
ただし四面体ABC-Dに対して入力の順序は
AB BC CA CD DA BD とする
892:デフォルトの名無しさん
17/12/11 16:06:12.32 k7Z6O4lr.net
>>857
8つだと多胞体が一意に定まらないと思うんだが
893:デフォルトの名無しさん
17/12/11 16:48:32.53 qWzXCzKk.net
>>853
64bit環境でやったらスラッシング起きて＼(^o^)／
894:デフォルトの名無しさん
17/12/11 16:53:24.07 iSg/oyC4.net
>>860
じゃあ10個で
895:デフォルトの名無しさん
17/12/11 17:03:18.77 k7Z6O4lr.net
>>862
１０でも足りないと思うんだけどひょっとして超五面体って五胞体のつもりで言ってる？
896:デフォルトの名無しさん
17/12/11 17:31:58.31 iSg/oyC4.net
4次元の5胞体
897:デフォルトの名無しさん
17/12/11 17:32:53.55 iSg/oyC4.net
5C2=10
898:デフォルトの名無しさん
17/12/11 22:30:10.81 pBTqvDfH.net
>>861
ウチはi6700メモリ8Gだな。20秒くらいボケーっとしてたらコンパイル完了する。
実実行より全然早い。
899:デフォルトの名無しさん
17/12/11 23:43:41.01 jF/PrBtV.net
>>866
んー32bitでコンパイルしてみるかな
64bitはマジ卍ヤバい
900:デフォルトの名無しさん
17/12/12 00:19:40.23 JpJzeAvs.net
>>866
悪い
VCで /constexpr:steps 1000000を付けてコンパイルしたら4秒ほどでコンパイルが終わった
多分/MPも付けてるからだと思う
実行結果は25になった
gcc 7.2.0 64bitだとどんどんメモリを食って行って最後にスラッシングが起きる
馬鹿正直な実装をしているからかも知れないね
VCの方がいろいろとメモリを食わないように工夫されてるのかも
Clangでも/constexpr:steps は -fconstexpr-steps という形でサポートされてるようだから
多分行けると思う
メモリ64G積んでるし
901:デフォルトの名無しさん
17/12/12 01:27:56.58 qpuoD4bc.net
>>868
いいマシーンだな。
まぁ、ウチはあれくらいで資源尽きちゃうけど、メモリ64Gもあったらもっと行けるな。
気が向いたらどうぞ。
902:デフォルトの名無しさん
17/12/12 04:08:00.08 SvlIPxM4.net
>>858 Java
URLﾘﾝｸ(ideone.com)
903:デフォルトの名無しさん
17/12/12 22:52:21.86 38dJ/vud.net
以下のURLのように、同じ色の点同士をつなぐゲームがある。
URLﾘﾝｸ(play.google.com)
N×Mの2次元配列が与えられる。配列の各要素は半角英字('a'-'z')または'*'である。
半角英字は色付きの点を表し、'*'は空のマスを表す。
'*'以外の文字は、配列中に必ず2個ずつ存在する。
このパズルの解を一つ出力せよ。
・'-'は左右のマスをつなぐ
・'|'は上下のマスをつなぐ
・'.'はマスをつながない
解がない場合は"No solution"と出力せよ。
[input]
***rg
**bg*
r****
ob*yo
****y
[output]
*-*-*-r.g
|.......|
*.*-b.g-*
|.|......
r.*.*-*-*
..|.|...|
o.b.*.y.o
|...|.|..
*-*-*.*-y
904:デフォルトの名無しさん
17/12/15 09:30:54.91 gDuLBiTf.net
>>841
やってはないけど、そもそもこれ間違ってるのと、同じような発想でやるとしても
全ての素数での分類ではなく、3分割くらいのほうが効率がいいのと、
Σ (2の倍数) + Σ (3の倍数かつ2の倍数でない) + Σ (2と3で割り切れない)
分割する事もなく、N項の和だとしたらNの階乗か分数をなくせる最小公倍数かけてもいい。それだと掛け算もしくは割り算がいくつも出てくるが。
905:デフォルトの名無しさん
17/12/16 14:04:43.43 +Cq6iaDY.net
>>871
等幅フォントで表示しているエディタにコピペしてようやっと何を言わんとしているか分かった。
それってマスとマスの間に - または | を入れて繋ぐってことでいいんだよね? で、つながない所がピリオドだと。
(まあ等幅フォントのASCIIでやるならそれしか方法ないとは思うけど)。
906:デフォルトの名無しさん
17/12/16 14:07:59.25 +Cq6iaDY.net
しかしピリオドは
**
**
の時に
*.*
...
*.*
のようになって中央のピリオドが本来なら不要なものになるわけだが、それはスペースでなくても良いのかな？
まあただの幅合わせだからどうでもいいものではあるが。
907:デフォルトの名無しさん
17/12/17 12:04:31.10 V69L7+t+.net
>>801 の方法で出来ると書いてるけど
結局誰もやってないのか
個人的には(高速には)出来ないと思っている
908:デフォルトの名無しさん
17/12/17 12:18:14.72 V69L7+t+.net
>>871
課題じゃなくて
単にソルバーの作成依頼でしょ
909:デフォルトの名無しさん
17/12/17 17:50:05.54 3PMrWzl3.net
無理に線引かないでrだのgだので埋めた方がわかりやすいと思うがな
すべてのマスを埋めなければ
910:ならないルールが抜け落ちてるみたいだから 実は別物のゲームで交差があるとかなったらそうはいかないが
911:デフォルトの名無しさん
17/12/17 20:33:27.61 0HU8GFa9.net
ブレゼンハム的なやつって、始点と傾き(と区間や境界等で決まる明示されない終点)が
与えられた際に、終点座標を求めてから始点に向かうのってアリなんだろうか？
912:デフォルトの名無しさん
17/12/18 08:21:39.40 T+ClDj4W.net
ここでやるには問題がでかすぎ
100分割してほしい
913:デフォルトの名無しさん
17/12/21 14:37:42.61 /SOyyWKP.net
>>871 Ruby
URLﾘﾝｸ(ideone.com)
ただし解は1つでありかつ線が通らないマスは無いことを前提とする
問題はここから引用:→URLﾘﾝｸ(www.nikoli.com)
914:デフォルトの名無しさん
17/12/21 14:38:13.66 /SOyyWKP.net
あ、あと出力方法は自分好みに適当にいじってる
915:デフォルトの名無しさん
17/12/21 15:58:54.33 jrnuCabF.net
訂正
ただし解は1つでありかつ線が通らないマスは無いことを前提とする
ではなく
解が存在すればすべての解は全てのマスを通ることを前提とする
916:デフォルトの名無しさん
17/12/22 19:30:58.88 PPoMR9m8.net
お題
22の分割(たとえば3+3+5+8)のうち
分割したそれぞれの数の逆数の和が1になるものを求める
917:デフォルトの名無しさん
17/12/22 19:39:05.90 PPoMR9m8.net
早速間違えましたすみません
3 +5 +6 +8
でした
918:デフォルトの名無しさん
17/12/22 20:06:25.02 FRcsVGN9.net
>>883 ruby
f=->n,k{n==1?[[k]]:(1..k/n).flat_map{|i|f[n-1,k-i].map{|j|[i,*j].sort}}.uniq}
(1..22).each{|i|f[i,22].each{|a|p a if a.map{|e|1r/e}.sum==1}}
#=>[2, 4, 8, 8]
[2, 5, 5, 10]
[3, 3, 4, 12]
919:デフォルトの名無しさん
17/12/22 21:21:23.60 Mb+deFNF.net
C++で書いたけど、オセー。
デバッグ大変だ。
うーん。困ったなぁ。
920:デフォルトの名無しさん
17/12/22 22:04:05.10 Mb+deFNF.net
URLﾘﾝｸ(ideone.com)
C++。こんなコード書いてみたけど、無理ゲー。
ちょっと厳しいなぁ。最近解けてないなぁ。
ちなみにデバッグ不完全なのであしからず。
921:デフォルトの名無しさん
17/12/22 22:16:42.15 cfNB9eDL.net
こういう数学的な問題を解くにはやっぱりプログラミング以前に数学を勉強した方がいいのでしょうか？
922:デフォルトの名無しさん
17/12/22 22:23:25.38 Mb+deFNF.net
>>888
数学は大事だよー。
俺数学出来ないから、解けない問題がそれなりにある。
算数では限界だ～～。
まぁ、数学とプログラミングって習得時はオーバーラップするところが少ないから融合するまでちょっと大変かな。
でも数学は強力なツールです。
923:デフォルトの名無しさん
17/12/22 22:40:51.06 wxhiocJz.net
一般論でいえば必要だろうけど>>883なんて全部列挙したところで計算量はたかが知れてるし
目下必要なのは論理学的思考能力なのでは
924:デフォルトの名無しさん
17/12/22 22:51:38.40 rSDEoHGj.net
>>883 Java
URLﾘﾝｸ(ideone.com)
22くらいなら大丈夫だけど桁が増えると(´・ω・`)
925:デフォルトの名無しさん
17/12/23 10:08:16.78 t1pvAVGb.net
お題
52をいくつかの自然数に分解して
それらの最小公倍数を最大化せよ
926:デフォルトの名無しさん
17/12/23 10:30:51.64 NDYwz7Jw.net
分解って、積じゃなくて和で良いんだよね？
数学の知識を使うと一瞬だけど
927:デフォルトの名無しさん
17/12/23 10:47:21.72 xQ13BTQc.net
>>892
2*3*5*7*11*23
928:デフォルトの名無しさん
17/12/23 10:51:04.98 NDYwz7Jw.net
>>894
ダメだろ
929:デフォルトの名無しさん
17/12/23 10:54:01.61 NDYwz7Jw.net
数学の知識が無いなら素直にコンピューターの力を借りなさ
930:い
931:デフォルトの名無しさん
17/12/23 11:07:49.77 afY4COyy.net
そもそも数学で簡単にとけない問題を力わざでとくための計算機だろ
932:デフォルトの名無しさん
17/12/23 11:20:55.96 2Y/dvvuZ.net
>>894
よくわからんが52の場合は
180180 [3, 4, 5, 7, 9, 11, 13]
ということらしいぞ
933:デフォルトの名無しさん
17/12/23 11:22:52.27 TLP4YLw7.net
2+3+5+7+11+13+11=52
934:デフォルトの名無しさん
17/12/23 11:23:44.11 ZIVZRbx3.net
C++17発行されたから開発環境がさっさと対応してGCDくらい使えるようになりたい。
935:デフォルトの名無しさん
17/12/23 20:45:26.14 PT43Bq9S.net
>>768の問題で0<=b<10,0<c<10という制限がついた時
移動を何回か繰り返すと必ず元に戻るんだけど
その回数はbには無関係にc,10-c,10の最小公倍数で
okかな？
936:デフォルトの名無しさん
17/12/23 23:54:31.73 PT43Bq9S.net
一回の移動ではd=1ね。
ま、その制限を付けなくともd,c,10-c,10の最小公倍数になるんだろうけど
937:デフォルトの名無しさん
17/12/24 06:15:12.28 C5ELqEVz.net
>>901-902
10-c,10の最小公倍数じゃね？
938:デフォルトの名無しさん
17/12/24 12:14:01.21 PCWcyI8B.net
>>899
>>896
939:デフォルトの名無しさん
17/12/24 13:55:05.53 aCkD6VOe.net
数学云々言ってる奴って、何故かその成果見せないよな。
俺でも出来そうなFUD、いやマウントかな。
940:デフォルトの名無しさん
17/12/24 16:16:06.49 7ASFTRv4.net
ていうか、計算機はどちらかというと算数だよな。
数学は公式とか証明とか、そういう手順みたいなものを考えるわけで、プログラミングに近い。
コンピュータは作られたプログラムに従って計算結果を出すだけ。
もちろんプログラムそのものをコンピュータに作らせることも可能だけどね。これは次元が違う話だよね。
941:デフォルトの名無しさん
17/12/24 20:21:20.17 TJswah5E.net
プログラムには算数と三角関数とかがあればいい
あとN進法
942:デフォルトの名無しさん
17/12/24 22:49:45.08 ke4WkGne.net
行列演算とか諸々の配列操作関数がないと無理だな
943:デフォルトの名無しさん
17/12/24 23:49:37.37 HHMC0VFW.net
では簡単なお題を
bを底とする値vを、2～36進数に変換し表示してください。
なお、bは2～36の整数、vは0以上の整数とし、不正な入力はないものとしてよい。
また、底と値の区切り文字は入出力ともに特に問わない。
[入力例]
16 deadbabe
[出力例]
2#11011110101011011011101010111110
3#100122100210210001200
4#3132223123222332
5#30122344134421
6#1414413520330
7#161402600604
8#33653335276
9#10570723050
10#3735927486
11#1647919685
(略)
27#9h9ll1i
28#7l225hi
29#6842o9l
30#53m7kg6
31#46f9hir
32#3farelu
33#2tf7mor
34#2e7m366
35#214kbpb
36#1ps9w3i
944:デフォルトの名無しさん
17/12/25 00:09:45.09 3pQBp6tI.net
>>909 Java 手抜き実装二つ
URLﾘﾝｸ(ideone.com)
URLﾘﾝｸ(ideone.com)
945:
17/12/25 00:32:41.94 LEWwY/wL.net
>>909
c++old ｽﾚﾘﾝｸ(tech板:29番)
946:デフォルトの名無しさん
17/12/25 02:44:06.33 FXcNW9u1.net
>>909 ruby
n=eval"%2$p.to_i %1$d"%"16 deadbabe".split
(2..36).each{|i|puts"%d#%s"%[i,n.to_s(i)]}
947:デフォルトの名無しさん
17/12/25 04:27:01.50 Cnt90MG5.net
>>909
URLﾘﾝｸ(ideone.com)
C++。まぁこれくらいなら算数でも解ける範囲や
948:な。 ただしコードがバグってないとは言ってない。へへ。
949:デフォルトの名無しさん
17/12/25 06:21:01.65 P1JMpVx5.net
>>909 lisp
URLﾘﾝｸ(ideone.com)
950:デフォルトの名無しさん
17/12/25 12:28:00.12 Lg9qxqUa.net
>>909
Kotlinらしくしてみようとはしたが、あまりにも短く、更に俺がまだよくKotlinを知らないためにこんな風になった。
URLﾘﾝｸ(paiza.io)
肝心な所はJavaとほぼ同じ。
951:デフォルトの名無しさん
17/12/25 19:56:50.93 IEH/2als.net
>>909 F#
URLﾘﾝｸ(ideone.com)
952:デフォルトの名無しさん
17/12/26 10:23:38.85 Hd2qVaf/.net
>>909 Squeak/Pharo Smalltalk
| n |
n := '16 deadbabe' replaceAll: Character space with: $r; asNumber.
2 to: 36 do: [:i | Transcript cr; show: i; space; show: (n radix: i) asLowercase]
953:デフォルトの名無しさん
17/12/28 04:53:27.57 N8L362th.net
お題を捏造してやるぜ。
アンサーが42になる式を捏造せよ。という数学パズル。
小難しい式をでっち上げた人が優勝。
算数から数学、物理まで式になってればすべての手法が使用可能。統計とかでもいいよ。
制約は答えが42になることのみ。
解けるものはいるか？
954:デフォルトの名無しさん
17/12/28 04:55:12.31 N8L362th.net
あー、忘れてた。
ちゃんと検算して答えを確認できること。
俺、算数しかできないから、各種サービスにかけて検算できるのが望ましい。
955:デフォルトの名無しさん
17/12/28 04:57:55.88 8O6aNcDe.net
ぷろぐらみんぐ・・・？
956:デフォルトの名無しさん
17/12/28 05:01:29.85 N8L362th.net
ベンチマーク的な感じだな。
たまには本気を出したいだろ？お前ら。
957:デフォルトの名無しさん
17/12/28 05:04:57.45 N8L362th.net
当たり前だが、必要な関数が標準ライブラリになかったら自作すること。
958:デフォルトの名無しさん
17/12/28 07:10:57.10 s+AqweGp.net
>>918 ruby
require 'open-uri'
expr = "the Answer to the Ultimate Question of Life, the Universe, and Everything"
uri = "URLﾘﾝｸ(www.google.com)
puts open(format(uri, expr.gsub(' ', '%20'))).string[/data="\K[^"]*/]
#=> 42
959:デフォルトの名無しさん
17/12/28 07:34:31.76 N8L362th.net
>>923
元ネタはそれ。正解の一端。
960:デフォルトの名無しさん
17/12/28 08:07:25.24 i+4FV8XV.net
>>918
brainfuck
URLﾘﾝｸ(ideone.com)
961:デフォルトの名無しさん
17/12/28 09:35:15.49 wX0EFIYP.net
>>918
難しさの判定を人間が気分でするしかないとなると死ぬまで気に入らないと
言い続けて終わらないようにもできてしまうわけで、少なくともお題の判定
方法としては適切ではないのではないか？
962:デフォルトの名無しさん
17/12/28 11:19:23.23 ZkyapKMq.net
式を捏造せよと言ってんのに、検算して答えがあってることを確かめろとか矛盾してて草
963:デフォルトの名無しさん
17/12/28 11:41:23.15 N8L362th.net
>>925
基本的かつ合理的。
>>926
投票制にする？
>>927
答えは42になることだけは決まってるんだから、検算できないのはどういう理由？
プログラミングやるんだから、イデオンとか使うんじゃだめなの？
964:デフォルトの名無しさん
17/12/28 15:25:23.94 0tvuK50P.net
片山に次ぐ逸材かもしれないが出題者が馬鹿だとやる気が出ないという良い見本
965:デフォルトの名無しさん
17/12/28 15:31:12.30 N8L362th.net
自由を泳げないって不便だね。
何やっても良いんだからなんかすればいいって話なんだけど。
定型の答えなんか求めてないのは出題見ればわかるだろ。
発想力が欠如してるんじゃないか？
基本的にベンチマークだと言ってるでしょ？
捏造っていう言葉が悪かったら謝るが。構成しろってことにすれば大体同じや。
966:デフォルトの名無しさん
17/12/28 15:32:51.23 N8L362th.net
口だけのやつはぶっぶーですわ。
967:デフォルトの名無しさん
17/12/28 16:00:26.20 4ng0NpPh.net
自由を泳げないって
968:デフォルトの名無しさん
17/12/28 18:49:12.75 Er3In3fn.net
Cコ:彡
969:デフォルトの名無しさん
17/12/29 00:30:23.43 +gfutoXL.net
>>909 rust
URLﾘﾝｸ(ideone.com)
・BigInt不使用
・n.to_s(b)の形にしたかったが素早く諦めた
・色んなところに迷いと妥協が見え隠れ
970:デフォルトの名無しさん
17/12/29 02:28:40.84 IV3yH5ho.net
お題：入力があったら6面のサイコロを振って出た目を出力してください
ただし数字を使ってはならない
971:デフォルトの名無しさん
17/12/29 03:07:31.93 GekNq94X.net
そういう数字を使ってはいけないって誰得なの？
972:デフォルトの名無しさん
17/12/29 05:31:16.53 5y9SQxLe.net
>>935
Unicode の U+2680 ～ U+2685 は?
??????
973:デフォルトの名無しさん
17/12/29 09:00:41.20 IV3yH5ho.net
>>936
さぁ。。。
>>937
確認してないけどいいのでは
974:デフォルトの名無しさん
17/12/29 09:20:10.35 GekNq94X.net
>>935
URLﾘﾝｸ(ideone.com)
C++。こんな感じ？
975:デフォルトの名無しさん
17/12/29 09:29:20.12 GekNq94X.net
URLﾘﾝｸ(ideone.com)
こっちの方がそれっぽいか。
976:デフォルトの名無しさん
17/12/29 20:57:46.71 QkO9em45.net
数字を使ってはならないってのが謎
AAで出力しろってか？
977:デフォルトの名無しさん
17/12/29 21:21:03.51 aTe03Y1I.net
>>935
Rubyで。
p rand('abcdef'.length) + 'z'.length
978:デフォルトの名無しさん
17/12/29 21:28:13.36 FAMD2vO+.net
数字を使うなって表示なのかそれともソースなのか？
表示なら
●●●●●●とか
979:デフォルトの名無しさん
17/12/29 21:29:41.90 u/2CuQjm.net
両方だろ
980:デフォルトの名無しさん
17/12/29 21:50:46.64 VnRfvHlH.net
そもそも入力が何なのかすら意味不明。却下
981:デフォルトの名無しさん
17/12/29 22:22:21.11 1z8qBjEb.net
お題
自然数 n を入力とし, a と b を乗ずると n になるような自然数 a と b を出力する.
a と b の侯補が複数存在する場合は, a と b の和がもっとも小さなものを出力すること.
982:デフォルトの名無しさん
17/12/29 22:32:07.85 5y9SQxLe.net
>>938
じゃあUnicodeのU+2680からの文字を使った版。Kotlinで。
URLﾘﾝｸ(paiza.io)
入力があったらの部分は最初の readLine() だ。
下の「入力」タブの所で改行を一つ入れてあるので開いたら即出力がある。
983:デフォルトの名無しさん
17/12/29 23:03:49.04 5y9SQxLe.net
>>935
また Kotlin。
サイコロの目の一つは5x5ビットあれば表現できるので配列に詰め込んで後で変換して出すようにした。
URLﾘﾝｸ(paiza.io)
別に配列でなくてもとにかく 5*5*6 (=150) bit 詰め込めるなら何でも良い。
984:デフォルトの名無しさん
17/12/29 23:13:30.16 VnRfvHlH.net
>>946
15.times{|n|
sqrt_n = Integer.sqrt(n)
(2 * sqrt_n..n + 1).each { |s|
(sqrt_n..n).each { |i|
next unless i * (s - i) == n
puts '%d * %d = %d' % [i, s - i, n]
break
} || break
}
}
0 * 0 = 0
1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 2 = 4
5 * 1 = 5
2 * 3 = 6
7 * 1 = 7
2 * 4 = 8
3 * 3 = 9
5 * 2 = 10
1
985:1 * 1 = 11 3 * 4 = 12 13 * 1 = 13 7 * 2 = 14
986:デフォルトの名無しさん
17/12/29 23:14:32.74 VnRfvHlH.net
>>949はRuby2.5.0ね
987:デフォルトの名無しさん
17/12/29 23:25:01.60 IY4nOP57.net
>>935
URLﾘﾝｸ(paiza.io)
988:デフォルトの名無しさん
17/12/30 00:34:17.12 64dx8gku.net
>>946
def r9_946(n)
Math.sqrt(n).to_i.downto(1) do |e|
return [e, n / e] if (n / e) * e == n
end
end
1.upto(100) do |n|
a, b = r9_946(n)
printf("%d = %d * %d¥n", n, a, b)
end
989:デフォルトの名無しさん
17/12/30 00:45:39.83 6/kbfUjB.net
>>949から100倍くらい早くなった
URLﾘﾝｸ(ideone.com)
990:デフォルトの名無しさん
17/12/30 01:37:16.58 2QbO+yEX.net
>>951
出目が0～6？
確率的には
0: 1.56%
1: 9.38%
2: 23.44%
3: 31.25%
4: 23.44%
5: 9.38%
6: 1.56%
くらいか？
991:デフォルトの名無しさん
17/12/30 09:12:17.38 6VD4P8Az.net
>>946
URLﾘﾝｸ(ideone.com)
C++。条件足りてるかよくわかってないけど、適当に書いたらそれぽい感じになった。
あってる保証はない。
992:デフォルトの名無しさん
17/12/30 09:19:03.41 6VD4P8Az.net
なんか俺の劣化>>953みたいな感じだな。
うーん。名案だとは思ったのだけど。むむむ・・・。
993:デフォルトの名無しさん
17/12/30 09:31:25.37 6VD4P8Az.net
うほ、フィルターしてる条件にバグがあった。良く動いてたな。
994:デフォルトの名無しさん
17/12/30 09:33:18.81 6VD4P8Az.net
これ、片方1のやつって素数かな？
エラトステネスの篩とどっちが軽いかな。
995:デフォルトの名無しさん
17/12/30 12:46:04.20 ZPxTZMGf.net
お題
要素が素数, かつ要素の総和が2018になる集合のうち, 要素数がもっとも大きい集合を出力する.
996:デフォルトの名無しさん
17/12/30 12:59:47.50 64dx8gku.net
>>959
[2]*(2018/2)
997:デフォルトの名無しさん
17/12/30 14:25:23.55 6VD4P8Az.net
>>959
URLﾘﾝｸ(ideone.com)
C++。DPの練習。必要な数はわかったが過程の表示の仕方がわからない。
どうすれバインダー。Orz
998:デフォルトの名無しさん
17/12/30 15:14:55.24 6VD4P8Az.net
>>961
URLﾘﾝｸ(ideone.com)
C++。あってるか知らんけど、力業でベタ作業した結果、それっぽい数字にたどり着いた。
と、思ったら全然違う数字を指していた。
999:デフォルトの名無しさん
17/12/30 15:16:57.66 6VD4P8Az.net
>>959
URLﾘﾝｸ(ideone.com)
C++。でけたー。DP難しいなぁ。
1000:デフォルトの名無しさん
17/12/30 15:18:24.57 ZOKm+QEU.net
>>959
それ1なのでは?
1001:デフォルトの名無しさん
17/12/30 15:25:04.70 6VD4P8Az.net
要素数だから、コンテナカウントだと思って書いたんだけど。
え？題意勘違いしてる？
1002:デフォルトの名無しさん
17/12/30 15:25:53.45 6VD4P8Az.net
element countだよね？
1003:デフォルトの名無しさん
17/12/30 15:30:31.85 qiSXHyFx.net
2が1009個ある集合、>>960で答えが出てる
1004:デフォルトの名無しさん
17/12/30 15:32:23.03 6VD4P8Az.net
>>967
あー、それそういう意味だったのか。
うわー俺、蛇足だった。
1005:デフォルトの名無しさん
17/12/30 15:36:57.18 6VD4P8Az.net
>>967
それをさ、プログラムで解くのきつくない？
総当たりしないと俺は無理。重複許可すると途端に大変になる。
1006:デフォルトの名無しさん
17/12/30 16:05:45.05 6VD4P8Az.net
URLﾘﾝｸ(ideone.com)
適当に拡張してみたが、搭載メモリ8Gを使い切ってしまいデバッグ不可。
これ、意外と難問かもしれん。
1007:デフォルトの名無しさん
17/12/30 16:20:15.12 6VD4P8Az.net
ちょっとくどいけど、
これさ、量子アニーリングじゃないと解けないやつかなぁ？？
なんかさっきからいじってるけど、ローカルポケットに落ちてる気がする。
グローバルポケットに落とす方法が皆目見当つかない。
解説頼む。
1008:デフォルトの名無しさん
17/12/30 16:48:17.65 ZPxTZMGf.net
すみません, お題での 集合 は Ruby では Setクラス のような, 要素に重複や順序性のないものを考えていました.
想定していた回答例は以下です.
answer
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 113 127 131 137 139)
(apply #'+ answer)
2018
(length answer)
33
1009:デフォルトの名無しさん
17/12/30 17:07:30.49 YKsh4iwJ.net
9個まではすぐ見つかるんだけど10個になった途端重くなる
10個の場合は存在しない？
逆に21個や33個の場合はすぐ見つかるんだ、どういう分布なんだろな
1010:デフォルトの名無しさん
17/12/30 17:11:07.91 6VD4P8Az.net
>>972
おー、よかった。どこまで深淵があるのか怖かったよ。
多分、>>963であってると思う。たぶん。
1011:デフォルトの名無しさん
17/12/30 18:48:52.49 YKsh4iwJ.net
>>959 C#
URLﾘﾝｸ(ideone.com)
33個と決め打ちした場合は4通りがすぐ出る
そのあと延々ループしてるがTime limit exceededで打ち切ってくれる
1012:デフォルトの名無しさん
17/12/30 21:03:54.80 30TR5CU8.net
>>959
１も素数なんだが１が2018個ある集合はありなのか?
それだとお題としてほとんど意味のないひっかけ問題みたいになるわけだが、
そうではないなら問題を修正しろ。
1013:デフォルトの名無しさん
17/12/30 21:15:48.77 KgXg1sy3.net
＞１も素数なんだが
＞１も素数なんだが
＞１も素数なんだが
1014:デフォルトの名無しさん
17/12/30 21:23:36.74 bLWDJrON.net
>>977
あ、2か。
でも問題がこれだと同じことだよなあ。
1015:デフォルトの名無しさん
17/12/30 21:26:45.29 bA88XQgg.net
>>976
4つ上のレスも確認できないくせに何言ってんの
1016:デフォルトの名無しさん
17/12/30 21:42:01.90 ZPxTZMGf.net
一般に, 素数は 1およびその数自身のほかに約数を有しない正の整数 と定義されますので, ここではその定義に従います.
また一般に, 重複や順序性のない もののあつまり を 集合(set) と呼ぶことが多いので, ここではその用法に従います.
集合(set)に対して, ものをならべたものは列(sequence)と呼ぶことが多いです.
ここでは『AABBCC』は文字列ですが, 文字集合ではないとします.
% irb
irb(main):001:0> require 'prime'
=> true
irb(main):002:0> 1.prime?
=> false
irb(main):003:0> 2.prime?
=> true
irb(main):004:0> require 'set'
=> true
irb(main):005:0> Set.new([1]*2018).size
=> 1
1017:
17/12/31 00:33:09.15 UjqOw9qv.net
お題：指定した複数の wav フォーマットを連結して一つ wav ファイルを作成するプログラムを書け
・ファイルの指定方法はコマンドライン引数指定でかまわない
・wav ファイルフォーマットの仕様上の上限である 4GiB まで正常に結合できることを必須の最低条件とする
・PCM フォーマット・ステレオ2ch・サンプリング周波数 44.1kHz に対応しておればよい
・GUI に対応しておればなおよい
背景：いや、いろいろダウンロードして試しているのだけれども、4GiB まで正常に結合できるソフトウェアが見つからないのです‥
1018:デフォルトの名無しさん
17/12/31 01:09:52.02 iFZSMKfw.net
それでこのスレに辿り着くのは面白い
1019:デフォルトの名無しさん
17/12/31 01:21:45.50 QH0un2fa.net
前からこのスレにいる人でしょ。
お題としてはまったくこのスレに向いてないと思うが。
1020:デフォルトの名無しさん
17/12/31 01:55:26.47 mjAZsjOp.net
2000から3000位まで試してみたが、大体33前後になるみたい
(微妙に増加していくが緩慢)
1021:デフォルトの名無しさん
17/12/31 03:02:32.19 rf+Z6LCT.net
>>981
これ使えないか?
URLﾘﾝｸ(hakobe932.hatenablog.com)
1022:デフォルトの名無しさん
17/12/31 05:23:36.13 Q5J3BQB7.net
>>981
waveチャンクって2gbまでだっけ？sizeフィールドが32bitsignedだったような気がするんだけど。どうだっけ？
1023:デフォルトの名無しさん
17/12/31 05:28:08.43 Q5J3BQB7.net
書き出すのはそんなに難しくないんだけど、読み込むのが面倒なんだよなぁ。
それに、適当にくっつけるとくっつけたところにブツ！っていうのノイズが入ることがあったはず。
1024:デフォルトの名無しさん
17/12/31 05:33:17.47 Q5J3BQB7.net
URLﾘﾝｸ(ideone.com)
これで、ちっちゃいやつは書き出した実績がある。ローカルの話だけどな。
読み込みはRiffの仕様よく知らないからわからない。
1025:デフォルトの名無しさん
17/12/31 09:49:37.67 Jha/n6sD.net
自分で書くよりfoobar2000でMerge all tracks into one output fileしちゃうよな
むしろ6GBとかいける、wave64になってんのかな
1026:デフォルトの名無しさん
17/12/31 10:12:35.10 vp+PvkVL.net
完全にスレチ
1027:
17/12/31 13:06:54.78 UjqOw9qv.net
>>989
foobar2000 に merge する項目はありますか？
最新バージョンをインストールしましたが見当たりません‥
1028:デフォルトの名無しさん
17/12/31 14:14:14.10 Jha/n6sD.net
>>991
foo_converter.dllが標準で入ってるからそのまま使えるよ
スレチというかこの場合はサイト違いだな、Hydrogenaudioで検索した方が沢山みつかる
1029:デフォルトの名無しさん
17/12/31 19:53:16.48 R6E+DNla.net
"2018と素数" 類似問題
[お題]
前問よりどうやら、ユニークな素数の和で2018を作ると、
構成(要素)数 33個が最大で 4種類あるらしい。
最小は2個で27種類あるみたいだ。
3個だと 73種類、 4個だと 85014種類あるみたいだ。
ユニークな素数の和で2018を作る時、
最大の種類が作れるのは、構成数何個のときで、何種類か。
(注) 8個を超えると10億超えがしばらく続くらしい。
1030:デフォルトの名無しさん
17/12/31 19:58:31.90 Q/CIq2T0.net
>>981
ちゃんと理想の仕様を書けば作るけど
1031:デフォルトの名無しさん
17/12/31 20:02:31.92 Q/CIq2T0.net
>>986
32bit unsignedで(4Gi-1)Bまでだね
ファイルサイズも32bit unsigned
1032:デフォルトの名無しさん
17/12/31 22:29:40.39 q2wUTltf.net
>>993 Java
URLﾘﾝｸ(ideone.com)
1033:
18/01/01 00:07:03.13 JOZ5/YyG.net
>>981
ｽﾚﾘﾝｸ(tech板:30番)
‥‥書初めになりました
1034:デフォルトの名無しさん
18/01/01 06:04:16.51 4wMbPbHX.net
どうして2048ではなく2018などという中途半端な数にしたんだろうとずっと不思議に思っていたのだが(お題だから敢えて変な数にしたのかとか思ったんだが)、ようやっとわかったよ。今年の西暦年だったんだね。
1035:デフォルトの名無しさん
18/01/01 06:13:54.33 +ZNxt5nC.net
>>995
勘違いしてたか。訂正ありがとう。
1036:デフォルトの名無しさん
18/01/01 08:09:01.71 OeEKMk/d.net
>>997
そっちのスレに書くと本当にBTC貰えるの？
てか、出題者と交渉したって貰える保障が全くなくて無意味なスレのような気がするんだけど。
1037:1001
Over 1000 Thread.net
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 395日 15時間 10分 31秒
1038:過去ログ ★
[過去ログ]
■ このスレッドは過去ログ倉庫に格納されています