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

1 名前：デフォルトの名無しさん mailto:sage [2016/12/01(木) 16:58:30.97 ID:gTkHDluD.net] プログラミングのお題スレです。 前スレ プログラミングのお題スレ Part8©2ch.net echo.2ch.net/test/read.cgi/tech/1444216746/ 【出題と回答例】 1 名前：デフォルトの名無しさん 　　お題：お題本文 2 名前：デフォルトの名無しさん 　　>>1 使用言語 　　回答本文 【ソースコードが長くなったら】 (オンラインでコードを実行できる) ideone.com/ codepad.org/ compileonline.com/ rextester.com/runcode runnable.com/ code.hackerearth.com/ melpon.org/wandbox https://paiza.io/ 宿題は宿題スレがあるのでそちらへ。 263 名前：デフォルトの名無しさん mailto:sage [2017/06/02(金) 22:03:48.67 ID:doJoDkLD.net] 賞金とか誰かと思ったら片山博文MZか。 264 名前：デフォルトの名無しさん mailto:sage [2017/06/02(金) 23:44:04.74 ID:cFhdiKGB.net] 三千円じゃ安い 265 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 01:24:32.19 ID:4TZnG99D.net] >>255 動的言語のscriptでもQt,Wxwidget,Tkinterなど色々のGUI　ｆｗが使えるから書けるよ。 でも、エッセンスがなく、会コードが無駄に長くなるお題は、作成に時間がかかるし獣よな技術はないし 趣旨を考えで出題しろよ。 すくなくとも自分で作る気になれる題を出せ 266 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 01:26:10.05 ID:4TZnG99D.net] >>261 会コードが無駄に長くなるお題は、作成に時間がかかるし獣よな技術はないし ↓ 解コードが無駄に長くなるお題は、作成に時間がかかるし技術はないし 267 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 01:50:43.99 ID:4TZnG99D.net] でも、まぁ地獄の沙汰も金次第というじゃありませんか。 お見積もり30万円以上でしたらpython+tkinterで書いてお納めすｔることも 検討させていただきますよ。ﾊｲ 更にハイグレードに300万円だったらPerl+Ptkもお付けいたいます。 いかがですか?だんな もみ手 268 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 19:38:09.78 ID:bt+/AaG5.net] 【問題】 アルバートとバーナードは、シェリルと友達になったばかりです。 シェリルの誕生日を2人は聞きましたが、彼女は10個の日にちを候補としてあげました。 ・5月15日、5月16日、5月19日 ・6月17日、6月18日 ・7月14日、7月16日 ・8月14日、8月15日、8月17日 それからシェリルは、アルバートに「月」だけを、バーナードに「日付」だけをそれぞれ教えました。 アルバート「僕はシェリルの誕生日を知らないけど、バーナードも知らないよ」 バーナード「僕はシェリルの誕生日を知らなかったけど、今は知ってるよ」 アルバート「それなら僕もいつだか知っているよ」 シェリルの誕生日はいつでしょうか？ プログラムを書いてプログラムに解かせること。 269 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 20:24:51.42 ID:LavjhbKR.net] Console.WriteLine("知らんがな"); 270 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 20:43:26.68 ID:GyX0IIiI.net] (begin (display "知らんがな")(newline)) 271 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 21:39:03.81 ID:3br47TQ3.net] print("知らんがな") 272 名前：デフォルトの名無しさん mailto:sage [2017/06/03(土) 21:39:54.96 ID:+ZiDT+Cr.net] 世界で初めて原爆実験が行われた日を わざわざ答えに選んだのは何か意図があってのこと？ 273 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 02:59:00.78 ID:vYNPJugT.net] 2年前のログ見てみたけどそのときはここに持ちこむ奴いなかったんだな Prologおじさんとかが嬉々としてやりそうだけど 274 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 03:31:57.97 ID:JSJPiIxT.net] 7月16日 275 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 11:23:47.25 ID:ICo3ogub.net] >>264 f# ideone.com/cBGHxs 276 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 12:17:11.76 ID:/fL6DBjJ.net] >>264 Perl @md = ([5, 15], [5, 16], [5, 19], [6, 17], [6, 18], [7, 14], [7, 16], [8, 14], [8, 15], [8, 17]); push @{$c{$$_[1]}}, $$_[0] for @md; push @{$d{$$_[0]}}, $$_[1] for grep{1 < @{$c{$$_[1]}}} @md; while (($m, $v) = each %d) { print "$m/$$v[0]\n" if 1== @$v; } 実行結果 $ perl 9_264.pl 6/17 277 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 12:22:24.53 ID:/fL6DBjJ.net] >>272 7月16日が正解なら 解き方間を違えているのかも知れん 278 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 14:27:12.46 ID:ArM8onCc.net] アルバート「僕はシェリルの誕生日を知らないけど、バーナードも知らないよ」 5,6月を排除 バーナード「僕はシェリルの誕生日を知らなかったけど、今は知ってるよ」 14日を排除 アルバート「それなら僕もいつだか知っているよ」 残り候補が一つの月 -> 7月16日 279 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 15:02:32.31 ID:/fL6DBjJ.net] >>272 の解き方で考えたこと アルバート「僕は(「月」だけしか教えてもらっていないので)シェリルの誕生日を知らないけど、 　　　　　　(「日付」だけを教えてもらった)バーナードも知らないよ」 ⇒「日付」だけ聞けば誕生日だと判明する、即ち日の登場回数が一回だけの月日、 　具体的には5月19日、6月18日は対象外とみなし除去 バーナード「僕は「日付」だけを教えてもらっても)シェリルの誕生日を知らなかったけど、 アルバートが「僕はシェリルの誕生日を知らないけど、バーナードも知らないよ」と言うのを聞いて 今は知ってるよ」 ⇒日の登場回数が一回だけの19日、6月18日を除去したあと、 　登場回数が一回だけの日が バーナードの聞いた「日付」に当たり、 　誕生日だと考えられる。 ⇒6/17 この考え方が違ったんだろうな… 280 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 15:42:35.42 ID:ArM8onCc.net] >>275 アルバートは月を知ってるが、バーナードも知らない事を確信できるのは、 18,19日を含まない7,8月のどちらかという事になる -> 5,6月は全削除 それを聞いてバーナードは誕生日がわかるので、7,8月両方に含まれる14日ではなく、 15,16,17日のどれかになる それを聞いてアルバートがわかるので、候補が一つしか残ってない7月16日という事になる 281 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 16:11:15.57 ID:Thsr1gL6.net] 6/17の方ぽいね 282 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 16:23:55.65 ID:8topuOK/.net] 5,6月は全排除でしょ 283 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 16:27:46.47 ID:/fL6DBjJ.net] >>278 そこがｵﾚにはよく理解できていなくてさ。 まぁ言葉にあいまいな面があるかもしれんから解釈に差が出たのかな 284 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 16:46:10.26 ID:3NGxsH/O.net] >>279 解釈の差だけが問題じゃないだろ > ⇒日の登場回数が一回だけの19日、6月18日を除去したあと、 > 　登場回数が一回だけの日が バーナードの聞いた「日付」に当たり、 > 　誕生日だと考えられる。 18日、19日は日の登場回数が一回だけであるということは 他の日は複数回登場するということだからその論理は破綻してる 285 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 16:54:14.37 ID:/fL6DBjJ.net] >>280 それは誤解というか解読不足。 5月19日、6月18日が除去されることによって、 元々複数回登場していた他の日のうち6月17日が単一の日となり 17日という日付さえ知らされれば、誕生日は6月17日と判明できる。 286 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:03:26.79 ID:ArM8onCc.net] >>281 客観的に見て、アルバートがバーナードも知らない事を確信できる為には、 アルバート自身が知っている月には18,19日が含まれていない必要がある 従って、アルバートが知っている月は5,6月ではないという事 287 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:07:47.61 ID:/fL6DBjJ.net] >>282 なるほど考え方は理解できた。 でも5月6月には他の日もあるからバーナードが聞かされた日がそれらで無いとはっきりしていないうちに 月ごと排除して大丈夫？ 288 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:11:33.29 ID:/fL6DBjJ.net] >>281 17日は8月17日もあるから、 6月が17日だけになったからといって、 6月17日が誕生日だとするのは アルバート、バーナードの台詞を根拠に基づく論理に 無理がないか検証不十分だという気が自分でもしてきた 289 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:12:55.48 ID:ArM8onCc.net] >>283 逆に最初の時点でアルバートはバーナードが知らないとは確信できない 例えばアルバートは6月と聞かされた場合、6月18日の可能性もあるので、 それだとバーナードは18日と聞かされているから知ってるかもしれない 290 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:26:33.24 ID:/fL6DBjJ.net] >>285 大体分かった。ありがとう 単一な日をまったく含まない月を教えられたからこそ、 アルバートは最初の台詞 「僕はシェリルの誕生日を知らないけど、バーナードも知らないよ」 になったという考え方だね。 291 名前：デフォルトの名無しさん mailto:sage [2017/06/04(日) 17:30:30.29 ID:ArM8onCc.net] >>286 イエスイエス 292 名前：デフォルトの名無しさん [2017/06/04(日) 22:32:17.70 ID:BGwDpUyE.net] ディスコプログラミングコンテスト 2017 7/8 https://www.disco.co.jp/procon/ の練習問題 https://www.disco.co.jp/procon/#example 解答バレにならないように１語だけ書くけど １問目の TOUSHITSUWOTOTTE だけが、わけわからん 293 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 00:31:08.14 ID:cnQQABDP.net] >>288 Q1といてみたけど 「糖質を摂って」じゃない？ 294 名前：デフォルトの名無しさん [2017/06/05(月) 08:51:14.13 ID:h9zULQkR.net] 糖質を摂って だよねぇ。 謎のメッセージだな。 295 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 09:47:23.18 ID:Na336mAM.net] >>290 いやそう謎でもない。 解の文を全部通しで読むと この前に食べものの話がある。 296 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 10:35:52.00 ID:S7KIxJHR.net] 糖質が頭の働きを良くするという通説と逆に頭を鈍らせるという説があるけど この会社が前者を支持することを明言する意味がある 297 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 13:18:37.12 ID:nmQdV7hA.net] 例題に挑戦して下さりありがとうございます！全問正解した参加者にはディスコ限定どら焼きをプレゼント！ 大会当日に受付でお渡ししします。糖質を摂って優勝目指して頑張って下さい！ 298 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 13:45:37.09 ID:hFu+7Z6c.net] 誰が統失だって？ 299 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 17:48:32.89 ID:2PleAf1D.net] ダメじゃん。全解答を書いちゃって。 でも簡単すぎる問題だしどうでもいいか。 300 名前：デフォルトの名無しさん [2017/06/26(月) 21:09:32.46 ID:92/cX5j1.net] 前にあったやつ。 回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。 コンベアは毎秒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" > ? 301 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 22:59:10.29 ID:GM19K0OY.net] 計算オーダーの条件は？ 無いなら二進木で 302 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 23:01:34.06 ID:GM19K0OY.net] 皿がもうちょっと多いと難しくなるけど、>>296なら力業でも 303 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 23:40:33.73 ID:JhsaOf6q.net] >>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になるの？ 304 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 23:41:06.22 ID:JhsaOf6q.net] >>299 研鑽じゃねぇや手で起算な。 305 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 23:45:40.94 ID:JhsaOf6q.net] >>300 起算でもねえ、手で計算な…orz 306 名前：デフォルトの名無しさん [2017/06/26(月) 23:58:59.38 ID:92/cX5j1.net] 313__　はこれでは? まず一皿ながして 1を食う、2秒時点の状態　 3__3_ 3を食う、5秒時点の状態　 3____ 3を食う、8秒で食べ終わり 307 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 00:02:53.75 ID:5fkiI7k4.net] >>302 そっか、最初の3を食べちゃったら最短時間にならないな >>299は最初の皿からﾀﾞﾎﾞﾊｾﾞみたいに食いつくので必ずしも最短にはならないな きっと腹が減りすぎていたんだろう…orz 308 名前：デフォルトの名無しさん [2017/06/27(火) 00:12:08.45 ID:PK1LDhK1.net] >>296 は、 目の前にあるやつを食べ続けるだけで最短になっちゃうのもあるってことか。 309 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 00:46:54.34 ID:v9AhJc3r.net] >>296 ideone.com/PGKCb4 計算量は2^n*n (n:コンベアの長さ) n=24はほぼ限界 n!をbitDPで計算量落とす。 (空皿処理で昔より手を抜いている) 310 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 08:18:25.38 ID:bJ//gE7J.net] 考えてみたけと計算オーダーを減らすのはむずかしいね 枝刈りは色々と出来るけど 311 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 00:38:04.57 ID:SkQPDtDj.net] >>218　Perl ttp://ideone.com/ylFIEa ソースコード4行目の my $n = 8; # 分割する自然数を設定 の8を書き換えると他の整数についてもヤング図形を出力できます。 312 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 10:38:30.75 ID:+O8L6XqQ.net] 366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE 今回の民法改正、ソフトウェア受託開発の場合、(検収後ではなく)バグ発見後１年瑕疵担保責任があるということで、地獄かよ、と思ったが、 元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。 一部で地獄を見ても。 https://twitter.com/yukihiro_matz/status/869061879389343744 367 :nobodyさん 2017/05/29(月) 16:28:06.55 ID:6v4UcGhE ニュース - 改正民法が成立、「瑕疵担保責任」などシステム開発契約に影響大：ITpro 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など動的言語は確実に廃れる。 保守に強い言語のみ生き残れる。 313 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 10:38:43.66 ID:+O8L6XqQ.net] 瑕疵担保責任（かしたんぽせきにん） 瑕疵担保責任のポイント 民法改正で事実上期限が「無制限」になった バグや設計のミスなどは、瑕疵担保責任 納品物に不具合があれば損害賠償を請求される可能性もある 不具合を指摘されたらすぐに行動をとるべし 軽微なミスでも先延ばししない www.atmarkit.co.jp/ait/articles/1706/26/news014.html itpro.nikkeibp.co.jp/atcl/news/17/052601508/?rt=nocnt 改正法では欠陥に気付いてから1年以内にITベンダーに通知すれば、 通知後5年以内は修正や報酬の減額などを求められるとしている 全ベンダーが泣いた民法改正案を解説しよう その1 www.atmarkit.co.jp/ait/articles/1609/14/news009.html www.atmarkit.co.jp/ait/articles/1609/14/news009_2.html www.atmarkit.co.jp/ait/articles/1609/14/news009_3.html ポイント1：修補や損害賠償、契約解除の期限がなくなる 従来あった「瑕疵担保期間は引き渡しから1年」という考えはなくなる。 条文にある通り、注文者は成果物が契約の目的に適合しないことを発見したら、 その「発見したときから1年以内」ならさまざまな請求ができる。発見が10年後なら、 11年後まで請求可能なのだ。 もっとも、現実のユーザーとベンダーの関係でも、たとえ契約書に「瑕疵担保責任期間は納品から1年と」明記されていても、 「2年目以降は不具合の修正に対応しない」と主張するベンダーはまれだ。多くの場合は、納品から何年たっても、 バグが見つかればユーザーのところに飛んで行き、無償で改修するだろう。 314 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 10:56:55.66 ID:fzKvr8sM.net] 315 名前：コピペマン参上！！まで読んだ [] [ここ壊れてます] 316 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 22:13:35.80 ID:CE32dHls.net] >>305 修正 ideone.com/PGKCb4 経路情報復元(ベストは複数あるかもしれない中から一つ選んで）。 ついでにその経路での途中経過を表示してみた。 インデックス、待機秒数、開始時間、食事秒数、終了時間、 317 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 23:25:36.64 ID:KJ5QOfYg.net] >>218 >>307 Perl ideone.com/GC2JTj 再帰を使わず、リスト処理とloopで書き直したら もう少しコンパクトですっきりしたものになりました… 318 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 18:47:40.02 ID:tnFwdv+3.net] 前に書いたけどコード紛失した。 319 名前：デフォルトの名無しさん [2017/07/01(土) 21:49:46.76 ID:WoDBh/Wa.net] お題：　パスカルの三角形 320 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 22:05:06.08 ID:1Cx1myAa.net] >>314 良いお題だね 321 名前：デフォルトの名無しさん mailto:sage [2017/07/02(日) 13:43:30.38 ID:bHJ33QxN.net] >>314 Perl5 ideone.com/YCw1OC 桁の多い数値の幅を反映して数値間の空白の数を決めれば 数値の位置がもう少し見やすくなるとおも… 322 名前：デフォルトの名無しさん mailto:sage [2017/07/03(月) 08:12:51.85 ID:EltE6GHS.net] お題：完全なヤング図ソルバー。 ideone.com/hkUkFM 書いてみたけど、不完全なのがやっとだった。 あってるかもわからん。 図の効率がいいほど評価が上がります。 323 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 21:28:12.76 ID:QK6Kginy.net] >>296 >>299 Perl5 ideone.com/0yJ5U9 リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。 3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、 取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、 再帰的に両方に分岐し、木構造で計算しているが、 逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので 来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。 それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、 四つめ以降は時間がかかりいつ終わるか分からない。 そこで、検索された食事秒数の最小値の更新状況を記録し、 同じ最小値が一定回数以上連続して繰り返し検出されるようになったら 最短値に収束したと見なし、探索を打ち切ることによって短時間で 解を出力できるようにした。打ち切り上限は10をハードコードしてあるが 今回のサンプルデータについては4か5で十分そうだ。 なお、23_ のような、2を食べることによって飛び越しを起こすポイントの 一番最後のものは,食べずにスルーして先に2を食べた方が、 次の周で早く食べ終わることは明らかだ。 これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが 難しそうなので、見送った。 324 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 21:31:48.78 ID:QK6Kginy.net] >>318 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら 打ち切るという、簡単な枝刈りを取り入れてあります。 連投ｽﾏｿ 325 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 23:51:29.56 ID:sQGcZTdy.net] >>318 枝刈りで最短を刈り取ってしまったら駄目じゃないか 例えば "3324" -> 15秒 にならないな 326 名前：318 mailto:sage [2017/07/06(木) 00:31:45.46 ID:iCfNzc8Y.net] >>320 誤解� 327 名前：ﾅす。 枝刈りは、ある探索中の枝において始点から既に経過した秒数が それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、 現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って 別の枝の探索に移るというものなので大丈夫です。 "3324" の最短秒数を探索すると 15秒になります。 [] [ここ壊れてます] 328 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 00:52:46.56 ID:ywrsmrRJ.net] >>321 あれ、変だな >>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？ 同様に"3328"、"3364"は最短19秒だけど>>318だと20になった 329 名前：318 mailto:sage [2017/07/06(木) 01:20:52.00 ID:iCfNzc8Y.net] >>322 同じコードをideoneに張りなおして3324を入力して実行してみました。 ideone.com/vXrTp8 ソースを一箇所編集しています。 31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出 の繰り返し回数上限判定地を10から20に増やしています。 3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。 3364も20が10回繰り返した後19が出て続きます。 お手数おかけしますが 一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして 評価してください。 330 名前：318 mailto:sage [2017/07/06(木) 01:35:51.32 ID:iCfNzc8Y.net] >>323 3324と3364の解を見ていて気が付いた点があります。 一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、 3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため 解として表示されています。 これは、3324の15や3364が4桁しかないので、 最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を 解として表示していることによります。 >>318の一定回数繰り返したら収束とみなすという判定方法は、 ニュートン法のような数値計算では有効ですが、 >>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz 331 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 01:53:08.89 ID:bBo7q2K6.net] 3324を拡張した887654329は閾値どれくらい増やせば対応できるんですかね 332 名前：318 mailto:sage [2017/07/06(木) 02:06:40.59 ID:iCfNzc8Y.net] >>325 延々探索を続けないと解に至らないかもしれない入力については 定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。 887654329がそういったカテゴリーに属する入力かというと ﾁｮｯﾄ分からない。 なので適切な閾値はこれだと断言しにくいです。 さーせん 333 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 21:08:21.84 ID:ywrsmrRJ.net] >>326 結局>>321は大嘘だったし、閾値20の>>323にしたところで 例えば"14432"は最短にならないし 閾値が決められないならその解法はやはり駄目だな 334 名前：318 mailto:sage [2017/07/06(木) 22:03:39.91 ID:0agEc1HZ.net] >>327 閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、 計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。 335 名前：318 mailto:sage [2017/07/06(木) 22:08:34.07 ID:0agEc1HZ.net] 見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。 それによって20で打ち切るようなやり方を改善できればいいんだけれども… それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して とけなくなる 336 名前：デフォルトの名無しさん [2017/07/06(木) 23:01:53.78 ID:ywrsmrRJ.net] >>328 閾値20で打ち切るのは枝切りじゃないという主張のようだけど 打ち切るという動作は枝切り以外の何物でもない >>318は”3324”の最短に到達しないから>>321の > "3324" の最短秒数を探索すると 15秒になります。 というのも嘘 337 名前：318 mailto:sage [2017/07/06(木) 23:19:13.87 ID:0agEc1HZ.net] >>330 絡むね。そんな暇あったらコードでも書けばいいのにｗ 閾値20でその入力については解の探査を� 338 名前：~めて 別の枝に移らず次の入力データに移るのはどちらかといえば中断で、 枝かりではないでしょ。 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 にかいてあるでしょうに。 >>318は”3324”の最短に到達しないから>>321の > "3324" の最短秒数を探索すると 15秒になります。 >というのも嘘 これは10回の打ち切りの緩和を書きもらしたんだよ。 何が狙いで、こだわって絡んでくるやらねぇ。 [] [ここ壊れてます] 339 名前：318 mailto:sage [2017/07/06(木) 23:37:37.26 ID:0agEc1HZ.net] 「打ち切る」という言葉を >318 >… >同じ最小値が一定回数以上連続して繰り返し検出されるようになったら >最短値に収束したと見なし、探索を打ち切ることによって短時間で >解を出力できるようにした。打ち切り上限は10をハードコードしてあるが では「その入力に対する求解を中断する」ところで使い、 >319 > >>318 > 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら > 打ち切るという、簡単な枝刈りを取り入れてあります。 では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの ところで使ったのが誤解を招いてしまったのかな… 340 名前：デフォルトの名無しさん mailto:sage [2017/07/07(金) 04:22:27.25 ID:pbX9YCbr.net] 3次の動的計画法ってどんだけメモリ食うんや？ 341 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:20:24.48 ID:hDxZO8qP.net] お題：　自然数Nの平方根を整数部含めて(1000*N)桁求めたとき、出現する0の個数を数える たとえば、N = 4の時ルート4を4000桁（整数部1桁＋小数部3999桁）求めたとき、出現する0の個数は3999個 N = 3 => ? N = 5 => ? N = 7 => ? 342 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:22:50.68 ID:5gcIwgbE.net] ブロックチェインの新手のコイン発掘か？ 343 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 03:59:02.35 ID: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 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 04:25:25.94 ID: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 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 07:13:48.73 ID:hDxZO8qP.net] >>337 N = 5の場合が間違ってると思う 多分、丸めモードの関係か、精度が足りてないと思われる 346 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 09:51:11.17 ID: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 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 11:54:07.74 ID:H5pSyGdF.net] >>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 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 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 12:18:57.24 ID:hDxZO8qP.net] >>339 N = 29とN=41の場合が間違ってる可能性？　それ以外は正しい模様 N = 29 => 2912、N = 41 => 4094 じゃなかろうか >>340 合ってる 350 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 12:48:13.59 ID:1hnJaOYb.net] >>334 Perl5 ideone.com/fAyh2l 351 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 13:10:39.20 ID:1hnJaOYb.net] >>334 Perl5 ideone.com/cMBD8o >>342 をもう少しすっきり書けたので差し替え。 352 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 13:31:31.09 ID:3gkxwDpM.net] >>341 > N = 29 => 2912、N = 41 => 4094 じゃなかろうか それが正しいようです GNU MPだとどうしても最後の桁は四捨五入?されるようで 任意のNに対して正確な答えを出すのは面倒なので修正は断念 353 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 10:26:36.71 ID:aJSGzdPS.net] 結局バイナリーツリーになっちゃったなぁ。むずかし。 354 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 10:55:01.51 ID:xLkjNLhf.net] >>344 考え直したら面倒じゃなかった >>334 C++ codepad.org/k0Sq8Fqo N=10000くらいまでなら現実的な時間で計算出来そうだ 355 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 11:25:12.20 ID:nhQrw0mT.net] N=100000, 1億桁のくらいなら現実的な時間で出来る 丸めは切り捨て？四捨五入？ 356 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 11:33:40.13 ID:nhQrw0mT.net] ルートの計算は速い 整数のルートは特に速い 357 名前：346 mailto:sage [2017/07/09(日) 12:21:20.78 ID:4Kodr3MO.net] >>347 GNU MPだとget_str() とか gmp_sprintf() では四捨五入されるようなので floor() であらかじめ切り捨ててから get_str() した 358 名前：デフォルトの名無しさん [2017/07/09(日) 12:57:37.64 ID:DBjzEn12.net] ルートの問題で初めてきたが、これってゼロの個数に上限があるのか? 簡単に求まるのか? 連続するゼロの個数の最大だろ? 無理数は規則なく無限に続くから、ゼロの個数ももし1000個連続が見つかれば、1001個もいつかでるとおもうんだが。 359 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 13:14:46.15 ID:df6kAKcY.net] 最大って何の話しとるんや 360 名前：デフォルトの名無しさん [2017/07/09(日) 13:28:51.97 ID:DBjzEn12.net] もとめる桁数のほうに上限があったのか、それを見逃してた。 361 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 13:45:03.68 ID:NvRZfELm.net] 連続する個数でもないぞw 362 名前：デフォルトの名無しさん [2017/07/09(日) 13:51:59.10 ID:DBjzEn12.net] どっちも間違えたな、ゼロの総数だったか。 363 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 19:14:37.92 ID:6MYOcrZ9.net] >>349 floorを行った後の結果に誤差は無い という検証は出来てるの？ 何もしてないなら、それはたまたま偶然当たったっていうだけだぞ ていうか、君には聞いてない 出題者の意図を聞いてる

---

---

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

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