プログラミングのお題スレ 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/03(火) 23:39:30.66

まさかな…

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

>>513
そのわりには>>469に至るまで出てきてないわけだが
コロンブスの卵にケチ付けた奴みたいだな

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

>>515
1,1,1の場合、0個で良いのか？

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

>>519
ググるような問題か？
普通に義務教育を出てれば一瞬でわかると思うのだが

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

>>522
「小さいな順」ってどっちだろうね？
単調増加か単調非減少か
私は単調増加だと思ったから答えは2個
普通のソートだと単調非減少だから単調増加？

どっちにしろアルゴリズムは大して変わらん

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

>>523
義務教育でlogはやら無いぞ
何分でコーディング完了して動作確認までいったのよ

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

logなんて使わん

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

素因数分解を習えば十分

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

>>526
何番のお台の話をしてるんだよ
ずれてるぞボケが

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

ずれたとしたら俺のせいではない
>>519か>>525が悪い

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

いや、お前が悪い。きっぱり

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

んで、お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ

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

>>519は>>459の問題であることは明らか

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

log使ってんじゃん

普通に義務教育を出てれば一瞬でわかると思って
お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ
上の方のレスでどれがお前の回答よ

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

>>531
簡単すぎて書く気にもならんレベル
logなんか使わん

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

>>506にlogなんか出て来ないだろ？

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

>>534
じゃあlogを使わない計算量の多い方法でもいいよ。

義務教育を出てれば一瞬でわかる問題を
お前が一から考えて自力で解いてコーディングして動作を確かめ
書き込んだレスは上の何番だよ

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

人のレスをを見たら簡単だと印象を持ったんだろ
自力ですぐには解けなかったんだろ

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

そもそもlogを使ったコードなんて出てきたか？

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

ぼけがｗ

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

考え方は>>506
以上

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

もう構うなよ

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

>>524
順に並べるということから同値の連続は許して広義の単調増加でよいのでは

工夫のない力技のを描いてみた
https://www.onlinegdb.com/ByuL67-iG

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

↑
一応2行ほど費やしてほんのちょびっとだけ枝刈りしてある

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

なら自分も広義単調増加で
LISだし二分探索のO(NlogN)で実装
https://ideone.com/kN5UFU

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

>>544
やっべLISで作ったから答えがLISのままだわ
n-出力に脳内変換しておいて

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

>>515
Kotlin
後ろから手前に見て行くように作ってみたが、これで良いのか？
https://paiza.io/projects/_o2ryjyVw3lQI2iKrDRf_A?language=kotlin

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

>>546
広義単調増加だよな？
そのプログラムだと
1, 3, 6, 8, 9, 10, 6, 5, 6, 7
が5で出力される(解は1,3,6,6,6,7より4)

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

>>515
間引きする関数というか方法は？サンプルもないのにどうしろと。

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

ほらサンプル

元のデータ 1, 3, 6, 8, 9, 10, 6, 5, 6, 7
これの 1, 3, 6, (8, 9, 10,) 6, (5,) 6, 7
括弧内の4つを間引けば昇順1,3,6,6,6,7になる
最小の間引く個数は4

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

>>549
1, 3, 6, 8, 9, 10, (6, 5, 6, 7)
これでいけない理由は？

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

>>550
そっちでもいい
答えは同じだから

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

>>551
残るものが変わってくるんだから、たまたま同じだったではすまんだろう。

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

たまたまじゃなくてどちらでも同じだから良いって言ってるんだよ
最小の個数が算出されれば良いんだよ

>>542を例にして説明するとv1とv2の長さが等しいとき、
選び方によって間引方は変わるがどちらを選んでも
同じ答え(個数)になるからどちらでもいい

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

「選び方」というのは等しいときv1を使うかv2を使うかってことね

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

主観がないな。

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

ただの荒らしだったか

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

まぁいいわ。説明が悪いとだけ言っとくわ。

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

http://arison.jp/wordpress/wp-content/project_comedy_l.gif

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

じゃー、ソートすれば常に0だな。
おしまーい。

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

これ、プログラムのお題じゃなくてイジワル問題ってやつだ。
一応間引くとは言ったけど、どのように間引きたいかは書いてない。
それを考えろっていうもんだいで、じょうけんとしては何もだされていない。
べつに大きくしてもよい。
が、大きくする必要性もないので、条件内でやる最善手がソートして昇順にするだけででも満たされうる。

以上。

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

https://ideone.com/G4cjeS
C++。これが間違ってるんだったらその理論を聞きたい。

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

思想でも読んでるのかなぁ。

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

なんだその、｢牛乳を1個買ってきて。卵があったら6個買ってきて｣と言われて卵があったから牛乳を6個買ってくるような行動
リアルでこんな奴いるんだな……
間違ってるわけではないのが余計質悪い

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

>>563
ん？だから説明が悪いっていのを体現しただけ。
>>558　で書いてるでしょ。
多分思想問題なんだよこれ。

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

例えばね、例えば。
この数字が暗号で間引くと人が死ぬとかいうシチュエーションでそもそも間引く必要あるの？っていう趣旨返しなわけ。

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

与えられたデータが数列とも限らないし勝手に解釈して好きなように作る以外にやりようがない問題
自由度が大きい問題はあらゆる答えが正解ともいえるから一つの正解にたどり着く過程を楽しむ数学好きとかには不評だろう

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

おいおいおいおい
勝手に解釈して好きなように作るしかない問題(←否定的な表現)だからあらゆる答えが正解だ、というの？

これは「どう解釈しても構わないから好きなように答えれば良い問題」っていうんだよ。

例えばソートのアルゴリズムだって別に数値かどうかなど決めずとも考察も品評もできる
「比較回数だけでいうならo(1)のバケツソートが最高。はい論破」とか言うのも自由
答えが一個ならただの問い、クイズだよ

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

[[[[[[][}[[[ [ {} [] ]]][ [[ [

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

暗号か？

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

C言語
なんか>>544とほとんど同じになってしまった
https://ideone.com/xraUUB

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

>>556
荒らしっていうかさ
その子はこのスレにながく張り付いてる
無職でかつガイジ
かわいそうな子だから放置しといてあげて

**デフォルトの名無しさん** · 2018/04/05(木) 00:22:00.99

A(間引く)の処理の後にB(小さい順に並べる)の処理をすると読んでしまったのは内緒

**デフォルトの名無しさん** · 2018/04/05(木) 22:33:01.28

お題
以下の配列pで与えられるツリー構造を図示せよ
・pの要素数はN
・p[i]はノードiの親ノードを表す
・p[i]=-1の場合、ノードiは根ノードである
・pに含まれる-1の数はちょうど1つ

[input]
1 2 -1 0 0 1 1 2

[outupt]
2
|-- 1
| |-- 0
| | |-- 3
| | `-- 4
| |-- 5
| `-- 6
`-- 7

**デフォルトの名無しさん** · 2018/04/06(金) 06:25:51.13

p[0]=1
p[1]=0

**デフォルトの名無しさん** · 2018/04/06(金) 06:27:10.11

p[2]=-1

**デフォルトの名無しさん** · 2018/04/06(金) 06:40:00.16

連結ではない <===> ループが存在する

**デフォルトの名無しさん** · 2018/04/06(金) 08:57:39.15

>>573
https://ideone.com/u2CqvF

**デフォルトの名無しさん** · 2018/04/06(金) 11:36:10.59

お題にツリー構造って明記されてるから閉路は無いのでは

**デフォルトの名無しさん** · 2018/04/06(金) 12:54:56.14

条件には書いてない
根が1個という条件だけ中途半端に書いてある
はて

**デフォルトの名無しさん** · 2018/04/06(金) 13:12:46.44

「～で与えられるツリー構造」

**デフォルトの名無しさん** · 2018/04/06(金) 13:39:17.95

条件には書いてない！（書いてある）
目か頭かどちらかあるいは両方おかしい。
頭の方ならこれからエクストリーム言い訳が来るだろうから楽しみにしてるｗ

**デフォルトの名無しさん** · 2018/04/06(金) 14:45:17.05

「解無し」という答えに文句言ったくち？

**デフォルトの名無しさん** · 2018/04/06(金) 16:12:43.87

>>577以外のやり方以外のやり方考えるの面倒だな。
てか、いきなり最適解が出てしまった感あるな。
他の言語に書き換えるのは簡単だが移植しただけになってなんとなく無意味。

**デフォルトの名無しさん** · 2018/04/06(金) 17:02:31.80

再帰じゃない解とか

**デフォルトの名無しさん** · 2018/04/06(金) 17:09:52.76

階層構造なのに再帰使わないのは辛いなあ。自分でデータを積む事になるだろうし。しかしそれぐらいしかないか？

**デフォルトの名無しさん** · 2018/04/06(金) 17:12:50.15

そだね
なにかアクロバティックな解法でもあれば面白いんだけど凡才で思いつけん

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

お題
5以上の素数が与えられたとき1番近い6の倍数を求める

**デフォルトの名無しさん** · 2018/04/06(金) 18:13:50.95

5以上の素数しか与えられない？
素数以外も与えられることもある？

**デフォルトの名無しさん** · 2018/04/06(金) 18:15:51.07

日本語読めないのか？

**デフォルトの名無しさん** · 2018/04/06(金) 18:17:05.45

(n+3)/6*6 かな

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

素数列挙がメンドだから日本語で。
素数を6で割って、ラウンドして1プラスして、6倍する。
であってる？

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

四捨五入の方がいいか？

**デフォルトの名無しさん** · 2018/04/06(金) 19:32:58.29

>>588
5以上の素数が与えられなかった場合の動作については何も書かれてないので
好きに仕様を決めれば良いんだよ

**デフォルトの名無しさん** · 2018/04/06(金) 19:36:58.77

エラー表示
動作不定
与えられるまでまつ
など

>>589
仕事だとそういうところでもめたりするのだ
今回は仕事じゃないので好きに決めればいい

**デフォルトの名無しさん** · 2018/04/06(金) 19:41:53.07

それ言い出したら、言語によっては実数も文字列も行列も与えられるし、きりがないよ

**デフォルトの名無しさん** · 2018/04/06(金) 19:47:17.56

int q587(int p){//pは5以上の素数
return (p % 6==1)? 6*(p/6):6*(p/6+1);
}

**デフォルトの名無しさん** · 2018/04/06(金) 19:51:17.88

>>595
「今回は仕事じゃないので好きに決めればいい」

**デフォルトの名無しさん** · 2018/04/06(金) 20:02:53.64

>>591>>592
7が与えられたら結果はいくつになるそれ？

**デフォルトの名無しさん** · 2018/04/06(金) 20:08:15.85

>>587
n - (-1)^(n%6/5)

**デフォルトの名無しさん** · 2018/04/06(金) 20:13:35.02

>>587
こっちの方がいいか。除算は切り捨て
n - 1 + n%6/5*2

**デフォルトの名無しさん** · 2018/04/06(金) 20:34:39.42

>>587 Ruby
-~n/6*6

**デフォルトの名無しさん** · 2018/04/06(金) 20:46:11.62

n+1 ってのを -~n と短縮してるわけか
面白い

**デフォルトの名無しさん** · 2018/04/06(金) 21:04:40.65

一番近くない答えを出す回答が混ざってるのが面白い

**デフォルトの名無しさん** · 2018/04/06(金) 21:06:03.82

面白いか？
どっちも

**デフォルトの名無しさん** · 2018/04/06(金) 22:19:03.40

お題
整数n(0 <= n < 2^32)を英語で表記する
0 => zero
134 => one hundred thirty four
1000000 => one million
4294967295 => ???

**デフォルトの名無しさん** · 2018/04/06(金) 23:06:37.46

その???のところどんな形式でもいいの？
それともtwo to the power of thirty two subtracted by oneじゃないとダメ？

**デフォルトの名無しさん** · 2018/04/06(金) 23:22:09.18

four billion なんちゃらだろjk

**デフォルトの名無しさん** · 2018/04/06(金) 23:56:30.88

>>605 Ruby

https://ideone.com/F3RT13

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

>>588
https://ideone.com/d3UrjB
C++。プライム検出をダメコードででっち上げて書いた。正直遅い。

**デフォルトの名無しさん** · 2018/04/07(土) 00:24:29.61

>>598
下がる方考慮してなかったから考慮したコード書いたよ。

**デフォルトの名無しさん** · 2018/04/07(土) 00:55:56.21

鈴木貫太郎
北海道大学　２種類の数字でできてるｎ桁の数字の個数
https://youtu.be/SHdUszy0qQs

2種類の数字だけでできている、4桁の数字は、いくつあるか？
答え、567

2種類の数字だけでできている、N桁の数字は、いくつあるか？
答え、81(2^(N-1) - 1)

N=5 の時も、求めて

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

>>611
普通に 81 * (2^(5 - 1) - 1) = 1215 なのに何を求めるの
10C2 * 5C2 - 9*5 + 10C2 * 10P2 - 9 * 10 = 1215 みたいに場合分けしてもう一度計算しろってことかね

**デフォルトの名無しさん** · 2018/04/07(土) 01:38:08.29

>>587
その問題って元の値が素数かどうかは関係ないのでは？
Perl だとnが正の整数なら int((n+3)/6)*6 の計算で出来てしまうと思うが。
/ の割り算が整数で出るような言語なら整数化も不要。(C言語で int n だった場合等)。

**デフォルトの名無しさん** · 2018/04/07(土) 01:39:34.76

素数は奇数だから、6 で割った余りのうち、1, 5 のみが素数になり得る。
つまり、6N + 1, 6N + 5 (6N ± 1)だけ。
6N + 3 は、3 の倍数になるので、素数にならない

この動画を参照

鈴木貫太郎
整数、素数、京都大学入試問題　数学
https://youtu.be/PCX6sqN9FhA

p, q が共に素数のとき、
p^q + q^p が素数になる、p, q をすべて求めよ

ヒント、どちらか一方は必ず、2 となる。
答え、(2, 3), (3, 2)

ちなみに、答えが合っていても、0点です。
それ以外に解が存在しないという、証明に加点される

**デフォルトの名無しさん** · 2018/04/07(土) 02:02:01.73

n = p^q + q^p, p <= q とすると
n >= 8 なのでnは奇素数
よって p = 2, q >= 3
q > 3 の時 n = 2^q + q^2 = 2 + 1 = 3 mod 6 で矛盾
q = 3 の時 n = 17 で必要条件を満たしている
よって (p, q) = (2, 3), (3, 2)

でこれをSATソルバーでも使って解けっていうのかね

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

>>605
Kotlin
https://paiza.io/projects/z6BKEqpdH_DuzQpj6TtxZg

色々細かいことやって英語に近づけたので少し複雑なものになってしまったような気もする。

**デフォルトの名無しさん** · 2018/04/07(土) 14:36:40.48

ttp://next.rikunabi.com/rnc/img/1820/o/0015904477.jpg
犯人は誰だ？

**577** · 2018/04/07(土) 23:23:36.77

>>577
訂正
https://ideone.com/yYE1Jb

[-1, 0, 1, 2] の出力が
0
└─ 1
│ └─ 2
│ │ └─ 3
となって間違った枝が伸びてました。

文字列を積みながら再帰は気持ち悪いから
フラグのリストとかの方がいいかも。

**611** · 2018/04/08(日) 12:22:11.48

>>611
N桁(4, 5桁)の数字の場合、どうプログラミングする？
ややこしい

誰か、N桁で一般化して、Ruby で書いて