17/07/02 13:43:30.38 bHJ33QxN.net
>>314 Perl5
URLﾘﾝｸ(ideone.com)
桁の多い数値の幅を反映して数値間の空白の数を決めれば
数値の位置がもう少し見やすくなるとおも…
322:デフォルトの名無しさん
17/07/03 08:12:51.85 EltE6GHS.net
お題：完全なヤング図ソルバー。
URLﾘﾝｸ(ideone.com)
書いてみたけど、不完全なのがやっとだった。
あってるかもわからん。
図の効率がいいほど評価が上がります。
323:デフォルトの名無しさん
17/07/04 21:28:12.76 QK6Kginy.net
>>296 >>299 Perl5
URLﾘﾝｸ(ideone.com)
リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。
3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、
取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、
再帰的に両方に分岐し、木構造で計算しているが、
逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので
来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。
それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、
四つめ以降は時間がかかりいつ終わるか分からない。
そこで、検索された食事秒数の最小値の更新状況を記録し、
同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
最短値に収束したと見なし、探索を打ち切ることによって短時間で
解を出力できるようにした。打ち切り上限は10をハードコードしてあるが
今回のサンプルデータについては4か5で十分そうだ。
なお、23_ のような、2を食べることによって飛び越しを起こすポイントの
一番最後のものは,食べずにスルーして先に2を食べた方が、
次の周で早く食べ終わることは明らかだ。
これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に
わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが
難しそうなので、見送った。
324:デフォルトの名無しさん
17/07/04 21:31:48.78 QK6Kginy.net
>>318
書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
打ち切るという、簡単な枝刈りを取り入れてあります。
連投ｽﾏｿ
325:デフォルトの名無しさん
17/07/04 23:51:29.56 sQGcZTdy.net
>>318
枝刈りで最短を刈り取ってしまったら駄目じゃないか
例えば "3324" -> 15秒 にならないな
326:318
17/07/06 00:31:45.46 iCfNzc8Y.net
>>320
誤解�
327:ﾅす。 枝刈りは、ある探索中の枝において始点から既に経過した秒数が それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、 現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って 別の枝の探索に移るというものなので大丈夫です。 "3324" の最短秒数を探索すると 15秒になります。
328:デフォルトの名無しさん
17/07/06 00:52:46.56 ywrsmrRJ.net
>>321
あれ、変だな
>>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？
同様に"3328"、"3364"は最短19秒だけど>>318だと20になった
329:318
17/07/06 01:20:52.00 iCfNzc8Y.net
>>322
同じコードをideoneに張りなおして3324を入力して実行してみました。
URLﾘﾝｸ(ideone.com)
ソースを一箇所編集しています。
31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出
の繰り返し回数上限判定地を10から20に増やしています。
3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。
3364も20が10回繰り返した後19が出て続きます。
お手数おかけしますが
一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして
評価してください。
330:318
17/07/06 01:35:51.32 iCfNzc8Y.net
>>323
3324と3364の解を見ていて気が付いた点があります。
一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、
3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため
解として表示されています。
これは、3324の15や3364が4桁しかないので、
最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を
解として表示していることによります。
>>318の一定回数繰り返したら収束とみなすという判定方法は、
ニュートン法のような数値計算では有効ですが、
>>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz
331:デフォルトの名無しさん
17/07/06 01:53:08.89 bBo7q2K6.net
3324を拡張した887654329は閾値どれくらい増やせば対応できるんですかね
332:318
17/07/06 02:06:40.59 iCfNzc8Y.net
>>325
延々探索を続けないと解に至らないかもしれない入力については
定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。
887654329がそういったカテゴリーに属する入力かというと
ﾁｮｯﾄ分からない。
なので適切な閾値はこれだと断言しにくいです。
さーせん
333:デフォルトの名無しさん
17/07/06 21:08:21.84 ywrsmrRJ.net
>>326
結局>>321は大嘘だったし、閾値20の>>323にしたところで
例えば"14432"は最短にならないし
閾値が決められないならその解法はやはり駄目だな
334:318
17/07/06 22:03:39.91 0agEc1HZ.net
>>327
閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、
計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。
335:318
17/07/06 22:08:34.07 0agEc1HZ.net
見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。
それによって20で打ち切るようなやり方を改善できればいいんだけれども…
それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して
とけなくなる
336:デフォルトの名無しさん
17/07/06 23:01:53.78 ywrsmrRJ.net
>>328
閾値20で打ち切るのは枝切りじゃないという主張のようだけど
打ち切るという動作は枝切り以外の何物でもない
>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
というのも嘘
337:318
17/07/06 23:19:13.87 0agEc1HZ.net
>>330
絡むね。そんな暇あったらコードでも書けばいいのにｗ
閾値20でその入力については解の探査を�
338:~めて 別の枝に移らず次の入力データに移るのはどちらかといえば中断で、 枝かりではないでしょ。 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 にかいてあるでしょうに。 >>318は”3324”の最短に到達しないから>>321の > "3324" の最短秒数を探索すると 15秒になります。 >というのも嘘 これは10回の打ち切りの緩和を書きもらしたんだよ。 何が狙いで、こだわって絡んでくるやらねぇ。
339:318
17/07/06 23:37:37.26 0agEc1HZ.net
「打ち切る」という言葉を
>318
>…
>同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
>最短値に収束したと見なし、探索を打ち切ることによって短時間で
>解を出力できるようにした。打ち切り上限は10をハードコードしてあるが
では「その入力に対する求解を中断する」ところで使い、
>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。
では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの
ところで使ったのが誤解を招いてしまったのかな…
340:デフォルトの名無しさん
17/07/07 04:22:27.25 pbX9YCbr.net
3次の動的計画法ってどんだけメモリ食うんや？
341:デフォルトの名無しさん
17/07/08 03:20:24.48 hDxZO8qP.net
お題： 自然数Nの平方根を整数部含めて(1000*N)桁求めたとき、出現する0の個数を数える
たとえば、N = 4の時ルート4を4000桁（整数部1桁＋小数部3999桁）求めたとき、出現する0の個数は3999個
N = 3 => ?
N = 5 => ?
N = 7 => ?
342:デフォルトの名無しさん
17/07/08 03:22:50.68 5gcIwgbE.net
ブロックチェインの新手のコイン発掘か？
343:デフォルトの名無しさん
17/07/08 03:59:02.35 kzKE4jeR.net
>>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
344:デフォルトの名無しさん
17/07/08 04:25:25.94 kzKE4jeR.net
>>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
345:デフォルトの名無しさん
17/07/08 07:13:48.73 hDxZO8qP.net
>>337
N = 5の場合が間違ってると思う
多分、丸めモードの関係か、精度が足りてないと思われる
346:デフォルトの名無しさん
17/07/08 09:51:11.17 3gkxwDpM.net
>>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
347:デフォルトの名無しさん
17/07/08 11:54:07.74 H5pSyGdF.net
>>334 Squeak/Pharo Smalltalk
| sqrt |
sqrt := [:n :m |
"ref. URLﾘﾝｸ(xar.sh) "
| a b |
a := 5 * n. b := 5.
[:exit | [
a >= b ifTrue: [a := a - b. b := b + 10] ifFalse: [
b log > m ifTrue: [exit v
348:alue] 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}"
349:デフォルトの名無しさん
17/07/08 12:18:57.24 hDxZO8qP.net
>>339
N = 29とN=41の場合が間違ってる可能性？ それ以外は正しい模様
N = 29 => 2912、N = 41 => 4094 じゃなかろうか
>>340
合ってる
350:デフォルトの名無しさん
17/07/08 12:48:13.59 1hnJaOYb.net
>>334 Perl5
URLﾘﾝｸ(ideone.com)
351:デフォルトの名無しさん
17/07/08 13:10:39.20 1hnJaOYb.net
>>334 Perl5
URLﾘﾝｸ(ideone.com)
>>342 をもう少しすっきり書けたので差し替え。
352:デフォルトの名無しさん
17/07/08 13:31:31.09 3gkxwDpM.net
>>341
> N = 29 => 2912、N = 41 => 4094 じゃなかろうか
それが正しいようです
GNU MPだとどうしても最後の桁は四捨五入?されるようで
任意のNに対して正確な答えを出すのは面倒なので修正は断念
353:デフォルトの名無しさん
17/07/09 10:26:36.71 aJSGzdPS.net
結局バイナリーツリーになっちゃったなぁ。むずかし。
354:デフォルトの名無しさん
17/07/09 10:55:01.51 xLkjNLhf.net
>>344
考え直したら面倒じゃなかった
>>334 C++
URLﾘﾝｸ(codepad.org)
N=10000くらいまでなら現実的な時間で計算出来そうだ
355:デフォルトの名無しさん
17/07/09 11:25:12.20 nhQrw0mT.net
N=100000, 1億桁のくらいなら現実的な時間で出来る
丸めは切り捨て？四捨五入？
356:デフォルトの名無しさん
17/07/09 11:33:40.13 nhQrw0mT.net
ルートの計算は速い
整数のルートは特に速い
357:346
17/07/09 12:21:20.78 4Kodr3MO.net
>>347
GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので
floor() であらかじめ切り捨ててから get_str() した
358:デフォルトの名無しさん
17/07/09 12:57:37.64 DBjzEn12.net
ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか?
連続するゼロの個数の最大だろ?
無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。
359:デフォルトの名無しさん
17/07/09 13:14:46.15 df6kAKcY.net
最大って何の話しとるんや
360:デフォルトの名無しさん
17/07/09 13:28:51.97 DBjzEn12.net
もとめる桁数のほうに上限があったのか、それを見逃してた。
361:デフォルトの名無しさん
17/07/09 13:45:03.68 NvRZfELm.net
連続する個数でもないぞw
362:デフォルトの名無しさん
17/07/09 13:51:59.10 DBjzEn12.net
どっちも間違えたな、ゼロの総数だったか。
363:デフォルトの名無しさん
17/07/09 19:14:37.92 6MYOcrZ9.net
>>349
floorを行った後の結果に誤差は無い
という検証は出来てるの？
何もしてないなら、それはたまたま偶然当たったっていうだけだぞ
ていうか、君には聞いてない
出題者の意図を聞いてる
364:デフォルトの名無しさん
17/07/11 15:16:56.21 1hL73PK3.net
√2でなるべく長い0の連続をみつけるは?
365:デフォルトの名無しさん
17/07/11 15:49:47.43 QxseLuPf.net
>>355
君には向いて無いよ
366: ◆QZaw55cn4c
17/07/11 16:29:49.99 ZfeFayuI.net
>>355
>floorを行った後の結果に誤差は無い
>という検証は出来てるの？
ぱっとみ当然だと思うんだが
>>356
何桁求めるか指定しないと意味がないのでは？
367: ◆QZaw55cn4c
17/07/11 16:35:18.57 ZfeFayuI.net
>>358
ん、考え直した
10進に変換した結果にて 99999 とかが末尾にあるようでは、余分の計算はしないと
368:いけないね
369:デフォルトの名無しさん
17/07/11 18:55:08.87 dSS1j36W.net
[][Tebla][]
}
000-"Yob*RtStrike"[%Kil\]MO,fla>%$9999VLTS
001-GYORLith"0\R"/"ESUBA"%$%
HADO-"EM","L","O","NU"###END
370:デフォルトの名無しさん
17/07/14 06:57:35.22 PYQ8V1MO.net
>>296
URLﾘﾝｸ(ideone.com)
C++。解けた気がする。
状態をメモ化してみた。
何で動いてるのか自分でもよくわからない。
暇だったので解いてみた。
371:デフォルトの名無しさん
17/07/14 07:42:51.88 PYQ8V1MO.net
あー多倍長精度演算ほしー。もちろん標準で。
372: ◆QZaw55cn4c
17/07/14 07:55:58.80 TDGI45F0.net
>>362
私も欲しかったので作ってしまった、今 >>334 を奮闘中
373:デフォルトの名無しさん
17/07/14 07:56:52.78 PYQ8V1MO.net
>>363
それはすごいな。
後々破棄するようなものを作るモチベーションが出てこないよ。
374:デフォルトの名無しさん
17/07/14 07:57:44.37 TDGI45F0.net
>>364
書き捨てに慣れてしまったんだ‥
375:デフォルトの名無しさん
17/07/14 07:59:21.83 PYQ8V1MO.net
>>365
あはは・・・。
コード書き捨てるのは良いけど、道具書き捨てるのは俺には向いてないわ。
なので、標準待ち。
376:デフォルトの名無しさん
17/07/14 09:33:33.04 gEZu1299.net
boostという任意倍長の計算Libraryがあります。
C++では使えるそうです。
377:デフォルトの名無しさん
17/07/14 09:38:45.73 PYQ8V1MO.net
>>367
Boostも良いんだけどね。残念なことにあれは実験環境で準標準って扱いなんだよなぁ。
あれから取り入れられるライブラリも多いんだけど、標準じゃないからね。
残念なことに。
378:デフォルトの名無しさん
17/07/14 12:49:16.12 gnKUWanp.net
まあ標準ライブラリしか使わない縛りをしたければ好きにすればいいんじゃない？
379:デフォルトの名無しさん
17/07/14 14:27:07.19 JyiCltLg.net
車輪の再発明
380:デフォルトの名無しさん
17/07/14 14:31:43.15 DwybRUfK.net
競プロみたいな相手方の環境使う物だと標準と準標準の差はでかい
自分の環境なら導入すればいいだけだが
381: ◆QZaw55cn4c
17/07/14 18:52:31.62 TDGI45F0.net
>>370
個体発生は系統発生を繰り返す
382:デフォルトの名無しさん
17/07/15 12:42:06.98 odVkuNfb.net
>>361
厳密解を出しているのなら、チャレンジ
(わかって近似値解狙いなら気にしないで)
"14432" と "887654329"
両方とも既出の"貪欲つぶし"(?)数列
"14432"は 20秒 (ゼロインデック順で02341)
"887654329"は 80秒(同123456708)でいける。
383:デフォルトの名無しさん
17/07/15 14:59:21.20 OEoVgGO0.net
>>373
URLﾘﾝｸ(ideone.com)
C++。それ解くとほかの問題が解けなくなる。
厳密解のつもりだったが、ちょっと自分の領分超えてるなぁ。
うまくいかないものだ。
真実が奥の方にあると貪欲法は弱いな。Orz
384:デフォルトの名無しさん
17/07/16 16:33:07.01 8ZBD9z9c.net
お題：
自分用多倍長整数演算関数
…って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの
制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。
385:デフォルトの名無しさん
17/07/16 18:30:49.57 8+Akms5T.net
多倍長整数演算がサポートされている言語を使う
終わり
386: ◆QZaw55cn4c
17/07/16 18:54:09.85 eA1jggM5.net
>>375
C++98 URLﾘﾝｸ(codepad.org)
オートボクシング等はなく便利にはできていない．
387:デフォルトの名無しさん
17/07/16 2
388:0:34:05.63 ID:yctBkD01.net
389: ◆QZaw55cn4c
17/07/16 20:36:24.09 eA1jggM5.net
>>378
うん，FFTを使うそうだが‥いまいちよくわからない
390:375
17/07/16 20:41:46.81 8ZBD9z9c.net
>>376
仕事で言語を選べる立場になってみたいものだわ。
この言語でやってってののは多々あるけど…orz
>>377
Karatsuba-Ofman法を目指してごーごー
391:デフォルトの名無しさん
17/07/17 22:48:25.95 5edeqhg+.net
>>296
手計算で計算出来るレベルにまで計算量を減らせた
もちろん数学的な裏付け付きで
ある条件を見たせば一瞬で求まる
"123456789123456789" > 98秒
残念ながら、これだけはその条件を満たしてない
392:デフォルトの名無しさん
17/07/18 06:37:17.84 nFCFlf58.net
>>381
22とか2323もその条件を満たしてない感じ？
393:デフォルトの名無しさん
17/07/18 07:37:05.09 Ew0RSScO.net
22 は微妙
2323 は大丈夫
394:デフォルトの名無しさん
17/07/18 07:41:44.22 Ew0RSScO.net
まだコードになってないんで、
コードになったらアップします
寿司を食べる時間 < レーンの回転周期
という前提をつけちゃおうと思ったけど、
つけない方が良さそうですね
寿司を食べる時間がレーンの回転周期の整数倍の寿司は
ちょっと特別な処理が必要
395:デフォルトの名無しさん
17/07/18 08:01:32.43 Ew0RSScO.net
整数倍の寿司が無いもので
条件に当てはまらない最小は
2222
かな
396:デフォルトの名無しさん
17/07/18 08:49:51.93 YLlwVFMJ.net
>>334 SageMath
URLﾘﾝｸ(sagecell.sagemath.org)
普通に(？)多桁のisqrt()なので何の捻りも無し。
397:386
17/07/18 09:39:56.20 YLlwVFMJ.net
>>339
つ mpz_sqrt()
398:デフォルトの名無しさん
17/07/19 18:12:29.37 Np9hKHT2.net
>>296
>>373
URLﾘﾝｸ(ideone.com)
C++。結局、i7-6700のmem2G使って7分で解けた。
どうしようもない位遅いな。
でも一応題意には添えたと思う。
もう見たくない・・・。Orz
高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。
よくわからんけど、数学で頑張ってる人に期待だ。
399:386
17/07/20 01:57:16.81 Q7XnESC/.net
100のべき乗に変更
URLﾘﾝｸ(sagecell.sagemath.org)
400:デフォルトの名無しさん
17/07/21 15:21:18.13.net
>>296
URLﾘﾝｸ(ideone.com)
C++。試しに再起化してみたら処理速度倍になった。
自分の環境では3分ちょいで解ける。
相変わらずメモリ馬鹿食いするけど。
もう俺には無理。
俺の中では終了でーす。Orz
401:デフォルトの名無しさん
17/07/22 08:54:36.28 OQXA8cUK.net
>>388
数学で頑張ってる人だけど、
もうちょっとまって
>>296の問題だけなら簡単だけど、
まだ全体を解明できてない
というか、忙しくて>>381から進んでない
402:デフォルトの名無しさん
17/07/22 08:55:28.19 OQXA8cUK.net
このスレが無くならないうちに解明します
403:デフォルトの名無しさん
17/07/22 10:43:30.03 apsnR2Z0.net
>>391
wktkデス！
コード見るのが好きなのでぜひ完走していただけたらと思います。
404:デフォルトの名無しさん
17/07/23 11:26:56.94 ipiEUPYV.net
>>375
のほかの実装はでてこないねぇ‥
405:デフォルトの名無しさん
17/07/23 12:53:55.68 7fREas1L.net
>>394
使えるコードにするためには、規模がでかくなりすぎるから
406:デフォルトの名無しさん
17/07/23 14:15:20.13 ipiEUPYV.net
C/C++ で最長1000行ぐらいとみて、2日ぐらいあれば、とりあ�
407:ｦず動く 土日で仕上がってくるんじゃないかと期待してたんだが
408:デフォルトの名無しさん
17/07/23 14:18:11.58 7fREas1L.net
速度が考えられてないコードなんて実用にはならないよ
409:デフォルトの名無しさん
17/07/23 14:21:31.79 7fREas1L.net
ていうか、
コードに対する条件とか
サポートする機能とか
条件が無さすぎる
410:デフォルトの名無しさん
17/07/23 14:24:57.75 ipiEUPYV.net
速度‥か‥
どうしてもローテートとかキャリーフラグとかを使いたいから、これはアセンブラの領域になるね
よくみかけるアセンブラ中毒者が今頃爪を研いでいるのだろうか？
411:デフォルトの名無しさん
17/07/23 14:25:42.29 ipiEUPYV.net
>>398
そこは「自分用」だから自由に決めていいんでないかい？
412:デフォルトの名無しさん
17/07/23 14:49:34.77 TcY6qE9r.net
>>394
当日に >>305 で >>390 より10倍以上早いのがでているだろう。
しかも 計算量まで書いてある
413:デフォルトの名無しさん
17/07/23 14:53:19.94 ipiEUPYV.net
>>401
お題が違うのでは？
414:デフォルトの名無しさん
17/07/23 15:05:28.62 TcY6qE9r.net
>>402 >>394
確かに違った、すいません。
c++多倍長なら、karatsubaにも対応して300行くらいの以下をパクって使うのも一案
URLﾘﾝｸ(sites.google.com)
415:デフォルトの名無しさん
17/07/23 15:09:21.91 ipiEUPYV.net
>>403
base 10進ならば、表示（operator<<) が楽でいいね、なるほど、それは思いつかなかった
416:デフォルトの名無しさん
17/07/23 16:51:44.88 7fREas1L.net
>>399
通常、
処理時間のほとんどが乗算
乗算のほとんどがFFT
アセンブラの出番は当分先
417:デフォルトの名無しさん
17/07/23 16:52:43.21 7fREas1L.net
FFTのライブラリをどこからか持ってくるのでもいいけど、
それなら素直に多倍長ライブラリを持ってくれば
ってことになる
418:デフォルトの名無しさん
17/07/23 16:54:07.19 7fREas1L.net
今は浮動小数点演算が速いので、
カラツバの出番はあまりない
419:デフォルトの名無しさん
17/07/23 18:50:17.74 5CSy1R8t.net
基数を10のべき乗にするとか(printf()的なものが簡単だから)、乗算はunsigned shortやintとの
乗算に限るとか、除算無しとかいうのは…
プログラムの本体に組み込まれてしまって、再利用可能なライブラリの形で括りだされてる事の
方が少ないかｗ
420:デフォルトの名無しさん
17/07/24 00:48:44.80 XgJeE+LA.net
>>6-285 SageMath
URLﾘﾝｸ(sagecell.sagemath.org)
421:デフォルトの名無しさん
17/07/24 18:24:00.06 UuUAOyUA.net
>>408
裁定ラインとしては、乗算は Bigint×Bigint、および除算の実装ですかね、でも足し算の回数での乗算や引き算の回数での除算は嫌ですね
422:デフォルトの名無しさん
17/07/24 18:58:12.05 5ve8i6tz.net
お題：お題スレ3の>>170をファレイ数列を使って解く。
ｽﾚﾘﾝｸ(tech板:170番)
423:デフォルトの名無しさん
17/07/24 19:10:35.21 nJVItCRy.net
>>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)]
424:デフォルトの名無しさん
17/07/24 19:11:05.16 7nQ6Z7f9.net
>>296
超高速版が出来ました！
URLﾘﾝｸ(ideone.com)
一皿9秒が上限であれば、計算オーダーはn
関数自体は何秒でも大丈夫です
コードだけじゃ意味がわからないでしょうけど、とりあえずコードだけ
あまりテストしてないので、バグって�
425:ｽらごめんなさい
426:デフォルトの名無しさん
17/07/24 23:00:47.69 fjGi9Yh0.net
オーダーnは凄いな
427:デフォルトの名無しさん
17/07/25 05:40:32.49 ubbfnjuS.net
>>413
うーんわからん。
俺の思考とは別系統かな。
ホントに0秒で解けてるし、素晴らしい。
素直に賞賛。
428:デフォルトの名無しさん
17/07/25 11:52:16.57 bLUUDw7G.net
回転寿しの問題は、部分的な最短経路が全体の最短経路にならないんだよな
だが最短時間はレーン長の2倍程度の再帰回数で出る
そのあと数十億回再帰して総当たりしてもそれより短くならない
最後の皿から逆方向に探索してもおそらく同じ状況
429:デフォルトの名無しさん
17/07/25 11:56:47.84 bLUUDw7G.net
例えば、”122” は最短時間6だが、1周目で2番目の要素”2”をパスしないとそうならない
430:411
17/07/26 19:54:35.63 6H34MdHA.net
>>412
ファレイ数列の中間数(mediant)を再帰的に生成すると、uniqもsortも要らないのだけど、
mが3や5だと大差無いかｗ
431:デフォルトの名無しさん
17/07/26 20:50:49.45 s8dUUqTb.net
>>411
リンク先が見えません
問題文をもう一回書いてください
432:デフォルトの名無しさん
17/07/26 20:52:34.29 s8dUUqTb.net
と思ったら見れました
ファレイ数列を使って何かを解くわけじゃなくて、
ファレイ数列を求める問題？
433:411
17/07/26 23:20:07.89 6H34MdHA.net
>>420
元の問題はそういうもの(＝ファレイ数列の両端(0/1と1/1)無し版を求める問題)と
解釈してますです。
434:デフォルトの名無しさん
17/07/26 23:26:01.52 lPM9zwS7.net
#include <list>
#include <iostream>
const int N_MAX = 10;
struct RATIONAL {
int num;
int den;
};
int main() {
std::list < RATIONAL > farey;
RATIONAL zero = {0, 1};
RATIONAL one = {1, 1};
farey.push_back(zero);
farey.push_back(one);
for (int n = 1; n <= N_MAX; n++){
for (std::list < RATIONAL > ::iterator i1 = farey.begin(), i0 = i1++; i1 != farey.end(); i0 = i1, i1++) {
if (i0->den + i1->den <= n) {
RATIONAL m = {i0->num + i1->num, i0->den + i1->den};
farey.insert(i1, m);
}
}
std::cout << n << " : ";
for (std::list < RATIONAL > ::iterator i = farey.begin(); i != farey.end(); i++) {
std::cout << i->num << "/" << i->den << " ";
}
std::cout << "\n";
}
return 0;
}
435:デフォルトの名無しさん
17/07/26 23:29:22.49 lPM9zwS7.net
これから0と1を除けば良いって問題であれば、
表示のループに以下を加えれば
if (i->den != 1)
436:デフォルトの名無しさん
17/07/26 23:31:57.11 lPM9zwS7.net
問題の意味も意図も良くわからん
出題者が「そういうものと解釈しています」とか
出題者が >>418 みたいな回答をバカにする発言とか
なんか非常に感じが悪い
437:412
17/07/27 00:12:38.86 qteH6K3e.net
そもそも>>412のfarey_sequenceは定義が間違ってたわ
んでもって再帰にすると>>412より遅くなるという
Ruby
class Farey
def self.[](m)
if m == 1
[0r, 1r]
else
succ(m - 1)
end
end
def self.succ(m)
self[m].each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == m + 1
s << b
}
end
end
Farey[3] # => [(0/1), (1/3), (1/2), (2/3), (1/1)]
Farey[5] # => [(0/1), (1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5), (1/1)]
438:デフォルトの名無しさん
17/07/27 01:59:46.61 GuEy9AL1.net
>>411 Java
URLﾘﾝｸ(ideone.com)
439:デフォルトの名無しさん
17/07/28 18:51:16.80 XBSdfIgC.net
>>375
のほかの実装はでてこないねぇ‥
440:デフォルトの名無しさん
17/07/28 19:19:26.77 mqZJq6H+.net
昔brainf**kで実装したのあるけどちょっとなぁ
441:デフォルトの名無しさん
17/07/28 19:24:55.65 WViVOgsq.net
また懐かしい言語を
442:デフォルトの名無しさん
17/07/28 19:26:36.86 WViVOgsq.net
どうせならチューリングマシンで作ってよ
443:デフォルトの名無しさん
17/07/30 10:59:37.37 A7gIx2b1.net
お題：MathematicaのFareySequence[n,k](引数2つ)に相当するものの実装
URLﾘﾝｸ(reference.wolfram.com)
444:デフォルトの名無しさん
17/07/30 11:53:03.31 EQKnHSgY.net
>>431
URLﾘﾝｸ(ideone.com)
C++。一瞬計算が合わなくてビビったけど、空目だった。
インデックス概念がベーシックなんだな。
445:デフォルトの名無しさん
17/07/30 12:00:36.94 EQKnHSgY.net
っていうか、この関数インデックスに0与えたら何が出力されるんだろう・・・。
早速バグってる気がする。
446:デフォルトの名無しさん
17/07/30 12:15:40.85 EQKnHSgY.net
>>432
バグってた。のでエディトしてFIXした。
所持する数の概念勘違いしてた。
447:デフォルトの名無しさん
17/07/30 12:25:59.30 B3p9Yl5S.net
>>422の微妙な変更でいいよね
448:デフォルトの名無しさん
17/07/30 12:26:41.34 B3p9Yl5S.net
1個だけ求めるなら、もっといい方法がある？
449:デフォルトの名無しさん
17/07/30 12:27:22.69 B3p9Yl5S.net
ていうか、いい加減Fareyはもういいでしょ
他の課題の方が
450:デフォルトの名無しさん
17/07/30 12:30:15.15 EQKnHSgY.net
フィボナッチって素数何だっけ？
451:デフォルトの名無しさん
17/07/30 12:44:33.08 B3p9Yl5S.net
1, 1, 2, 3, 5, 8, ...
違うよね
452:デフォルトの名無しさん
17/07/30 12:47:15.18 EQKnHSgY.net
だよねー。>>422ってフィボナッチ使ってない？
あんまり深く考えてないだけど。Orz
453:デフォルトの名無しさん
17/07/30 12:47:30.85 B3p9Yl5S.net
じゃあ、任意の二個の数からはじまるフィボナッチ数列で、はじめから連続する素数の数が多い物を探す
って課題で
454:デフォルトの名無しさん
17/07/30 12:48:36.68 B3p9Yl5S.net
>>440
フィボナッチではない
wikipediaにのってるレベルの知識で作った
455:デフォルトの名無しさん
17/07/30 12:49:05.29 EQKnHSgY.net
あれ？俺とんちんかんなこと言ってるか？
>>422が数列としてあってるのかよくわからない。Orz
どう考えればいいんだろう。
456:デフォルトの名無しさん
17/07/30 12:53:04.00 EQKnHSgY.net
まぁ、俺のもあってるかどうかはしらんけど。＞＜；
457:デフォルトの名無しさん
17/07/30 12:56:43.60 EQKnHSgY.net
頭悪くてゴメン。爆発しそう。。。
458:デフォルトの名無しさん
17/07/30 13:01:05.96 EQKnHSgY.net
引っ込む。すまんかった。
459:デフォルトの名無しさん
17/07/30 14:17:22.65 t+CfDp82.net
>>431 Java
URLﾘﾝｸ(ideone.com)
460:デフォルトの名無しさん
17/07/30 19:16:10.29 LizATlBz.net
>>431 Ruby
def farey(n, k)
return [0r, 1r][k] if n == 1
farey(n - 1, 0..-1).each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == n
s << b
}[k]
end
461:デフォルトの名無しさん
17/08/03 07:36:01.80 cLWzUq7C.net
お題：ミンコフスキーの疑問符関数の実装
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(reference.wolfram.com)
462:デフォルトの名無しさん
17/08/03 10:39:36.15 ONmyLPuf.net
WIKIぺにコード乗ってますが。
463:デフォルトの名無しさん
17/08/03 10:48:34.50 ONmyLPuf.net
>>449のWIKIより。
/* Minkowski's question mark function */
double minkowski(double x) {
long p=x; if ((double)p>x) --p; /* p=floor(x) */
long q=1, r=p+1, s=1, m, n;
double d=1, y=p;
if (x<(double)p||(p<0)^(r<=0)) return x; /* out of range ?(x) =~ x */
for (;;) /* invariants: q*r-p*s==1 && (double)p/q <= x && x < (double)r/s */
{
d/=2; if (y+d==y) b
464:reak; /* reached max possible precision */ m=p+r; if ((m<0)^(p<0)) break; /* sum overflowed */ n=q+s; if (n<0) break; /* sum overflowed */ if (x<(double)m/n) r=m, s=n; else y+=d, p=m, q=n; } return y+d; /* final round-off */ }
465:デフォルトの名無しさん
17/08/05 17:44:11.83 40G0sflG.net
>>375
のほかの実装はでてこないねぇ‥
466:デフォルトの名無しさん
17/08/12 18:46:00.57 953va2dM.net
寿司のオーダーNのやつを理解しようとしたけどまだやってない。
その仕組みと、ほんとに正解してるのかとか。いたら誰が解説して。
467:デフォルトの名無しさん
17/08/12 19:04:22.18 Bi4KH0eW.net
>>413です
もちろん合っているつもりのコードです
作者が言っても何の説得力もありませんが
468:デフォルトの名無しさん
17/08/12 19:07:04.34 4r/z/Qd5.net
会社に帰ってこない巡回セールスマンだよね
寿司の乗った皿がノード、計算量はO(n!)
469:デフォルトの名無しさん
17/08/12 19:10:18.10 Bi4KH0eW.net
それぞれの寿司を食べている期間をレーン上の線分で表します
この線の重なり具合をpileで表しました
効率良く食べられた場合はレーンがpile_max周するまでの間に食べきることが出来ます
170行目の判定がそれで、trueの場合は効率良く食べられない場合です
470:デフォルトの名無しさん
17/08/12 19:12:06.32 4r/z/Qd5.net
>>456
もしそれで最適解が得られるなら巡回セールスマンも可能じゃないかな？
471:デフォルトの名無しさん
17/08/12 19:17:11.73 6XNTCj+p.net
巡回セールスマン問題とけたら色々応用範囲アルヨ。
マジでどっかに売り込んでもいいくらい。
天才か。
472:デフォルトの名無しさん
17/08/12 19:18:34.85 6XNTCj+p.net
社会的に言うと交通統制とかもそれじゃないかな？
信号の待ち時間問題。よくしらんけど。
473:デフォルトの名無しさん
17/08/12 19:19:17.76 Bi4KH0eW.net
効率良く食べられない方が簡単なのでその場合から
お寿司を以下のグループに分けます
----
各グループのお寿司は、レーンの特定の位置から食べ始めた場合、pile[グループ]周以内で食べ終わることが出来る
このとき、pile_max = Σ pile[グループ]
となる
---
このようなグループの分け方の最小の物が存在します
474:デフォルトの名無しさん
17/08/12 19:22:56.16 Bi4KH0eW.net
同じグループのお寿司は連続して食べます
開始時と、各グループのお寿司を食べ終わった後、最初に来るお寿司から食べはじめ、pile[グループ]以内で食べられる食べ方でそのグループを食べ終える
ということを繰り返せば最小の時間で食べ終えることが出来ます
475:デフォルトの名無しさん
17/08/12 19:26:29.79 Bi4KH0eW.net
グループ分けした時に1個のグループになった場合は、
効率良く食べられることになります
つまり、pile_max周以下で食べ終えることが出来ます
この時は、コード上にあるダミーのお寿司を追加してから最小時間を求め、ダミーのお寿司を食べてる時間を引けば求められます
476:デフォルトの名無しさん
17/08/12 19:28:18.79 4r/z/Qd5.net
うーん、よくわからん
セールスマンの巡回先を一次元にマッピングできれば同じことできそうな
無理か
477:デフォルトの名無しさん
17/08/12 19:30:27.01 Bi4KH0eW.net
グループの分け方は少し難しいです
レーンの各整数位置に対して、
お寿司の線の両端にあたる点同士
線の重なりがpile_max未満である区間の点(両端を含む)
を同じグループの点とし、
これらを続けることで最小のグループ分けが出来ます
線の両端の点のグループが、そのお寿司のグループになります
478:デフォルトの名無しさん
17/08/12 19:31:42.19 Bi4KH0eW.net
それぞれ、証明は出来ているつもりです
479:デフォルトの名無しさん
17/08/12 19:32:49.51 Bi4KH0eW.net
もちろん、一般の巡回問題はこの方法では無理です
480:デフォルトの名無しさん
17/08/12 19:37:29.23 4r/z/Qd5.net
全ノードを巡回する最短時間の問題だから、できそうな気がするけどね
481:デフォルトの名無しさん
17/08/12 19:39:44.61 2Yw2XYfL.net
372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっている
482:フリーランスのサイトはだめだ。 高額に見せているけど実際は50万前後 JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円 平凡な稼働時間の80万円の案件もある。 ユー子も求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト 473非決定性名無しさん2017/08/03(木) 15:21:30.71 JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる 自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の 間でやらしている。 446非決定性名無しさん2017/08/02(水) 22:12:48.95 JIETに毎月5千円払えば３次から入場できるだろ？ 高額をうたうフリーランスのサイトはだいたい５次から４５万円 JIETで閲覧応募できる末端価格からさらに搾取するのが高額をみせつけるフリーランスサイトでした 高額案件をみせつけるフリーランスサイトも案件の取得はJIETでした 自称エージェントはJIETから流れてくる案件を転売してるだけだった。 JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む
483:デフォルトの名無しさん
17/08/12 19:40:20.63 Bi4KH0eW.net
pile_maxとその位置から下限が得られますが、
>>296 の例では98秒の物以外はすべてその下限になっています
一個その下限になるような例を見つければ答えがわかるのですが、
自力で検索してみればわかると思いますがそのような例はあっさり見つかります
98秒の例は効率良く食べられない場合になります
効率良く食べられる側のなかでも、pileから得られる下限値より大きくなる場合もあります
484:デフォルトの名無しさん
17/08/12 19:43:06.99 Bi4KH0eW.net
いずれの場合も、PCを使わなくても手計算で十分可能です
485:デフォルトの名無しさん
17/09/15 10:14:33.05 lRMsxOf0.net
お題:
N次元で１辺のマス目がM個の魔法陣を作る
N>3(任意)、M>=3(任意)の超立方体
486:デフォルトの名無しさん
17/09/15 10:20:33.77 lRMsxOf0.net
参考
URLﾘﾝｸ(magcube.la.coocan.jp)
URLﾘﾝｸ(nadamath2012.web.fc2.com)
487:デフォルトの名無しさん
17/09/17 16:38:38.03 DSKC3zx4.net
魔方陣は1個作ればいいの？
Mが奇数か4の倍数は簡単
4で割って2余るのは検索するしかないのかな？
488:デフォルトの名無しさん
17/09/17 16:55:04.37 fthJj6jv.net
バックトラックで組もうかと思ったけど、重そうだったからやめた。
数独より重そう。
それに一列合計をどの数字にするのかちょっとわからなかった。
489:デフォルトの名無しさん
17/09/17 23:20:36.13 DSKC3zx4.net
一列合計は、M*[数字の平均]
になる
つまり
M*(M^N+1)/2
490:片山博文MZ
17/09/18 21:53:54.06 iMidYxoH.net
お題: URLから適当なサムネイルを生成するWebプログラム。
491:デフォルトの名無しさん
17/09/18 23:06:01.10 FC5+Wne9.net
お題
0以上90未満の整数nを入力として
タンジェントn°の値が有理数ならば真
そうでなければ偽を返す
492:デフォルトの名無しさん
17/09/18 23:29:46.49 45aelXxs.net
bool f(int n){return n==0 || n == 45;}
493:デフォルトの名無しさん
17/09/18 23:33:52.62 ILsR+BHw.net
sed -r -e "s/^(0|45)\$/True/" -e "s/[1-8][0-9]*/False/"
494:デフォルトの名無しさん
17/09/19 01:13:30.78 zMNLdsjY.net
tanの計算しないのはどうかと
495:デフォルトの名無しさん
17/09/19 01:57:23.24 Ten4kOds.net
計算で有理数かどうか確�
496:F？ それは非常に難しいな by 東大数学科卒
497:デフォルトの名無しさん
17/09/19 02:28:36.10 SyuGyzWY.net
>>480
そう思うなら他者を批判するより行動で示せばいいと思うよ
498:デフォルトの名無しさん
17/09/19 03:58:59.82 KVkpgN/c.net
tan1°が無理数であることの証明すら面倒くせえのに一体どんな回答を求めているんだ
499:デフォルトの名無しさん
17/09/19 06:37:25.45 Ten4kOds.net
>>483
面倒くさい？
てことは出来るの？
やってみて
500:デフォルトの名無しさん
17/09/19 07:41:26.64 KVkpgN/c.net
>>484
確か京大の過去問にあったでしょう
説明めんどいからは解法は自分で調べて
501:デフォルトの名無しさん
17/09/19 08:13:59.26 Ten4kOds.net
いや、おれは出来るよ
>>483の実力で出来るのか？と疑問に思っただけ
実力じゃなくてカンニングね
502:デフォルトの名無しさん
17/09/19 08:21:42.19 KVkpgN/c.net
何言ってんだこいつ
503:デフォルトの名無しさん
17/09/19 08:49:35.38 q1kL6yRz.net
問題が悪いな
与えられた有理数rに対し、
tan(πr)が有理数かどうか判別するプログラムを書け
ならテーブルは使えない
504:デフォルトの名無しさん
17/09/19 09:06:24.19 emxMAzY1.net
また、多倍長精度演算のないC++にはきつい問題を・・・。
505:デフォルトの名無しさん
17/09/19 11:09:01.37 q1kL6yRz.net
>>488
すいません
結果を知っていたらこれでも簡単でした
506:デフォルトの名無しさん
17/09/19 11:10:19.22 q1kL6yRz.net
>>489
多倍長を使っても解決しないでしょ
507:デフォルトの名無しさん
17/09/19 12:53:02.28 RSOddfRB.net
そもそも出題者はどういう回答を期待してるんだ？
数学の知識無しでは作れないし、数学の知識を使えば>>478になる
508:デフォルトの名無しさん
17/09/19 14:38:36.12 LvSRuVZD.net
tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数nにより
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数
証明終わり
509:デフォルトの名無しさん
17/09/19 14:54:56.80 RSOddfRB.net
>>476を解くにはあとtan(18度)が無理数であることを証明しないと
510:デフォルトの名無しさん
17/09/19 14:55:28.25 RSOddfRB.net
>>476じゃなくて>>477
511:デフォルトの名無しさん
17/09/19 16:11:41.85 HSXd4/vW.net
>>493
なるほど面白いねw
512:デフォルトの名無しさん
17/09/19 19:41:00.46 Ten4kOds.net
>>493
tan(π/4)は有理数だけど
tan(π/2)は有理数じゃない
513:デフォルトの名無しさん
17/09/19 20:13:34.35 KVkpgN/c.net
tan1(rad)が超越数であることを証明せよ
514:デフォルトの名無しさん
17/09/19 22:25:08.25 FbLYus+p.net
>>492
WolframAlphaが
is tan(pi * 1 / 180) a rational number?
→ not a rational number
と返す仕組みを知りたかった
515:デフォルトの名無しさん
17/09/19 22:57:34.84 Ten4kOds.net
xが有理数、tan(πx)が有理数 ====> xは1/4の倍数
って覚えてるだけかと
516:デフォルトの名無しさん
17/09/20 14:48:00.57 jgmli1ek.net
>>493
は加法定理で（1-tanαtanβ）が０になってはまずいので
０度以上９０未満の範囲内に限定しないといけないな。
tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数で、かつ 0 <= nα < 90なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数 n ( 0 <= n < 90 ) により
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数
517:デフォルトの名無しさん
17/09/20 14:51:06.46 jgmli1ek.net
tan(1)だけじゃなくて
>>477 >>478 も証明できるかな？？？
つまり整数 n ( 0 <= n < 90 ) において
tan(n)が有理数になるのはn=0,45に限ることの証明
tan(90-n) = 1/tan(n) なので
n ( 0 <= n < 45 ) の範囲で証明されればＯＫ
またtan(45)が有理数で加法定理で減算し
tan(45-n):有理数 ⇔ tan(n):有理数 ( 0 <= n < 45 )
も成立
518:デフォルトの名無しさん
17/09/20 14:51:42.84 jgmli1ek.net
60の約数 はtan(n)無理数
1,2,3,4,5,6,10,12,15,20,30
519: これの45-n もtan(n)無理数 44,43,42,41,40,39,35,33,25,15 この約数で、まだ含まれていないもの 11,22,21,8,13,7 45-nにより 34,23,24,37,32,38 この約数で、まだ含まれていないもの 17,16,19 45-nにより 28,29,26 この約数で、まだ含まれていないもの 14 45-nにより 31 ここまでの数を並べると 01,02,03,04,05,06,07,08,**,10, 11,12,13,14,15,16,17,**,19,20, 21,22,23,24,25,26,**,28,29,30, 31,32,33,34,35,**,37,38,39,40, 41,42,43,44 ９度の倍数の証明のみが残された
520:デフォルトの名無しさん
17/09/20 16:48:28.32 UU/UGcdT.net
だから>>494と書いたんだけど
521:デフォルトの名無しさん
17/09/20 21:20:48.49 8kWE0pQL.net
tan(1 rad)が超越数であることは誰も証明できないの
522:デフォルトの名無しさん
17/09/20 21:27:13.08 UU/UGcdT.net
プログラムに証明させる問題？
523:デフォルトの名無しさん
17/09/20 22:23:37.78 vEoThqNS.net
なぜラジアン？
話の流れ的にはtan(1度)だろ
524:デフォルトの名無しさん
17/09/20 22:25:37.42 vEoThqNS.net
と思ったけど、簡単すぎた
525:デフォルトの名無しさん
17/09/21 16:21:06.33 na02B6ss.net
[1] 授業単元名：FizzBuzzクイズ
[2] 問題文(含コード&リンク)：
[3] 環境
[3.1] OS： (Windows/Linux/等々)特に問わない
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)特に問わない
[3.3] 言語： (C/C++/どちらでも可 のいずれか)特に問わない
ｽﾚﾘﾝｸ(prog板:401番)
FizzBuzzクイズ
1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
999.fizz.buzz #=> 999
となるようなメソッドfizz、buzzは定義可能か？
可能である場合、同様にgizzを追加定義し、
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz" と拡張・応用ができるか？
メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。
526:デフォルトの名無しさん
17/09/21 19:58:51.31 +ykHPOb/.net
まともに仕様を書けない出題者
527:デフォルトの名無しさん
17/09/22 07:02:49.79 aD9oWCn2.net
これ普通の発想では無理
528:デフォルトの名無しさん
17/09/22 07:14:29.33 eEMHecr4.net
>>509
修正
×999.fizz.buzz #=> 999
○997.fizz.buzz #=> 997
529:デフォルトの名無しさん
17/09/22 07:55:33.84 FtjqsiSd.net
>>509
C++版
URLﾘﾝｸ(ideone.com)
530:デフォルトの名無しさん
17/09/22 08:00:39.43 pX6TouLp.net
仕様が謎
531:デフォルトの名無しさん
17/09/22 08:13:32.67 FtjqsiSd.net
>>509
C言語
URLﾘﾝｸ(ideone.com)
532:デフォルトの名無しさん
17/09/22 09:43:07.90 eeRMTLx0.net
外部出力を伴う関数（あるいはメソッド）なら簡単
たぶん関数（あるいはメソッド）の返値がそうなるようにって意味かと
（じゃないと普通に書けてクイズにならない）
たしか数理学的にはこういう関数は書けないことになっていたはず
533:デフォルトの名無しさん
17/09/22 12:43:18.77 qmG6L9xB.net
>>509 や >>516 みたいなのとは絶対に一緒に仕事をしたくない
534:デフォルトの名無しさん
17/09/22 12:43:56.86 qmG6L9xB.net
別に戻り値にしても大して変わらんけど
535:デフォルトの名無しさん
17/09/22 12:51:02.25 qmG6L9xB.net
C言語だとトリッキーな技を使わないと出来ない
同じ関数名で複数関数を作れないから
2段や3段重ねて、intを受けて文字列を返すのは普通には無理
C++だと簡単
大きく分けて２つの方法がある
C++でも数値によって戻り値の型を変えるのは無理
数値がconstexprで
536:良いなら出来るだろうけど
537:デフォルトの名無しさん
17/09/22 14:57:30.68 eEMHecr4.net
>>513
＞int l_ = 3
これ、なんとかならないか？
538:デフォルトの名無しさん
17/09/22 16:30:21.56 W1Y66+yK.net
>>520
関数インターフェース的にはその値を与えることが出来ない
別の関数か何かで変えるかインターフェースを変えるしか
539:デフォルトの名無しさん
17/09/22 16:41:43.04 W1Y66+yK.net
>>516
戻り値を文字列にする方法
方法１
段階によって引数と戻り値の型を変える
S1 fizz(int n);
S2 fizz(S1 s);
std::string fizz(S2 s);
※テンプレートを使うと楽
方法２
戻り値をstd::string固定にしてなんとかする
方法２-１
戻り値は常に結果の文字列にし、パラメーター以外で情報を渡す
方法２-２
文字列に情報をエンコードして入れる
最終型段だけ結果を返すようにする
方法３
戻り値を結果文字列そのままではなく、文字列情報を含む情報とする
(これは反則かな？)
540:デフォルトの名無しさん
17/09/22 16:44:03.80 W1Y66+yK.net
方法２-１であれば >>520の問題は解決する
ただし、そのままだとスレッドセーフじゃなくて気持ち悪い
541:デフォルトの名無しさん
17/09/22 16:48:22.63 eEMHecr4.net
>>509
#=>
これって ruby の記法だったかな？評価値を変えたいようだ
542:デフォルトの名無しさん
17/09/22 18:17:47.82 eeRMTLx0.net
例えばRubyだと文字列を含め組み込み型にインスタンス変数を仕込めるので
たぶんそれで次のメソッドに情報を渡せる
543:デフォルトの名無しさん
17/09/22 19:04:29.86 FtjqsiSd.net
>>522 の方法２-１
C++版
URLﾘﾝｸ(ideone.com)
外部情報は「n」のみ
複数スレッドや割り込みハンドラからコールする時はこのnが問題になるんで
なんとかしてstd::stringに埋め込めれば良いんだけど
>>525
問題を変えちゃダメだよね
> [3.3] 言語： (C/C++/どちらでも可 のいずれか)特に問わない
544:デフォルトの名無しさん
17/09/22 19:08:43.22 FtjqsiSd.net
8行目、なんとなく文字列から判別してみたけど、
素直にnと同じように外部にフラグを持てば条件が減る
(文字列の最後が数字にならないとか文字コードが連続してるとか)
545:デフォルトの名無しさん
17/09/22 19:09:11.03 pX6TouLp.net
「(C/C++/どちらでも可 のいずれか)特に問わない」って日本語がまず謎
有限個の具体例しか与えられていないので仕様も謎
546:デフォルトの名無しさん
17/09/22 19:26:24.34 FtjqsiSd.net
出題者の選択枝が [C/C++/どちらでも可] の３個あって、出題者がその「いずれか」を選ぶ
というフォーマットを使った出題
出題者は回答者に対し『その３個のどれでも良いよ』という意味で「特に問わない」と
と私は解釈した
つまり、回答者の選択枝はCかC++のどちらかだと
出力する文字列のルールはリンク先を見れば大体わかる
gizzが7の倍数かどうかは実際には不明で、実は14で割ると7余る数かもしれないが...
リンク先に「プリントする」とあるので
printfなどで標準出力に出せば良いのかと思ったが、
>>516の解釈は違うらしい
数値の場合だけ""でくくってないので、
文字列の場合は""をくっつける必要があるのか、
型を変えろと言っているのかはよくわからん
いずれにしろ、CやC++では値によって戻り値の型を変えるのは不可能
547:デフォルトの名無しさん
17/09/22 19:32:11.08 FtjqsiSd.net
いずれにしろ、
>>510 >>514 >>517
548:デフォルトの名無しさん
17/09/22 19:33:47.07 eEMHecr4.net
>>529
＞回答者の選択枝はCかC++のどちらかだと
いや、そうじゃなくて、本当に「特に問わない」、どういったらいいかな、このテンプレはC宿題スレのものを、そのまま頂戴しただけじゃない？
549:デフォルトの名無しさん
17/09/22 19:36:43.23 FtjqsiSd.net
>>531
君は出題者なのか？違うのか？
立場をはっきりと
550:デフォルトの名無しさん
17/09/22 19:39:18.64 FtjqsiSd.net
出題者なら０点
551:デフォルトの名無しさん
17/09/22 19:43:00.43 pX6TouLp.net
>>529
なるほど
.gizzは、与えられた数字に対してfizzbuzzが数字になるなら"Gizz"、
それ以外の場合は所定の位置(説明省くけど)に"Gizz"を挿入するものなのかと思ってたわ
552:デフォルトの名無しさん
17/09/22 19:51:22.72 FtjqsiSd.net
確かに
7の倍数じゃなくて1の倍数でも良いよな
たまたま >>509 の例がすべて7の倍数になってただけで
この場合、上にあげた３個のコードいずれも
7 を 1 に変えてくださいな
553:デフォルトの名無しさん
17/09/22 19:54:43.95 FtjqsiSd.net
そろそろ
出題者の模範解答
よろしくね
554:デフォルトの名無しさん
17/09/22 20:00:08.36 eEMHecr4.net
え゛
0点の出題だしー模範解答の質も推して知るべし、なんじゃないでしょうか……：－）
555:デフォルトの名無しさん
17/09/22 20:35:12.69 aD9oWCn2.net
>>526
↓この但し書きがあるってことは、問題作成者（≠出題者）としてはC/C++限定とは考えてはいないだろう
> メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
> オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。
そもそもここで出題する時点で [3] の縛りは意味をなさないよ
556:デフォルトの名無しさん
17/09/22 20:43:54.80 W1Y66+yK.net
>>509に書いてある以上は、それに従うのが基本
557:デフォルトの名無しさん
17/09/22 20:47:11.96 W1Y66+yK.net
と思って私は回答しましたが、
他の人が他の解釈で回答することまで否定はしません
558:デフォルトの名無しさん
17/09/22 20:47:48.19 W1Y66+yK.net
ということで、
>>538 よろしく！
559:デフォルトの名無しさん
17/09/23 03:26:09.79 nBwtcNcI.net
>>509 Ruby >>525の方針で
URLﾘﾝｸ(ideone.com)
560:デフォルトの名無しさん
17/09/23 05:00:15.00 FxaWa0db.net
>>509 F#
URLﾘﾝｸ(ideone.com)
561:デフォルトの名無しさん
17/09/23 09:40:19.02 9eQI4Qct.net
>>509
@Mathematica
URLﾘﾝｸ(ideone.com)
入力値（n）をリストにして次の関数に渡さないとﾀﾞﾒﾎﾟ
562:デフォルトの名無しさん
17/09/23 11:10:41.17 koNmB6po.net
PerlやPythonは？
563:デフォルトの名無しさん
17/09/23 11:25:56.13 7PRDVMsP.net
ネタバレになるけど
このクイズはグローバル変数を使えばそれで済んでしまうシンプルな話なんだけど、それをあえて
- 各言語の機能を熟知・駆使して、面白くしたりひと工夫したりする（たとえばスレッドセーフとか）
- 前者のしくみと、7の倍数のgizzの拡張に必要な追加を最小限にすることを両立させる
というポイントが楽しみどころなんじゃないかな
564:デフォルトの名無しさん
17/09/23 11:29:36.36 w6RxEhSu.net
>>509
URLﾘﾝｸ(ideone.com)
C++。題意は満たしてないけど、自分が書くとこんな感じだな。
末尾判定難しい。
565:デフォルトの名無しさん
17/09/23 17:45:33.07 tyQvRaHd.net
>>509
>>536
>>524～>>547 の方法を想定
Java: URLﾘﾝｸ(ideone.com)
566:デフォルトの名無しさん
17/09/23 17:47:47.85 tyQvRaHd.net
× >>524 >>547
○ >>524 >>542
567:デフォルトの名無しさん
17/09/23 18:26:18.44 80k6Tqnu.net
関数の入出力の型が同一である必要がある
Cならintをchar*と解釈するわけにいかないから構造体だろう
568:デフォルトの名無しさん
17/09/23 22:30:47.29 PEiEI8OX.net
スレッドローカル変数で
書いてみている
569:デフォルトの名無しさん
17/09/23 22:51:39.70 PEiEI8OX.net
>>509 Squeak Smalltalk だけどなんとか >>547 っぽい方法で
| FizzBuzzQuiz |
FizzBuzzQuiz := Trait named: #FizzBuzzQuiz uses: #() category: 'FizzBuzz-Quiz'.
FizzBuzzQuiz compile: 'isDivisibleBy: m
^(Processor activeProcess environmentAt: #
570:fbValue) isDivisibleBy: m'. FizzBuzzQuiz compile: ', str Processor activeProcess environmentAt: #fbValue put: self. ^str'. FizzBuzzQuiz compile: 'fizz ^(self isDivisibleBy: 3) ifTrue: [self, ''Fizz''] ifFalse: [self]'. FizzBuzzQuiz compile: 'buzz ^(self isDivisibleBy: 5) ifTrue: [self, ''Buzz''] ifFalse: [self]'. {Number. String} do: [:each | each uses: FizzBuzzQuiz]. 1 fizz buzz. "=> 1 " 3 fizz buzz. "=> 'Fizz' " 5 fizz buzz. "=> 'Buzz' " 15 fizz buzz. "=> 'FizzBuzz' " 14 fizz buzz. "=> 14 " FizzBuzzQuiz compile: 'gizz ^(self isDivisibleBy: 7) ifTrue: [self, ''Gizz''] ifFalse: [self]'. 7 fizz buzz gizz. "=> 'Gizz' " 21 fizz buzz gizz. "=> 'FizzGizz' " 35 fizz buzz gizz. "=> 'BuzzGizz' " 105 fizz buzz gizz. "=> 'FizzBuzzGizz' " 105 fizz gizz buzz. "=> 'FizzGizzBuzz' "
571:デフォルトの名無しさん
17/09/24 08:25:43.37 wOaJDXIV.net
>>552
×>>547 っぽい方法で → ○>>542 っぽい方法で
572:デフォルトの名無しさん
17/09/24 08:49:01.13 wOaJDXIV.net
>>509 Ruby >>542 を >>552 と同様の手法でリファイン
URLﾘﾝｸ(ideone.com)
573:デフォルトの名無しさん
17/09/25 19:17:51.82 WU5gUeBt.net
>>509 c
URLﾘﾝｸ(ideone.com)
・構造体つこうた
・gizzの「追加定義」については簡易解釈
574:デフォルトの名無しさん
17/10/15 20:26:14.16 12RNBD+4.net
過去問を眺めていたが、もっとお気楽な問題が多かったようですね
肩慣らし問題を一つ
問題
循環小数を有理数に直せ。
循環節は括弧をつかって表現する。
例
0.[555] = 5/9
0.3[33] = 1/3
12.[345] = 4111/333
1.2[34] = 611/495
575:デフォルトの名無しさん
17/10/15 21:45:12.25 IPnwHMWa.net
連分数を使うのかね
576:デフォルトの名無しさん
17/10/15 23:12:59.97 Y75uJW9z.net
>>556 Java
URLﾘﾝｸ(ideone.com)
577:デフォルトの名無しさん
17/10/17 15:01:04.33 qd6dTZ1I.net
循環小数は有理数な訳だが
578:デフォルトの名無しさん
17/10/17 16:22:17.58 kN20YVKE.net
0.[555] = 0.[5] = 5/9
0.3[33] = 0.[3] = 3/9
12.[345] = 12+345/999
1.2[34] = 1.2+34/990
579:デフォルトの名無しさん
17/10/17 18:47:49.98 ELG/Hivs.net
てすと
580:デフォルトの名無しさん
17/10/18 11:15:59.21 xwRaz5Kx.net
>>560
おお。そういう法則で行けるのか。
きっと数学では大昔に証明されてるんだろうけど知らなかった。(または忘れたのかなあ？)
581:デフォルトの名無しさん
17/10/18 11:35:57.38 bG8m3FQp.net
ああ。なんとなくわかった。10の桁数乗の値で割るとそっくりそのまま小数点以下になるが
1足りないから循環するのか。ああ、しかし、数学的にどう表現したらいいかわからない。w
582:デフォルトの名無しさん
17/10/18 15:51:59.37 +Osy4cjh.net
お題：顔文字(^o^)があります。この(^o^)を左右に動かしながら出力します。(^o^)は左から右へ一文字ずつ動き、端に到達した瞬間だけ(^o^)から(>_<)に変化し、また(^o^)に戻って左端へ行き、同じように繰り返します。
端から端までは最初80文字分の幅がありますが、(^o^)が端に達した回数だけ1文字ずつ狭くなっていき、最終的に(^o^)の端まで狭くなり、(^o^)が動けなくなります。(^o^)が動けなくなったらプログラムを終了してください。
583:デフォルトの名無しさん
17/10/18 17:36:32.86 jSYDae9q.net
>>564 Bash (builtins)
URLﾘﾝｸ(ideone.com)
幅80文字だと出力が長くなりすぎて途中で切られるので50文字にしました。
584:デフォルトの名無しさん
17/10/18 19:53:42.77 4F2aMcKp.net
ウインドウズでエスケープシーケンス扱うのにおまじないいるからメンドクセー。
585:デフォルトの名無しさん
17/10/18 21:05:28.73 xwRaz5Kx.net
>>564
改行せずにカーソルを先頭に戻すのは CR (13) の出力で良いのか？
それとも curses ライブラリを使うべき�
586:ｩ？
587:デフォルトの名無しさん
17/10/19 01:56:08.11 Lj1i7npR.net
>>567
好きな方をどうぞ
curses使うのはいいですね
こちらからは見れませんが
588:デフォルトの名無しさん
17/10/19 03:35:28.31 CNJYIyj0.net
じゃ、とりあえず CR 出力版。Perl プログラム。
但し、待ち時間入れないと速すぎて見えないので適当に usleep を入れた。
テストした環境は Linux で端末は Windows の TeraTerm。
TERM=xterm の状態。
但し、プログラムを貼り付けたサイト(paiza.io)での出力はおかしくなる。
何故なら端末として動いてないから。
試したい場合はプログラムをコピーして自分の環境のエディタ等にペーストして保存後に実行して。
URLﾘﾝｸ(paiza.io)
589:デフォルトの名無しさん
17/10/19 05:11:39.88 sgSfn4oM.net
>>564
URLﾘﾝｸ(ideone.com)
C++。改行でやってみた。ちょっと汚い。
590:名無しさん＠そうだ選挙に行こう！ Go to vote!
17/10/22 11:49:54.00 /Umsqxkx.net
お題:A～Z、1～9で出来たランダムな文字列がある(文字列はプログラム開始時に自動的に決めてよい)
キーを2つ決めて(←→キーが自然かも)例えば→キーを押すと、文字列のうち2～9があるか
どうかを調べ、あればそのうち一つをランダムに選び、数字を一つ減らし(9なら8へ)、左右ランダムに
1を置く
つまり2以上の数字文字があればそこがゴムのような役目をして文字列が伸びる
全部の数字文字が1になったら何もしない
逆に例えば←キーを押すと、文字列のうち1～8があるかどうかを調べ、そのうちランダムに一つを
選び、その左右どちらかに数字文字がないかを調べ、足した合計が9を超えないようなら足し合わせて
数字文字をその合計値にし、文字列を1つ縮める
足し合わせた合計が9を超えるようなら他の数字文字もランダムに同様に一つ選び、足し合わせて
9を超えない数字文字の部分が見つかったらそれを一つだけ足し合わせて縮める
全部の数字文字が9になるか、9に満たないが足し合わせると9を超えるようになったら何もしない
591:デフォルトの名無しさん
17/10/23 04:21:48.29 sHZ1Pe4U.net
>>571
URLﾘﾝｸ(ideone.com)
C++。デバッグ難しくてやる気がしないのでバグってるかも。
カーソルキー取るの面倒だからASキーにしておいた。
こんな感じでいいのか？
何のシミュレータかしらんけどめんどくせーな。
592:デフォルトの名無しさん
17/10/23 04:35:24.25 sHZ1Pe4U.net
あ、それと、文字列で計算するのめんどくさかったから、数字でやった。
そっち事情なんか知ったこっちゃない。
593:デフォルトの名無しさん
17/10/23 05:46:30.69 iFI38Dlw.net
%%%%1000%%%%
000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end
594:デフォルトの名無しさん
17/10/23 17:28:50.67 f/2PkHQ/.net
>>574
全く読めねぇｗ
595:デフォルトの名無しさん
17/10/23 20:53:32.54 burVCZw1.net
ランダムの分布は指定なし？
596:デフォルトの名無しさん
17/10/23 23:01:59.68 sHZ1Pe4U.net
いろ
597:んなところでたまに見かけるけど、>>547 ってPGなの？
598:デフォルトの名無しさん
17/10/24 06:49:36.20 kt50Dt6N.net
PGとは？
599:デフォルトの名無しさん
17/10/24 07:14:59.91 Ohc+APnW.net
プロパンガス
600:デフォルトの名無しさん
17/10/24 08:55:25.49 TzjXrYm3.net
パーフェクトグレイド
601:デフォルトの名無しさん
17/10/24 11:04:02.33 2qWQgTrR.net
>>575>>577
>>574はvbsウィルスの一部だよ
つまりワクチンソフトに引っかかるとこのログが検疫されるので注意
602:デフォルトの名無しさん
17/10/24 21:14:43.61 6ceRFBNE.net
>>581
さんくす。
603:デフォルトの名無しさん
17/10/25 20:13:14.36 gieh1Z5o.net
お題
())())のように括弧のみからなる文字列が与えられるので
すべての括弧が正しく対応付けされるためには
最低で何箇所の括弧を逆向きに変更すればよいか求めよ
例えば上の例では2文字目か3文字目を変更すればよいので1を出力せよ
何文字変更しても正しく対応付けできない場合は-1を出力せよ
) -> -1
())()) -> 1
)()()( -> 2
)))((( -> 4
(())())((())(()( -> 3
())((())()))()(((()))()((((((((()()(())) -> ?
604:デフォルトの名無しさん
17/10/25 21:21:26.00 /TQ9iqwZ.net
>>583 Java
URLﾘﾝｸ(ideone.com)
605:デフォルトの名無しさん
17/10/26 00:42:38.67 0Gn/TXrF.net
>>583
Ruby
URLﾘﾝｸ(ideone.com)
606:デフォルトの名無しさん
17/10/26 07:09:40.17 vEkFybta.net
>>583
URLﾘﾝｸ(ideone.com)
C++。効率とかショートコーディングとかそういうものをかなぐり捨ててべた書き。
あってるかな？
607:デフォルトの名無しさん
17/10/26 08:33:36.44 8oLfrbud.net
おむ
608:デフォルトの名無しさん
17/10/26 08:35:57.56 8oLfrbud.net
誤爆
>>583 Ruby
def calc str
return -1 if str.size.odd?
ary = optimise str.scan(/(?=.)(\(*)(\)*)/).map{|a, b| a.size - b.size}
(-ary[0] + ary[1].to_i).abs/2 + ary[0]%2
end
def optimise ary
a = ary.reject(&:zero?).chunk(&:positive?).to_a.transpose[1].map(&:sum)
return a if a.size < 3
a.unshift(0) if a[0] < 0
optimise a.each_slice(2).map(&:sum)
end
STR = %w{
)
())())
)()()(
)))(((
(())())((())(()(
())((())()))()(((()))()((((((((()()(()))
}
STR.each{|s| puts "%s -> %d"%[s, calc(s)]} #=>
) -> -1
())()) -> 1
)()()( -> 2
)))((( -> 4
(())())((())(()( -> 3
())((())()))()(((()))()((((((((()()(())) -> 5
609:デフォルトの名無しさん
17/10/26 19:12:02.71 MqWL4ZqL.net
>>583 ruby
URLﾘﾝｸ(ideone.com)
610:デフォルトの名無しさん
17/10/27 22:31:59.57 sfTuRN3o.net
>>583
@Mathematica
URLﾘﾝｸ(ideone.com)
611:デフォルトの名無しさん
17/11/04 00:05:20.36 4+O3ouw4.net
Quineの派生ということで、コードそれ自身を反転させたものを出力せよ
反転とは文字列"abc\ndef"を"fed\ncba"にすること
612:デフォルトの名無しさん
17/11/04 01:52:41.37 P09Vk2Mx.net
数列 6,66,666,6666,66666.....
これをダミアン数列と呼ぶことにしましょう
nを自然数としたときn^n（^はべき乗）の桁数（１０進数で）が
ダミアン数列のどれかになることはあるか？
初歩的な計算で7^7=823543が6桁になることがわかります
問 このような不吉な数は
7のみである
有限個存在する
無限に存在する
ここまで書いてみたけどこの問題だとプログラミングのお題じゃないね
数論で解けるのかなあ？
改めてお題
ダミアン数列の最初の10項につながる不吉な自然数はあるか、あるとすれば
その数はいくつ
613:か 力技では時間が掛かりすぎると思うので工夫してみてください
614:デフォルトの名無しさん
17/11/04 03:18:31.96 RXqoYVvx.net
意味不明
615:デフォルトの名無しさん
17/11/04 03:39:51.41 pxF/c+yt.net
>>591
URLﾘﾝｸ(ideone.com)
C++。VCオンリー。
ウニコード対応しようと思って色々やってたけど、なんかうまくいかねー。
一応VCではうまくいってるっぽいけど、GCCと共通のコードはまだ規格的にきつそうだ。
うへー。大変だったわ。やっぱ、文字列は鬼門。
616:デフォルトの名無しさん
17/11/04 04:34:35.38 tUO6oLmA.net
>>592 Java
URLﾘﾝｸ(ideone.com)
617:デフォルトの名無しさん
17/11/04 08:04:59.76 bqd73Ayh.net
>>591 Squeak/Pharo Smalltalk
thisContext method getSource reversed allButLast: 8
"=> '8 :tsaLtuBlla desrever ecruoSteg dohtem txetnoCsiht' "
618:デフォルトの名無しさん
17/11/04 10:09:48.41 VZ1zDZPp.net
>>591 ruby
URLﾘﾝｸ(ideone.com)
619:デフォルトの名無しさん
17/11/05 14:54:08.02 rWIlHQ+T.net
>>597 ruby
d="]esrever.d,d[%'d=p%;s%' stup";puts '%s;%p=d'%[d,d.reverse]
#=> ]esrever.d,d[%'d=p%;s%' stup;"puts '%s;%p=d'%[d,d.reverse]"=d
620:デフォルトの名無しさん
17/11/05 14:54:35.06 rWIlHQ+T.net
安価ミスったorz
621:デフォルトの名無しさん
17/11/05 22:47:04.05 Pt23fyK7.net
>>595
2で割らずにシフトしてたり芸が細かいですな
622:片山博文MZ
17/11/07 23:38:24.35 BS6pey7a.net
お題。ツイッターのフォロワーを使ってお金を稼ぐ具体的な方法を思い付く限り列挙せよ。
623:デフォルトの名無しさん
17/11/07 23:48:06.18 aP9yM4om.net
やだ。
624:デフォルトの名無しさん
17/11/08 00:39:27.61 z/y1zyUv.net
プログラミングに関係ないお題は却下
625:デフォルトの名無しさん
17/11/08 20:48:53.00 XbOytUUT.net
片山博文MZってコジキなのか？
626:デフォルトの名無しさん
17/11/13 00:48:07.30 PHmyYrtX.net
コジキっていうか、頭の弱い子
627:デフォルトの名無しさん
17/11/14 21:49:31.73 yEmE0LhS.net
コード中でa-zA-Z0-9の文字を一切使わずに
Hello World!!
と出力せよ。
"!"の後ろの改行の有無は問わない。
628:デフォルトの名無しさん
17/11/14 22:13:39.71 1d5ZohBo.net
>>606 whitespace
629:デフォルトの名無しさん
17/11/15 00:12:32.03 ckRbh5hb.net
前にも見たなぁ。
630:デフォルトの名無しさん
17/11/15 00:21:09.60 edbITJRa.net
>>606
それじゃプログラム組めないと思うんだが、記号だけの言語みたいなの使えってこと？
631:デフォルトの名無しさん
17/11/15 00:30:14.08 au/IFdC5.net
>>606 bhnjdsbkjdsb
_
632:デフォルトの名無しさん
17/11/15 00:31:44.60 ckRbh5hb.net
iostreamがすでにアウト。
633:デフォルトの名無しさん
17/11/15 01:21:11.75 f03ykBDy.net
>>606
634:デフォルトの名無しさん
17/11/15 01:21:50.26 f03ykBDy.net
>>606 Ruby
URLﾘﾝｸ(ideone.com)
perlとjavascriptでも殆ど同じことができる
635:デフォルトの名無しさん
17/11/15 01:23:33.97 0AqsUHvD.net
今日は七五三ということで
7,5,3,+,-,×,÷,(),^2を使った式（ただし7,5,3は一個しか使えない）で1から連続でいくつまで数を作れるか
1=3+5-7
2=5-3
3=3
4=(5-3)^2
5=5
6=(7-5)×3
…
636:デフォルトの名無しさん
17/11/15 06:25:11.32 21MTGrxx.net
^2 もありですか
637:デフォルトの名無しさん
17/11/15 11:19:06.80 +wQkBp8E.net
>>613
回答見てもわからない
どういうこと?
638:デフォルトの名無しさん
17/11/15 11:36:08.43 cnBo
639:JhFE.net
640:デフォルトの名無しさん
17/11/15 11:46:46.76 f03ykBDy.net
>>616
特殊変数$$から1を作ってそれをもとに2, 4, 8, 16などを作る
"%c"を繰り返したものをあらかじめ作っておき
そこに上記の数字で作った"Hello World!!"の文字コードをsprintフォーマットする
標準出力を表す特殊変数$>に<<メソッドでできた文字列を出力する
あとは 「"" << 文字コード」で「文字コード.chr」と同様の結果が得られるので適宜利用すると便利
641:デフォルトの名無しさん
17/11/15 12:14:35.50 GYwcr8MQ.net
>>617の間抜けさ加減に草
642:デフォルトの名無しさん
17/11/15 13:25:57.72 YypYHZ3m.net
>>614
^2 は
int sqr(int n){return n*n;}
みたいな関数が使えるって意味だよね
つまり、
x^2^2 とかは (x^2)^2 の意味で使うなら可能ってことだよね
643:デフォルトの名無しさん
17/11/15 13:32:50.33 +wQkBp8E.net
>>618
記号で1を作って、数値、文字コード、文字列としてくのか
いろんな省略記法も知らないとできないな
解説ありがとう
644:デフォルトの名無しさん
17/11/15 19:03:12.96 vzgZy9E8.net
>>614
5と3を繋げて53にするようなこともしていいの？
645:デフォルトの名無しさん
17/11/16 00:18:43.09 /xRbPsNU.net
計算部は書いたけど、元の表記で何算してるか表記するのが面倒だ。
あと、遅い・・・。
646:デフォルトの名無しさん
17/11/16 00:24:47.24 IIofg8Am.net
73/5=14とかは駄目だよね？
647:デフォルトの名無しさん
17/11/16 01:59:04.45 /xRbPsNU.net
>>614
URLﾘﾝｸ(ideone.com)
C++。
それとなく書いてみたけど、誤差でまくり。割り算鬼門すぎる。
多分バグってる。あと、題意理解してない可能性が微レ存。
648:デフォルトの名無しさん
17/11/16 02:00:39.12 /xRbPsNU.net
あ、そうだ。
カッコの処理がバグバグだったからカッコ使わなかった。
649:デフォルトの名無しさん
17/11/16 02:11:42.94 /xRbPsNU.net
うーむ・・・。なんていうか。。。
ギブアップだ。Orz
650:デフォルトの名無しさん
17/11/16 11:38:12.54 clS3oGAP.net
>>625
「題意理解してない可能性が微レ存」どころじゃねえだろこれｗｗ
651:デフォルトの名無しさん
17/11/16 14:11:34.74 9+S8V57k.net
整数の範囲でも有理数の範囲でも答えが変わらないからつまらん
一旦非整数を経由しないと作れないのがないとやっぱり...
652:デフォルトの名無しさん
17/11/16 15:03:27.99 /xRbPsNU.net
>>628
可笑しいところ教えて！
653:デフォルトの名無しさん
17/11/16 15:46:11.61 9+S8V57k.net
(3^2)^2 = 3^4
((3^2)^2)^2 = 3^8
だから、3^(2*3) とかやっちゃダメだろ
あと、
3×5÷7 = 15÷7 ≠ 2
654:デフォルトの名無しさん
17/11/16 15:59:11.96 /xRbPsNU.net
>>631
あー、俺がタコでした。
まぁ、前段は表示系の問題だと思うお。
後者は割り算が全部悪い。
浮動小数で比較したくないんだよなぁ。悩ましい。
655:デフォルトの名無しさん
17/11/16 16:39:35.92 9+S8V57k.net
有理数クラスを作るのだ
656:デフォルトの名無しさん
17/11/16 17:43:36.30 /xRbPsNU.net
有理数の法則がよくわかってないし、デカイ。
ままならんなー。
657:デフォルトの名無しさん
17/11/16 18:03:35.37 9+S8V57k.net
(a/b) + (c/d) = (ad + bc) / bd
(a/b) - (c/d) = (ad - bc) / bd
(a/b) * (c/d) = ac / bd
(a/b) / (c/d) = ad / bc
(a/b) = (c/d) <===> ad = bc
分子 : 整数
分母 : 0以外の整数
658:デフォルトの名無しさん
17/11/16 21:25:39.77 /xRbPsNU.net
数学ムズイ。。。
PGも算数で解いてるからな。
659:デフォルトの名無しさん
17/11/17 00:16:40.63 5DUWZGJy.net
紙とペ
660:ンで考えてみたところ 0以外の任意の整数なら3,5,7で表わせるから問題として不適なのでは？
661:デフォルトの名無しさん
17/11/17 00:20:03.76 M2EFWWXH.net
17
662:デフォルトの名無しさん
17/11/17 10:03:52.61 oe8UBfUe.net
>>637
3,5,7は１回までって回数制限があるから
表せる数は限られるよ。
663:デフォルトの名無しさん
17/11/17 10:44:12.02 a6b9gyRQ.net
17が出来ない
664:デフォルトの名無しさん
17/11/17 19:35:00.15 5DUWZGJy.net
ああ、本当だ。17はどうやっても作れないね
しかしこれをどうやってコードで計算すんだろう
^2があるから全探査はできないし
自分は「+または-」をいくつ使うかで場合分けして一個一個可能性を消していったんだけれども
665:デフォルトの名無しさん
17/11/17 20:04:40.56 M2EFWWXH.net
コードはアップしないけど出来たよ
666:デフォルトの名無しさん
17/11/17 20:07:16.14 M2EFWWXH.net
独自有理数クラス
演算回数を1回ずつ増やしていって、
出来た値に対応するフラグをセット
667:デフォルトの名無しさん
17/11/17 20:09:06.68 M2EFWWXH.net
数値をstd::multisetで保持
演算n回目のmultisetをstd::setで保持
668:デフォルトの名無しさん
17/11/18 17:51:34.79 6foiYhRZ.net
ABC4D
-E3FG
-----
77777
A～G は、1～9 の異なる数字。
ただし、3, 4 ではない
669:デフォルトの名無しさん
17/11/18 17:56:36.72 R4dFDjUs.net
はい、そうですか。
670:デフォルトの名無しさん
17/11/18 19:08:28.21 8fhXEikQ.net
>>645 Java
2年前の問題と俺の回答
ｽﾚﾘﾝｸ(tech板:451番)
を改造したもの (50-54行目と標準入力)
URLﾘﾝｸ(ideone.com)
671:デフォルトの名無しさん
17/11/18 19:44:36.57 oFg54zrO.net
>>645 Ruby
f = ->a, b, c, d, e, f, g{10000*a + 1000*b + 100*c + d - (1000*e + 10*f + g) == 78037}
[1, 2, 5, 6, 7, 8, 9].permutation{|a| puts "%d%d%d4%d - %d3%d%d == 77777" % a if f[*a]}
#=>87142 - 9365 == 77777
672:デフォルトの名無しさん
17/11/18 20:40:01.77 6foiYhRZ.net
>>647
何も、そこまで作り込まなくても良いだろw
色々な覆面算に対応するため、汎用的に書いたのか
673:デフォルトの名無しさん
17/11/19 22:39:02.74 oda4btU4.net
500, 100, 50, 10, 5, 1円のすべての種類の硬貨を、1枚以上使って、
合計15枚で750円にする時、10円硬貨は何枚になるか？
A～E の5人のランナーが走った結果、
完走したのは、1着とべべの2人で、残りの3人は、途中で棄権した
ここで、完走した2人は、必ず真実を言い、
棄権した3人は、必ず嘘をつくものとする
(つまり、事実に対して、真偽値を取る)
A: D は棄権した
B: A は、べべだった
C: E は棄権した
D: C は、べべだった
E: B は完走した
A～Eがこのように答えた時、1着は誰か？
674:デフォルトの名無しさん
17/11/20 01:25:03.39 Z32/GYkn.net
先に答えやそれに至る式がわかっててコードに書き直すだけになっちゃうから
数学的に道筋立てて答えが出せるものはあんまりおもしろくないんだよな
675:デフォルトの名無しさん
17/11/20 03:34:46.27 GkhyFhEh.net
アルゴリズムとは、数式の完全コピー
最初に、数式を考えて、その数式が間違っていれば、
撃墜モードでは、そこを突かれて撃墜される
結局、数式の証明が大事。
証明に、勘違いが無いかどうか
676:デフォルトの名無しさん
17/11/20 11:24:27.08 7i/OQPcC.net
べべってなんぞ？
677:デフォルトの名無しさん
17/11/20 11:38:36.82 OJcNabXy.net
>>653
たぶんこの場合は大阪の方言
678:デフォルトの名無しさん
17/11/20 11:45:30.45 7i/OQPcC.net
俺地方の人間だからわかんない。
679:デフォルトの名無しさん
17/11/20 18:24:16.80 Slkhafwt.net
べべって最下位のことじゃないか
どべ
680:デフォルトの名無しさん
17/11/21 23:50:05.58 zUV8sDjk.net
>>645
こんなのどうかな。Kotlin で作った。
URLﾘﾝｸ(paiza.io)
681:デフォルトの名無しさん
17/11/23 10:05:44.85 zWeuVerg.net
お題
1から99を表示する
お題：1から999を出力する
ただし0を含む数は除く
682:デフォルトの名無しさん
17/11/23 10:11:40.40 TrZHjzbP.net
>>658
1000.times{|i|p i unless i.to_s[?0]}
683:デフォルトの名無しさん
17/11/23 12:15:31.91 6AL/1aep.net
>>658 GNU Smalltalk
1 to: 999 do: [:n | (n asString includes: $0) ifFalse: [n displayNl]]
684:デフォルトの名無しさん
17/11/23 12:38:42.26 KUvGqrz8.net
>>658 F#
let () = seq { 1..999 } |> Seq.iter (printfn "%d")
685:デフォルトの名無しさん
17/11/23 12:40:24.86 KUvGqrz8.net
>>661
すまん、問題よく読んでなかった･･･
686:デフォルトの名無しさん
17/11/23 13:30:23.43 jBvfUrCY.net
>>658
URLﾘﾝｸ(ideone.com)
C++。ほかの言語だと一行で書けるんだけどなぁ。
まぁ過去に比べれば大分短くなったけど。
687:デフォルトの名無しさん
17/11/23 15:45:02.09 ys+VuKpG.net
>>658
文字も数もその場に合わせて適当に解釈してくれる言語だと楽だね。
perl だとこれでできる。
for(1..999){print"$_\n"unless(/0/)}
688:デフォルトの名無しさん
17/11/23 16:16:10.88 JcpJJmmU.net
>>658
@Mathematica
nListWithoutZero[n_]:=n//
Range[1,#]&//
Map[ToString,#]&//
StringCases[#,RegularExpression["^(?!.*0).*$"]]&//
Flatten;
In[1] := nListWithoutZero[999]
Out[1] = (略)
689:デフォルトの名無しさん
17/11/23 16:34:54.15 2sNCCDGP.net
>>658
ダメだお題の意味がわからん
降参
690:デフォルトの名無しさん
17/11/23 16:42:00.54 QTAUjuBR.net
>>658 rust
URLﾘﾝｸ(ideone.com)
fn main() {
println!("{:?}", (1..1000).filter(|i| !i.to_string().contains("0")).collect::<Vec<_>>())
}
691:デフォルトの名無しさん
17/11/23 16:46:25.38 ys+VuKpG.net
>>658
Kotlin で文字列変換してやる場合
fun main(args: Array<String>) {
for (i in 1..999)
if (! i.toString().contains('0', false))
println(i)
}
数値のままやる場合
fun main(args: Array<String>) {
for (i in 1..999)
if (i % 10 != 0
&& (i < 10 || i / 10 % 10 != 0)
&& (i < 100 || i / 100 % 10 != 0))
println(i)
}
692:デフォルトの名無しさん
17/11/23 17:05:13.53 fGVRHt7J.net
>>658
>>668 同じく数値のままやる場合
URLﾘﾝｸ(ideone.com)
693:デフォルトの名無しさん
17/11/23 17:08:37.18 fGVRHt7J.net
ｽﾚﾘﾝｸ(math板:722番)
お題：
n^2-1 = m^5
を満たす自然数 n, m は存在するか？
存在するという人と存在しないという人の両方が存在します
694:デフォルトの名無しさん
17/11/23 17:18:38.32 TrZHjzbP.net
>>670
(n, m) = (1, 0)
揚げ足取りはおいておいて、プログラミングで説く問題じゃないよね
695:デフォルトの名無しさん
17/11/23 18:35:09.23 zveldNvP.net
>>658
python
今回は必要ないかもだけど桁数増えた場合を考え再帰で
URLﾘﾝｸ(ideone.com)
696:デフォルトの名無しさん
17/11/23 19:09:48.15 fGVRHt7J.net
>>671
まあ自明な解はさておき、その他は見つからないのが不思議です
697:
698:デフォルトの名無しさん
17/11/23 20:21:54.46 /mQ4CZGQ.net
>>673
カタラン予想ですでに存在しないことが証明されているのに何が不思議なのかね
699:デフォルトの名無しさん
17/11/23 20:24:10.50 hjkeK8jf.net
>>673
その問題は数学的に解くものではないかな?
まあ、コンピュータなら力業でかなりの値を n, m に入れて計算して確認できるけどさ。
700:デフォルトの名無しさん
17/11/23 20:56:22.87 fGVRHt7J.net
>>674
カタラン予想というのがあるんですね、ありがとうございます！
URLﾘﾝｸ(en.wikipedia.org)
701:デフォルトの名無しさん
17/11/23 21:05:28.66 uF7hi9HH.net
>>658
#!/bin/sh
seq 999|grep -v 0
702:668
17/11/24 06:21:36.98 8wyGH9pr.net
>>658
Kotlin数値判定版。こんな風にも書けるなと後で気づいた。
fun f(n: Int): Boolean {
var m = n;
while (m != 0) {
if (m % 10 == 0)
return false
m = m / 10
}
return true
}
fun main(args: Array<String>) {
(1..999).filter(::f).forEach(::println)
}
703:デフォルトの名無しさん
17/11/24 07:42:25.55 MEHEP0+e.net
存在するしないをプログラミングで証明するのはお題として良くない
704:デフォルトの名無しさん
17/11/24 20:42:02.54 G34PGfZh.net
log 2 を2進数表記した時の小数点第 n 位から n + 9 位までを求めよ． (1 ≦ n ≦ 10^10)
cf. log 2 = 0.10110001...
*Sample input*
1
11
10000
31415926
314159265
*Sample output*
1011000101
1100100001
0010110110
1001010110
0111101001
705:デフォルトの名無しさん
17/11/24 23:31:00.22 r53+zpq0.net
>>680
c++で書いたけど小数第100億位を計算するのに5時間くらいかかりそうorz
706:
17/11/25 00:04:03.20 ROI3Hzdd.net
>>681
もう初手に届くとは劇速ですね
707:デフォルトの名無しさん
17/11/25 06:53:37.62 Uo3oYb2P.net
無条件でlogって書いたら普通自然対数だろ
708:デフォルトの名無しさん
17/11/25 07:01:13.88 Uo3oYb2P.net
ライブラリを使えばほとんど何も書かなくて良いけど
どこから書くことを求められてるの？
709:デフォルトの名無しさん
17/11/25 07:03:54.53 Uo3oYb2P.net
>>679
「良くない」じゃなくて「出来ない」でしょ
710:デフォルトの名無しさん
17/11/25 07:16:55.64 Uo3oYb2P.net
>>684
と思ったけど、普通に全桁計算したら終わらないな
711:デフォルトの名無しさん
17/11/25 07:34:12.57 Uo3oYb2P.net
Σ { 1 / (2^i × i) }
を使って10^10項位までを42bitくらいだけ計算すれば出来るかな？
1/nの周期性を考えないと計算量的に無理？
10^10が微妙に32bitを越えてるのがイヤだねえ
712:デフォルトの名無しさん
17/11/25 08:21:38.07 Uo3oYb2P.net
>>687
ダメだ
ざっと計算量を見積もったらとても5時間じゃ終わらない
713:デフォルトの名無しさん
17/11/25 13:10:34.24 l6j6CjYT.net
>>375
xxx@xxx-VirtualBox:~/casl$ casl -s -e -i stdlib.casl -i bigint.casl fact.casl
1
1
2
6
24
120
720
5040
40320
362880
途 中 省 略
1405006117752879898543142606244511569936384000000000
60415263063373835637355132068513997507264512000000000
2658271574788448768043625811014615890319638528000000000
119622220865480194561963161495657715064383733760000000000
5502622159812088949850305428800254892961651752960000000000
714:258623241511168180642964355153611979969197632389120000000000 12413915592536072670862289047373375038521486354677760000000000 608281864034267560872252163321295376887552831379210240000000000 30414093201713378043612608166064768844377641568960512000000000000 暇つぶしに書いてみたけど足算掛算割算しかできない 引算は難しすぎるんで諦めた
715:デフォルトの名無しさん
17/11/25 16:35:37.76 J1zvm3XW.net
バイナリ法で最適化した結果なんとか1時間あれば10^10位は計算できるようになったがまだ縮められるかな
716:
17/11/25 16:41:37.19 ROI3Hzdd.net
備忘メモ
ｽﾚﾘﾝｸ(math板:890番)
ちゃんとお題にして出題しなおします
717:
17/11/25 21:49:51.82 ROI3Hzdd.net
>>680
指数関数のマクローリン展開で試してみたのですが、これは収束が遅すぎますね、それに収束半径を超えてるし…
なにか収束の早いよい方法はないものか…
718:
17/11/25 21:54:37.24 ROI3Hzdd.net
>>692
×指数関数
○対数関数
719:デフォルトの名無しさん
17/11/25 22:58:19.91 yyAYDlfh.net
対数関数のマクローリン展開？
そりゃ無理だ
log 0 が定義されてない
720:デフォルトの名無しさん
17/11/25 23:12:41.85 FRsJtlII.net
>>689
CASLで書いたの?
ソースコードは?
721:デフォルトの名無しさん
17/11/25 23:38:41.06 yyAYDlfh.net
>>680
log 2 = Σ_[i=1, 2, ...] { 1 / (2^i × i) }
冪剰余
でいける気がしてきた
しばらく暇がない
時間が空いたら
アセンブラ & C++ & OpenMP
でやってみる