プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>275 アルバートは月を知ってるが、バーナードも知らない事を確信できるのは、 18,19日を含まない7,8月のどちらかという事になる -> 5,6月は全削除 それを聞いてバーナードは誕生日がわかるので、7,8月両方に含まれる14日ではなく、 15,16,17日のどれかになる それを聞いてアルバートがわかるので、候補が一つしか残ってない7月16日という事になる >>278 そこがオレにはよく理解できていなくてさ。 まぁ言葉にあいまいな面があるかもしれんから解釈に差が出たのかな >>279 解釈の差だけが問題じゃないだろ > ⇒日の登場回数が一回だけの19日、6月18日を除去したあと、 > 登場回数が一回だけの日が バーナードの聞いた「日付」に当たり、 > 誕生日だと考えられる。 18日、19日は日の登場回数が一回だけであるということは 他の日は複数回登場するということだからその論理は破綻してる >>280 それは誤解というか解読不足。 5月19日、6月18日が除去されることによって、 元々複数回登場していた他の日のうち6月17日が単一の日となり 17日という日付さえ知らされれば、誕生日は6月17日と判明できる。 >>281 客観的に見て、アルバートがバーナードも知らない事を確信できる為には、 アルバート自身が知っている月には18,19日が含まれていない必要がある 従って、アルバートが知っている月は5,6月ではないという事 >>282 なるほど考え方は理解できた。 でも5月6月には他の日もあるからバーナードが聞かされた日がそれらで無いとはっきりしていないうちに 月ごと排除して大丈夫? >>281 17日は8月17日もあるから、 6月が17日だけになったからといって、 6月17日が誕生日だとするのは アルバート、バーナードの台詞を根拠に基づく論理に 無理がないか検証不十分だという気が自分でもしてきた >>283 逆に最初の時点でアルバートはバーナードが知らないとは確信できない 例えばアルバートは6月と聞かされた場合、6月18日の可能性もあるので、 それだとバーナードは18日と聞かされているから知ってるかもしれない >>285 大体分かった。ありがとう 単一な日をまったく含まない月を教えられたからこそ、 アルバートは最初の台詞 「僕はシェリルの誕生日を知らないけど、バーナードも知らないよ」 になったという考え方だね。 ディスコプログラミングコンテスト 2017 7/8 https://www.disco.co.jp/procon/ の練習問題 https://www.disco.co.jp/procon/#example 解答バレにならないように1語だけ書くけど 1問目の TOUSHITSUWOTOTTE だけが、わけわからん >>288 Q1といてみたけど 「糖質を摂って」じゃない? >>290 いやそう謎でもない。 解の文を全部通しで読むと この前に食べものの話がある。 糖質が頭の働きを良くするという通説と逆に頭を鈍らせるという説があるけど この会社が前者を支持することを明言する意味がある 例題に挑戦して下さりありがとうございます!全問正解した参加者にはディスコ限定どら焼きをプレゼント! 大会当日に受付でお渡ししします。糖質を摂って優勝目指して頑張って下さい! ダメじゃん。全解答を書いちゃって。 でも簡単すぎる問題だしどうでもいいか。 前にあったやつ。 回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。 コンベアは毎秒1皿分の速度で流れ、目の前の皿を取るか取らないかを選ぶことができる。 皿取ると同時に食べ始め、食べている間は次の皿を取ることができない。 私が取る以外、皿は追加されたり無くなったりしない。 コンベアの状態が次のような文字列で与えられる。 "31_2" 数字はその皿を食べ終えるのにかかる秒数を表し、_は皿がないことを表す。1文字目が目の前にあり毎秒、左へ回転する。 例えば、"31_2"で最初の皿を食べたとき食べ終わった時の状態は、"2_1_"となる。 すべての寿司を食べ終えるまで最短何秒かかるか求めよ。 "12_3" > 6秒 "313__" > 8秒 "4_35_1264_23_434" > 60秒 "123456789123456789" > 98秒 "88967472612377988186" > 149秒 "19898693316679441672" > 170秒 "93769682716711132249893" > ? 皿がもうちょっと多いと難しくなるけど、>>296 なら力業でも >>296 Perl ttp://ideone.com/iUAYUy 実行結果は $ perl 9_296.pl 12_3: 6 313__: 10 (合わない…orz) 4_35_1264_23_434: 62 (合わない…orz) 123456789123456789: 98 88967472612377988186: 151 (合わない…orz) 19898693316679441672: 170 93769682716711132249893: 176 となり、半分が合わない。 そのうち 313__ を手で研鑽すると 10 になるのだが、 313__ は本当に8になるの? 313__ はこれでは? まず一皿ながして 1を食う、2秒時点の状態 3__3_ 3を食う、5秒時点の状態 3____ 3を食う、8秒で食べ終わり >>302 そっか、最初の3を食べちゃったら最短時間にならないな >>299 は最初の皿からダボハゼみたいに食いつくので必ずしも最短にはならないな きっと腹が減りすぎていたんだろう…orz >>296 は、 目の前にあるやつを食べ続けるだけで最短になっちゃうのもあるってことか。 >>296 http://ideone.com/PGKCb4 計算量は2^n*n (n:コンベアの長さ) n=24はほぼ限界 n!をbitDPで計算量落とす。 (空皿処理で昔より手を抜いている) 考えてみたけと計算オーダーを減らすのはむずかしいね 枝刈りは色々と出来るけど >>218 Perl ttp://ideone.com/ylFIEa ソースコード4行目の my $n = 8; # 分割する自然数を設定 の8を書き換えると他の整数についてもヤング図形を出力できます。 366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE 今回の民法改正、ソフトウェア受託開発の場合、(検収後ではなく)バグ発見後1年瑕疵担保責任があるということで、地獄かよ、と思ったが、 元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。 一部で地獄を見ても。 https://twitter.com/yukihiro_matz/status/869061879389343744 367 :nobodyさん 2017/05/29(月) 16:28:06.55 ID:6v4UcGhE ニュース - 改正民法が成立、「瑕疵担保責任」などシステム開発契約に影響大:ITpro http://b.hatena.ne.jp/entry/itpro.nikkeibp.co.jp/atcl/news/17/052601508/ 372 :nobodyさん2017/05/29(月) 19:10:37.12 ID:??? Railsでシステム作って納品する ↓ Railsはマイナー、メジャーのアップデートが半年以内に必ずある ↓ 客がアップデートする。アップデートによるエラーやバグ、動作の不具合に気づく ↓ 気づいてから1年以内に通知すれば、5年間無料保証ゲット ↓ つまりRailsがアップデートするたびに、無償の修正作業を発生するということかな 376 :nobodyさん2017/05/30(火) 09:20:20.09 ID:L5po86sS >>378 >>379>>375 客が瑕疵担保責任法の法改正を知ってくると思うから、今後5年無償保証をお願いされるだろう 営業がそれでも仕事を取ってこれるか?たぶん無理だろう。無限の直していたら赤字になる。 こういう保守に弱い言語、ころころ仕様が変わる言語は仕事として発生しなくなってくる。 これは変わり目だ。お前らも早く逃げたほうがいいぞ。RubyやPHPなど動的言語は確実に廃れる。 保守に強い言語のみ生き残れる。 瑕疵担保責任(かしたんぽせきにん) 瑕疵担保責任のポイント 民法改正で事実上期限が「無制限」になった バグや設計のミスなどは、瑕疵担保責任 納品物に不具合があれば損害賠償を請求される可能性もある 不具合を指摘されたらすぐに行動をとるべし 軽微なミスでも先延ばししない http://www.atmarkit.co.jp/ait/articles/1706/26/news014.html http://itpro.nikkeibp.co.jp/atcl/news/17/052601508/?rt=nocnt 改正法では欠陥に気付いてから1年以内にITベンダーに通知すれば、 通知後5年以内は修正や報酬の減額などを求められるとしている 全ベンダーが泣いた民法改正案を解説しよう その1 http://www.atmarkit.co.jp/ait/articles/1609/14/news009.html http://www.atmarkit.co.jp/ait/articles/1609/14/news009_2.html http://www.atmarkit.co.jp/ait/articles/1609/14/news009_3.html ポイント1:修補や損害賠償、契約解除の期限がなくなる 従来あった「瑕疵担保期間は引き渡しから1年」という考えはなくなる。 条文にある通り、注文者は成果物が契約の目的に適合しないことを発見したら、 その「発見したときから1年以内」ならさまざまな請求ができる。発見が10年後なら、 11年後まで請求可能なのだ。 もっとも、現実のユーザーとベンダーの関係でも、たとえ契約書に「瑕疵担保責任期間は納品から1年と」明記されていても、 「2年目以降は不具合の修正に対応しない」と主張するベンダーはまれだ。多くの場合は、納品から何年たっても、 バグが見つかればユーザーのところに飛んで行き、無償で改修するだろう。 >>305 修正 http://ideone.com/PGKCb4 経路情報復元(ベストは複数あるかもしれない中から一つ選んで)。 ついでにその経路での途中経過を表示してみた。 インデックス、待機秒数、開始時間、食事秒数、終了時間、 >>218 >>307 Perl http://ideone.com/GC2JTj 再帰を使わず、リスト処理とloopで書き直したら もう少しコンパクトですっきりしたものになりました… >>314 Perl5 http://ideone.com/YCw1OC 桁の多い数値の幅を反映して数値間の空白の数を決めれば 数値の位置がもう少し見やすくなるとおも… お題:完全なヤング図ソルバー。 http://ideone.com/hkUkFM 書いてみたけど、不完全なのがやっとだった。 あってるかもわからん。 図の効率がいいほど評価が上がります。 >>296 >>299 Perl5 http://ideone.com/0yJ5U9 リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。 31…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、 取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、 再帰的に両方に分岐し、木構造で計算しているが、 逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので 来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。 それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、 四つめ以降は時間がかかりいつ終わるか分からない。 そこで、検索された食事秒数の最小値の更新状況を記録し、 同じ最小値が一定回数以上連続して繰り返し検出されるようになったら 最短値に収束したと見なし、探索を打ち切ることによって短時間で 解を出力できるようにした。打ち切り上限は10をハードコードしてあるが 今回のサンプルデータについては4か5で十分そうだ。 なお、23_ のような、2を食べることによって飛び越しを起こすポイントの 一番最後のものは,食べずにスルーして先に2を食べた方が、 次の周で早く食べ終わることは明らかだ。 これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが 難しそうなので、見送った。 >>318 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら 打ち切るという、簡単な枝刈りを取り入れてあります。 連投スマソ >>318 枝刈りで最短を刈り取ってしまったら駄目じゃないか 例えば "3324" -> 15秒 にならないな >>320 誤解です。 枝刈りは、ある探索中の枝において始点から既に経過した秒数が それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、 現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って 別の枝の探索に移るというものなので大丈夫です。 "3324" の最短秒数を探索すると 15秒になります。 >>321 あれ、変だな >>318 のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな? 同様に"3328"、"3364"は最短19秒だけど>>318 だと20になった >>322 同じコードをideoneに張りなおして3324を入力して実行してみました。 http://ideone.com/vXrTp8 ソースを一箇所編集しています。 31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出 の繰り返し回数上限判定地を10から20に増やしています。 3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。 3364も20が10回繰り返した後19が出て続きます。 お手数おかけしますが 一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして 評価してください。 >>323 3324と3364の解を見ていて気が付いた点があります。 一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、 3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため 解として表示されています。 これは、3324の15や3364が4桁しかないので、 最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を 解として表示していることによります。 >>318 の一定回数繰り返したら収束とみなすという判定方法は、 ニュートン法のような数値計算では有効ですが、 >>296 の問題の解の判定方法としては適切とは言えないかもしれませんね…orz 3324を拡張した887654329は閾値どれくらい増やせば対応できるんですかね >>325 延々探索を続けないと解に至らないかもしれない入力については 定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。 887654329がそういったカテゴリーに属する入力かというと チョット分からない。 なので適切な閾値はこれだと断言しにくいです。 さーせん >>326 結局>>321 は大嘘だったし、閾値20の>>323 にしたところで 例えば"14432"は最短にならないし 閾値が決められないならその解法はやはり駄目だな >>327 閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、 計算しても最小を更新しない枝に降りずに切り上げてくる>>321 は嘘ではないよ。 見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。 それによって20で打ち切るようなやり方を改善できればいいんだけれども… それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して とけなくなる >>328 閾値20で打ち切るのは枝切りじゃないという主張のようだけど 打ち切るという動作は枝切り以外の何物でもない >>318 は”3324”の最短に到達しないから>>321 の > "3324" の最短秒数を探索すると 15秒になります。 というのも嘘 >>330 絡むね。そんな暇あったらコードでも書けばいいのにw 閾値20でその入力については解の探査を止めて 別の枝に移らず次の入力データに移るのはどちらかといえば中断で、 枝かりではないでしょ。 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 にかいてあるでしょうに。 >>318 は”3324”の最短に到達しないから>>321 の > "3324" の最短秒数を探索すると 15秒になります。 >というのも嘘 これは10回の打ち切りの緩和を書きもらしたんだよ。 何が狙いで、こだわって絡んでくるやらねぇ。 「打ち切る」という言葉を >318 >… >同じ最小値が一定回数以上連続して繰り返し検出されるようになったら >最短値に収束したと見なし、探索を打ち切ることによって短時間で >解を出力できるようにした。打ち切り上限は10をハードコードしてあるが では「その入力に対する求解を中断する」ところで使い、 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの ところで使ったのが誤解を招いてしまったのかな… お題: 自然数Nの平方根を整数部含めて(1000*N)桁求めたとき、出現する0の個数を数える たとえば、N = 4の時ルート4を4000桁(整数部1桁+小数部3999桁)求めたとき、出現する0の個数は3999個 N = 3 => ? N = 5 => ? N = 7 => ? >>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 >>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 >>337 N = 5の場合が間違ってると思う 多分、丸めモードの関係か、精度が足りてないと思われる >>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 >>334 Squeak/Pharo Smalltalk | sqrt | sqrt := [:n :m | "ref. https://xar.sh/post/67066374255/ " | a b | a := 5 * n. b := 5. [:exit | [ a >= b ifTrue: [a := a - b. b := b + 10] ifFalse: [ b log > m ifTrue: [exit value] ifFalse: [ a := a * 100. b := b // 10 * 100 + (b \\ 10) ] ] ] repeat] valueWithExit. b ]. #(3 5 7) collect: [:i | i -> (((sqrt value: i value: i*1000) asString first: i*1000) occurrencesOf: $0)] "=> {3->309 . 5->493 . 7->738}" >>339 N = 29とN=41の場合が間違ってる可能性? それ以外は正しい模様 N = 29 => 2912、N = 41 => 4094 じゃなかろうか >>340 合ってる >>341 > N = 29 => 2912、N = 41 => 4094 じゃなかろうか それが正しいようです GNU MPだとどうしても最後の桁は四捨五入?されるようで 任意のNに対して正確な答えを出すのは面倒なので修正は断念 結局バイナリーツリーになっちゃったなぁ。むずかし。 >>344 考え直したら面倒じゃなかった >>334 C++ http://codepad.org/k0Sq8Fqo N=10000くらいまでなら現実的な時間で計算出来そうだ N=100000, 1億桁のくらいなら現実的な時間で出来る 丸めは切り捨て?四捨五入? >>347 GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので floor() であらかじめ切り捨ててから get_str() した ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか? 連続するゼロの個数の最大だろ? 無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。 もとめる桁数のほうに上限があったのか、それを見逃してた。 >>349 floorを行った後の結果に誤差は無い という検証は出来てるの? 何もしてないなら、それはたまたま偶然当たったっていうだけだぞ ていうか、君には聞いてない 出題者の意図を聞いてる >>355 >floorを行った後の結果に誤差は無い >という検証は出来てるの? ぱっとみ当然だと思うんだが >>356 何桁求めるか指定しないと意味がないのでは? >>358 ん、考え直した 10進に変換した結果にて 99999 とかが末尾にあるようでは、余分の計算はしないといけないね [][Tebla][] } 000-"Yob*RtStrike"[%Kil\]MO,fla>%$9999VLTS 001-GYORLith"0\R"/"ESUBA"%$% HADO-"EM","L","O","NU"###END >>296 http://ideone.com/VzYVY9 C++。解けた気がする。 状態をメモ化してみた。 何で動いてるのか自分でもよくわからない。 暇だったので解いてみた。 >>362 私も欲しかったので作ってしまった、今 >>334 を奮闘中 >>363 それはすごいな。 後々破棄するようなものを作るモチベーションが出てこないよ。 >>365 あはは・・・。 コード書き捨てるのは良いけど、道具書き捨てるのは俺には向いてないわ。 なので、標準待ち。 boostという任意倍長の計算Libraryがあります。 C++では使えるそうです。 >>367 Boostも良いんだけどね。残念なことにあれは実験環境で準標準って扱いなんだよなぁ。 あれから取り入れられるライブラリも多いんだけど、標準じゃないからね。 残念なことに。 まあ標準ライブラリしか使わない縛りをしたければ好きにすればいいんじゃない? 競プロみたいな相手方の環境使う物だと標準と準標準の差はでかい 自分の環境なら導入すればいいだけだが >>361 厳密解を出しているのなら、チャレンジ (わかって近似値解狙いなら気にしないで) "14432" と "887654329" 両方とも既出の"貪欲つぶし"(?)数列 "14432"は 20秒 (ゼロインデック順で02341) "887654329"は 80秒(同123456708)でいける。 >>373 http://ideone.com/cBzPSj C++。それ解くとほかの問題が解けなくなる。 厳密解のつもりだったが、ちょっと自分の領分超えてるなぁ。 うまくいかないものだ。 真実が奥の方にあると貪欲法は弱いな。Orz お題: 自分用多倍長整数演算関数 …って思ったけど、処理系の標準ではないとか、仕事でGNU MP使っては駄目とかの 制約で、簡易的なもの(乗算くらいまでとか)を書いた事ある人は少なくないと見た。 多倍長整数演算がサポートされている言語を使う 終わり ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる