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

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

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

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

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

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

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

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

**デフォルトの名無しさん** · 2023/03/02(木) 01:19:19.82

>>509

Haskell

https://ideone.com/dFgLSr

**デフォルトの名無しさん** · 2023/03/03(金) 10:31:20.70

Haskellすごい

**デフォルトの名無しさん** · 2023/03/04(土) 05:29:06.95

>>509
Kotlin
https://paiza.io/projects/sDzTXxh4G5zC4DO7mtbkVg

**デフォルトの名無しさん** · 2023/03/04(土) 19:18:05.94

>>509

awk

https://ideone.com/rS1puq

**デフォルトの名無しさん** · 2023/03/05(日) 09:55:30.27

友人がブログを削除したんですが、そのあと、そのURLをクリックすると
アダルトサイトに飛ぶようになりました。本人はずかしいはずです。
これは何が原因なんでしょうか？

**デフォルトの名無しさん** · 2023/03/05(日) 11:12:32.57

こういう話の登場人物
「友人」は大抵が本人

**デフォルトの名無しさん** · 2023/03/05(日) 11:32:29.47

こんなところで聞く方が無駄だとわかりました。すいません

**デフォルトの名無しさん** · 2023/03/05(日) 11:56:22.33

>>516
負けてて草

**デフォルトの名無しさん** · 2023/03/05(日) 12:23:59.19

答えを聞き出す前に暴言はいて逃亡するのは三流
答えを聞き出してから態度を豹変させるのが一流

**デフォルトの名無しさん** · 2023/03/05(日) 12:57:55.93

無駄な労力を費やす前に退却するのが真の一流

**デフォルトの名無しさん** · 2023/03/05(日) 14:53:40.73

>>514
println("知らんがな。")

**デフォルトの名無しさん** · 2023/03/05(日) 18:35:08.91

>>456
Elixir で再帰で書いた。
末尾再帰になっているかどうかは分からないけど。難しかった

https://paiza.io/projects/2HEEsPP7gqa7Yoq2U1darw?language=elixir

以下は、データの変遷

input_list は、[ ["ガンド部長", "ブリ事業部長", "9000"], ["モジャコ", "ヤズ係長", "39000"] ]

input_map は順不同で、%{ "イナダ課長" => {"ワラサ部長", 5000}, "ガンド部長" => {"ブリ事業部長", 9000} }

蓄積変数は、[ {["", "ブリ事業部長", "ガンド部長"], 41000},
{["", "ブリ事業部長", "メジロ部長", "ハマチ課長", "ヤズ係長", "モジャコ"], 147000} ]

出力はリストを逆順にして、
41000 : ガンド部長 -> ブリ事業部長
147000 : モジャコ -> ヤズ係長 -> ハマチ課長 -> メジロ部長 -> ブリ事業部長

**デフォルトの名無しさん** · 2023/03/06(月) 14:19:42.45

>>456
awkで書いてみた

https://ideone.com/Ufy2b4

再帰呼び出ししてみた。
表示順を考えなくて良いならmember[]は要らなくなるので
BEGIN{}も要らないし、もう一段簡単になる。

**デフォルトの名無しさん** · 2023/03/07(火) 12:52:38.48

お題
個人の名前,上司の名前,個人の仕事力
が入力されます

個人の仕事力とその部下たちの仕事力を合計した値を出力してください
ブリ事業部長は全員の仕事力の合計になります

入力
ガンド部長,ブリ事業部長,9000
モジャコ,ヤズ係長,39000
ワラサ部長,ブリ事業部長,46000
メジロ部長,ブリ事業部長,34000
ブリ事業部長,,32000
ツバイソ,コズクラ係長,24000
ツバス係長,ハマチ課長,23000
ワカナ,ツバス係長,4000
イナダ課長,ワラサ部長,5000
ヤズ係長,ハマチ課長,23000
ワカナゴ係長,イナダ課長,49000
フクラギ課長,ガンド部長,17000
ハマチ課長,メジロ部長,19000
コズクラ係長,フクラギ課長,31000

出力
ガンド部長:81000
モジャコ:39000
ワラサ部長:100000
-----省略-----

**デフォルトの名無しさん** · 2023/03/07(火) 13:16:03.87

お題：数字が入力されるので日付かどうか判定してください

in < 20230306
out > true
in < 20232250
out > false

**デフォルトの名無しさん** · 2023/03/07(火) 14:17:27.14

仕事そっちのけでやり始めちゃいそうないいお題だ

**デフォルトの名無しさん** · 2023/03/07(火) 21:36:23.54

>>524
ChatGPTに聞いたら瞬殺だった。

@Python

import datetime

def is_valid_date(date_string):
try:
datetime.datetime.strptime(date_string, '%Y%m%d')
return True
except ValueError:
return False

**526** · 2023/03/07(火) 21:37:25.32

インデントに失敗した orz

**デフォルトの名無しさん** · 2023/03/07(火) 22:32:08.33

>>524
haskell
https://ideone.com/1oSNqd

“数値が読めない”とかは無視
純粋にy/m/dがグレゴリオ歴として成立するかどうかの判定
wikiに載ってたy/m/dから修正ユリウス通日を計算する公式を使ってその月の長さを(次の月の初日のユリウス通日)-(その月の初日のユリウス通日)で算出

**デフォルトの名無しさん** · 2023/03/07(火) 23:34:02.90

>>524
Kotlin

java.time.LocalDate クラスに判定させるという超手抜きプログラム。

https://paiza.io/projects/giMWgob2AM7gEy4sGrP50w

**デフォルトの名無しさん** · 2023/03/08(水) 10:26:04.32

>>523
awkで書いてみた

https://ideone.com/eEfpDm

**デフォルトの名無しさん** · 2023/03/08(水) 13:26:39.43

>>524
Java
https://paiza.io/projects/CPs2AVS47pUCL5Kev4cS-Q

**デフォルトの名無しさん** · 2023/03/08(水) 21:40:39.00

>>524
awkで書いてみた
https://ideone.com/N3weSI

**デフォルトの名無しさん** · 2023/03/09(木) 01:22:26.54

お題：引数の絶対値を1-2-5シリーズ(1, 2, 5と、その10の整数べき乗の集合
(..., 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, ...)に切り捨てる関数。
IEEE754で正確に表現出来ない数(0.2とか)になる場合、最も近い値を返す事。
(例 : 0.2の場合は0x1.999999999999ap-3
その場合でも、(切り捨てなので)引数の絶対値を超えてはならない)

f(1) → 1
f(1.1) → 1
f(1.9) → 1
f(2) → 2
f(2.1) → 2
f(4.9) → 2
f(5) → 5
f(5.1) → 5
f(9.9) → 5
f(10) → 10
f(10.1) → 10

発展的なお題：
引数の絶対値が5e-308未満の場合の望ましいと思われる振る舞いについて述べよ
(「思われる」なので正解はありません)。

**529** · 2023/03/09(木) 02:14:16.41

>>531
俺も最初はそうやって parse() 使ってやるやつを作ったんだけど、それだと 20230229 や 20231131 が true になる。
どうやら parse() でやろうとすると年月日それぞれの値のチェックはするが年月日の値を繋げた状態で日付として
正しいかのチェックがされない。日に関して1～31なら全てOKになってしまってそれが何月なのかのチェックがされない。
それで文字列を分解して整数にしてから LocalDate.of(y, m, d) のやり方でやるようにしたんだよ。それだとチェックされるので。

**デフォルトの名無しさん** · 2023/03/09(木) 02:59:36.54

>>523
親 : 子 = 1 : 多

多分木の走査か。
プログラミング・コンテストの基本だけど、自作するのは難しい

**デフォルトの名無しさん** · 2023/03/09(木) 07:19:28.41

>>533
0.2に一番近い値が0.2より小さい場合
この値の入力に対して
0.2に一番近い値を返せばいいのか
0.1に一番近い値を返せばいいのか
どっち？

**533** · 2023/03/09(木) 07:42:30.20

>>536
前者(0.2に一番近い値を返す)

**デフォルトの名無しさん** · 2023/03/09(木) 09:11:59.20

0.2より小さいのに0.2を返す意図がわからない

**デフォルトの名無しさん** · 2023/03/09(木) 09:33:04.67

例えばIEEE754の倍精度だと10^23に一番近い値は2個存在するけど
それぞれの入力値に対して何を返す？

**デフォルトの名無しさん** · 2023/03/09(木) 09:51:28.51

https://tools.m-bsys.com/calculators/ieee754.php

**デフォルトの名無しさん** · 2023/03/09(木) 10:06:31.31

文字列で処理した方が楽そうだな

**デフォルトの名無しさん** · 2023/03/09(木) 10:11:31.04

>>534
ResolverStyleを指定すればよさそう
https://paiza.io/projects/CPs2AVS47pUCL5Kev4cS-Q

**デフォルトの名無しさん** · 2023/03/09(木) 13:53:10.22

>>533
log₂5が無理数なので集合
{ 2ᵐ5ⁿ | 2ᵐ5ⁿ ≦ a }
は最大値を持たない、すなわち“切り捨て＝下界の最大値”が一般には存在しない

**デフォルトの名無しさん** · 2023/03/09(木) 14:58:46.74

>>543
2^m 5^n じゃなくて [1,2,5] x 10^n

**デフォルトの名無しさん** · 2023/03/09(木) 17:53:05.38

>>533
Haskell

https://ideone.com/QDxKsx

負の数とかは無視
f(x) = max { a×10ⁿ | a∈{1,2,5}, n∈ℤ, a×10ⁿ≦x }
を出力

**デフォルトの名無しさん** · 2023/03/09(木) 18:24:41.73

10^23の結果が10^23にならない

**デフォルトの名無しさん** · 2023/03/09(木) 18:51:23.08

f(x) = max { 近似(a×10ⁿ) | a∈{1,2,5}, n∈ℤ, 近似(a×10ⁿ)≦x }

お題はこれなんだよね

**デフォルトの名無しさん** · 2023/03/09(木) 19:49:31.53

>>546

f(10^23) = 10^23
f(9.999999999999999e22) = 5e22

でいいの？

**デフォルトの名無しさん** · 2023/03/09(木) 20:42:50.12

とりあえず>>548の解釈でhaskell

https://ideone.com/KMyKL4

入力を普通に受け渡しすると

f(10^23) = 10^23
f(9.999999999999999e22) = 5e22

は実現できるはずないので引数は文字列で渡す
文字列は0～9, e,.のみ処理
パーサーやん

**デフォルトの名無しさん** · 2023/03/09(木) 21:55:00.68

>>548
>>537

**デフォルトの名無しさん** · 2023/03/10(金) 00:33:46.36

このすいや、違うって、出力側の問題ではなく入力側
出力側は出力が1.0e_、2.0e_、5.9e_の形に限られるため、打ち切り誤差でに4.9999..e23とか9.999...e12とか出力されてもそれぞれ5e23、1e13の打ち切り誤差と判断できるけど、入力側では不可能、つまりそもそも1e23を入力するには文字列がなんかで入力受け取るとか、significantとexponentを整数値で受け取る形式にするとかしないとそもそも入力を受けられないけどそこはどうすんの？つて話

**デフォルトの名無しさん** · 2023/03/10(金) 00:35:33.83

あれ？なんか日本語変換メチャクチャになってる
言いたい事わかる？
1e23なんてそもそも例えばhaskellのDouble型だと受け取れないんだよ

**デフォルトの名無しさん** · 2023/03/10(金) 07:45:37.27

もう一回落ち着いて >>536 >>537 を読んでみようか

**デフォルトの名無しさん** · 2023/03/10(金) 11:39:00.03

>>553
何がおかしい？
例えば

10^23の結果が10^23にならない

と指摘してたけどこれは違う
コードはちゃんと

f(9.999999999999999e22) = 5e22

を算出してる
しかし>>545のコードでコードの使用者が

a = fl125 $ 10^23

とやってもaには1e23ではなく5e22が返ってきてしまう
しかしそれはfl125がうまく機能していないのではなくhaskellの使用上標準の値受け渡しでは9.999999999999999e22と1e23を区別して渡す方法がないんだよ
かと言って

「9.999999999999999e22が引数で来る事はないな、きっとこれは1e23が精度の限界で誤って渡されてるんだ、引数は1e23とみなして答え返そう」

とかあり得んやろ？
わかる？

**デフォルトの名無しさん** · 2023/03/10(金) 12:12:05.54

本当に読んだ？

**デフォルトの名無しさん** · 2023/03/10(金) 12:45:16.91

もういいよ

**デフォルトの名無しさん** · 2023/03/10(金) 16:22:43.21

お題：スレのHTMLが入力されるのでもっともレスが付いているレス番号を表示しなさい
複数同率の場合は複数表示しなさい

**534** · 2023/03/10(金) 16:31:19.44

>>542
そんなやり方があったとは気付かなかった。

**デフォルトの名無しさん** · 2023/03/10(金) 17:58:27.90

>>533
kotlin

出力がちょっと違うけど値としては合っている。
まあしかし BigDecimal 使って文字列で処理しちゃってて桁数大きくてもドーンと来いみたいになっててつまりほぼ手抜き。

https://paiza.io/projects/bgGSIZ8CEEFszHzDBQqD8g

**デフォルトの名無しさん** · 2023/03/10(金) 18:24:41.36

あ。負の数には未対応だった。

**デフォルトの名無しさん** · 2023/03/10(金) 18:51:26.52

こっそり負の値に対応するプログラムに修正しておいた。

**デフォルトの名無しさん** · 2023/03/10(金) 18:53:36.03

だめだ。 -0.9 や 0.9 みたいなのがうまく行かない。後で時間があったら考えよう。

**デフォルトの名無しさん** · 2023/03/10(金) 20:31:33.45

>>557
Java
https://paiza.io/projects/2Ey1sWGJckwBYNaTK0Ppnw?language=java

**デフォルトの名無しさん** · 2023/03/10(金) 21:02:13.08

>>557
jQuery なら、

selector = 'div.thread > div.post > div.message > span > a.reply_link'

$( selector ).each( function( index, elem ) {
console.log( index + ': '+ $( elem ).text( ) );
} );

リンクは、こういう >>1
だけじゃなく、範囲もあるのをどうするのか？

998-
-2
1-2

**デフォルトの名無しさん** · 2023/03/10(金) 22:07:04.07

>>561
誰も見てないから心配すんな。

**559** · 2023/03/12(日) 02:44:00.49

>>533
Kotlin

BigDecimal (及び BigInteger)は使うが文字列を使うのは止めて色々計算して何とかするようにした。

https://paiza.io/projects/6H3b_gf_Kc3RCT6_S_HISw

**デフォルトの名無しさん** · 2023/03/12(日) 18:49:22.70

>>557のお題を勝手に改造

お題：5chのスレのURLが入力されるので内容を取得してもっともレスが付いているレス番号から順に出力しなさい
複数同率の場合は複数表示しなさい

回答例
Kotlin
https://paiza.io/projects/CICvfqwT52X4FsmIwxb_Zw
出力はURLと「レス数: レス番号, ...」になる。

要するに、>>557作っている内に最大のやつ一つ出すだけなのも勿体ないなと思って改造して出来上がったが元のお題とちょっと違うのでお題も勝手に改造した。

**564** · 2023/03/13(月) 02:22:32.85

>>557
については、

>>564
にも書いたけど、リンクの定義が分からない

>>1
みたいに、単独の数字だけとするのか？

998-
-2
1-2
みたいな範囲指定も含むのか？

**デフォルトの名無しさん** · 2023/03/14(火) 04:11:08.17

>>509
Ruby で、

require 'csv'
require 'json'

# 製品タイプの出現回数を数える。初期値は0
prod_type_count = Hash.new( 0 )

# 1行ずつ処理する。Array.new( 1 ) で先頭要素に、nil が入る。
# 蓄積変数・ary のインデックスと、出現回数を同じにする。
# 例えば、ary[ 2 ] には、2つ目のB やC などが入る
result_ary = CSV.foreach( "input.csv" ).
each_with_object( Array.new( 1 ) ) do |row, ary|
plus_1 = prod_type_count[ row[ 0 ] ] + 1
prod_type_count[ row[ 0 ] ] = plus_1

if ary[ plus_1 ] # 存在する
ary[ plus_1 ].push row
else # 存在しない
ary[ plus_1 ] = [ row ]
end
end

# p prod_type_count
#=> { "B"=>2, "C"=>3, "F"=>2, "E"=>3, "D"=>4, "A"=>1, "G"=>1 }

次へ続く

**569** · 2023/03/14(火) 04:12:26.06

result_ary.shift # 先頭要素のnil を削除する
res = result_ary.each_with_object( [ ] ) do |outer_ary, accum|
outer_ary.sort_by! { |inner_ary| inner_ary[ 0 ] } # 製品タイプでソートする
transposed_ary = outer_ary.transpose # 2次元配列を転置する

accum.push ( { "製品タイプ" => transposed_ary[ 0 ],
"製品ID" => transposed_ary[ 1 ],
"製品色" => transposed_ary[ 2 ] } )
end

puts JSON.dump( res ) # 文字列化

# p result_ary
=begin
ソート後のデータ

[ [["A", "01", "Y"], ["B", "02", "B"], ["C", "04", "Y"], ["D", "07", "B"], ["E", "12", "C"], ["F", "15", "R"], ["G", "16", "M"]],
[["B", "03", "C"], ["C", "06", "G"], ["D", "08", "B"], ["E", "11", "Y"], ["F", "14", "G"]],
[["C", "05", "C"], ["D", "10", "M"], ["E", "13", "B"]],
[["D", "09", "B"]] ]
=end

**567** · 2023/03/15(水) 02:47:25.92

>>557
Kotlin

>>567を更に改造して>>568の言うような >>xxx-xxx とかも可能にした。
実際に受け付けるのは「>>」の後が「数」または「数-数」で複数ある場合はカンマ区切り。

https://paiza.io/projects/CDH-JDZD12laCkRrON4Q2A

**デフォルトの名無しさん** · 2023/03/16(木) 19:59:21.18

マッチ棒パズルソルバ

0123456789+-=×/からなる文字列が与えられる
この文字列にC変換1回、またはA変換とB変換を一回ずつ行って得られる文字列のうち数式として成立するものを列挙せよ

https://youtu.be/2sqvh8KBdQk

例
6 = 3 + 3 - 8 → 6 = 3 + 3 = 6
7 = 6 + 5 → 11 = 6 + 5
2 = 3 + 0 → 3 = 3 + 0, 2 = 2 + 0
6 = 9 - 3 → 5 = 8 - 3

A変換(逆変換がB変換)

6 → 5
8 → 0, 6, 9
9 → 3, 5
= → -
× → /

C変換

0 → 6,9
2 → 3
3 → 2,5
4 → 7,11
5 → 3
6 → 0
7 → 4,11
9 → 0
11 → 4,7

**デフォルトの名無しさん** · 2023/03/18(土) 05:36:02.04

>>572
A変換に + → - もあるよね？

**デフォルトの名無しさん** · 2023/03/18(土) 06:36:08.37

他にも色々と抜けっぽいのが

B変換 : A変換の逆変換
C変換 : B変換=>A変換 (元に戻るのは除く)
だから

A変換だけ(またはB変換だけ)ちゃんと考えて定義すれば良いよ

「数式が成り立つ」もちゃんと定義しないと
"1+1=2" "1+1" "1"
どこまで含む？

**デフォルトの名無しさん** · 2023/03/18(土) 12:24:06.83

>>573
"+"→"-"も抜けてたし"-"→"/"とかも抜けてた
あとB変換として「先頭が0～9のとき先頭に-をつける」もある
これは各文字だけ見ればいい変換ではないらかややこしい
>>574
まぁ()ないから普通に
まともに定義書くとうるさいだけだと思うので

ちなみに当方まだ模範解答作れてません

**デフォルトの名無しさん** · 2023/03/18(土) 18:16:04.06

要するにマッチ棒使って数字と四則演算記号と = 記号を表現した時に1本動かして、最低でも一つは = 記号がある状態で式が成立すれば良いんだよね?

**デフォルトの名無しさん** · 2023/03/18(土) 18:56:17.32

>>576
yes

**デフォルトの名無しさん** · 2023/03/20(月) 16:53:45.60

≠もOK？

**デフォルトの名無しさん** · 2023/03/20(月) 17:51:34.56

まともに出題出来ないヤツは出題するなよ

**デフォルトの名無しさん** · 2023/03/21(火) 15:12:23.88

AIは数式や記号に意味を持たせない

**デフォルトの名無しさん** · 2023/03/25(土) 18:45:52.85

>>572
Kotlin

https://paiza.io/projects/mlep0Qk1tQhwMlC1r6awRw

式が成立するかの判定ではパターンマッチング使ってやっているので多分ちゃんと出来ないこともあるんじゃないかと思うが、多分だいたいは大丈夫。
式の計算は括弧を使った入れ子がないので再帰は使ってない。掛け算と割り算を優先してるだけ。

**521** · 2023/03/27(月) 05:06:18.68

>>523
Elixir で再帰で書いた。多分木の走査か。
末尾再帰になっているかどうかは分からないけど。
>>456 よりも、さらに難しかった

https://paiza.io/projects/oeDtiQEX0oQtWQT7SMKwLA?language=elixir

以下は、データの変遷

input_list は、[ ["ガンド部長", "ブリ事業部長", "9000"], ["モジャコ", "ヤズ係長", "39000"] ]

input_map は順不同で、%{ "イナダ課長" => {"ワラサ部長", 5000}, "ガンド部長" => {"ブリ事業部長", 9000} }

boss_subordinates_map は、%{ "ツバス係長" => ["ワカナ"], "ハマチ課長" => ["ヤズ係長", "ツバス係長"] }

total_power は、[ {"ガンド部長", 81000}, {"モジャコ", 39000} ]

出力
ガンド部長 : 81000
モジャコ : 39000

**デフォルトの名無しさん** · 2023/03/30(木) 17:53:04.26

お題　板違い
数学板に貼られてた問題
こっちでしょ

298 １３２人目の素数さん[] 2023/03/30(木) 16:50:53.60 ID:FIHeBSy3
66,203,335,759,2227,3663,7249,80,252,420,882,2770,4618,9126

の数字の和を使って22999をピッタリ作りたい
この時、解は存在するか。
数字は重複して何度でも使用して良いが、使う回数は少なければ少ないほど良い。
18-(使用した数字の合計個数)をこの問題の得点とする

という問題誰かといてください！

**デフォルトの名無しさん** · 2023/03/30(木) 20:36:43.76

4618+3663+3663+3663+3663+3663+66

**デフォルトの名無しさん** · 2023/03/30(木) 20:56:17.32

GPT4がこのスレ知っててワロタ

**デフォルトの名無しさん** · 2023/04/05(水) 19:08:55.65

お題　nか2n

長さがn+1, 総和が3nの正の整数の列が入力されます
その連続する部分列で総和がnまたは2nであるものを見つけ、その先頭と最後のindexの組み(indexは1～n+1とする)を返す関数を作ってください
存在しない時は(-1,-1)を返して下さい

備考　総当たりでも列の長さnに対して計算量はn²オーダーですが、線形オーダーの解があります(四則演算等をO(1)として)

例
[4,1,2,3,3,2]
(3,4)
[3,2,1,3,2,3,4,3,1,4,4]
(6,8)
[3,9,1,1,1,2,5,4,3,5,4,2,1,10,3,4,2,7,1,5,1,2,3,3,1,1,1,1,3,1,2,4,1,1,2,2,11,2,1,4,7,4,6,1,7,1,4,2,1,5,2,5,6,1,5,2,1,1,5,1,1,1,1,5,1,1,3,2,9,6,1,3,4,11,1,1,4,1,2,6,1,2,1,1,3,1,1,1,1,1,2,7,6,2,1,3,9,1,1,2,2]
(36,67)

**デフォルトの名無しさん** · 2023/04/05(水) 20:56:42.55

簡単すぎる
他の人どうぞ

**デフォルトの名無しさん** · 2023/04/05(水) 21:33:05.46

2^(2^(2^(2^(2^(2^2)))))
を10進数で先頭から100桁を出力する方法は？

**デフォルトの名無しさん** · 2023/04/05(水) 21:40:43.46

1桁でも無理

**デフォルトの名無しさん** · 2023/04/09(日) 16:16:32.45

お題
4つの数字a,b,c,dが複数個入力されます

入力
0, 1, 1, 1
0, 0, 0, 0
1, 0, 0, 1
1, 0, 1, 0
0, 0, 0, 1
0, 0, 1, 1
1, 1, 1, 0
1, 0, 0, 0
1, 1, 1, 1
0, 1, 1, 0
1, 1, 0, 0
1, 0, 1, 1
0, 1, 0, 1
1, 1, 0, 1
0, 0, 1, 0
0, 1, 0, 0

次の条件でソートして出力してください
dの昇順
, bの降順
, cの昇順
, aの降順

出力
1, 1, 0, 0
0, 1, 0, 0
1, 1, 1, 0
0, 1, 1, 0
1, 0, 0, 0
0, 0, 0, 0
1, 0, 1, 0
0, 0, 1, 0
1, 1, 0, 1
0, 1, 0, 1
1, 1, 1, 1
0, 1, 1, 1
1, 0, 0, 1
0, 0, 0, 1
1, 0, 1, 1
0, 0, 1, 1

**デフォルトの名無しさん** · 2023/04/09(日) 19:47:50.00

>>590

Haskell

https://ideone.com/KdiMvQ

**デフォルトの名無しさん** · 2023/04/09(日) 19:53:31.67

>>590
C
https://ideone.com/lDXYbw

**デフォルトの名無しさん** · 2023/04/09(日) 22:47:43.52

>>590

ChatGPT -> Python
https://ideone.com/rxlYUS

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

>>590
Kotlin
https://paiza.io/projects/r4VWdOkemR0ZJl0f0qJtHQ

**デフォルトの名無しさん** · 2023/04/12(水) 12:53:01.20

お題　何通り？
黒玉 b 個、赤玉 r 個、白玉 w 個が入ってる袋の中から玉を一個ずつ取り出し、取り出した玉を順に横一列に b+r+w 個すべて並べる。

どの黒玉同士も隣り合わず、どの赤玉同士も隣り合わない数を求めよ

例　
( b, r, w ) = ( 1,2,2)
→ 18
( b, r, w ) = ( 1,2,3 )
→ 40
( b, r, w ) = ( 3,4,5 )
→ 4326
( b, r, w ) = ( 12,34,56 )
→ 138961718287080638152811314224672

( b, r, w ) = ( 1, 2, 2 )の場合の18通り
["BRWRW","BRWWR","BWRWR","RBRWW","RBWRW","RBWWR","RWBRW","RWBWR","RWRBW","RWRWB","RWWBR","RWWRB","WBRWR","WRBRW","WRBWR","WRWBR","WRWRB","WWRBR"]

**デフォルトの名無しさん** · 2023/04/12(水) 14:41:48.33

こういうの、中学の時に散々やった

**デフォルトの名無しさん** · 2023/04/13(木) 01:54:06.79

>>595
Kotlin

これは馬鹿正直に並べ替えてるだけなので多くなると結果が中々出ないだけでなくメモリが足りなくなって終わるかも知れない。

https://paiza.io/projects/GIJzZldH4F366cas93uAzg

**デフォルトの名無しさん** · 2023/04/13(木) 04:34:12.97

>>595
https://ideone.com/FhA9vc

**デフォルトの名無しさん** · 2023/04/13(木) 17:25:16.88

この問題よくある「受験問題計算機で解こう」です
元ネタは今年の東大理系[2]が(b,r,w) = (3,4,5)の場合、もちろん元の問題は「手計算で解け」

https://youtu.be/KAJpzptO5Ws

なのでうまく立式すると(b,r,w) = (3,4,5)程度なら手計算でも解けます、計算機ならこの程度なら全数でも27720通りのうちの4326通りなのでいけます
( b, r, w ) = ( 12,34,56 )あたりだと総当たりするのは難しくなります
ちなみにn = b+r+wについて計算量がO(n²⁺ᵉ)のオーダーの解があります
というか普通に動画のように解いた時の一番素直な解法がO(n²⁺ᵉ)オーダーになります
もっと早いのあるかもしれませんけど

**デフォルトの名無しさん** · 2023/04/13(木) 18:39:05.80

全然違うアプローチで解いた

乗算やCombinationの計算オーダーをどう考えてるか知らないけど、
シンプルな２重ループの中身がCombination、2のn乗、乗算、加減算だけだから、
Combinationを毎回単純に計算してもO(n^4 log(n))
工夫すればO(n^3 log(n))になる

**デフォルトの名無しさん** · 2023/04/14(金) 16:38:26.25

動画の方法の計算量は高々O(n²⁺ᵉ)なのはすぐ言えます
ここでの計算量は普通の固定長のレジスタしか持たない計算機で計算した場合の計算回数
動画の計算は0<b≦rのときは

Σ[ k:1～b ]C[ b-1, k-1 ]C[ w+1, k ]C[ k+w+1, w+b+1-r ]
( ただしm<0,m>nのときはC[ m,n ] = 0とする )

で漏れなくダブりなく計算できるというやつ
これの計算量ですが

①ループはb≦nなのでO(n)回
②計算で出てくる数値の大きさは大体指数オーダーなので桁数はO(n¹⁺ᵉ)オーダー
③３つあるCの計算は漸化式使って前で求めた値にそれぞれ掛け算1回、割り算1回で求まるので桁数がO(n¹⁺ᵉ)だからO(n¹⁺ᵉ)オーダーで計算可能、それを掛け算2回して累計に足すだけなので結局ループ1回の計算量はO(n¹⁺ᵉ)オーダー
④総計算量は結局高々O(n²⁺ᵉ)オーダー

Σの各項は階乗がたくさん出る形なのでBinary splittingとか使ったら早くなる可能性もあるけど、流石に暇つぶしにそこまでやる気は出ない

**デフォルトの名無しさん** · 2023/04/14(金) 16:42:45.21

Cの但し書き逆 orz
C[ m, n ] = 0 if n < 0 or n > m
でつ

**デフォルトの名無しさん** · 2023/04/14(金) 18:34:45.76

eはεか
2.718... かと思って、えらい遅いなあと思ってしまった

桁数はn log n 程度、乗除算の定数の桁数がlog nだから、
だいたい n^2 (log n)^2 くらい

**デフォルトの名無しさん** · 2023/04/14(金) 19:30:49.02

そうそう、上つきのεが出ないのでeで代用しました
明示しとくべきでした
そもそも計算過程でO(exp(n))オーダーちょいの数扱わざるを得ないしO(n)より真に小さいオーダーのループも無理っぽいのでO(n²⁺ᵉ)より劇的に早くするのは無理ではなかろかと思う今日この頃

**デフォルトの名無しさん** · 2023/04/17(月) 12:15:45.96

お題　何通り？
黒玉 b 個、赤玉 r 個、白玉 w 個が入ってる袋の中から玉を一個ずつ取り出し、取り出した玉を順に横一列に b+r+w 個すべて並べる。

どの黒玉同士も隣り合わず、どの赤玉同士も隣り合わず、どの白玉同士も隣り合わない数を求めよ

**デフォルトの名無しさん** · 2023/04/18(火) 20:26:54.25

オリジナル問題をほんの少し変えただけなんだけど
解き方の解説動画がない問題には回答出来ない人なのかな？

**デフォルトの名無しさん** · 2023/04/19(水) 10:51:18.73

haskell

https://ideone.com/ff0ut9

ほとんど大差ないから書かなかっただけだよ

**デフォルトの名無しさん** · 2023/04/19(水) 23:01:33.08

>>605
Kotlin

前回のプログラムを修正して入力の最初の値として 0 または 0 以外を受け付けるようにして、
それが 0 だったら前回と同じ動作(Wは連続して良い)、0以外だったら今回のお題の動作(連続不可)
になるようにした。

https://paiza.io/projects/YHo1f9RRZcJ5qWeKjh4A5A

**デフォルトの名無しさん** · 2023/04/20(木) 16:05:31.06

>>605
haskell

https://ideone.com/eoDuMc

アルゴリズムは何も変わってないんだけどGHCという一番メジャーなhaskell コンパイラはソースでユニコード文字で処理してるので変数名に漢字とか使えてちょっと面白いんですけど試しr̅みたいな合字やってみたら使えました、まぁそりゃ使えるだろって話なんですけど
ちょっとコードの見た目が全然違って楽しい