[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
150(8): 2019/12/07(土)03:39 ID:GrS1V5od(1/4) AAS
お題
1以上、20以下の整数がランダムに10個与えられます。
与えられた整数の集合から1つ以上の整数を抜き出し、残った整数の集合からまた1つ以上の整数を抜き出します。
この時2つの抜き出した整数の集合のそれぞれの和が同値であり、かつ最小のものを出力して下さい。
例
与えられた整数の集合 : 2 3 4 5 6 7 8 9 10 11
期待される出力 : 5
この場合、与えられた整数の集合から
「2,3」「5」の整数を抜き出しています。
157(2): 2019/12/07(土)09:57 ID:WrheNqRo(1/3) AAS
>>150
取り敢えずRで力任せ。これでも瞬時に終わるので工夫の必要なし。
外部ﾘﾝｸ:ideone.com
160(2): 2019/12/07(土)20:45 ID:HU7sPj+p(1) AAS
>>150
この問題から関連して考えてたんだけど
5を
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
省5
169: 2019/12/08(日)17:53 ID:FOSx0Jk/(4/4) AAS
すまん
不満は>>150に言ったつもり
そんな重要な事を省略すんなって
171: 2019/12/08(日)19:37 ID:KCeBLlvA(1/8) AAS
>>150
外部ﾘﾝｸ:ideone.com
C++。総当たりです。スカイレークのi7で12秒くらいかかります。
久しぶりにまじめに総当たりを書いた気がしました。
172: 2019/12/08(日)19:44 ID:KCeBLlvA(2/8) AAS
>>150
外部ﾘﾝｸ:ideone.com
オマケで、答えが見える版を置いておきます。C++。
178(2): 2019/12/08(日)21:17 ID:FKbRmDMb(1/2) AAS
>>150
これは問題の設定がつまらないな。1〜20の中から10個を選んで元の集合を作るから、
結果に1個か2個の和しかほとんど現れず、集合の最初の方をパッと見ただけで
暗算でも分かってしまう。1〜5000の中から10個を選ぶ設定にすると、
結果がなしだったり、3個の和と4個の和だったり、2個の和と6個の和だったり、
変化に富んで面白くなる。外部ﾘﾝｸ:ideone.com
例えば、リンク先にある
入力: [63, 70, 269, 949, 1337, 2670, 3538, 3764, 4183, 4320]
出力: Σ[3764, 4183] = Σ[63, 70, 269, 1337, 2670, 3538] = 7947
なんてパッと見では思いつかないから、コンピュータに探させる意義がある。
182(1): 2019/12/09(月)00:06 ID:QbXWD96q(1/4) AAS
>>150
N!より速い方法ある？
186: 2019/12/09(月)02:04 ID:vzskLW//(1) AAS
>>150 外部ﾘﾝｸ:ideone.com
By PyPy、 ノーマルpythonでは力業の(N=20)が8秒くらいかな、
力業が 2^N * N
最小値だけなら、N*数列の合計 = N^2 * 数の平均(/2) ででる(みたい？)
(自信ががないDP解)
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.056s