[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
153: 2019/12/07(土)04:23 ID:GrS1V5od(3/4) AAS
>>152
同値は単に同じ(等しい)値という意味で使っています。
解が存在しない場合は「ないよー」と出力して下さい。
与えられる整数は重複する可能性があります。
154(1): 2019/12/07(土)05:16 ID:HQTo5ewj(1/2) AAS
ならば結局こういうことでよいのかね.
もとのスレを見ても出題者本人の主張が不明瞭なうえに二転三転していて気持ち悪いが.
与えられた数列を {a_n} に対して,
{a_n} の異なる項からなる任意の部分列の内それぞれの和が等しくなるものを {b_n}, {c_n} として
Σb_n (= Σc_n) が最小となる {b_n}, {c_n} を求めよ.
そして今回は b, c の項数をそれぞれ 2, 1 に限るものとすると.
155(1): 2019/12/07(土)05:38 ID:GrS1V5od(4/4) AAS
もう少し例を載せるべきでした。
すいません。
例えば
>>152
さんの解が存在しないとしているものですが、
9 10 11 12 13 14 15 16 17 18
を与えられた場合の出力は
21となります。(10,11と9,12)
入力が
1 1 1 1 1 1 1 1 1 1
省2
156: 2019/12/07(土)06:50 ID:HQTo5ewj(2/2) AAS
>>155
なるほど、概ね理解した
157(2): 2019/12/07(土)09:57 ID:WrheNqRo(1/3) AAS
>>150
取り敢えずRで力任せ。これでも瞬時に終わるので工夫の必要なし。
外部ﾘﾝｸ:ideone.com
158: 2019/12/07(土)15:33 ID:WrheNqRo(2/3) AAS
実は>>157は「残った整数の集合から」の条件を忘れていて、元の集合から抜き出すと
勘違いして書いてしまったプログラム。
が、改めて条件を考えてみると、既に抜き出された数と同じものを選んでしまうのは、
「片方の部分集合の要素が2個以上で、もう片方の部分集合の要素が3個以上の場合」(A)
に限られる。例えば、2+9=11と2+3+6=11。この場合、2回選んでしまった2を取り除いた
部分集合は、和9=9と3+6=9が11より小さく、かつ(A)の場合に該当しないので2回選んで
しまった数は存在しない。
だから結局、>>157のプログラムのままで正解が得られることになる。
159: 2019/12/07(土)16:28 ID:tj55yZgB(1) AAS
へなへななお題へなへなな回答
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
161: 2019/12/07(土)22:36 ID:WrheNqRo(3/3) AAS
>>160
Rでお決まりの再帰呼び出し。
外部ﾘﾝｸ:ideone.com
162: 2019/12/07(土)23:22 ID:eT8T+vHJ(1) AAS
分割数でググれば考え方いっぱい出てくるよ
163: 2019/12/08(日)13:36 ID:jvur7pXC(1) AAS
>>160
C++
外部ﾘﾝｸ:ideone.com
164(1): 2019/12/08(日)13:57 ID:FOSx0Jk/(1/4) AAS
>>154
最後の文はどこから出てきたの？
165(1): 2019/12/08(日)13:58 ID:xElyalHo(1/2) AAS
>>164
元のスレ
166: 2019/12/08(日)14:21 ID:FOSx0Jk/(2/4) AAS
しらんがな
167: 2019/12/08(日)14:22 ID:FOSx0Jk/(3/4) AAS
その制限が無い方がアルゴリズムとしておもしろい
制限があるとつまらなすぎる
168: 2019/12/08(日)17:19 ID:xElyalHo(2/2) AAS
知らんがなって
なら聞くなアホ
169: 2019/12/08(日)17:53 ID:FOSx0Jk/(4/4) AAS
すまん
不満は>>150に言ったつもり
そんな重要な事を省略すんなって
170: 2019/12/08(日)19:17 ID:DgjgjjxW(1) AAS
別に項数の制限はつけていませんよ
「項数の制限が無い」という事を省略したのに怒っているのならすいません。
ですが制限があるのなら普通に問題文に加えますし、別に書くほどの事では無いかな〜と
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++。
173: 2019/12/08(日)20:22 ID:KCeBLlvA(3/8) AAS
ちなみにオーダーは大体O(N!)位です。（笑
174: 2019/12/08(日)20:35 ID:KCeBLlvA(4/8) AAS
ギャグですけど、並列化は比較的簡単なのでそれで時間短縮はできます。
底の値をシェアードにすると早く終わります。Nになってると思うんだけど。
175: 2019/12/08(日)20:48 ID:KCeBLlvA(5/8) AAS
一回を関数に切り出して実行した場合、
一回のイテレーションが大体100回のループに収まるはずなのでザクザクおわります。
多分。
176: 2019/12/08(日)20:49 ID:KCeBLlvA(6/8) AAS
一回を関数に切り出して実行した場合、
一回のイテレーションが大体100回のループに収まるはずなのでザクザクおわります。
多分。
177: 2019/12/08(日)20:59 ID:KCeBLlvA(7/8) AAS
ぐあ、重複した・・・。
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
なんてパッと見では思いつかないから、コンピュータに探させる意義がある。
179: 2019/12/08(日)21:27 ID:KCeBLlvA(8/8) AAS
>>178
異様に早いなーと思ったら、言語にコンビネーションあるんかいな。
裏山シー。
180(2): 2019/12/08(日)22:01 ID:h14g0YSH(1) AAS
サンプルだから人間が簡単に検証できるようにしてるんでしょ
普通それぐらいはわかりそうなもんだけど、>>165みたいに項数だと思う奴とか>>178みたいにイチャモンつける奴とか世の中広いわw
181(1): 2019/12/08(日)22:35 ID:FKbRmDMb(2/2) AAS
>>180
そんなことは分かっているよ。だから、お題通りの1〜20の場合も>>157でちゃんと回答した。
その上で、もっと面白い場合の追加を提案してみただけ。
182(1): 2019/12/09(月)00:06 ID:QbXWD96q(1/4) AAS
>>150
N!より速い方法ある？
183: 2019/12/09(月)00:53 ID:rq2SBWAq(1) AAS
>>182
動的計画法？
184: 2019/12/09(月)01:15 ID:2eMu76Ef(1/2) AAS
外部ﾘﾝｸ:ideone.com
全ての和を計算して並べ替えるだけ
多分最も愚直な方法
185: 2019/12/09(月)01:57 ID:2eMu76Ef(2/2) AAS
bit演算で面倒なことやってたけどpairっての使えば良かったのか
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解)
187(1): 2019/12/09(月)02:51 ID:ElWitvQQ(1/2) AAS
>>180
日本語が読め無い馬鹿発見
188: 2019/12/09(月)04:54 ID:wE9bCkNR(1/2) AAS
>>181
わかってたら
> これは問題の設定がつまらないな。
なんていう物言いにはならんだろ
>>187
夜中まで必死だな…
何に必死なのかよくわからんけどw
189: 2019/12/09(月)05:00 ID:ElWitvQQ(2/2) AAS
必死なのはお前だろ
お前一人だけ日本語すらまともに読めてない馬鹿だって気づけよ
190: 2019/12/09(月)06:12 ID:wE9bCkNR(2/2) AAS
うわっ、アホが無駄に絡んできたよw
191: 2019/12/09(月)06:42 ID:QCNDYaVq(1) AAS
明け方からどんだけ必死なんだよ
以降、劣等感の塊のID:wE9bCkNRくんが全レスしてくれるってよ！
192(1): 2019/12/09(月)06:46 ID:PLlkWb6P(1) AAS
こいつ少し上の方でレスバしてたアホやろ？
さんざん馬鹿にされて悔しい思いしたから早朝にちょろっと顔出してるんやろ
193: 2019/12/09(月)07:23 ID:RwnUxfkW(1) AAS
単芝ガイジ君、情けなさ過ぎて草
194: 2019/12/09(月)12:30 ID:G+LM1RHL(1) AAS
>>192
自己紹介乙ww
195: 2019/12/09(月)15:19 ID:gONUrOAf(1/2) AAS
外部ﾘﾝｸ:ideone.com
C++面白いな
196: 2019/12/09(月)15:48 ID:gONUrOAf(2/2) AAS
(sum[i].second & sum[i + 1].second) == 0
この比較はいらないのかな
これが重なってるならより小さい重なってない組合せが必ず存在するか
197(9): 2019/12/09(月)21:07 ID:l5WymCFL(1/2) AAS
お題：2つの素数（2つは同じでもよい）の積で表される数は半素数と呼ばれる。
1万以下の半素数をすべて表示せよ。
198: 2019/12/09(月)21:20 ID:QbXWD96q(2/4) AAS
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91};
199: 2019/12/09(月)21:22 ID:QbXWD96q(3/4) AAS
91じゃなかった
200: ◆QZaw55cn4c 2019/12/09(月)21:29 ID:ZryjKmS+(1/2) AAS
>>197
2chｽﾚ:tech
2625個、でしょうか？
201(1): ◆QZaw55cn4c 2019/12/09(月)21:35 ID:ZryjKmS+(2/2) AAS
やりなおします
>>197
2chｽﾚ:tech
2625個
202: 2019/12/09(月)22:42 ID:QbXWD96q(4/4) AAS
ふるいで5000以下の素数を求めて
2重ループで列挙
が速いかな
203(1): 2019/12/09(月)22:48 ID:l5WymCFL(2/2) AAS
>>201
正解。Rでエラトステネスの篩を使って求めるプログラムを一応貼っておく。
外部ﾘﾝｸ:ideone.com
204: 2019/12/10(火)06:55 ID:cIwr+d9F(1) AAS
>>197 J
(smoutput~ 2=#@q:)@>>:i.10000
4
6
9
10
...
9991
9993
9995
省2
205(1): 2019/12/10(火)07:06 ID:qBy9puuu(1/4) AAS
問題の一区分である素数判定、並びに範囲内の素数列挙するコード
外部ﾘﾝｸ:ideone.com
~/bin/is_prime.exe 2 10000
とやれば1万までの素数が列挙され、
~/bin/is_prime.exe 2017
と1つ引数与えればそれだけ判定
引数無いとURLの用にOFする限界付近まで全部
1万までの素数出して、それパイプで処理したら楽かなと思った
206(1): 2019/12/10(火)08:49 ID:92MPgAr5(1) AAS
5000までの素数で十分だって言ってるのに
207(2): 2019/12/10(火)09:32 ID:WOcT9SPT(1) AAS
>>197
お題：このお題の回答を論理式で表すとどうなるでしょうか。
208: 2019/12/10(火)09:53 ID:gKYhlG5V(1) AAS
>>207
それはプログラミングのお題なのか？
209: 2019/12/10(火)13:07 ID:bINIS1ks(1) AAS
また数(ry
210(2): 2019/12/10(火)13:10 ID:FDwwVytW(1) AAS
出題者はいろんな言語の表記方法を知りたいだけか？
数学やアルゴリズム的には全然おもしろくないのばかり
211: 2019/12/10(火)15:09 ID:zIz8I18p(1/2) AAS
>>197
外部ﾘﾝｸ:ideone.com
C++。>>205 の素数判定パクりました。楽すぎ。
と、思ったらこれ、俺の回答間違ってる。
212: 2019/12/10(火)15:15 ID:zIz8I18p(2/2) AAS
>>197
外部ﾘﾝｸ:ideone.com
C++。こうかいな。
213(1): 2019/12/10(火)16:37 ID:hI+yeapE(1) AAS
>>210
お前が面白い問題出せばいいじゃん
たぶん誰も解かないだろうけどwww
214(1): 2019/12/10(火)17:22 ID:Ajx0JUvY(1/2) AAS
過去スレからお題引っ張りたいんだけど、有料会員じゃないからむりぽ
215: 2019/12/10(火)17:45 ID:qBy9puuu(2/4) AAS
2chscとかいうのが無料サルベージに向いていると聞いたことがある
216(1): 2019/12/10(火)17:47 ID:ClyY78bX(1/2) AAS
>>214
普通のブラウザで見ても出ないんだっけ？
217(2): 2019/12/10(火)18:57 ID:W3sLZ8lM(1/3) AAS
>>213
問題を出して人に解かせるのはあまり好きじゃない
解く方が好き
218: 2019/12/10(火)19:01 ID:W3sLZ8lM(2/3) AAS
過去の良問があればおしえろください
219(1): 2019/12/10(火)19:30 ID:Ajx0JUvY(2/2) AAS
>>216
見れた( ﾟДﾟ)
220: 2019/12/10(火)20:07 ID:ClyY78bX(2/2) AAS
>>219
そうか。普通のブラウザだとエロ広告が激しく付くからそれで過去スレ見せる料金なんとかしてるのかもね。
>>217
そんなあなたにとっておきのお題をひとつ。
お題: 面白いお題を作れ。
221: 2019/12/10(火)20:25 ID:6QYDHDQi(1) AAS
じゃあ四角形を全部違う大きさの円で埋める
222: 2019/12/10(火)21:05 ID:0RQ6ozIG(1) AAS
>>207
答えは高々有限個の整数でしかないんだから論理式にはならない
223: 2019/12/10(火)22:54 ID:ZImsJVBi(1/2) AAS
>>210
まあ、そんな所だね。このスレは競技プログラミングじゃないから、アルゴリズムや
パフォーマンスの追求よりは、各自が使う言語で楽な書き方ができるのを披露する方が多い。
>>203も可変長ベクトルへの再代入の繰り返しという非効率なことをやっているが、
自前のforループ不要で簡潔に書けるし、篩い落とす操作を忠実に表してもいる。
昔と違ってこれでも実用な速度で動くので、色々な書き方ができるようになった。
C#, Julia, PowerShellでも類似の書き方ができる（>>206の通り素数は5000までにした）。
C# 外部ﾘﾝｸ:ideone.com
Julia 外部ﾘﾝｸ:ideone.com
PowerShell 外部ﾘﾝｸ:ideone.com
省12
224(3): 2019/12/10(火)22:54 ID:ZImsJVBi(2/2) AAS
>>217
じゃあ、これ解いてみる?
整数x, y, z, kに関する方程式x^3 + y^3 + z^3 = kの解を、k = 1から100までの場合について求めよ。
外部ﾘﾝｸ[html]:engineer.fabcross.jp
225: 2019/12/10(火)23:25 ID:qBy9puuu(3/4) AAS
k = 64, z = 4の時
任意の整数 を+-反転した組が x,yの解であり、その個数は無限
226: 2019/12/10(火)23:27 ID:W3sLZ8lM(3/3) AAS
なぜ
k=1, z=1
じゃない？
227: 2019/12/10(火)23:47 ID:qBy9puuu(4/4) AAS
あとから追加されそうな条件の
仮に全部0以上の整数とした時に
5*5*5>125,100>4*4*4のメモ代り
228: 2019/12/10(火)23:59 ID:RjwvfByt(1) AAS
k=1から100のどれかに対してじゃなくて、
k=1から100のそれぞれすべてに対して求めるんじゃろ…
229: 2019/12/11(水)00:11 ID:10jfhd7e(1/7) AAS
外部ﾘﾝｸ:ideone.com
10000000以下で0.04秒
C++は速い！
230: 2019/12/11(水)00:13 ID:10jfhd7e(2/7) AAS
C#の10000以下より速い！
231: 2019/12/11(水)00:30 ID:10jfhd7e(3/7) AAS
>>224
k=1の時からいきなり難しいなあ
232: 2019/12/11(水)00:40 ID:10jfhd7e(4/7) AAS
>>224
ん？
解を全て求めるのではなく
各kに対して1個解を求めればいいの？
233(5): 2019/12/11(水)09:11 ID:aadkbL3F(1) AAS
>>197 seq, factor, awk
seq 10000 | factor | awk 'NF == 3'
234(1): 2019/12/11(水)09:24 ID:ztpKOEip(1) AAS
>>233
awkのとここれどういう意味？わたし女騎士だけど教えて！
235: 2019/12/11(水)10:31 ID:dG8VWZ74(1/2) AAS
>>234
女騎士？
まあいいや。NFが3になる行だけ出力するんだよ。NFはフィールド数ね。
区切り文字がデフォルトのままだと空白文字で区切った時の個数。例えば行に a b c って入ってたら 3 になる。
236: 2019/12/11(水)12:05 ID:dG8VWZ74(2/2) AAS
>>197
Kotlin
外部ﾘﾝｸ:paiza.io
237: 2019/12/11(水)13:38 ID:ivhCTlPt(1/3) AAS
>>233
素因数分解しちゃえばいいのか
サイコー
238: 2019/12/11(水)13:42 ID:QbvBtpFM(1/3) AAS
>>233
やってみたら
--- Data stack:
って出力が10000行並ぶだけなんだけど…
なんかオプションいる？
239: 2019/12/11(水)14:03 ID:jagg9gKF(1/2) AAS
普通にできたけど
何のシェル使ってるの？
240: 2019/12/11(水)14:35 ID:QbvBtpFM(2/3) AAS
bash。macで。
241: 2019/12/11(水)14:38 ID:jagg9gKF(2/2) AAS
俺もbashもだけど
seq 100くらいなら動くの？
242: 2019/12/11(水)15:36 ID:QbvBtpFM(3/3) AAS
$ seq 3 | factor で止めてawk飛ばすと以下の出力です。
Factor 0.98 x86.64 (1886, heads/master-211d69561a, Jul 2 2018 17:46:19)
[Clang (GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.29))] on macosx
IN: scratchpad
--- Data stack:
1
IN: scratchpad
--- Data stack:
1
2
省6
243(1): 2019/12/11(水)16:49 ID:1E1+DBtw(1) AAS
>>233
約数が3個な数を列挙ってこと？
4の約数は1,2,4の3個だけど
6の約数は1,2,3,6の4個だよ
244: 2019/12/11(水)17:02 ID:hUZCfnLs(1) AAS
factorみりゃわかんだろ……
素因数の数だっつーの
245: 2019/12/11(水)18:01 ID:10jfhd7e(5/7) AAS
素因数の数が3？
246: 2019/12/11(水)18:12 ID:ivhCTlPt(2/3) AAS
こんな具合だろ
seq 100 | ~/bin/factorization.pl| awk -F, "NF==2" | ~/bin/align.pl "=" 4 2,2
6 2,3
9 3,3
10 2,5
14 2,7
......
9995 5,1999
9997 13,769
9998 2,4999
247(1): 2019/12/11(水)19:33 ID:ReYSFEXH(1) AAS
>>224
とりあえず7個を除いて出来た
ここからが長いのかな？
248: ◆QZaw55cn4c 2019/12/11(水)19:46 ID:6E3wj7zP(1/2) AAS
>>243
そうそう、それに
8 の約数は 1, 2, 4, 8 の 4 個だけれども、これは >>197 のいう半素数ではないんですよね
>>233 は間違っていますね
249: 2019/12/11(水)20:44 ID:WjX/lCwK(1) AAS
QZがそういうなら合ってるんじゃないの？
250: 2019/12/11(水)20:51 ID:7CYZ1E2N(1/3) AAS
反面教師？
251(2): 2019/12/11(水)20:54 ID:7CYZ1E2N(2/3) AAS
お題
1兆以下の半素数の個数を求めよ
これだとスクリプト系は無理かな？
252(2): 2019/12/11(水)21:07 ID:ivhCTlPt(3/3) AAS
素数判定で書いた
long long int のC言語でも100億ぐらいを上限でサポートしてる
100億以上の判定は遅くてより優れた判定アルゴリズムが必要だからだ
推定:C系、優れた判定、現代スペックのPCが必要
上下前次1-新書関写板覧索設栞歴
あと 750 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.054s