[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
426(5): 2019/12/25(水)16:51 ID:eBvDhPt7(1/3) AAS
[お題] 2020と素数
"2020"の省略形は"20"
異なる素数を20個使って、総合計で2020を作る。
1) 何種類できるか(組合せで)。 --> ?
以下 数列は昇順でソート済みでの比較
2) 数列の比較で(辞書順)最小な数列を出力。
--> [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,73,1381]
3) 数列の比較で(辞書順)最大な数列を出力。
--> ?
例) 総合計 26 で要素数 3の場合
省2
428: 426 2019/12/25(水)19:20 ID:eBvDhPt7(2/3) AAS
>>427
1)は二年前の大晦日に、part9で ほぼ既出問題。
とても大きな数字になるから、
全探索しないでね、って意味で1)においたのだが……
432(1): 426 2019/12/25(水)23:33 ID:eBvDhPt7(3/3) AAS
>>429 431 当方とおなじです。
>>426
外部ﾘﾝｸ:ideone.com
数が程々なので、まとめて手抜きの"文字列DP"をやってます。
(pypyで1秒以内で回っているのだから、真面目にやる必要ないでしょう)
449(2): 2019/12/27(金)22:14 ID:novkoLBo(1/2) AAS
>>426 類似問題
素数を20個使って、総合計で2020を作る。
(同じ素数を複数使ってよい）
何種類できるか(組合せで)。 -->?
(同じ数字は区別しない -> ソートして数列が異なるもので1種類)
ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。
※ 2020で20個なら、まだint64_tでおさまる
460: 2019/12/28(土)19:46 ID:mH66EenF(1/4) AAS
>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
外部ﾘﾝｸ:ideone.com
Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。
64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
外部ﾘﾝｸ:ideone.com
480: 2019/12/29(日)22:43 ID:KptD7+e9(1) AAS
>>426
1)数百万規模でありそう。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.083s