プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2016/12/01(木) 16:58:30.97

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

前スレ
プログラミングのお題スレ Part8©2ch.net
http://echo.2ch.net/test/read.cgi/tech/1444216746/

【出題と回答例】
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/

宿題は宿題スレがあるのでそちらへ。

**デフォルトの名無しさん** · 2017/12/03(日) 13:08:19.92

みなさんプログラム作るの早いですね

>>774
一応a、b、cの条件は、このようになると思います。
0 <= a <= 9
0 <= b <= 8
0 <= c <= 10 - b - 1

bとcは0では意味がないので、こっちのほうがいいのかな
0 <= a <= 9
1 <= b <= 8
1 <= c <= 10 - b - 1

**デフォルトの名無しさん** · 2017/12/03(日) 13:12:58.80

>>776
すみません、間違えました、abcじゃなくてbcdですね
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - b - 1

**デフォルトの名無しさん** · 2017/12/03(日) 13:34:35.32

>>777
すみません、訂正の訂正です。dは10-c-1ですorz
0 <= b <= 9
1 <= c <= 8
1 <= d <= 10 - c - 1

**デフォルトの名無しさん** · 2017/12/03(日) 17:47:25.64

Linked list 使うと楽そうな感じするな

**デフォルトの名無しさん** · 2017/12/03(日) 18:26:21.27

>>770,771
せっかくなのでこのテストデータを作って検証してみましたが、全部合っていました、さすがですね
それにしても他人のプログラムって動かすことはできても、理解するのは困難ですね
>>772
Mathematicaは残念ながら持っていないので検証できませんでした

b = 8 c = 6 d = 2 a = 8901236745
b = 4 c = 3 d = 2 a = 0123784569
b = 4 c = 5 d = 2 a = 8123904567
b = 2 c = 5 d = 2 a = 0178234569
b = 0 c = 5 d = 3 a = 5670123489
b = 9 c = 3 d = 4 a = 3459016782
b = 5 c = 1 d = 7 a = 1253467890
b = 4 c = 6 d = 2 a = 8923014567
b = 6 c = 7 d = 2 a = 8901253467
b = 7 c = 5 d = 4 a = 5789016234
b = 4 c = 2 d = 2 a = 0123674589
b = 6 c = 4 d = 5 a = 4678950123
b = 7 c = 4 d = 4 a = 4789056123
b = 4 c = 5 d = 4 a = 6783901245
b = 8 c = 1 d = 5 a = 1238456790
b = 0 c = 2 d = 6 a = 2345670189
b = 3 c = 7 d = 1 a = 9120345678
b = 9 c = 4 d = 2 a = 4901256783
b = 8 c = 3 d = 6 a = 3456890712
b = 2 c = 5 d = 3 a = 0178923456

**デフォルトの名無しさん** · 2017/12/03(日) 20:16:05.68

>>768
ruby ワンライナー
https://ideone.com/sXGhCG

**デフォルトの名無しさん** · 2017/12/03(日) 20:37:58.61

>>780
お、あんた偉いな。
出題者でちゃんと答え合わせやってくれる人が稀でレスポンス薄いことが多いんだよ。
ちゃんと動いてよかったよ。

**デフォルトの名無しさん** · 2017/12/03(日) 20:51:48.60

>>774
自分は10超えてもらったら困るなぁ。
10っていうか、配列の要素数だな。
修正はそんなに難しくないけど。

**デフォルトの名無しさん** · 2017/12/03(日) 23:00:23.32

>>781
1行プログラムすごいですね
さすがスクリプト言語

>>782
そうなんですか、でもいろいろな言語で回答されるから、出題者も大変かもしれないですね
私は問題の意味すらよく分からないことが多いので、もっぱら見る専ですが

**デフォルトの名無しさん** · 2017/12/04(月) 02:36:11.06

>>768
これでいいのかなあ？
Perl で書いた。
https://paiza.io/projects/ncIY4LljeBahWZPJpd8ZPQ

**デフォルトの名無しさん** · 2017/12/04(月) 06:47:18.44

>>785
b = 6、 c = 6、 d = 2
のときの動作がおかしいようです
8901452367
となるはずが
0167892345
となっており、移動する"678901"の並びが崩れてしまっています

**785** · 2017/12/05(火) 02:32:35.27

>>786
問題勘違いしてました。素直にぐるぐる回すように修正しました。
https://paiza.io/projects/ncIY4LljeBahWZPJpd8ZPQ
下の「入力」タブの方にスペース区切りで b, c, d の値を1行づつ並べて入れてから実行させると「出力」に結果が出ます。
とりあえず >>768 に書いてある値を入力にセットしたところ出力は同じになりました。

**デフォルトの名無しさん** · 2017/12/05(火) 20:55:13.95

>>787
入出力の確認をしただけですが、今回は問題ないようです
paiza使うと簡単に確認できて便利ですね

**デフォルトの名無しさん** · 2017/12/05(火) 21:48:50.31

>>768
僕の頭だとどうしても右端から左端に行くときの動きがイメージできないので、解答締め切ったあとでもいいのでちょろっと教えてもらえると嬉しいです
上3つまではわかるけどそこから先がそもそも答えにたどり着けない……

**デフォルトの名無しさん** · 2017/12/05(火) 23:47:14.24

>>789
ヒント。
(インデックス++)%配列の長さ
を繰り返すとどうなりますか？%は余剰デス。

**デフォルトの名無しさん** · 2017/12/06(水) 00:25:49.49

>>789
上の３つまでは分かるということなので、３つめのcの値を一つずつ増やしてみると、こんな感じになります
"7"、"78"、"789"、"7890"と並ぶ数値が増えていっているのが分かると思います
c+d の合計は9が最高なので、これ以上cを増やすにはdを減らさなくてはなりません
b = 7 c = 1 d = 5 a = 1273456890
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 3 d = 5 a = 3478956012
b = 7 c = 4 d = 5 a = 4578906123

今度はcを2に固定して、dの値を一つずつ増やすと、こんな感じになります
"78"の並びが一つずつ右へずれていっているのが分かると思います
c+d の合計は9が最高なので、これ以上dを増やすにはcを減らさなくてはなりません
b = 7 c = 2 d = 1 a = 0123456978
b = 7 c = 2 d = 2 a = 8123456907
b = 7 c = 2 d = 3 a = 7823456901
b = 7 c = 2 d = 4 a = 2783456901
b = 7 c = 2 d = 5 a = 2378456901
b = 7 c = 2 d = 6 a = 2347856901
b = 7 c = 2 d = 7 a = 2345786901

こんな感じで分かるでしょうか？私も自分の頭で考えると混乱しますw

**デフォルトの名無しさん** · 2017/12/06(水) 00:31:57.65

自分の考え方は、配列の一部を切り取ってパッディングするんだけど、
まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。
すると、配列の後ろにはすでにパディングが終わった数列のができてる。
で切り取って削除して尻尾にくっつける。
で、さっき回した分を戻してやると完成。

という方法で、>>770を解いた。

**デフォルトの名無しさん** · 2017/12/06(水) 00:32:05.18

自分の考え方は、配列の一部を切り取ってパッディングするんだけど、
まず配列を回転させて切り取る第0インデックスを配列の最初に持って来る。
すると、配列の後ろにはすでにパディングが終わった数列のができてる。
で切り取って削除して尻尾にくっつける。
で、さっき回した分を戻してやると完成。

という方法で、>>770を解いた。

**デフォルトの名無しさん** · 2017/12/06(水) 00:32:32.42

あちゃー
二重投稿になったある。
そんなに大事でもないのだけど。

**デフォルトの名無しさん** · 2017/12/06(水) 00:38:22.54

C++は比較的不自由な言語なので頭使うのは鍛えられるよ。
パーツが少ないのでほとんど自作しないといけない。

**デフォルトの名無しさん** · 2017/12/06(水) 00:46:18.89

コンパイルが必要とかでスクリプト系の言語より
使うことに不便があるかもしれないが、
できるアプリが自由で高速・軽量！

ライブラリもＳＴＬやboost以外にも、探せば便利なのがいっぱい。

**デフォルトの名無しさん** · 2017/12/06(水) 01:07:01.76

よそのライブラリ使うとイデオンで動かないからなぁ。
まぁ、業務ではライセンスに合ったものを使えばいいよ。

**デフォルトの名無しさん** · 2017/12/06(水) 02:01:03.49

>>789
塊が移動すると考えれば良い。
例えば 7, 4, 2 だとすると、 789 と先頭の 0 が移動する塊だ。
で、ちょっと分かり易くするためにこの塊を伏せて * で書くとするとこうなる。

*123456***

それでこの塊を右に一つずらす。その時に1は食われて尻尾から吐き出される。

**234561**

移動量2なのでもう一回右にずらす。すると2が食われて尻尾から吐き出される。

***345612*

それでは * から 7890 に戻してみよう。

8903456127

できあがり。

**デフォルトの名無しさん** · 2017/12/06(水) 02:58:25.26

>>793
これ間違ってるな。
最後尻尾にくっつけるんじゃなくて、適所にインサートだった。
で戻す。
書いた日から時間たってるからすまん。

**デフォルトの名無しさん** · 2017/12/06(水) 08:41:18.93

>>790
>>791
>>798
ありがとうございます
やっと理解できました
がんばって解いてみます

**デフォルトの名無しさん** · 2017/12/06(水) 17:48:37.81

log2だけど、これ使うといいらしいよ。分割統治法のBSA法というやつらしい。
2個ずつの積を繰り返すことで計算回数が減らせる。

{{1, a0}, {0, r}}*{{1, a1}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/rであり、

{{1, a0}, {0, r}}*{{1, a1}, {0, r}}*{{1, a2}, {0, r}}を[ [○,P], [○,Q] ]とおくと
r*P/Qはa0 + a1/r + a2/r^2。

上の式を実際に計算してみる。
http://www.wolframalpha.com/input/?i=%7B%7B1,+a0%7D,+%7B0,+r%7D%7D*%7B%7B1,+a1%7D,+%7B0,+r%7D%7D*%7B%7B1,+a2%7D,+%7B0,+r%7D%7D

**デフォルトの名無しさん** · 2017/12/06(水) 21:09:44.45

>>801
普通のlog 2の計算には使えても
>>680 には使えないかと

**デフォルトの名無しさん** · 2017/12/07(木) 00:07:53.25

>>731 から更に縮まりました
もう誰も興味が無いかも知れませんが

コードいる？

**デフォルトの名無しさん** · 2017/12/07(木) 09:24:10.80

>>801でできるはずだ。やってみる

**デフォルトの名無しさん** · 2017/12/07(木) 10:09:03.65

n=10^10で19.28秒にまで縮めた
n=10^13くらいまでなら夜寝てる間に終わる

>>804
期待してます！

**デフォルトの名無しさん** · 2017/12/07(木) 15:54:52.13

804だけど考えてみたら面倒なんだな。
有理数(整数)で完全に求めてから割り算するのは時間かかりそうだから、
展開も、割り算も、有限で打ち切って求める精度がでるようにするのが普通?

**デフォルトの名無しさん** · 2017/12/07(木) 18:15:20.36

お題
辺の長さが10,000以下の整数である直方体について
すべての面の対角線も整数となるものを全て求める

**デフォルトの名無しさん** · 2017/12/07(木) 19:52:07.65

対角線を出す式を忘れたのだ～。
数学って難しい。

**デフォルトの名無しさん** · 2017/12/07(木) 20:10:49.23

>>807
答えは浮かんだけど、
手元にインタプリタがないので書けない。

**デフォルトの名無しさん** · 2017/12/07(木) 20:38:16.84

>>808
えーと、ほら、三角形の三角形のアレ

**デフォルトの名無しさん** · 2017/12/07(木) 21:23:21.04

>>805 のソース一式とexeです。
>>680 の回答となります。
http://fast-uploader.com/file/7068204781334/

実行ファイルは、拡張子をexe_からexeに変えてください。
OSはWindows 64bit Vista以降
CPUはHaswell以降
で動作します。

**デフォルトの名無しさん** · 2017/12/07(木) 21:26:37.34

作ってみたけど、オッセ―。
なんか数学的にやらないとダメぽ。

>>810
検索したら出てきた。
ただのHYPODだった。

**デフォルトの名無しさん** · 2017/12/07(木) 21:34:41.35

あ～ん。足し算10兆回かかるとかむりげーじゃ。
どうしようかこれ。

**デフォルトの名無しさん** · 2017/12/07(木) 21:40:02.60

>>807
https://ideone.com/5Tu6fx
C++。ギブアップ。遅すぎだ。
デバッグ不完全だからそこを忘れないで。
多分1日かけても終わらないと思う。

**デフォルトの名無しさん** · 2017/12/07(木) 21:40:16.73

>>807
特に大きな工夫もなく普通に3重ループで出来ましたよ
151個かな

**デフォルトの名無しさん** · 2017/12/07(木) 21:42:04.13

https://ideone.com/09jmll

**デフォルトの名無しさん** · 2017/12/07(木) 21:44:43.70

>>807 Java
https://ideone.com/iYsIgq
こうでいいのけ？

**デフォルトの名無しさん** · 2017/12/07(木) 21:48:20.51

ぶ。おれは・・・いったい・・・。
だめだなぁ。才能ないなぁ。

**デフォルトの名無しさん** · 2017/12/07(木) 22:07:39.64

>>817の意味がわからん
解説よろしく！

**デフォルトの名無しさん** · 2017/12/07(木) 22:27:00.87

>>801のように積へ変換した場合、どれ位の精度・桁数が必要なのか簡単にわからないな。
>>801でやると、誤差ありの巨大な数同士の掛け算になって、その結果誤差が拡大する。
和のままやると、適当に2ベキをかければ、各項の整数部分だけ計算すればよさそうだけど。
>>801は桁を十分にとったとしても、2進10桁以上の部分も計算途中で無視はできないか。

**デフォルトの名無しさん** · 2017/12/07(木) 22:32:10.24

グア。題意勘違いしてた。
直方体の対角線はいらんのか。うおー。
ばかばかー。

**デフォルトの名無しさん** · 2017/12/07(木) 22:57:05.97

>>807
https://ideone.com/Uipgvw
C++。書き直したら、>>816のパクリ見たくなった。
そしてそれでも遅いとかあかんなー。
うーん。なんでなんだろう・・・。

**デフォルトの名無しさん** · 2017/12/07(木) 23:06:46.33

>>820
普通に、求めたい精度＋α の精度を保てば十分かと
演算回数はlog(n)のオーダーなので
普通にlog(2)を求める時には使える手法

**デフォルトの名無しさん** · 2017/12/07(木) 23:06:47.69

>>819
https://ideone.com/ZCINKa
適当にコメント付けた

**デフォルトの名無しさん** · 2017/12/07(木) 23:18:28.32

物体は表面だけでなく無数の内面を有するという考えは絶対に存在する
一方で全てを表面でしかとらえない人の存在も否定できない

**デフォルトの名無しさん** · 2017/12/07(木) 23:24:59.96

このポエムをどうプログラミングしろと？

**デフォルトの名無しさん** · 2017/12/08(金) 03:20:08.11

>>807 Ruby
https://ideone.com/3BPK13
20秒程かかってしまう

**デフォルトの名無しさん** · 2017/12/08(金) 12:45:22.72

log2は>>801でもできそうだ。
積の先頭ほど精度が必要で、無視できる上限・下限を積の位置で可変にするか、
最初の積の計算で必要な精度をすべてに適用するかでいけそう。

**デフォルトの名無しさん** · 2017/12/08(金) 14:42:05.63

>>817
これパクってstd::bitset<10001>でやったら動かないかな
nextSetBitだけ作れば動きそう

**デフォルトの名無しさん** · 2017/12/08(金) 17:20:05.13

>>829
やってみた
いろいろ怪しいが速度は強烈に速いな

https://ideone.com/d4dU1Q

**デフォルトの名無しさん** · 2017/12/09(土) 00:08:31.54

>>828
時間的に無理だろって話

**デフォルトの名無しさん** · 2017/12/09(土) 02:59:25.21

>>807
これでいいかな？
Kotlin で書いた。しかしpaiza.ioの制限なのか、何故か import kotlin.math.* がエラーだったので java.lang.Math の関数を使っている。
https://paiza.io/projects/ImbYdf3NSWgW-zj8Ke6cDw

**デフォルトの名無しさん** · 2017/12/09(土) 09:05:25.04

お題
10,000以下の三角形数をもとめる

**デフォルトの名無しさん** · 2017/12/09(土) 09:42:44.72

>>833
三角数だよね？
.js
https://ideone.com/WZBIFF

**デフォルトの名無しさん** · 2017/12/09(土) 10:35:24.71

>>833　ruby
i,j=0,-1;p i while(i+=j+=1)<10000

**デフォルトの名無しさん** · 2017/12/09(土) 21:40:06.26

>>833 Brainf**k ワンライナー(笑)
https://ideone.com/TyMeco
遅すぎて8bitまでしか計算できなかった

**デフォルトの名無しさん** · 2017/12/09(土) 23:46:47.87

ideone.comはたいして最適化しないBrainf**k処理系だからな

**デフォルトの名無しさん** · 2017/12/10(日) 00:50:34.10

>>833
1+2+3+... だよね? じゃあこうだ。
perl -e '$i=0;$n=1;while(($i+=$n)<=10000){print"$i\n";++$n}'

**デフォルトの名無しさん** · 2017/12/10(日) 00:52:24.37

>>833
while じゃなくて for にするとこう。
perl -e 'for($i=0,$n=1;($i+=$n)<=10000;++$n){print"$i\n"}'

**デフォルトの名無しさん** · 2017/12/10(日) 08:00:18.20

>833 R
cat(cumsum(0:140))

**デフォルトの名無しさん** · 2017/12/10(日) 09:05:44.08

>>801は精度管理の手間を考えたら、そのまま級数計算するのと大差ないと諦めたが。
こうすれば割り算の小数計算がほぼでないからいいのでは?　既に実装済?

an = 1/n、r = 2として、Σ an/r^n を定数C倍したやつの整数部分の取り出し。
C*anを再びanとおく。
Σ an/r^n
= a2/r^2 + a4/r^4 +・・・+ aN(2)/r^N(2) (添え字は2の倍数を動く)
+ a3/r^3 + a9/r^9 + a15/r^15 + ・・・+ aN(3)/r^N(3)
+ ap/r^p + ・・・+ aq/r^q + ・・・ (pは素数、qはp未満の数で割り切れないpの倍数)

= 1/N(2)r^N(2)　*　( N(2)*a2*r^(N(2)-2) + ・・・ + N(2)*aN(2) )　+ ・・

この分子部分は、各項、整数でそのまま計算しても>>801でも速くなるはず。

**デフォルトの名無しさん** · 2017/12/10(日) 21:52:17.18

>>841は添え字に被りが出ていて間違えてた。

**デフォルトの名無しさん** · 2017/12/10(日) 22:07:36.99

やってみて時間教えて

**デフォルトの名無しさん** · 2017/12/10(日) 22:08:42.09

>>805 >>811 を抜ける？

**デフォルトの名無しさん** · 2017/12/10(日) 22:22:45.57

秒数ではCPU依存するから正確に比較できない。
掛ける2だけのループを10^10回するだけでも19秒では終わらない。
無料のideone　codepadなどの実行可能時間以内にできる範囲とか、
ベースとなる簡単なコード、関数の何倍時間がかかるかなどだと比較できるけど。

**デフォルトの名無しさん** · 2017/12/10(日) 22:36:08.95

演算回数の見積りは？

**35歳** · 2017/12/11(月) 02:10:45.96

Bronze取りました

**35歳** · 2017/12/11(月) 02:11:34.08

Bronze取りました

**デフォルトの名無しさん** · 2017/12/11(月) 04:58:28.24

くだらん話かも知れんけど
竹内関数のメモ化

https://ideone.com/sVhke1

これはC++によるものだけど、C++や他の言語でもっと高速に書く方法はあるか？

**デフォルトの名無しさん** · 2017/12/11(月) 05:19:34.19

あ、ちなみにideoneの結果は間違っている
多分スタックオーバーフローしている
100, 50, 0の場合は答えは100

**デフォルトの名無しさん** · 2017/12/11(月) 05:38:23.74

>>849
constexprにすれば実行時はほぼ計算無しにできると思う。
コンパイル時間半端ないけど。

**デフォルトの名無しさん** · 2017/12/11(月) 05:45:19.55

ところで、いくらメモ化してても5回しか呼ばれないってことがあるのか？って気はする。

**デフォルトの名無しさん** · 2017/12/11(月) 07:04:34.34

https://ideone.com/Y9WhRz
竹内関数constexprにしてみた。
ウチの環境だとこの辺のパラメータが限界っぽいかな。
100,50,0だとメモリ使い切るらしい。

**デフォルトの名無しさん** · 2017/12/11(月) 07:09:30.00

あら、コンパイルエラーになっちゃった。
VCだと通ったんだけど。もちろんステップ数とか設定はいじってるが。

**デフォルトの名無しさん** · 2017/12/11(月) 08:32:22.37

>>849
こんなのとか？

たらいを回すならHaskella
2006年04月07日 22:09
http://blog.livedoor.jp/dankogai/archives/50447103.html

**デフォルトの名無しさん** · 2017/12/11(月) 12:03:51.37

お題
6つの辺の長さが与えられた4面体の体積を求める

**デフォルトの名無しさん** · 2017/12/11(月) 13:07:53.63

お題
8つの辺の長さが与えられた超5面体の体積を求める

**デフォルトの名無しさん** · 2017/12/11(月) 14:29:31.82

お題
与えられた自然数を高々四個の四角数(平方数)の和で表せ

**デフォルトの名無しさん** · 2017/12/11(月) 14:35:19.85

>>856 Ruby
https://ideone.com/qbHExm
ただし四面体ABC-Dに対して入力の順序は
AB BC CA CD DA BD とする

**デフォルトの名無しさん** · 2017/12/11(月) 16:06:12.32

>>857
8つだと多胞体が一意に定まらないと思うんだが

**デフォルトの名無しさん** · 2017/12/11(月) 16:48:32.53

>>853
64bit環境でやったらスラッシング起きて＼(^o^)／

**デフォルトの名無しさん** · 2017/12/11(月) 16:53:24.07

>>860
じゃあ10個で

**デフォルトの名無しさん** · 2017/12/11(月) 17:03:18.77

>>862
１０でも足りないと思うんだけどひょっとして超五面体って五胞体のつもりで言ってる？

**デフォルトの名無しさん** · 2017/12/11(月) 17:31:58.31

4次元の5胞体

**デフォルトの名無しさん** · 2017/12/11(月) 17:32:53.55

5C2=10

**デフォルトの名無しさん** · 2017/12/11(月) 22:30:10.81

>>861
ウチはi6700メモリ8Gだな。20秒くらいボケーっとしてたらコンパイル完了する。
実実行より全然早い。

**デフォルトの名無しさん** · 2017/12/11(月) 23:43:41.01

>>866
んー32bitでコンパイルしてみるかな
64bitはマジ卍ヤバい

**デフォルトの名無しさん** · 2017/12/12(火) 00:19:40.23

>>866
悪い
VCで /constexpr:steps 1000000を付けてコンパイルしたら4秒ほどでコンパイルが終わった
多分/MPも付けてるからだと思う
実行結果は25になった

gcc 7.2.0 64bitだとどんどんメモリを食って行って最後にスラッシングが起きる
馬鹿正直な実装をしているからかも知れないね

VCの方がいろいろとメモリを食わないように工夫されてるのかも

Clangでも/constexpr:steps は -fconstexpr-steps という形でサポートされてるようだから
多分行けると思う
メモリ64G積んでるし

**デフォルトの名無しさん** · 2017/12/12(火) 01:27:56.58

>>868
いいマシーンだな。
まぁ、ウチはあれくらいで資源尽きちゃうけど、メモリ64Gもあったらもっと行けるな。
気が向いたらどうぞ。

**デフォルトの名無しさん** · 2017/12/12(火) 04:08:00.08

>>858 Java
https://ideone.com/ND4D2n

**デフォルトの名無しさん** · 2017/12/12(火) 22:52:21.86

以下のURLのように、同じ色の点同士をつなぐゲームがある。
https://play.google.com/store/apps/details?id=com.bigduckgames.flow

N×Mの2次元配列が与えられる。配列の各要素は半角英字('a'-'z')または'*'である。
半角英字は色付きの点を表し、'*'は空のマスを表す。
'*'以外の文字は、配列中に必ず2個ずつ存在する。

このパズルの解を一つ出力せよ。
・'-'は左右のマスをつなぐ
・'|'は上下のマスをつなぐ
・'.'はマスをつながない

解がない場合は"No solution"と出力せよ。

[input]
***rg
**bg*
r****
ob*yo
****y

[output]
*-*-*-r.g
|.......|
*.*-b.g-*
|.|......
r.*.*-*-*
..|.|...|
o.b.*.y.o
|...|.|..
*-*-*.*-y

**デフォルトの名無しさん** · 2017/12/15(金) 09:30:54.91

>>841
やってはないけど、そもそもこれ間違ってるのと、同じような発想でやるとしても
全ての素数での分類ではなく、3分割くらいのほうが効率がいいのと、
Σ　(2の倍数)　+　Σ　(3の倍数かつ2の倍数でない)　+　Σ　(2と3で割り切れない)　
分割する事もなく、N項の和だとしたらNの階乗か分数をなくせる最小公倍数かけてもいい。それだと掛け算もしくは割り算がいくつも出てくるが。

**デフォルトの名無しさん** · 2017/12/16(土) 14:04:43.43

>>871
等幅フォントで表示しているエディタにコピペしてようやっと何を言わんとしているか分かった。
それってマスとマスの間に - または | を入れて繋ぐってことでいいんだよね? で、つながない所がピリオドだと。
(まあ等幅フォントのASCIIでやるならそれしか方法ないとは思うけど)。

**デフォルトの名無しさん** · 2017/12/16(土) 14:07:59.25

しかしピリオドは

**
**

の時に

*.*
...
*.*

のようになって中央のピリオドが本来なら不要なものになるわけだが、それはスペースでなくても良いのかな？
まあただの幅合わせだからどうでもいいものではあるが。

**デフォルトの名無しさん** · 2017/12/17(日) 12:04:31.10

>>801 の方法で出来ると書いてるけど
結局誰もやってないのか

個人的には(高速には)出来ないと思っている

**デフォルトの名無しさん** · 2017/12/17(日) 12:18:14.72

>>871
課題じゃなくて
単にソルバーの作成依頼でしょ