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

プログラミングのお題 ..

360:デフォルトの名無しさん
19/12/18 00:09:07.64 i+6d3gEf.net
>>346 C
int s(int n){ return (1000/n)*(1000/n+1)/2*n; }
int main(){ return s(3)+s(5)-s(15); }

361:デフォルトの名無しさん
19/12/18 00:12:20.91 i+6d3gEf.net
int main(){ return 234168; }
で良い気がしてきた

362:デフォルトの名無しさん
19/12/18 00:13:22.10 LTf

363:Q+mrC.net

364:デフォルトの名無しさん
19/12/18 00:28:03.60 i+6d3gEf.net
どうせコンパイルしたら >>355になる

365:デフォルトの名無しさん
19/12/18 01:55:09 JeMlTDQr.net
>>351 Common Lisp
URLﾘﾝｸ(ideone.com)

366:デフォルトの名無しさん
19/12/18 06:09:15.93 6RKB+CQ3.net
>>351 Ruby
p 'acgtaattgaaagggtctt'.scan(/((.)\2*)/).group_by{|s, _| s.size}.max&.last&.map{|s, c| [c, s.size]}
# => [["a", 3], ["g", 3]]

367:デフォルトの名無しさん
19/12/18 10:45:51.93 AmwvkO78.net
acgtが出てくんだからながさ１億の文字列なんじゃね

368:蟻人間
19/12/18 11:33:42.87 Zo1XP656.net
>>350
__getmainargs

369:デフォルトの名無しさん
19/12/18 12:47:12.26 Xcao9p4E.net
acgtが出てくんだからDNA配列だろな。
　a=adenine, c=cytosine, g=guanine, t=thymine
ながさ30億の塩基対なんぢゃね？（ヒトの場合）

370:デフォルトの名無しさん
19/12/18 13:00:45.28 Xcao9p4E.net
>>331
・n=7 のとき
　条件(1,2) または条件(2,2) とする。
　1234567, -, -, -
　　(>328)
　67, -, -, 12345
　7, 6, -, 12345
　-, 6, 7, 12345
　6, -, 7, 12345
　　(>327)
　12346, -, 7, 5
　12346, 5, 7, -
　12346, 5, -, 7
　12346, -, 5, 7
　　　(>327)
　6, -, 5, 12347
　6, 5, -, 12347
　-, 5, 6, 12347
　5, -, 6, 12347
　　　(>327)
　12345, -, 6, 7
　12345, -, -, 67
　　　(>328)
　-, -, -, 1234567
にて可能。

371:デフォルトの名無しさん
19/12/18 13:04:26.11 iEIErwam.net
(1,2)で8
(2,2)だと12
までは出来たぞ

372:デフォルトの名無しさん
19/12/18 13:06:11.00 iEIErwam.net
(1,3)で11
紙と鉛筆で考えただけなんで
もっと出来るかも

373:デフォルトの名無しさん
19/12/18 13:29:12.80 iEIErwam.net
(n,1)=3n+2
(2,2)以上だと
(m, n)=4(n+m-1)
まではいける

374:デフォルトの名無しさん
19/12/18 14:02:18.59 1FTJXM5f.net
>>317
Kotlin
URLﾘﾝｸ(paiza.io)
実は数字かどうかではなく '0' かどうかで見てるだけ。

375:デフォルトの名無しさん
19/12/18 14:58:11.70 Xcao9p4E.net
>>331
・n=8のとき
　条件(1,2) または条件(2,2) とする。
　12345678, -, -, -　　　　(>328)
　678, -, -, 12345
　78, -, 6, 12345　　　　　　(>328)
　1234578, -, 6, -
　1234578, -, -, 6　　　　　(>328)
　78, -, -, 123456
　8, 7, -, 123456
　-, 7, 8, 123456
　7, -, 8, 123456　　　　　　(>328)
　123457, -, 8, 6
　123457, 6, 8, -
　123457, 6, -, 8
　123457, -, 6, 8　　　　　　(>328)
　7, -, 6, 123458
　7, 6, -, 123458
　-, 6, 7, 123458
　6, -, 7, 123458　　　　　　(>328)
　123456, -, 7, 8
　123456, -, -, 78　　　　　(>328)
　6, -, -, 1234578
　-, -, 6, 1234578　　　　　(>328)
　12345, -, 6, 78
　12345, -, -, 678　　　　　(>328)
　-, -, -, 12345678
にて可能。
・n=9 は条件(1,2) では無理か････

376:デフォルトの名無しさん
19/12/18 16:04:48.01 iEIErwam.net
(0,0)=1
(n,m)=(n+2)(m+2)-4
ですかね

377:デフォルトの名無しさん
19/12/18 21:05:50.74 WdZQqUwr.net
>>359
Rでrle関数を使って楽々
MaxRepChar <- function(s) {
　if (!nchar(s)) return(invisible())
　r <- rle(unlist(strsplit(s, "")))
　b <- r$lengths == max(r$lengths)
　cat(sprintf('("%s", %d)', r$values[b], r$lengths[b]), sep = ", "); cat("\n")
}
MaxRepChar("acgtaattgaaagggtctt")
MaxRepChar("ｽﾚﾘﾝｸ(tech板)")
-- 実行結果 --
("a", 3), ("g", 3)
("t", 2), ("/", 2), ("8", 2), ("2", 2)

378:デフォルトの名無しさん
19/12/18 21:06:21.05 H5ShkPcr.net
f(m, n) : 動かせる最大枚数
m≧n≧1の時
x=f(m-1,n)
A:1,2,3,...,x
B:x+1,...,x+n
C:x+n+1
D:x+n+2
ABCD, -, -, -
CD, -, -, AB
C, D, -, AB
AC, D, -, B
AC, -, -, BD
C, -, - ABD
-, C, -, ABD
A, C, -, BD
A, -, -, BCD
-, -, - ABCD
よって
f(m, n)≧f(m-1,n)+n+2
f(1,0)=2
f(m,n)=f(n,m)
と数学的帰納法により
f(m,n)≧(m+2)(n+2)-4

379:
19/12/18 22:57:24.30 tbeJyQYA.net
>>371
理論はどうでもいいから動く

380:コードを出して欲しいです、このスレ的には

381:デフォルトの名無しさん
19/12/18 23:01:39.59 i+6d3gEf.net
ここまで出来ればあとは簡単
他の人に任せた

382:デフォルトの名無しさん
19/12/19 00:58:04.71 1AoIgbUn.net
>>317 文言 wenyan-lang
URLﾘﾝｸ(wenyan-lang.lingdong.works)
吾有一術。名之曰「零右寄」。欲行是術。必先得一數。曰「数」。乃行是術曰。
吾有三數。曰零。曰零。曰一。名之曰「甲」曰「乙」曰「丙」。
恆為是。若「数」等於零者乃止也。除「数」以十。所餘幾何。昔之「甲」者。今其是矣。
若「甲」等於零者。乘「乙」以十。昔之「乙」者。今其是矣。若非。乘「甲」以「丙」。
加其以「乙」。昔之「乙」者。今其是矣。也。除「数」以十。昔之「数」者。今其是矣。
除其以一。所餘幾何。減「数」以其。昔之「数」者。今其是矣。
乘「丙」以十。昔之「丙」者。今其是矣。云云。乃得「乙」。是謂「零右寄」之術也。
吾有一列。名之曰「丁」。充「丁」以二千零一十九。以一十萬二千零三十。以一百二十三。
凡「丁」中之「戊」。施「零右寄」於「戊」。名之曰「己」吾有三數。曰「戊」。曰「「、」」。曰「己」。書之。云云。
OUTPUT ---------------------
二千零一十九、二千一百九十
一十萬二千零三十、一十二萬三千
一百二十三、一百二十三

なんかGIGAZINEで紹介されていたので

383:デフォルトの名無しさん
19/12/19 03:38:08.86 i+MhtJYW.net
>>363
・n=7 のとき
　条件(1,2) または条件(2,2)
　{1234}=A と略記する。
　A567, -, -, -　　　(>327)
　567, -, -, A
　67, 5, -, A
　7, 5, 6, A
　57, -, 6, A　　　　(>327)
　A57, -, 6, -
　A57, -, -, 6　　　(>327)
　57, -, -, A6
　7, 5, -, A6
　-, 5, 7, A6
　5, -, 7, A6　　　　(>327)
　A5, -, 7, 6
　A5, 6, 7, -
　A5, 6, -, 7
　A5, -, -, 67　　　　(>327)
　5, -, -, A67
　-, -, 5, A67　　　　(>327)
　A, -, 5, 67
　A, -, -, 567　　　　(>327)
　-, -, -, A567
にて可能。

384:デフォルトの名無しさん
19/12/19 03:43:24.67 i+MhtJYW.net
>>368
・n=8のとき
　条件(1,2) または条件(2,2)
　{12345} = A と略記する。
　A678, -, -, -　　　　　　(>328)
　678, -, -, A
　78, 6, -, A
　8, 6, 7, A
　68, -, 7, A　　　　　　　(>328)
　A68, -, 7, -
　A68, -, -, 7　　　　　　　(>328)
　68, -, -, A7
　8, 6, -, A7
　-, 6, 8, A7
　6, -, 8, A7　　　　　　　(>328)
　A6, -, 8, 7
　A6, 7, 8, -
　A6, 7, -, 8
　A6, -, -, 78　　　　　　　(>328)
　6, -, -, A78
　-, -, 6, A78　　　　 (>328)
　A, -, 6, 78
　A, -, -, 678　　　　　　　(>328)
　-, -, -, A678
にて可能。

385:デフォルトの名無しさん
19/12/19 04:34:36.23 i+MhtJYW.net
・n=12 のとき
　条件(2,2)
{12345678} = A, {9,10} = B, 11=C, 12=D と略記する。
　ABCD, -, -, -　　　(>376)
　BCD, -, -, A
　CD, -, B, A
　D, C, B, A
　BD, C, -, A　　　　(>376)
　ABD, C, -, -
　ABD, -, -, C　　　(>376)
　BD, -, -, AC
　D, -, B, AC
　-, D, B, AC
　B, D, -, AC　　　　(>376)
　AB, D, -, C
　AB, D, C, -
　AB, -, C, D
　AB, -, -, CD　　　(>376)
　B, -, -, ACD
　O, 9, -, ACD　　　(>376)
　AO, 9, -, CD
　AO, -, -, 9CD　　　(>376)
　O, -, -, A9CD
　-, O, -, A9CD　　　(>376)
　A, O, -, 9CD
　A, O, 9, CD
　A, -, 9, OCD
　A, -,-, BCD　　　　(>376)
　-, -, -, ABCD
にて可能。

386:デフォルトの名無しさん
19/12/19 07:01:53.01 NLbJ7Izu.net
>>317 J
f =: 3 : 0
a =. ": y
b =. a -. '0'
". b , a -. b
)

387:346
19/12/19 11:40:09.74 dMnFAlGo.net
>>346
Ruby で、234,168
# 蓄積変数の初期値は、0
puts ( 1..1_000 ).inject( 0 ) { |sum, num|
num % 3 == 0 || num % 5 == 0 ? sum + num : sum
}

388:デフォルトの名無しさん
19/12/19 13:03:26.44 LRZ6v8WB.net
>>375-377
>>371で理論は出来たんだから
次は
プログラムにするか
等号の証明をするか
最短手順を調べるか
本数を増やすか
ではないでしょうか？
私は >>371で満足
出題者ありがとう

389:デフォルトの名無しさん
19/12/19 14:49:39.96 i+MhtJYW.net
>>380
う～む、等号の証明でござる。

390:デフォルトの名無しさん
19/12/19 16:03:07.29 POC72xQm.net
どれが？

391:デフォルトの名無しさん
19/12/19 16:34:48.53 dMnFAlGo.net
お題
MY FAVORITE SONGS を、Snake, Camel, Pascal にして！
my_favorite_songs, myFavoriteSongs, MyFavoriteSongs

392:デフォルトの名無しさん
19/12/19 17:08:15.12 0uPukb6z.net
>>346
Kotlin script
ただ馬鹿正直に抜き出して足すだけ。
println((1..1000).filter { it % 3 == 0 || it % 5 == 0 }.sum())

393:デフォルトの名無しさん
19/12/19 17:42:54.73 0uPukb6z.net
>>383
Kotlin
URLﾘﾝｸ(paiza.io)

394:デフォルトの名無しさん
19/12/19 19:39:18.71 xlnTqgd4.net
>>383 Ruby
str = 'MY FAVORITE SONGS'
puts str.tr('A-Z ', 'a-z_') # => my_favorite_songs
puts str.gsub(/ (\w)/){$1.downcase}.swapcase # => myFavoriteSongs
puts str.split.map(&:capitalize).join # => MyFavoriteSongs

395:デフォルトの名無しさん
19/12/19 20:42:11.68 M6N2QgoX.net
>>351 >>362 Common Lisp
URLﾘﾝｸ(ideone.com)
30億バイトでの実行結果:
% uname -p
Intel(R) Core(TM) i7-4765T CPU @ 2.00GHz
% /usr/bin/time -p sbcl --script odai-pt16-351-362-lisp-3-hash-table.lisp </tmp/random-acgt-3-billion.txt
((#\T . 17))
real 178.75
user 177.55
sys 1.17
%
*standard-input* ではなく (open "/dev/stdin" ...) を使っているのは *standard-input* が遅いから
ざっと六倍もの時間がかかった

396:デフォルトの名無しさん
19/12/19 21:46:59.61 XnN+NvoA.net
>>383
R
URLﾘﾝｸ(ideone.com)

397:デフォルトの名無しさん
19/12/19 22:59:23.08 L7o4TfDh.net
>>371
f(m,n)≧2mn+m+n+1
が示せました
(2,2)の条件で13枚移動できます

398:383
19/12/20 14:24:42 A+TGdcd9.net
>>383
Ruby で、

ary = "MY FAVORITE SONGS".split.map( &:downcase ) # すべて小文字へ

puts ary.join( "_" ) #=> my_favorite_songs
puts ary.map( &:capitalize ).join #=> MyFavoriteSongs

puts ary.map.with_index { |word, idx|
if idx == 0
word # 最初だけ、そのまま
else
word.capitalize
end
}.join #=> myFavoriteSongs

399:デフォルトの名無しさん
19/12/20 17:55:37.64 KHh/7LOP.net
>>346 julia
println(sum(Set([3:3:1000; 5:5:1000])))

400:デフォルトの名無しさん
19/12/20 19:38:12.53 KibkA5Ab.net
お題（>>346の改変版）
1から100万までの整数のうち、2か3か5か7か11か13か17か19の倍数の合計を
求める処理を3000回繰り返してから、結果を表示せよ。ただし、ideoneの
実行制限時間（5秒）以内に完了すること。

401:デフォルトの名無しさん
19/12/20 20:40:12.54 l1czkVGZ.net
>>392 C++
URLﾘﾝｸ(ideone.com)

402:デフォルトの名無しさん
19/12/20 21:09:48.70 ZH5ZbPnE.net
今アップしようと思ったら
 >>393とそっくりだった

403:デフォルトの名無しさん
19/12/20 21:22:01.32 ZH5ZbPnE.net
素数の数をカウントする代わりに
マイナスを付けて素数を掛け算してるのが違うくらい

404:デフォルトの名無しさん
19/12/20 21:28:45.69 ZH5ZbPnE.net
お題
3000回じゃなくてもっとマシな出し方なかったのかね？
最適化で1回の結果を使い回されて何回やっても時間同じになっちゃってたよ
3000回数分合計して、最後に3000で割ってたんだけど
最適化が頭良すぎた

405:デフォルトの名無しさん
19/12/20 21:49:16.14 qHTdS2+z.net
やったー僕が考えた効率良いプログラムだと5秒以内で3000回も計算できたぞ！
そうだこれを

406:お題にしてやろう！

407:デフォルトの名無しさん
19/12/20 22:16:29.10 ZH5ZbPnE.net
C/C++だと
ほんのちょっと数学の知識を使えば
コード上の工夫をまったくしなくても0.01秒
コード上の工夫でまだまだ速くなる
スクリプト系言語でも100倍はかからない気がする
なぜ5秒？
なぜ1000000？
なぜ3000回？
謎だ

408:デフォルトの名無しさん
19/12/20 22:30:48.36 fz/tpFJr.net
些末な最適化など
数学的知識に基づくオーダーの低減に比べたらむなしい

409:デフォルトの名無しさん
19/12/20 22:30:49.77 ZH5ZbPnE.net
数学的知識を使わないで
単純に足していくアルゴリズムを
コードの工夫で5秒切るって問題？

410:デフォルトの名無しさん
19/12/20 22:38:11.88 PCNOOvYP.net
>>399
>>393は素数の数に対してオーダーは2^n nだけど、
コード上の工夫で2^nになる
さらに、
乗算の数十倍時間がかかる、変数による除算も
コード上の工夫で無くせる
些細な差では無いと思う

411:デフォルトの名無しさん
19/12/20 22:38:43.75 ZH5ZbPnE.net
>>399
>>393は素数の数に対してオーダーは2^n nだけど、
コード上の工夫で2^nになる
さらに、
乗算の数十倍時間がかかる、変数による除算も
コード上の工夫で無くせる
些細な差では無いと思う

412:デフォルトの名無しさん
19/12/20 22:39:52.16 ZH5ZbPnE.net
ダブった

413:デフォルトの名無しさん
19/12/20 22:50:38.46 qHTdS2+z.net
数学も計算機学もどっちも大事

414:デフォルトの名無しさん
19/12/20 23:00:03.89 KibkA5Ab.net
>>393
正解。ちなみにRで短く書いたプログラム: URLﾘﾝｸ(ideone.com)
結局、奇数個の積の倍数の個数の和から偶数個のそれを引くというやり方は同じだな。
>>397
そう。上のプログラムが5秒以内に余裕を持って終わるように繰り返し回数を設定したw
効率というより短いのが好きで書いた。
>>398
>>393をRにそのまま移植すると5秒以内に終わらず、1000回に減らしても
（URLﾘﾝｸ(ideone.com)）4.56秒かかって、上のプログラムの2.43秒より
遅いよ。Rでは自前のループを書くよりも、関数や演算子を使って短く書いた方が
速くなることが多い。

415:デフォルトの名無しさん
19/12/20 23:06:22.58 ZH5ZbPnE.net
>>405
Rだと3桁倍も時間がかかるのか
衝撃

416:デフォルトの名無しさん
19/12/20 23:10:59.45 KibkA5Ab.net
1000までではなく与えられた自然数までということ以外は >>346と同じ問題が
オライリーの「Modern C++チャレンジ」に載っているが、示されている解答は
if (i % 3 == 0 || i % 5 == 0) sum += i; という単純に足していく方式だな。
本の副題は「C++17プログラミング力を鍛える100問」だが、何が鍛えられられるのか
よく分からない。

417:デフォルトの名無しさん
19/12/20 23:11:25.23 ZH5ZbPnE.net
C/C++で1秒かかる問題は
C/C++限定になっちゃう感じだね

418:デフォルトの名無しさん
19/12/20 23:14:31.11 ZH5ZbPnE.net
>>407
算数やアルゴリズムじゃなくて
言語の勉強ってことでしょ

419:デフォルトの名無しさん
19/12/21 05:43:11.08 vVh8rrgH.net
連投アスペ君うざいよ
学歴詐称までしてたみたいだけど

420:デフォルトの名無しさん
19/12/21 17:30:00.35 BSqycIZI.net
お題
ビットコインの採掘問題です
000 ～ 300 までの3桁の整数の文字列を、MD5 で暗号化した時に、
冒頭部分から、5 が最も多く続く、整数は何？
答え、239 : 555d6～

421:デフォルトの名無しさん
19/12/21 21:23:49.40 WOeaPgYE.net
>>411
Java
URLﾘﾝｸ(paiza.io)

422:デフォルトの名無しさん
19/12/21 22:58:23.57 hbXQRpYW.net
>>411　PowerShell
$MD5 = new-object "System.Security.Cryptography.MD5CryptoServiceProvider"
$a = 0..3

423:00 $hash = $a |% {-join ($MD5.ComputeHash([char[]]("{0:000}" -f $_)) |% {"{0:x2}" -f $_})} $n = $hash |% {[RegEx]::Match($_, "^5+").length} $max = ($n | measure -max).Maximum $a |? {$n[$_] -eq $max} |% {"$_ : " + $hash[$_]} -- 実行結果 -- 239 : 555d6702c950ecb729a966504af0a635

424:デフォルトの名無しさん
19/12/22 03:50:07 lBW/6Z3k.net
>>411
Kotlin
URLﾘﾝｸ(paiza.io)

425:デフォルトの名無しさん
19/12/22 14:00:57.91 sfBU8dhx.net
>>411 Ruby
require 'digest'
p ("000".."300").map{|i|[Digest::MD5.hexdigest(i).index(/[^5]/),i]}.max[1]

426:411
19/12/22 19:20:37.12 u+b66RrE.net
>>411 Ruby
require 'digest'
# :count は、先頭から続く、5の数
Result = Struct.new( :num, :md5, :count )
res = ( "000".."300" ).each_with_object( Result.new( nil, nil, -1 ) ) do |num, res|
md5 = Digest::MD5.hexdigest( num ) # ハッシュ化
md5.each_char.with_index do |char, idx| # 1文字ずつ処理する
if char != "5"
if idx > res.count # 大きい時だけ更新する
res.num = num
res.md5 = md5
res.count = idx
end
break
end
end
end
puts "#{ res.num } : #{ res.md5 }"
#=> 239 : 555d6702c950ecb729a966504af0a635

427:デフォルトの名無しさん
19/12/23 15:49:57.54 8tSOZ4fL.net
>>411
Perl5
URLﾘﾝｸ(paiza.io)

428:デフォルトの名無しさん
19/12/24 02:05:20.47 3/kDRwCG.net
>>377
>>389
・n=13 のとき
　条件(2,2)
{12345678} = A, {9,10} = B, 11=C, 12=D, 13=E と略記する。
　ABCDE, -, -, -
　　手順１
　CDE, -, -, AB
　　手順２
　CD, E, -, AB
　ACD, E, -, B
　　手順３
　ACD, -, -, BE
　CD, -, -, ABE
　　手順２
　C, D, -, ABE
　AC, D, -, BE　
　　手順３
　AC, -, -, BDE
　C, -, -, ABDE
　-, C, -, ABDE
　A, C, -, BDE
　　手順３
　A, -, -, BCDE
　-, -, -, ABCDE
にて可能。

429:デフォルトの名無しさん
19/12/24 02:16:33.78 3/kDRwCG.net
　#A = f(2,1) = 8,　　　#B = 2
* 手順１
　ABX, -, -, -
　BX, -, -, A
　OX, 9, -, A
　AOX, 9, -, -
　AOX, -, -, 9
　OX, -, -, A9
　X, O, -, A9
　AX, O, -, 9
　AX, O, 9, -
　AX, -, 9, O
　AX, -, -, B
　X, -, -, AB
*手順２
　CDY, -, -, *
　DY, C, -, *
　Y, C, D, *
　Y, -, CD, *
　-, Y, CD, *
　-, CY, D, *
　D, CY, -, *
　CD, Y, -, *
* 手順３
　*, Y, -, BZ
　*, 9Y, -, OZ
　*, 9Y, O, Z
　*, Y, B, Z
　*, -, B, YZ
　*, 9, O, YZ
　*, 9, -, OYZ
　*, -, -, BYZ

430:デフォルトの名無しさん
19/12/24 06:16:15 cUFUrp77.net
おめでとう
次は(2,2,2)

431:デフォルトの名無しさん
19/12/24 06:33:05.83 cUFUrp77.net
n=13を考えるとき
真ん中2本が空いてる時にはn=12までは動かせる
っていう仮定を使うと
考え方が楽になりますよ
これが出来たら
あとは(2,1)のn=8から1枚ずつ増やしていく帰納法が使えます

432:デフォルトの名無しさん
19/12/24 07:26:03.90 cUFUrp77.net
a≧b≧c≧d≧e≧1
f(a,b,c,d,e)=f(a-1,b,c,d,e)+2n+1
n = max { a, f(b-1,c,d,e) }
+ max { b, f(c-1,d,e) }
+ max { c, f(d-1,e) }
+ e

433:デフォルトの名無しさん
19/12/24 07:43:48.05 cUFUrp77.net
(a,b,c,d,e) の動かしかた
A : 小さい f(a-1,b,c,d,e) 枚
X : 最大の1枚
(n) : A,X以外の任意のn枚
n : >>422で定義
A(2n)X / - / -
(n)X / - / A(n)
(n) / X / A(n)
A(n) / X / (n)
A(n) / - / (n)X
- / - / A(2n)X

434:デフォルトの名無しさん
19/12/24 07:48:24.24 cUFUrp77.net
ミスった
n = min { a, f(b-1,c,d,e) }
+ min { b, f(c-1,d,e) }
+ min { c, f(d-1,e) }
+ e

435:デフォルトの名無しさん
19/12/24 19:47:21.14 cUFUrp77.net
動かせる枚数だけですがコードにしました
URLﾘﾝｸ(ideone.com)

436:デフォルトの名無しさん
2019/12/25

437:(水) 16:51:57.78 ID:eBvDhPt7.net

438:デフォルトの名無しさん
19/12/25 19:05:13.68 LrSoTBV6.net
2) 3) は瞬時だけど
1) は難しい
出題者は出来たんだよね？

439:426
19/12/25 19:20:25.05 eBvDhPt7.net
>>427
1)は二年前の大晦日に、part9でほぼ既出問題。
とても大きな数字になるから、
全探索しないでね、って意味で1)においたのだが……

440:デフォルトの名無しさん
19/12/25 22:46:56.00 LrSoTBV6.net
URLﾘﾝｸ(ideone.com)

441:デフォルトの名無しさん
19/12/25 22:48:16.07 LrSoTBV6.net
合ってる？

442:デフォルトの名無しさん
19/12/25 22:57:35.89 LrSoTBV6.net
辞書順最後は
{ 53, 59, 61, 67, 71, 73, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151 }

443:426
19/12/25 23:33:28.28 eBvDhPt7.net
>>429, 431 当方とおなじです。
>>426
　URLﾘﾝｸ(ideone.com)
数が程々なので、まとめて手抜きの"文字列DP"をやってます。
(pypyで1秒以内で回っているのだから、真面目にやる必要ないでしょう)

444:デフォルトの名無しさん
19/12/26 01:18:40.30 rIhsLdYp.net
がんばって速くしてみたけどあまり速くならなかった
URLﾘﾝｸ(ideone.com)

445:デフォルトの名無しさん
19/12/26 01:28:39.37 rIhsLdYp.net
C++だから速いはず
だけど大差無いって事は
アルゴリズムで負けてる？

446:デフォルトの名無しさん
19/12/26 04:04:05.93 Wc5llTmi.net
>>421
>>418 は >>371 にEを追加したものです。
　ピン0⇔ピン3 間で移動する「4ピン手順」と
　ピン{{0,1,2} または {1,2,3} 間で移動する「3ピン手順」
　を交互に行ないます。
*手順１は4ピン手順で、ABの10個を移動します。
*手順2、手順3 は3ピン手順です。
　　ピン0→ピン{1,2}　あるいはピン{1,2}→ピン3　間でxを移動するときは
　　xより小さい円盤を1本のピンに集めることが必要で、これがネックですね。
　　最初に12個移動するのはどうかと思うけど････

447:デフォルトの名無しさん
19/12/26 07:13:27.63 rIhsLdYp.net
>>435
帰納法を使えば
具体的な手順は >>423の手順だけで
≧を示せる
と言ってるだけですよ
帰納法の仮定として
・>>422の式より円盤の枚数が少ない時は動かせる
・>>422の条件より置ける置ける枚数が少ない時は >>422が成り立つ
を使う

448:デフォルトの名無しさん
19/12/26 07:22:33.88 rIhsLdYp.net
>>371から >>423に進化して
本数も枚数も一般化出来た
( >>425 )
帰納法の仮定を使って
 >>423の(n)は任意のn枚に出来る
これによって手順の記述が対称になり
非常に簡略化出来てます
最短手順を求めるのはまた別の話で
これは帰納的には求められないと思っています

449:デフォルトの名無しさん
19/12/26 07:28:47.21 rIhsLdYp.net
ちなみに >>371の式は最大枚数ではなくて
Cをn枚にすることで最大になります
動かせる最大枚数はわかったので
残る

450:課題は｢最短手順を求める｣のみ

451:蟻人間
19/12/26 15:19:10.12 Npbug+/w.net
お題: 半角英数からなるユーザーIDとパスワードで認証できるアカウントのシステムを以下の要件で作る。
1.新規登録を選んでユーザーIDとパスワードとメールアドレスを入力するとアカウント登録ができる。
2. 複数アカウント対応。ユーザーIDの重複はダメ。
3. アカウント一覧を選ぶとアカウントの一覧とログイン状態が見える。
4. ログインを選んでユーザーIDとパスワードの入力が一致すればログインできる。
5. ログアウトを選べばログアウトできる。
6. パスワードを忘れたとき、アカウントの回復を選んでメルアド入力すると、メールが来てパスワードがリセットされる。

452:デフォルトの名無しさん
19/12/26 19:06:46.63 ArA1I+l7.net
>>432
　URLﾘﾝｸ(ideone.com)
　
　よくある経路復元方式に変更。
　(大量な文字列のコピーが減った)

453:デフォルトの名無しさん
19/12/26 19:20:20.20 nVG7mTn1.net
>>429を少し速くした
URLﾘﾝｸ(ideone.com)

454:デフォルトの名無しさん
19/12/26 21:44:10.91 nVG7mTn1.net
URLﾘﾝｸ(ideone.com)
vectorを使いまわしするようにしたら速くなった

455:デフォルトの名無しさん
19/12/27 00:16:14.43 N7T+QvJX.net
URLﾘﾝｸ(ideone.com)
まだ省くことができた

456:蟻人間
19/12/27 18:58:01.81 0l4cUgpw.net
Web系もプログラミングの一種なんだけど、日本のIT教育では軽視されてるみたいなんだ。

457:デフォルトの名無しさん
19/12/27 20:56:28.17 JVKHwIo7.net
<('o')>ﾌｰﾝ

458:
19/12/27 21:03:47.38 9iE1xeZJ.net
>>444
web 系をはじめるには、どういう環境で学べばいいですか？

459:デフォルトの名無しさん
19/12/27 21:12:37.24 IA42SgXa.net
URLﾘﾝｸ(ideone.com)
>>440のアルゴリズムの方が速いね

460:デフォルトの名無しさん
19/12/27 21:14:11.36 IA42SgXa.net
↑が100回
これが1回
URLﾘﾝｸ(ideone.com)

461:デフォルトの名無しさん
19/12/27 22:14:31.51 novkoLBo.net
>>426 類似問題
素数を20個使って、総合計で2020を作る。
(同じ素数を複数使ってよい）
何種類できるか(組合せで)。 -->?
(同じ数字は区別しない -> ソートして数列が異なるもので1種類)
ちなみに、辞書順最小が[ 2(* 18), 5, 1979] 、最大が[ 101(* 20)]になる。
※ 2020で20個なら、まだint64_tでおさまる

462:デフォルトの名無しさん
19/12/27 22:54:15.08 IA42SgXa.net
↑
>>429の+1を消すだけ

463:デフォルトの名無しさん
19/12/27 22:58:27.12 Wx5tgQ31.net
お題: 「Happy New Year!!」と出力するプログラムを2020年元日に投稿せよ

464:デフォルトの名無しさん
19/12/27 23:32:30.61 novkoLBo.net
>>450
やっぱり(既にできていて)、その程度なのだろう。
自分の方も、ユニーク時は更新が伝播しないように
逆順で処理していたのを、伝播するよう正順に戻すだけ。
>>449
　URLﾘﾝｸ(ideone.com)

465:デフォルトの名無しさん
19/12/27 23:43:22.25 IA42SgXa.net
>>452
お題
同じ数は4個まで

466:デフォルトの名無しさん
19/12/28 01:41:03.72 HU/ZZyYG.net
>>447のだと
for (j = N - 1; j >= 0; j--) {
これを
for (j = 0; j < N; j++) {
こう逆にすると重複の計算ができるんだね

467:デフォルトの名無しさん
19/12/28 03:25:23 HeaGj5a1.net
>>423

m≧n≧1 のとき
　ピン2に大円盤が1枚以下のときは、ピン0⇔ピン1間、ピン1⇔ピン3間で
　n枚組の円盤を移動できますね。 (3ピン手順)

　A: 1,2,････,x　のx個組　ただし x=f(m-1,n)
　B: x+1,...,x+n　のn個組
　C: x+n+1,････,x+2n+1 のn個組
　D: x+2n+1
とする。

468:デフォルトの名無しさん
19/12/28 03:28:09 HeaGj5a1.net
　ABCD, -, -, -
　B

469:CD, -, -, A 　　手順２　BC(2..n)D, -, C(1), A 　ABC(2..n)D, -, C(1), - 　ABC(2..n)D, -, -, C(1) 　BC(2..n)D, -, -, AC(1) 　　手順２　BC(3..n)D, -, C(2), AC(1) 　ABC(3..n)D, -, C(2), C(1) 　　手順３　ABC(3..n)D, -, -, C(1..2) 　････　同様にしてC(k)とDを移動する。(k=1..n) 　････　ABD, -, -, C 　BD, -, -, AC 　　手順２　B, -, D, AC 　AB, -, D, C 　　手順３　AB, -, -, CD 　B, -, -, ACD 　B(2..n), -, B(1), ACD 　AB(2..n), -, B(1), CD 　AB(2..n), -, -, B(1)CD 　B(2..n), -, -, AB(1)CD 　B(3..n), -, B(2), AB(1)CD 　AB(3..n), -, B(2), B(1)CD 　　手順３　AB(3..n), -, -, B(1..2)CD

470:デフォルトの名無しさん
19/12/28 03:34:05 HeaGj5a1.net
　B(3..n), -, -, AB(1..2)CD
　･････
　同様にしてB(k) を移動する。(k=1..n)
　･･････
　B(n), -, -, AB(1..n-1)CD
　-, -, B(n), AB(1..n-1)CD
　A, -, B(n), B(1..n-1)CD
　　手順３’
　A, -, -, BCD
　-, -, -, ABCD

∴　f(m,n) ≧ f(m-1,n) + 2n + 1,

・手順２
　BC(k..n)D, -, -, *
　C(k..n)D, B, -, *
　C(k+1..n)D, B, C(k), *
　BC(k+1..n)D, -, C(k), *　

・手順３
　*, -, C(k), C(1..k-1)
　*, C(1..k-1), C(k), -
　*, C(1..k-1), -, C(k)
　*, -, -, C(1..k)

・手順３’
　*, -, B(k), B(1..k-1)CD
　*, B(1..k-1), B(k), CD
　*, B(1..k-1), -, B(k)CD
　*, -, -, B(1..k)CD

471:デフォルトの名無しさん
19/12/28 12:49:55.64 eBmyBfXD.net
いつまでハノイのメモ帳続けるんだよｗ

472:デフォルトの名無しさん
19/12/28 16:57:29.50 hZH7LPev.net
>>453
本気でやるには、"もらう"へ作り変える必要もあり、辛い
4つ程度なら、4倍回して出しちゃうだろう。
　(四重ループで汚すぎるのでソースは非公開)
　4と6の結果のみ載せておこう、あっているかも微妙。
　
合計: 2020 使用個数: 20 複数制限: 4-->
15100329420197868
[2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7, 11, 11, 17, 1913]
[89, 89, 89, 97, 97, 97, 101, 101, 101, 101, 103, 103, 103, 103, 107, 107, 107, 107, 109, 109]
********************************************* 0.43922sec ********************
合計: 2020 使用個数: 20 複数制限: 6-->
16509239212753751
[2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 1951]
[97, 97, 97, 97, 97, 97, 101, 101, 101, 101, 101, 101, 103, 103, 103, 103, 103, 103, 107, 107]
********************************************* 0.30568sec ********************

473:デフォルトの名無しさん
19/12/28 19:46:33.82 mH66EenF.net
>>426の1)はRで短く書ける(先頭・末尾行は正味の実行時間計測用)。
URLﾘﾝｸ(ideone.com)
Rでは整数は32ビットまでなので、浮動小数点型(double型)で計算しているが、
double型の有効桁数は15桁なので、小数部を非表示にすれば、答である13桁の
整数は正しく表示される。
64ビット整数を扱うbit64というパッケージも一応あるが、それを使うと
正味の実行時間が4.3倍もかかってしまう。
URLﾘﾝｸ(ideone.com)

474:デフォルトの名無しさん
19/12/28 21:25:10.79 4BOt7DVD.net
>>453
>>447を使って書いた
URLﾘﾝｸ(ideone.com)
メモリの使用を抑えたのも書いたけど遅くなった

475:デフォルトの名無しさん
19/12/28 22:48:40.84 AtehPr/g.net
お題
最小値のあるインデックスから離れるほど数字が大きくなる数列があります
増加量はランダムです
その数列の中から効率よく最小値を探してください
入力: 115, 109, 107, 101, 92, 85, 76, 66, 65, 62, 53, 49, 40, 38, 35, 25, 23, 17, 9, 2, 0, 5, 8, 10, 11, 20, 30, 37, 42, 47
出力: 0
入力: 110, 104, 96, 93, 84, 83, 87, 93, 98, 103, 113, 120, 121, 128, 133, 134, 142, 152, 159, 169, 171, 174, 183, 186, 196, 203, 210, 212, 221, 224
出力: 83
入力: 138, 135, 127, 124, 122, 112, 103, 98, 92, 87, 77, 73, 71, 63, 59, 51, 41, 36, 45, 54, 63, 71, 81, 88, 90, 98, 105, 112, 114, 119
出力: 36

476:デフォルトの名無しさん
19/12/28 23:28:52.09 mH66EenF.net
>>462
二分探索で答えてもらいたいんだろ。
URLﾘﾝｸ(ideone.com)

477:デフォルトの名無しさん
19/12/28 23:34:06.76 AtehPr/g.net
>>463
私が用意してた答えは二分探索ではありませんでした�

478:ｪ二分探索でできるんですねすごいです

479:デフォルトの名無しさん
19/12/28 23:38:08.54 mH66EenF.net
>>463 訂正。signが抜けていた。
URLﾘﾝｸ(ideone.com)

480:デフォルトの名無しさん
19/12/28 23:42:14.62 mH66EenF.net
再度訂正。1行目が消えていた。
URLﾘﾝｸ(ideone.com)

481:デフォルトの名無しさん
19/12/28 23:45:03.69 4BOt7DVD.net
最初に思いつくのが二分探索だからそれより速い方法があるんだろうなと思った

482:デフォルトの名無しさん
19/12/29 00:04:58.67 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)

483:デフォルトの名無しさん
19/12/29 00:15:11.87 Jtzyjysr.net
URLﾘﾝｸ(ideone.com)

484:デフォルトの名無しさん
19/12/29 00:41:31.56 wJ/DeyFk.net
>>466 最小値が複数ある場合の条件分けが抜けていた。
URLﾘﾝｸ(ideone.com)
Rのbinsearch関数は値の返し方に癖があって、条件分けを見落としやすいな。

485:デフォルトの名無しさん
19/12/29 02:13:42.53 2ZGuf6bc.net
>>462
Java 三分探索で2/3に範囲を狭めてく
URLﾘﾝｸ(paiza.io)
1/2に減らせる二分探索には敵わない
傾きを二分探索するって発想はなかったわー

486:デフォルトの名無しさん
19/12/29 02:17:13.97 2ZGuf6bc.net
>>468
実装の効率はパないすね、効率はそういう意味でもありましたホントです

487:デフォルトの名無しさん
19/12/29 09:24:17.66 Y3W4ZjXN.net
いやいや
ただのリニア検索より遅いのはあり得ん

488:デフォルトの名無しさん
19/12/29 19:39:43.67 Jtzyjysr.net
でも出てる中で一番速いけど。

489:デフォルトの名無しさん
19/12/29 21:33:41.90 wJ/DeyFk.net
>>474
そりゃ、例の数列では要素数が少なくてアルゴリズムの差が出にくいからだろ。
「効率よく」とわざわざ書いてある問題なんだから、もっと大きなデータを与えた
場合も想定して答えるのが普通。
例えば、100万から1までの連番の後に2から50万までの連番が続く数列を与えれば
アルゴリズム間の違いは歴然。
Rで二分探索、min関数、sort関数で求めたときの1回あたり平均実行時間を計測すると、
0.132, 2.08, 55.2ミリ秒で桁が違う (PCでは二分探索はもう少し速かった)。
計算量オーダーがO(log n), O(n), O(n log n)だから当たり前だが。
URLﾘﾝｸ(ideone.com)
C++の >>468に同じデータを与えると108ミリ秒かかり、何とRのsort関数より遅い。
Rの関数はCで書かれているものが多いから、この差はつまりはCとC++のSTLの
性能差によるものだろう。
URLﾘﾝｸ(ideone.com)

490:デフォルトの名無しさん
19/12/29 21:37:04.80 Jtzyjysr.net
>>475
>>469の場合だとどんな感じ？

491:デフォルトの名無しさん
19/12/29 21:41:48.80 2ZGuf6bc.net
なんかすまんなみんな、ワイのせいで・・・ワイのせいで・・・ワイは悪くない

492:デフォルトの名無しさん
19/12/29 22:06:29.15 Y3W4ZjXN.net
>>462くらい乱数に法則があれば2分検索より速いアルゴリズムを作れる
例としてはイマイチ

493:デフォルトの名無しさん
19/12/29 22:38:51.59 Byl7yBSZ.net
このスレだけマジで何言ってんのか理解できない
やっぱまずいよなあ、数学勉強し直さなきゃなあ

494:デフォルトの名無しさん
19/12/29 22:43:46.32 KptD7+e9.net
>>426
1)数百万規模でありそう。

次ページ