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

レス数が900を超えています。1000を超えると表示できなくなるよ。
2018/01/01(月) 11:15:04.40ID:2Vr1CPKy
プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part9
https://mevius.5ch.net/test/read.cgi/tech/1480579110/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。
2018/04/15(日) 20:12:02.04ID:qw72cACc
>>821
253:x=115:155
x=341

整数で十分だけど？
824デフォルトの名無しさん
垢版 |
2018/04/15(日) 20:16:25.14
算数板でやれ
2018/04/15(日) 20:29:51.65ID:CIuag2/D
>>822-823
比率の問題って書いてあるのに指摘の意味もわかってないのかよ w
2018/04/15(日) 20:32:49.64ID:NqrSXbP9
指摘が適当じゃないからでしょ
2018/04/15(日) 20:35:30.23ID:uWituoMu
>>825
だから答えが一意に決まるんだから素因数分解して自明な解を提示したレスに難癖付けるのはバカだっつってんの
2018/04/15(日) 20:40:17.66ID:CIuag2/D
>>827
たまたま素因数分解できるからいいだけで常に使えるわけじゃない解法示す奴は頭悪いと思われてもしょうがない
しかも単なる算数レベルの問題だしな w
2018/04/15(日) 20:41:46.95ID:vNL79cRV
で、お前らはいつになったらプログラミングをするんだ？
2018/04/15(日) 20:45:57.62ID:uWituoMu
>>828
日本語読める？
「解法を示す」じゃなくて「解を提示した」っつってんだけど
解の一意性は明確なんだから簡単に解を提示すれば
それで十分性を満たしていると同時に必要性も満たしてるんだけど
重箱の隅にもならないクソみたいな指摘してんだから突っ込まれて当然でしょ
2018/04/15(日) 20:54:58.94ID:GeThIANt
>>779 Squeak/Pharo Smalltalk

https://ideone.com/43b7Uk
2018/04/15(日) 21:05:23.77ID:CIuag2/D
>>830
解と言い張るならなら答えだけ書けよ
言い訳にしてもダサすぎるわ w
2018/04/15(日) 21:10:51.18ID:uWituoMu
>>832
初めは「なんで整数限定なんだ？」というアホな主張しておいて論点すり替えないでくれよ
剰えこっちは>>822で答え書いてるんだけど文字読めないの？なんなのこいつ
2018/04/15(日) 21:35:40.74ID:CIuag2/D
>>833
因数分解してどやってたアホがいたからな w
ひょっとしてアンカーも見れないのか？
2018/04/15(日) 21:49:46.05ID:NqrSXbP9
なにやら揉めてますね
さて、次のお題どうぞ
2018/04/15(日) 23:35:46.74ID:sXJBpbWg
>>818
そりゃできるだろうねえ
だから何？

先に素数を求めた方が処理が速そうだと思ったわけだが
求めないで求めめ欲しければ>>816に書きなさい
2018/04/16(月) 00:40:40.93ID:0r0tOoJV
いい加減プログラミングらしいお題出してよ
838デフォルトの名無しさん
垢版 |
2018/04/16(月) 07:54:19.83ID:sVtsCMAa
>>837
プログラミングらしいお題なら、すでに>>779にあるよ
回答はRuby(>>809)とSmalltalk(>>831)しかないけどね

組織の中で働き者は全体の１割しかいないと言われているけど、
このスレでも見事に再現されていてワロタ
2018/04/16(月) 08:39:56.02ID:lrRTONI/
>>836
>>817-818で完結したのでこのお題は終了です
回答ありがとうございました
2018/04/16(月) 08:56:27.76ID:ZFIHRn8x
おう先生によろしくな！
2018/04/16(月) 09:21:55.35ID:F4Ovhl4T
気分転換にどうぞ

お題:与えられた迷路図の通路幅を2倍にした迷路図を作成する

入力例
#.#..
.#..#
.#...
..##.
###..

出力例
##..##....
##..##....
..##....##
..##....##
..##......
..##......
....####..
....####..
######....
######....
2018/04/16(月) 09:22:29.79ID:lrRTONI/
はい、次どうぞ
2018/04/16(月) 09:38:08.21ID:JqHYG+3X
>>841 ruby
$<.read.split.map{|s|[s.gsub!(/./,'\&\&'), s]}*$/
2018/04/16(月) 11:16:53.07ID:1KO8LMUv
お題: あみだくじが与えられる
あみだくじは'|','-',' 'の3つで構成されている
スタート地点が左からn番目、ゴール地点が左からm番目と与えられた時、横棒を追加することでゴールに向かう為の最小の本数を答えよ
なお解が存在しなければ-1と答えよ
横棒の高さを半分ずらして設置や長さ2以上の横棒などは禁止とする

入力例
1 4
| | |-| |
|-| | |-|
| | | | |
|-| |-| |
出力例
1
2018/04/16(月) 11:30:39.95ID:rl+JKxfh
同じ高さの横棒は隣接しないということでいいのかな？
2018/04/16(月) 12:23:47.11ID:ZFIHRn8x
最小の、とか書くから数学のマウント合戦になるのでは？アミダくじを解け、でいいじゃん。出た解答の中で最小で出してるのがあったらその時点でスゴイスゴイ
2018/04/16(月) 12:33:28.31ID:rl+JKxfh
>>846
それおもしろい？
2018/04/16(月) 12:58:29.77ID:qlfABgAK
ニコリのナンバーリンク、スリザーリンクとか、
あみだくじ・電力網・鉄道経路・選挙区割り・正多面体の展開図とか、この本に載ってる

北大の湊真一の、ZDD。
Python, Ruby でも使える

超高速グラフ列挙アルゴリズム−〈フカシギの数え方〉が拓く，
組合せ問題への新アプローチ
ERATO 湊離散構造処理系プロジェクト・湊真一、2015

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD
2018/04/16(月) 14:43:52.77ID:VE3/OCqi
>>846
1人頭が悪いのがいただけ
最小って言葉を使えなかったら問題に制約がつきすぎる
2018/04/16(月) 14:45:34.28ID:VE3/OCqi
もちろん>>844は(存在すれば)最小値が存在する
2018/04/16(月) 15:43:24.03ID:4eWg6WR3
なるほど、最小って条件は止めるか
条件を変えるわ
解がN通りある時、それぞれの解の本数をa_i(1≦i≦N)とする
この時、任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力してくれれば良いよ
>>845 隣接しない
隣接したらあみだくじとして成立しないしね
852デフォルトの名無しさん
垢版 |
2018/04/16(月) 19:17:35.12ID:CKG1x9VY
>>841 J
2 echo 2&#;._2 stdin''
2018/04/16(月) 19:21:25.33ID:T6RcU2kF
>>851
よくわからん日本語だな
2018/04/16(月) 19:23:45.57ID:T6RcU2kF
多分最小を別の表現にしたつもりなんだろうけど
日本語がめちゃくちゃ
無理しなくて良いよ
2018/04/16(月) 19:31:45.75ID:gUfDVwYo
>>852
なにこれなにこれ
2018/04/16(月) 19:45:15.45ID:14bBH5UG
>>853-854
ここ数日、数学の知識全くないくせに噛みついてる無知はお前だろ
>>851は一般的な最小元の定義だろうが
2018/04/16(月) 20:06:21.68ID:w6kJX9+o
「任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力」

意味がわかりません
2018/04/16(月) 20:08:00.59ID:yQIjKmTg
>>856
「任意の i, j」というのがおかしい、i を先に決定した上での「任意の j　」でいい
2018/04/16(月) 20:09:07.01ID:w6kJX9+o
一応私数学の専門家
2018/04/16(月) 20:15:07.59ID:yQIjKmTg
>>859
分野、ご専攻は何ですか？
2018/04/16(月) 20:17:49.89ID:w6kJX9+o
バレるので言わない
狭い世界なんでね
2018/04/16(月) 20:18:51.48ID:w6kJX9+o
駒場

とだけ言っておく
2018/04/16(月) 20:19:40.83ID:JqHYG+3X
>>862
アロハシャツの先生元気？
2018/04/16(月) 20:21:37.49ID:w6kJX9+o
ここまで
2018/04/16(月) 20:23:32.19ID:w6kJX9+o
回転寿司問題の高速ソルバーを作ったのは私
2018/04/16(月) 20:37:10.86ID:yQIjKmTg
>>859 >>861
一般ピープルが習得するとよい（大げさにいえば世界観が変わるような）数学の分野を教えていただければ嬉しいです
2018/04/16(月) 20:39:42.03ID:w6kJX9+o
集合論
2018/04/16(月) 20:59:44.33ID:gZF8UNgN
群論・環論

ごめん聞いたことあるような言葉を羅列してみただけ
2018/04/16(月) 21:07:23.11ID:8eszbiHC
お題
マイナンバーが一部欠けてしまった
?部分を補完して可能性のあるマイナンバーをすべて列挙せよ

[example 1]
99999999999?
=>
999999999996

[example 2]
??9999999999
=>
069999999999
179999999999
289999999999
399999999999
509999999999
619999999999
729999999999
839999999999
949999999999
2018/04/16(月) 22:11:04.19ID:NpxY1/hQ
摂動論とか難しいけどできたら気持ちいいだろうな
2018/04/16(月) 22:21:24.15ID:p2Ysyc3s
>>869 Ruby 全探索

A = (1..11).map{|i| i + 1 - i / 7 * 6}
%w[
99999999999? ??9999999999
].each{|s|
puts '', s, '=>'
10.**(s.count(??)).times{|i|
d = "%012d".%(i).chars
m = s.gsub(??){d.pop}.reverse.chars.map(&:to_i)
x = A.zip(m[1, 11]).map{|a, b| a * b}.sum % 11
puts m.reverse.join if (x == 1 ? 0 : -x % 11) == m[0]
}
}
#=>
99999999999?
=>
999999999996

??9999999999
=>
509999999999
619999999999
729999999999
839999999999
949999999999
069999999999
179999999999
289999999999
399999999999
2018/04/17(火) 03:09:26.43ID:pX2t5ilp
マイナンバーのチェックディジットを分かり易く解説しているページはないものかと探したらあったのでURL書いとく。
https://qiita.com/kmz_kappa/items/af18ac7b6b8bfe9041b0
2018/04/17(火) 10:02:17.20ID:XkVoPtoV
>>858 マジだわ、算数できない奴に噛み付いて自分がダメージ受けた
やはり数学で無理に語るべきではないな、専攻の情報の範囲だけにしとこ……
2018/04/17(火) 10:33:51.01ID:ePc5Lh3L
>>869 Squeak/Pharo Smalltalk

| check |

check := [:digitsStr |
　| digits checkDigit calcDigit |
　digits := digitsStr asArray collect: #digitValue.
　checkDigit := digits last.
　calcDigit := ((digits * #(6 5 4 3 2 7 6 5 4 3 2 0)) sum \\ 11
　　in: [:x | x < 2 ifTrue: [0] ifFalse: [11 - x]]).
　checkDigit = calcDigit
].

#('99999999999?' '??9999999999') collect: [:incmpNum |
　| indices candNums |
　indices := incmpNum asArray collectWithIndex: [:chr :idx | chr == $? ifTrue: [idx] ifFalse: [0]].
　indices := indices reject: #isZero.
　candNums := OrderedCollection new.
　($0 to: $9) asDigitsToPower: indices size do: [:digs |
　　| candNum |
　　candNum := incmpNum copy.
　　indices with: digs do: [:idx :dig | candNum at: idx put: dig].
　　(check value: candNum) ifTrue: [candNums add: candNum]
　].
　incmpNum -> candNums asStringWithCr
]
2018/04/17(火) 13:45:56.41ID:dXM64r3I
>>865
回転すし問題が気になります＞＜
教えてください！！
2018/04/17(火) 14:23:34.06ID:g5yHmTYu
自演乙。
2018/04/17(火) 16:49:46.20ID:KTfx2aCu
>>875

0296 デフォルトの名無しさん 2017/06/26 21:09:32

前にあったやつ。??

回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。??
コンベアは毎秒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" > ?
2018/04/17(火) 17:32:19.21ID:dXM64r3I
>>877
ありがとうございます
879デフォルトの名無しさん
垢版 |
2018/04/17(火) 19:05:05.39ID:S4fl8nYd
>>322 J
echo !23x
2018/04/17(火) 19:21:24.18ID:g5yHmTYu
>>879
どうなってんのこれ
2018/04/18(水) 00:46:46.99ID:fMrElfkf
お題
0〜N-1の数字を1つずつ使ったN進数表記でN桁の数のうち、最も多くの素因数を持つ数を求めよ

N=2
→10

N=5
→34210 (10進数で2430=2*3^5*5, 素因数は7個)

N=10
→???
2018/04/18(水) 00:56:38.62ID:JUjvxXNW
全てを探索
しかない気がする

N=14くらいが限度か
2018/04/18(水) 01:23:42.06ID:UfQjex1N
まーた数学の問題か。
まーたマウント取りたいセンセの荒らしか。
うんざり
2018/04/18(水) 03:59:26.48ID:Acg84ZKa
アルゴリズムと数学は切り離せないものだし数学が役立つ場面はもちろん多いんだけど、数学だけで完結しちゃう問題では、プログラミングのお題としては面白味がないよね。
むしろこのスレに的には悪問と言ってもよいと個人的には思う。

素直なプログラミングでは複雑になってしまうところを数学を使うことでスマートに解けるとか、逆に数学を使うことで全く別のアプローチの解法があるとかだと、面白いと思う。
必ずしも速い、安い、上手いが正義じゃなくて、そんな解き方もあるのねとか、それどうなってんの？と不思議に思えるような解法とかも見てみたいし、そんな解法が見られるお題が面白いと思う。
2018/04/18(水) 04:07:00.58ID:Acg84ZKa
追加すると、言語によって異なる記述能力や得手不得手を活かして上手く解いたとか簡潔に書けたとか、逆にわざわざそんな敢えて難しいやり方をするかとか、そういうのも面白いなと思います。
2018/04/18(水) 06:03:49.90ID:iqodOpJQ
数学で完結してんのかこれ
コンピュータ使わない解法思いつかんが
2018/04/18(水) 07:07:15.79ID:qlMtX02l
素因数の個数って何だっけ
互いに素な約数の個数なら、N=5の時33220(=2310=2*3*5*7*11)の方が多いし、素因数分解で出てくる素数の個数ならN=5の時31143(=2048=2^11)の方が多いし
私が文を読めていないだけ？
2018/04/18(水) 07:22:32.10ID:pdl2KQl9
ただ列挙して調べなきゃいけないとすると面白くもなんともない。
いい解を作ろうとすれば、できるかどうかはともかく
数学ひねり回すのだけがメインの仕事になるみたいな。
2018/04/18(水) 07:24:04.47ID:pdl2KQl9
>>887
0から4を全部使うという制約。
2018/04/18(水) 08:01:49.71ID:iqodOpJQ
J ブルートフォース

q =: >./&(+/&|:&(0&<)&q:&(#. (i.@! A. i.)))"0

iPhone の J インタプリタでは N=8 までが限界だった
q 2 3 4 5 6 7 8
1 2 6 7 13 10 16
2018/04/18(水) 08:02:43.21ID:JUjvxXNW
素因数の個数だと2^11は2の1個だけなんだけどなあ
例だと11個と数えたいようだけど
2018/04/18(水) 08:04:10.88ID:iqodOpJQ
9 も大丈夫だった
q 9
12
2018/04/18(水) 08:04:22.36ID:JUjvxXNW
>>888
数学ひねり回してどうにかなる気はしない
2018/04/18(水) 08:15:58.76ID:iqodOpJQ
>>891
問題の着目点に応じて相異なる素因数の数になるか重解を許すか解釈すればいいんじゃないの

そうしないと高校数学に良くある(このスレにも出てるな)
「n! の素因数2の個数を求めよ」の答えが恒等的に1になってしまう。
知らんけど。
2018/04/18(水) 08:33:43.28ID:CiWWe7S5
重解
因数

意味を知らんヤツが問題を作る
2018/04/18(水) 08:39:01.69ID:loM0N11v
重解じゃなくて重根な
2018/04/18(水) 08:40:26.67ID:CiWWe7S5
www
同じだろ
2018/04/18(水) 08:48:02.15ID:iqodOpJQ
いや重解は変換ミス
それに重複を許さない個数でも問題は成立するな、
良く考えると。
2018/04/18(水) 08:53:49.03ID:loM0N11v
>>897
解と根は本来、別の用語だよ
今はごっちゃに使われてるけど
2018/04/18(水) 09:55:28.20ID:8LhMtFC1
>>898
例を出さなかったらそれぞれの解釈が見れて面白かったかも

>>899
それで言い訳になってると思ってんの？
2018/04/18(水) 10:31:06.41ID:SkflZos/
自演乙
2018/04/18(水) 11:13:23.97ID:2HNL8zBg
>>889 Thanks、理解した
全探索しか思いつかなかったorz
903デフォルトの名無しさん
垢版 |
2018/04/18(水) 14:43:49.71ID:mfkhz8pH
>>816 J
200$(#~ 2&=@#@q:)2+i.1000
2018/04/18(水) 15:36:58.27ID:8LhMtFC1
このスレを見ると
世の中のソフトが重くなる理由がよく分かる
2018/04/18(水) 17:14:39.91ID:AXVF0Rxy
>>903
それ1000までの間に半素数が200個存在するってあらかじめ分かってなきゃ使えなくない
2018/04/18(水) 17:19:26.83ID:8LhMtFC1
あらかじめ調べておけばいい
どうせなら半素数自体もしらべてテーブルにしておけば
2018/04/18(水) 18:12:40.76ID:AXVF0Rxy
だから調べてテーブル作るお題やろ
2018/04/18(水) 18:20:10.32ID:8LhMtFC1
コンパイラが究極に進化するとそうなる
今でも純関数&定数指定にすれば
2018/04/18(水) 18:35:30.37ID:MXcoXWvI
究極に進化して、ある数を素因数分解しろとか離散対数求めろと言われたら、
何桁でもテーブルにあって即答ってか？
暗号死ぬわ。
2018/04/18(水) 18:51:51.73ID:8LhMtFC1
当然限度はある
当たり前
2018/04/18(水) 19:18:25.23ID:SkflZos/
君さ、ちょっと黙ってて
912デフォルトの名無しさん
垢版 |
2018/04/18(水) 20:18:15.86ID:mfkhz8pH
>>816 J
>>817のやり方で
/:~~.,*/~p:i.20
913デフォルトの名無しさん
垢版 |
2018/04/18(水) 23:38:59.46ID:BI6oaZDa
>>871
Kotlin
https://paiza.io/projects/BHMBjMpBsKkeWxw_1WxpQw
何も考えずに総当たり。7桁以上は多すぎるのでやらないようにした。
914デフォルトの名無しさん
垢版 |
2018/04/18(水) 23:39:47.19ID:BI6oaZDa
ごめん。アンカ間違えた。>>869だった。
2018/04/18(水) 23:57:26.29ID:+652BqLv
トップバストとアンダーバストがmm単位で与えられるので
JIS L 4006におけるカップ体型区分を出力せよ
なお、与えられた体系が当該規格の数値と一致しない場合は
最も差の少ない体型区分を選べ

-*- input -*-
880 815
999 799
755 480

-*- output -*-
AA
E
H
2018/04/19(木) 00:17:12.74ID:7EnHL2Zb
JISの抜粋はよ
2018/04/19(木) 01:14:32.58ID:AYGORpen
三人目、人間？
2018/04/19(木) 01:50:36.78ID:uvuGKqvu
>>915 Ruby
2018/04/19(木) 01:51:08.23ID:uvuGKqvu
ミス
>>915 Ruby

#!ruby -na
puts ['AA',*?A..?I][(eval($F*?-)/25.0-3).round.clamp(0,9)]
2018/04/19(木) 02:02:41.15ID:FEDLlhkO
Jアニキはよ
2018/04/19(木) 04:01:30.95ID:4mrmpy84
このスレは、素数表を使う問題が多い

一方、プログラミング・コンテストでは、自作ライブラリも持ち込めるから、
素数表・ZDD を持ち込んで、解けるような問題は少ない

数学的な解法がなくて、全探索して見つけるものが多い
2018/04/19(木) 09:28:13.47ID:/i49YDDr
じゃあここで出てる問題をまず最初にNP完全かどうかを判定すればいい
競技プログラミングに適している問題かどうかを証明してから、改めてプログラミングにあたる
レス数が900を超えています。1000を超えると表示できなくなるよ。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況