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

**デフォルトの名無しさん** · 2018/01/01(月) 11:15:04.40

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ 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/16(月) 11:30:39.95

同じ高さの横棒は隣接しないということでいいのかな？

**デフォルトの名無しさん** · 2018/04/16(月) 12:23:47.11

最小の、とか書くから数学のマウント合戦になるのでは？アミダくじを解け、でいいじゃん。出た解答の中で最小で出してるのがあったらその時点でスゴイスゴイ

**デフォルトの名無しさん** · 2018/04/16(月) 12:33:28.31

>>846
それおもしろい？

**デフォルトの名無しさん** · 2018/04/16(月) 12:58:29.77

ニコリのナンバーリンク、スリザーリンクとか、
あみだくじ・電力網・鉄道経路・選挙区割り・正多面体の展開図とか、この本に載ってる

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

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

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD

**デフォルトの名無しさん** · 2018/04/16(月) 14:43:52.77

>>846
1人頭が悪いのがいただけ
最小って言葉を使えなかったら問題に制約がつきすぎる

**デフォルトの名無しさん** · 2018/04/16(月) 14:45:34.28

もちろん>>844は(存在すれば)最小値が存在する

**デフォルトの名無しさん** · 2018/04/16(月) 15:43:24.03

なるほど、最小って条件は止めるか
条件を変えるわ
解がN通りある時、それぞれの解の本数をa_i(1≦i≦N)とする
この時、任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力してくれれば良いよ
>>845 隣接しない
隣接したらあみだくじとして成立しないしね

**デフォルトの名無しさん** · 2018/04/16(月) 19:17:35.12

>>841 J
2 echo 2&#;._2 stdin''

**デフォルトの名無しさん** · 2018/04/16(月) 19:21:25.33

>>851
よくわからん日本語だな

**デフォルトの名無しさん** · 2018/04/16(月) 19:23:45.57

多分最小を別の表現にしたつもりなんだろうけど
日本語がめちゃくちゃ
無理しなくて良いよ

**デフォルトの名無しさん** · 2018/04/16(月) 19:31:45.75

>>852
なにこれなにこれ

**デフォルトの名無しさん** · 2018/04/16(月) 19:45:15.45

>>853-854
ここ数日、数学の知識全くないくせに噛みついてる無知はお前だろ
>>851は一般的な最小元の定義だろうが

**デフォルトの名無しさん** · 2018/04/16(月) 20:06:21.68

「任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力」

意味がわかりません

◆QZaw55cn4c · 2018/04/16(月) 20:08:00.59

>>856
「任意の i, j」というのがおかしい、i を先に決定した上での「任意の j　」でいい

**デフォルトの名無しさん** · 2018/04/16(月) 20:09:07.01

一応私数学の専門家

◆QZaw55cn4c · 2018/04/16(月) 20:15:07.59

>>859
分野、ご専攻は何ですか？

**デフォルトの名無しさん** · 2018/04/16(月) 20:17:49.89

バレるので言わない
狭い世界なんでね

**デフォルトの名無しさん** · 2018/04/16(月) 20:18:51.48

駒場

とだけ言っておく

**デフォルトの名無しさん** · 2018/04/16(月) 20:19:40.83

>>862
アロハシャツの先生元気？

**デフォルトの名無しさん** · 2018/04/16(月) 20:21:37.49

ここまで

**デフォルトの名無しさん** · 2018/04/16(月) 20:23:32.19

回転寿司問題の高速ソルバーを作ったのは私

◆QZaw55cn4c · 2018/04/16(月) 20:37:10.86

>>859 >>861
一般ピープルが習得するとよい（大げさにいえば世界観が変わるような）数学の分野を教えていただければ嬉しいです

**デフォルトの名無しさん** · 2018/04/16(月) 20:39:42.03

集合論

**デフォルトの名無しさん** · 2018/04/16(月) 20:59:44.33

群論・環論

ごめん聞いたことあるような言葉を羅列してみただけ

**デフォルトの名無しさん** · 2018/04/16(月) 21:07:23.11

お題
マイナンバーが一部欠けてしまった
?部分を補完して可能性のあるマイナンバーをすべて列挙せよ

[example 1]
99999999999?
=>
999999999996

[example 2]
??9999999999
=>
069999999999
179999999999
289999999999
399999999999
509999999999
619999999999
729999999999
839999999999
949999999999

**デフォルトの名無しさん** · 2018/04/16(月) 22:11:04.19

摂動論とか難しいけどできたら気持ちいいだろうな

**デフォルトの名無しさん** · 2018/04/16(月) 22:21:24.15

>>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.43

マイナンバーのチェックディジットを分かり易く解説しているページはないものかと探したらあったのでURL書いとく。
https://qiita.com/kmz_kappa/items/af18ac7b6b8bfe9041b0

**デフォルトの名無しさん** · 2018/04/17(火) 10:02:17.20

>>858 マジだわ、算数できない奴に噛み付いて自分がダメージ受けた
やはり数学で無理に語るべきではないな、専攻の情報の範囲だけにしとこ……

**デフォルトの名無しさん** · 2018/04/17(火) 10:33:51.01

>>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.41

>>865
回転すし問題が気になります＞＜
教えてください！！

**デフォルトの名無しさん** · 2018/04/17(火) 14:23:34.06

自演乙。

**デフォルトの名無しさん** · 2018/04/17(火) 16:49:46.20

>>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.21

>>877
ありがとうございます

**デフォルトの名無しさん** · 2018/04/17(火) 19:05:05.39

>>322 J
echo !23x

**デフォルトの名無しさん** · 2018/04/17(火) 19:21:24.18

>>879
どうなってんのこれ

**デフォルトの名無しさん** · 2018/04/18(水) 00:46:46.99

お題
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.62

全てを探索
しかない気がする

N=14くらいが限度か

**デフォルトの名無しさん** · 2018/04/18(水) 01:23:42.06

まーた数学の問題か。
まーたマウント取りたいセンセの荒らしか。
うんざり

**デフォルトの名無しさん** · 2018/04/18(水) 03:59:26.48

アルゴリズムと数学は切り離せないものだし数学が役立つ場面はもちろん多いんだけど、数学だけで完結しちゃう問題では、プログラミングのお題としては面白味がないよね。
むしろこのスレに的には悪問と言ってもよいと個人的には思う。

素直なプログラミングでは複雑になってしまうところを数学を使うことでスマートに解けるとか、逆に数学を使うことで全く別のアプローチの解法があるとかだと、面白いと思う。
必ずしも速い、安い、上手いが正義じゃなくて、そんな解き方もあるのねとか、それどうなってんの？と不思議に思えるような解法とかも見てみたいし、そんな解法が見られるお題が面白いと思う。

**デフォルトの名無しさん** · 2018/04/18(水) 04:07:00.58

追加すると、言語によって異なる記述能力や得手不得手を活かして上手く解いたとか簡潔に書けたとか、逆にわざわざそんな敢えて難しいやり方をするかとか、そういうのも面白いなと思います。

**デフォルトの名無しさん** · 2018/04/18(水) 06:03:49.90

数学で完結してんのかこれ
コンピュータ使わない解法思いつかんが

**デフォルトの名無しさん** · 2018/04/18(水) 07:07:15.79

素因数の個数って何だっけ
互いに素な約数の個数なら、N=5の時33220(=2310=2*3*5*7*11)の方が多いし、素因数分解で出てくる素数の個数ならN=5の時31143(=2048=2^11)の方が多いし
私が文を読めていないだけ？

**デフォルトの名無しさん** · 2018/04/18(水) 07:22:32.10

ただ列挙して調べなきゃいけないとすると面白くもなんともない。
いい解を作ろうとすれば、できるかどうかはともかく
数学ひねり回すのだけがメインの仕事になるみたいな。

**デフォルトの名無しさん** · 2018/04/18(水) 07:24:04.47

>>887
0から4を全部使うという制約。

**デフォルトの名無しさん** · 2018/04/18(水) 08:01:49.71

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.21

素因数の個数だと2^11は2の1個だけなんだけどなあ
例だと11個と数えたいようだけど

**デフォルトの名無しさん** · 2018/04/18(水) 08:04:10.88

9 も大丈夫だった
q 9
12

**デフォルトの名無しさん** · 2018/04/18(水) 08:04:22.36

>>888
数学ひねり回してどうにかなる気はしない

**デフォルトの名無しさん** · 2018/04/18(水) 08:15:58.76

>>891
問題の着目点に応じて相異なる素因数の数になるか重解を許すか解釈すればいいんじゃないの

そうしないと高校数学に良くある(このスレにも出てるな)
「n! の素因数2の個数を求めよ」の答えが恒等的に1になってしまう。
知らんけど。

**デフォルトの名無しさん** · 2018/04/18(水) 08:33:43.28

重解
因数

意味を知らんヤツが問題を作る

**デフォルトの名無しさん** · 2018/04/18(水) 08:39:01.69

重解じゃなくて重根な

**デフォルトの名無しさん** · 2018/04/18(水) 08:40:26.67

www
同じだろ

**デフォルトの名無しさん** · 2018/04/18(水) 08:48:02.15

いや重解は変換ミス
それに重複を許さない個数でも問題は成立するな、
良く考えると。

**デフォルトの名無しさん** · 2018/04/18(水) 08:53:49.03

>>897
解と根は本来、別の用語だよ
今はごっちゃに使われてるけど

**デフォルトの名無しさん** · 2018/04/18(水) 09:55:28.20

>>898
例を出さなかったらそれぞれの解釈が見れて面白かったかも

>>899
それで言い訳になってると思ってんの？

**デフォルトの名無しさん** · 2018/04/18(水) 10:31:06.41

自演乙

**デフォルトの名無しさん** · 2018/04/18(水) 11:13:23.97

>>889 Thanks、理解した
全探索しか思いつかなかったorz

**デフォルトの名無しさん** · 2018/04/18(水) 14:43:49.71

>>816 J
200$(#~ 2&=@#@q:)2+i.1000

**デフォルトの名無しさん** · 2018/04/18(水) 15:36:58.27

このスレを見ると
世の中のソフトが重くなる理由がよく分かる

**デフォルトの名無しさん** · 2018/04/18(水) 17:14:39.91

>>903
それ1000までの間に半素数が200個存在するってあらかじめ分かってなきゃ使えなくない

**デフォルトの名無しさん** · 2018/04/18(水) 17:19:26.83

あらかじめ調べておけばいい
どうせなら半素数自体もしらべてテーブルにしておけば

**デフォルトの名無しさん** · 2018/04/18(水) 18:12:40.76

だから調べてテーブル作るお題やろ

**デフォルトの名無しさん** · 2018/04/18(水) 18:20:10.32

コンパイラが究極に進化するとそうなる
今でも純関数&定数指定にすれば

**デフォルトの名無しさん** · 2018/04/18(水) 18:35:30.37

究極に進化して、ある数を素因数分解しろとか離散対数求めろと言われたら、
何桁でもテーブルにあって即答ってか？
暗号死ぬわ。

**デフォルトの名無しさん** · 2018/04/18(水) 18:51:51.73

当然限度はある
当たり前

**デフォルトの名無しさん** · 2018/04/18(水) 19:18:25.23

君さ、ちょっと黙ってて

**デフォルトの名無しさん** · 2018/04/18(水) 20:18:15.86

>>816 J
>>817のやり方で
/:~~.,*/~p:i.20

**デフォルトの名無しさん** · 2018/04/18(水) 23:38:59.46

>>871
Kotlin
https://paiza.io/projects/BHMBjMpBsKkeWxw_1WxpQw
何も考えずに総当たり。7桁以上は多すぎるのでやらないようにした。

**デフォルトの名無しさん** · 2018/04/18(水) 23:39:47.19

ごめん。アンカ間違えた。>>869だった。

**デフォルトの名無しさん** · 2018/04/18(水) 23:57:26.29

トップバストとアンダーバストがmm単位で与えられるので
JIS L 4006におけるカップ体型区分を出力せよ
なお、与えられた体系が当該規格の数値と一致しない場合は
最も差の少ない体型区分を選べ

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

-*- output -*-
AA
E
H

**デフォルトの名無しさん** · 2018/04/19(木) 00:17:12.74

JISの抜粋はよ

**デフォルトの名無しさん** · 2018/04/19(木) 01:14:32.58

三人目、人間？

**デフォルトの名無しさん** · 2018/04/19(木) 01:50:36.78

>>915 Ruby

**デフォルトの名無しさん** · 2018/04/19(木) 01:51:08.23

ミス
>>915 Ruby

#!ruby -na
puts ['AA',*?A..?I][(eval($F*?-)/25.0-3).round.clamp(0,9)]

**デフォルトの名無しさん** · 2018/04/19(木) 02:02:41.15

Jアニキはよ

**デフォルトの名無しさん** · 2018/04/19(木) 04:01:30.95

このスレは、素数表を使う問題が多い

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

数学的な解法がなくて、全探索して見つけるものが多い

**デフォルトの名無しさん** · 2018/04/19(木) 09:28:13.47

じゃあここで出てる問題をまず最初にNP完全かどうかを判定すればいい
競技プログラミングに適している問題かどうかを証明してから、改めてプログラミングにあたる

**デフォルトの名無しさん** · 2018/04/19(木) 09:46:04.07

出題者がPと証明してから出すのが筋だろ

**デフォルトの名無しさん** · 2018/04/19(木) 09:51:24.98

プログラミング・コンテストの良問は、
持ち込みの自作ライブラリでは解けないもので、

素直に全探索すると、計算回数が1億回以上になって、2秒以内に解けないもの

ここで、パズル的に考えて、数学的な法則を使うことで、
枝切り・ショートカットして、計算回数が1千万回以下になるもの

**デフォルトの名無しさん** · 2018/04/19(木) 10:05:22.86

>>915 J
f=:{&(25#'AA'';;/'ABCDEFGHI')@<.@-&62.5&(-/)

**デフォルトの名無しさん** · 2018/04/19(木) 12:09:31.59

>>925
分かりにくいのは毎度の事だが今回はあんまり短くもならないんだな。

**デフォルトの名無しさん** · 2018/04/19(木) 20:55:00.88

JアプリみつけたのでJで遊んでる初学者だけど
参考にするコード見つけにくい(少ない検索し難い読みにくい)から
>>925の人の存在は有り難い

見所はインデックスを25で割らずテーブルを25倍にしてるとこか

**デフォルトの名無しさん** · 2018/04/21(土) 20:19:05.79

お題：文字列の配列をカンマ区切りで表示せよ
複数の方法を用いること

ruby
https://ideone.com/cKprYN

**デフォルトの名無しさん** · 2018/04/21(土) 21:12:35.96

配列を、って言ってるのに%wでスペース区切りの文字列から作るの？
てかrubyの%wって何のためにあるの？
splitあるのに組み込みので提供するほどのもの？
他言語者からしたらsplitは分かってもらえると思うが%wは分からんと思うぞ？
やっぱ書くだけの書き捨て言語なんかな。

**デフォルトの名無しさん** · 2018/04/21(土) 21:20:16.29

>>928 common lisp

(let ((a '("java" "ruby" "rust")))
　　(format t "~{~A~^, ~}~%" a)
　　(princ (reduce (lambda ($0 $1) (concatenate 'string $0 ", " $1)) a))
)
; java, ruby, rust
; java, ruby, rust

**デフォルトの名無しさん** · 2018/04/21(土) 22:20:27.52

>>929
＞てかrubyの%wって何のためにあるの？

まさに今回のような場合に配列リテラルを作るためのものだろ
各要素が所与なのになんでわざわざ繋いだ文字列リテラル書いてsplitしようとするの？

**デフォルトの名無しさん** · 2018/04/21(土) 22:36:51.73

>>928 ruby
puts a[0...-1].inject(''){|r,s| r << s << ',' } + a.last
puts a.inject(''){|r,s| r << s << ',' }.chop
puts a.map{|s| [s, ','] }.join.chop
b = a.join
a[0...-1].inject(0){|r,s| r += s.length + 1; b = b.insert(r-1, ','); r }
puts b

**デフォルトの名無しさん** · 2018/04/21(土) 22:45:40.32

>>929
Perl だと
@week = qw(Sun Mon Tue Wed Thu Fri Sat)

**デフォルトの名無しさん** · 2018/04/21(土) 23:51:06.09

>>931
今回のような？？
今回の問題文、「文字列の配列をカンマ区切りで表示せよ」ってなってんだが…
スペース区切りの文字列から始めてどうする。
それじゃ%wで配列にするまでもなく正規表現でスペースをカンマに置換すればいいじゃん。

**デフォルトの名無しさん** · 2018/04/22(日) 02:37:42.05

>>928
Kotlin
https://paiza.io/projects/ZW2Hjc9tfnlrMwqvblaKlw
文字列は1行づつ入力から読んで MutableList に add して終わったら Array に変換して文字列の配列にしている。

**デフォルトの名無しさん** · 2018/04/22(日) 02:46:31.80

>>928 javascript

var langs = ['javascript', 'python', 'go']
console.log(langs.join()) //ES5
console.log(langs.reduce((acc, elm) => `${acc},${elm}`)) //ES2015
langs |> ary => ary.join() |> console.log //ESNext
console.log((langs + ',').slice(0, -1)) //ES5

**デフォルトの名無しさん** · 2018/04/22(日) 03:13:36.97

一番かんたんなの忘れてた
console.log(langs.toString())
console.log(langs + '')
console.log(`${langs}`)

**デフォルトの名無しさん** · 2018/04/22(日) 03:19:59.16

console.log(String(langs))
langs |> String |> console.log //ESNext

**デフォルトの名無しさん** · 2018/04/22(日) 06:29:12.88

>>928 Squeak Smalltalk

| arr |
arr := #(java rust ruby).
arr asCommaString. "=> 'java, rust, ruby' "
arr asCommaStringAnd. "=> 'java, rust and ruby' "

String streamContents: [:ss |
arr do: [:each | ss << each] separatedBy: [ss << ', ']
]. "=> 'java, rust, ruby' "

**デフォルトの名無しさん** · 2018/04/22(日) 10:27:04.31

>>928
join一発でできるようなことをわざわざ問題にするなよ...

**デフォルトの名無しさん** · 2018/04/22(日) 12:09:53.80

誰かにコードを教えてもらう為に「お題」と言ってるだけじゃね？

**デフォルトの名無しさん** · 2018/04/22(日) 13:43:01.03

不快に思うなら取り組まなきゃいいだけ

**デフォルトの名無しさん** · 2018/04/22(日) 13:54:40.34

サムダウンボタンがあったら容赦なく押していたよ

**デフォルトの名無しさん** · 2018/04/22(日) 13:57:18.11

数学センセが嫉妬かみっともない
開口の広いお題が繁盛すんのは当たり前