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

**デフォルトの名無しさん** · 2023/08/03(木) 13:52:13.20

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

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

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

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

17 · 2024/02/05(月) 02:54:15.12

>>206
Kotlin

入力データを標準入力から入力したり、クラス作ってその中でまとめる等、色々やって長くなった。

https://paiza.io/projects/zdysD5ygRDFVbY2gAGCwOw

**221** · 2024/02/05(月) 20:08:21.07

>>206 ruby
https://ideone.com/j2xPyB
・>>221から若干のアレンジ
・SortedSet単位でのみいじるようにした
f = -> a {
g = -> a {a.combination(2) {|x, y| break g.(a.tap {x.merge y; a.delete y}) if x.intersect? y}}
h = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a = a.map {|s| s.split('=').map {|k| h[k]}.to_set SortedSet}
g.(a).map {|set| set.map &h.invert.method(:[])}
}

**デフォルトの名無しさん** · 2024/02/05(月) 23:26:45.85

>>206
>>218-219をC#化
https://ideone.com/qWA5TB

**223** · 2024/02/05(月) 23:51:15.55

>>206 rust
https://ideone.com/Ma1WGV
・>>223の移植
・色々迷いアリ
　.map(|k| *h.get(k).unwrap())のところは当初
　.map(|k| h.get(k).map(|&i| i)).flatten()などとしていたが
　正解がわからないので迷った挙げ句に短く書けるほうを採用
・これに限らずrustは不慣れなので色々珍妙なことをしている可能性アリ

**225** · 2024/02/06(火) 22:07:13.88

>>206 rust
https://ideone.com/m5INyJ
・>>225から若干の修正
・不必要なループ回数を訂正
・二重forを一重に（でもかえって煩雑に）
・まだまだ迷いアリ
　.map(|k| *h.get(k).unwrap())は結局
　.flat_map(|k| h.get(k)).cloned()に置き換え
　こっちのほうが個人的にはスッキリ感アリ

>>206 rust
https://ideone.com/hT5zGF
・上記のmutナシ版
・パフォーマンス的な観点もナシ

**デフォルトの名無しさん** · 2024/02/06(火) 22:17:05.66

>>206
C#で>>224とは別の解法
https://ideone.com/fvtgZa

**デフォルトの名無しさん** · 2024/02/09(金) 20:11:03.28

>>206
C#でHashSet型を使用。実効速度は>>224と>>227より遅い。
https://ideone.com/cPsAYu

**226** · 2024/02/09(金) 22:33:42.16

>>226
すべてruby移植版rust
DでもE見た目派生まとめ

mutあり版
https://ideone.com/m5INyJ // for if return
https://ideone.com/R8wcOJ // match find
https://ideone.com/ifI5EX // if let find

mutなし版
https://ideone.com/hT5zGF // for if return
https://ideone.com/1PNKbR // match find
https://ideone.com/btKWb1 // if let find

集合同士の組み合わせに重なりが一個もなかったときに
最後に返す a がポツーンと片隅に居るのが落ち着かなかったので
match/if letで書き直してみたがそれはそれで難があり？
条件部分が奥に入ってしまったのがなんかイヤだったり？
一行目が長くなりすぎる、という理由で二行に分けたり？
やっぱ元のfor if returnのリズムのほうが眼球に入りやすい？

**デフォルトの名無しさん** · 2024/02/10(土) 22:10:46.31

>>206
>>227をC++に移植
https://ideone.com/RgBBVA

**デフォルトの名無しさん** · 2024/02/11(日) 15:34:27.52

>>206 octave
https://ideone.com/b2MsDk

>>206 octave
https://ideone.com/x6Lzmb

**デフォルトの名無しさん** · 2024/02/11(日) 20:38:42.50

>>206
>>230をDで書くと
https://ideone.com/9oenyq
になるが、switch case 0, 1, 2の場合も3の場合と同じ処理にすると、効率は落ちるもののかなり短くできる。
https://ideone.com/ILLUdy

**223** · 2024/02/12(月) 23:45:12.86

>>206 octave
https://ideone.com/VtqJcV
・組み合わせつくって集合のペアごとに調べることをやめた
・集合間で重複する要素に着目して集合を減らすようにした

>>223
g.(a).map {|set| set.map &h.invert.method(:[])}じゃなくて単に
g.(a).map {|set| h.keys.values_at *set}で良かった

**デフォルトの名無しさん** · 2024/02/14(水) 09:32:06.19

お題：数値が入力されるのでその数値に最も近い回分数を出力せよ
回分数とは回分になっている数（負数含まず）のことである
最も近い回分数が2つある場合は2つとも出力せよ

入力　0
出力　0

入力　17
出力　22

入力　100
出力　99
出力　101

**デフォルトの名無しさん** · 2024/02/14(水) 15:20:24.32

>>234 lisp
https://ideone.com/MvDoGf

**デフォルトの名無しさん** · 2024/02/14(水) 21:10:48.99

>>234 ocaml
https://ideone.com/4RtyBj

>>234 rust
https://ideone.com/eLCvSJ

**デフォルトの名無しさん** · 2024/02/14(水) 23:21:42.28

>>236
PowerShell
https://ideone.com/voA7MH

**デフォルトの名無しさん** · 2024/02/15(木) 21:30:35.17

>>234
Rust

fn foo(n: usize) -> (usize, Option<usize>) {
　let n2b = |n: usize| { let mut o = Some(n); iter::from_fn(|| { let n = o.take()?; o = (n >= 10).then(|| n / 10); Some((n % 10) as i8) }).collect::<Vec<i8>>() };
　let b2n = |b: &[i8]| b.iter().rev().fold(0_usize, |n, b| n * 10 + *b as usize);
　let pal = |b: &mut [i8]| { let len = b.len() / 2; let (l, u) = b.split_at_mut(len); iter::zip(l, u.iter().rev()).for_each(|(l, u)| *l = *u); };
　let inc = |b: &mut [i8]| { let len = b.len() / 2; let mut c = 1; b[len..].iter_mut().for_each(|b| { *b += c; if *b > 9 { *b = 0; c = 1; } else { c = 0; }}); };
　let dec = |b: &mut [i8]| { let len = b.len() / 2; let mut c = 1; b[len..].iter_mut().for_each(|b| { *b -= c; if *b < 0 { *b = 9; c = 1; } else { c = 0; }}); };
　let fix = |b: &mut [i8]| { if b.last() == Some(&0) { if b.len() & 1 == 0 { b[(b.len() - 1) / 2] = 9; } true } else { false } };
　
　let mut b = n2b(n);
　pal(&mut b);
　let n1 = b2n(&b);
　match n.cmp(&n1) {
　　Ordering::Equal => return (n, None),
　　Ordering::Greater => inc(&mut b),
　　Ordering::Less => dec(&mut b),
　}
　if fix(&mut b) { b.pop(); }
　pal(&mut b);
　let n2 = b2n(&b);
　match n.abs_diff(n1).cmp(&n.abs_diff(n2)) {
　　Ordering::Less => (n1, None),
　　Ordering::Greater => (n2, None),
　　Ordering::Equal => (n1, Some(n2)),
　}
}

**デフォルトの名無しさん** · 2024/02/15(木) 22:00:50.95

>>234
>>237は入力が1～9のとき出力が正しくなかった。function内の1行目に if ($n -le 9) {return $n} を
挿入すると修正される。

Rでは添字の開始値は1で添字0では空のデータが返るので、入力が1～9のときの場合分けは不要。
[]演算子と+演算子を文字列でも使えるように再定義した。
https://ideone.com/PP5swB

Dでは添字範囲指定は半開区間なので、入力が1～9のときの場合分けは不要。
https://ideone.com/hvNBia

**デフォルトの名無しさん** · 2024/02/15(木) 23:18:01.58

>>234 c
https://ideone.com/mWihci

9 · 2024/02/16(金) 02:56:10.41

>>234 Perl5

for $n (0,17,100,123459321) {
　my %a;
　for (0..$n) {
　　$i = $n - $_;
　　$a{$i} = $i if 0 <= $i and $i =~ /^((\d)(?1)\2|\d?)$/;
　　$j = $n + $_;
　　$a{$j} = $j if $j =~ /^((\d)(?1)\2|\d?)$/;
　　last if keys %a;
　}
　@a = keys %a;
　print "$n -> @a\n";
}

※見やすくするためインデントを全角スペースに置換してあります。

実行結果

$ perl 22_234_palindromic_number.pl
0 -> 0
17 -> 22
100 -> 99 101
123459321 -> 123464321 123454321

9 · 2024/02/16(金) 03:13:10.80

>>241

　　last if keys %a;
　}
　@a = keys %a;

は

　　last if @a = keys %a;
　}

とコンパクトに書けるんだった、まぁいいや

9 · 2024/02/16(金) 14:47:55.29

>>234 Perl5、小さい方の検索は0で止まるので負の値を避ける必要はなかった、書き直し。

$r = qr/^((\d)(?1)\2|\d?)$/;
for $n (0,17,100,123459321) {
　my %a;
　for (0..$n) {
　　$a{$n - $_} = 1 if ($n - $_) =~ $r;
　　$a{$n + $_} = 1 if ($n + $_) =~ $r;
　　last if @a = keys %a;
　}
　print "$n -> @a\n";
}

**デフォルトの名無しさん** · 2024/02/16(金) 21:57:03.19

>>234 pascal
https://ideone.com/F1gAKR

17 · 2024/02/16(金) 23:58:17.22

>>234
Kotlin

何か画期的なアルゴリズムを使ったわけではなく、むしろほとんど何も考えずただ作られただけのプログラム。

https://paiza.io/projects/S5qsLnHz_pZD3um9jYRg_Q

9 · 2024/02/17(土) 02:10:36.54

>>234 Python3

def f(k):
　　s = str(k)
　　return s == s[::-1]
for n in [0, 17, 100, 123459321]:
　　l = set()
　　for i in range(n + 1):
　　　　if f(n - i): l.add(n - i)
　　　　if f(n + i): l.add(n + i)
　　　　if l:
　　　　　　print(n, l)
　　　　　　break

※見易くするためインデントは全角空白に置換してあります

実行結果

$ python3 22_234_palindromic_number..py
0 {0}
17 {22}
100 {99, 101}
123459321 {123454321, 123464321}

**デフォルトの名無しさん** · 2024/02/17(土) 18:14:20.87

>>234 pascal
https://ideone.com/kRXq6z
・dynamic array 使用

**デフォルトの名無しさん** · 2024/02/17(土) 19:03:53.65

>>234
C++
https://mevius.5ch.net/test/read.cgi/tech/1434079972/126

**デフォルトの名無しさん** · 2024/02/17(土) 20:00:17.98

>>234
>>239のC#版
https://ideone.com/glAEMw

Julia版
https://ideone.com/cbP5Dm

**デフォルトの名無しさん** · 2024/02/17(土) 20:51:00.88

>>234 octave
https://ideone.com/MXux5X

**デフォルトの名無しさん** · 2024/02/17(土) 21:45:58.19

>>234 ruby
https://ideone.com/0pvK4o

**デフォルトの名無しさん** · 2024/02/18(日) 17:05:41.93

>>251
>[[0, [0]], [17, [11]], [100, [99, 101]]]

17 は、22 だよ

**デフォルトの名無しさん** · 2024/02/18(日) 18:14:23.24

>>235
しらみ潰しで失格
>>236
しらみ潰しで失格
>>240
しらみ潰しで失格

**デフォルトの名無しさん** · 2024/02/18(日) 18:14:51.62

>>243
しらみ潰しで失格
>>244
しらみ潰しで失格
>>245
しらみ潰しで失格

**デフォルトの名無しさん** · 2024/02/18(日) 18:15:27.81

>>246
しらみ潰しで失格
>>247
しらみ潰しで失格
>>248
しらみ潰しで失格

**デフォルトの名無しさん** · 2024/02/18(日) 18:16:03.57

>>250
しらみ潰しで失格
>>251
しらみ潰しで失格

**デフォルトの名無しさん** · 2024/02/18(日) 18:26:09.28

>>253-256 アスペで不合格ｗ

**デフォルトの名無しさん** · 2024/02/18(日) 18:34:19.30

>>234 ruby
https://ideone.com/N0w91j
f = -> n {
(0..n).lazy.map {|i| [n - i, n + i].select {|x| x.to_s.reverse.to_i == x}}.find(&:any?).uniq
}

>>252
(｀･ω･´)ゞ
誤：a - 1, a + 1
正：a - 1, b + 1

**デフォルトの名無しさん** · 2024/02/18(日) 19:41:35.69

>>234 dart
https://ideone.com/e23wRv
void main() {
var rev = (n) => int.parse(n.toString().split('').reversed.join());
var f = (n) => Iterable.generate(n + 1).map((i) => [n - i, n + i].where((x) => x == rev(x))).firstWhere((a) => a.isNotEmpty).toSet().toList();
print([0, 17, 100].map((n) => [n, f(n)]));
}

**デフォルトの名無しさん** · 2024/02/20(火) 08:46:37.56

【㋮㋑㋣㋹㊀㋳】　チャールズ３世戴冠式に｀死神´
https://rio2016.5ch.net/test/read.cgi/kokusai/1690352002/l50

17 · 2024/02/20(火) 10:47:13.25

>>254
しらみ潰しって、どんなテストしたの？

**デフォルトの名無しさん** · 2024/02/20(火) 12:59:46.62

しらみ潰しとは例えば1から順番に見つかるまで全てを試していく最悪な方法を指す
今回の場合だと与えた数から順番に見つかるまで±1を続けて全てを試していって探すプログラムが該当する

9 · 2024/02/20(火) 17:18:07.59

「どんなテストしたの？」
って質問だよ

◆QZaw55cn4c · 2024/02/20(火) 20:48:17.02

>>262
私は >>248
だけれども、解法としてはそれしかないと思いますね

**デフォルトの名無しさん** · 2024/02/20(火) 22:00:55.76

>>249 と >>238 は
しらみ潰しではなく
きちんとプログラミングして算出しているようにみえますね

**デフォルトの名無しさん** · 2024/02/21(水) 13:54:29.89

>>264
私は解答は提出していないが、ざっくりと自分が思いついた方法

まず、以下のような操作を考える
A. 1234という入力に対して1234321を返す
B. 1234という入力に対して12344321を返す
ここで、xという入力に対してA,Bが返す数をA(x),B(x)と表すことにする

次に、与えられた数の桁数で場合分け
(1)与えられた数字の桁数が奇数の場合
例として5桁の数字を考える
N=a*10000+b*1000+c*100+d*10+e*1 (a~eは1桁の自然数, aは0でない)
が与えられたとき、
M=a*100+b*10+c*1
とすると、N=10000の場合を除いて、Nに最も近い回文数は
A(M), A(M+1), A(M-1)
の3つの候補に絞られる(厳密にはA(M)とNとの大小比較からA(M±1)の何れかは明らかに候補にならないので2つを考えれば良い)
N=10000の場合は9999と10001が答え

(2)与えられた数の桁数が偶数の場合
例として6桁の数を考える
(1)と同様に
N=a*100000+b*10000+c*1000+d*100+e*10+f*1
に対して
M=a*100+b*10+c*1
とすると、N=100000の場合を除いて
B(M), B(M+1), B(M-1)
のどれかがNに最も近い回文数（厳密には以下略）
N=100000の場合は99999と100001が答え

十分大きな数に対しては虱潰しに回文判定していくより速く求まる

**デフォルトの名無しさん** · 2024/02/21(水) 16:02:55.06

>>266
N=17
のときは？

**259** · 2024/02/21(水) 23:06:20.13

>>259
Iterable.generate(n).map(f)は単に
Iterable.generate(n, f)で良かったと判明

**デフォルトの名無しさん** · 2024/02/21(水) 23:42:23.78

>>234
>>249をC++で書き換え（入力値は64ビット整数の範囲内限定）
https://ideone.com/e1AM8A

元々はCで書き、4行目はなし、15行目と24行目はstrrev(s + i);だったが、Windowsのgccでは
コンパイルできたのにideoneではできなかったので、仕方なくC++にしてstd::reverseで代用した。

**デフォルトの名無しさん** · 2024/02/22(木) 00:34:50.13

>>234 lisp
>>266を参考に>>249(C#)を移植
https://ideone.com/CUPTas

**デフォルトの名無しさん** · 2024/02/22(木) 01:30:35.61

>>234
Rust

fn nearest_palindrome_numbers(n: usize) -> Vec<usize> {
　let mut dd = DecimalDigits::new(n);
　dd.palindrome_using_upper_half();
　let n1 = dd.to_number();
　match compare(n, n1) {
　　Equal => return vec![n],
　　Greater => dd.increment_upper_half(),
　　Less => dd.decrement_upper_half(),
　}
　if dd.is_most_upper_zero() {
　　return vec![n - 1, n + 1];
　}
　dd.palindrome_using_upper_half();
　let n2 = dd.to_number();
　match compare_absolute_diff((n, n1), (n, n2)) {
　　Less => return vec![n1],
　　Greater => return vec![n2],
　　Equal => return if n1 < n2 { vec![n1, n2] } else { vec![n2, n1] },
　}
}

**266** · 2024/02/22(木) 01:47:44.56

>>267
N=17=1*10+7*1のとき、Nは2桁(偶数桁)でM=1*1=1
B(M)=B(1)=11はNより小さいのでB(M-1)は考えなくてよい
B(M+1)=B(2)=22なので11,22が答えの候補
11より22のほうが17に近いので22が答え

ちょっとNに対するMの説明が足りてなかったけど言葉で上手く言い表せないすみません（上位半分以上かつ最小の桁数を抜き出す、的な）

**デフォルトの名無しさん** · 2024/02/22(木) 20:54:45.16

>>234 ruby
https://ideone.com/rJCYgT
・それっぽい三個の候補から選んでるだけ

**デフォルトの名無しさん** · 2024/02/22(木) 21:04:16.48

>>234
>>269の一部でC++の機能をどうせ使ってしまったので、この際、全部をC++流に変えたら
C流よりすっきり書けた。
https://ideone.com/38bo2E

**273** · 2024/02/22(木) 21:48:36.22

>>273
> [1000, [1001]]

誤：ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u)]
正：ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u), p.(s.to_i.pred.abs.to_s)]

とりあえず雑に修正してみたが？
(ﾉ∀`)ｱﾁｬｰ

17 · 2024/02/23(金) 18:10:28.85

>>262
>>245のKotlinのプログラムは何も考えてなくて本当に馬鹿正直に±1して一つ一つ検査する方式で作ったんだけど、それでもあなたのテストではダメということになったの?
まあ Int (符号付32bit整数) 使ってるからその限界超えたらダメではあるんだけど、そういう問題ではなく?

**デフォルトの名無しさん** · 2024/02/23(金) 18:58:34.05

>>276
それはしらみつぶしと言われる駄目プログラミングだよ
例えば求める解法が存在する方程式を解くのに値を±1しながら順に代入して試していくのと同じ

**デフォルトの名無しさん** · 2024/02/23(金) 21:39:34.55

>>277
あー。プログラムにバグがあってまともに答えが出ないっていうことではなく何の捻りもないプログラムだからダメっていう感想ね。それならわかる。
こちらもアルゴリズム思い浮かばないけどとりあえず作ってみただけだし。ダメというほどではないが良いとも思えないプログラムなので。

**273** · 2024/02/23(金) 23:06:54.56

>>234 ruby
https://ideone.com/E9VSE3
・273の[1000, [1001]]バグ修正版
・275とは違う方法で修正してみたがやっつけ感大

>>234 ruby 2.5.5
https://ideone.com/1zqSr1
・いわゆる（？）ジェネレータ版
・「終端を持たない範囲オブジェクト」はRuby 2.6.0から

**デフォルトの名無しさん** · 2024/02/24(土) 00:25:03.27

>>234
Ruby
https://paiza.io/projects/2G8vPQJQOBZecXPD5ZIFTQ?language=ruby

**279** · 2024/02/24(土) 13:21:16.94

>>234 ruby 2.5.5
https://ideone.com/04fxGM
・ジェネレータ版ちょっとアレンジ
・to_sしてto_iするのをやめた

◆QZaw55cn4c · 2024/02/24(土) 14:25:41.40

異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。
異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき
その組(a, b)...(j, k) および三乗差自体を求めよ
異なる6通りの組で三乗差が相等しい場合があるかも検討せよ

**デフォルトの名無しさん** · 2024/02/24(土) 16:47:38.19

>>282
[(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)]
a^3 - b^3 == 1412774811

17 · 2024/02/24(土) 16:52:08.36

数学、か・・・

**デフォルトの名無しさん** · 2024/02/24(土) 18:16:29.01

>>282 ruby
https://ideone.com/wBX9Rs
・そのまま版
・5秒じゃ㍉

**デフォルトの名無しさん** · 2024/02/24(土) 20:03:55.52

>>234
>>274を巨大整数対応にした。
https://ideone.com/Hg3kGJ

**デフォルトの名無しさん** · 2024/02/24(土) 22:30:55.28

>>282
aが5000以下限定で>>283の解はRで5秒以内に求められた。8～9行目は下三角行列の要素番号から
行番号と列番号を求めているだけで、>>282を解く特別なアルゴリズムというわけではない。
https://ideone.com/w4X3DC

**285** · 2024/02/25(日) 08:52:58.18

>>282 ruby 2.5.5
https://ideone.com/4GdMaO
・285の無駄なループ回数を削減
・でも5秒じゃ㍉

**デフォルトの名無しさん** · 2024/02/25(日) 21:06:57.77

>>282
>>287は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、
各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。
https://ideone.com/Tefgkh

n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に
見つからなかった。

**デフォルトの名無しさん** · 2024/02/26(月) 22:18:39.21

>>282
>>289と似た手順でC++
https://ideone.com/nFRsrK

Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか
使えないので使っていない。

**288** · 2024/02/27(火) 21:45:30.42

>>282 c
https://ideone.com/eM18H1
・288の移植

**デフォルトの名無しさん** · 2024/02/27(火) 22:30:42.88

>>282
下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290は下三角行列の全要素を
ソートして無駄なので、列のマージに変更（要するにマージソートを途中段階から開始）
したら少し速くなった。
https://ideone.com/EZSvB3

n = 10000でも5秒以内に終わった。
https://ideone.com/huQiBe

**288** · 2024/02/28(水) 22:00:05.18

>>282 c++
https://ideone.com/teo5Mm
・288の移植

>>282 rust
https://ideone.com/G94aN3
・288の移植

**デフォルトの名無しさん** · 2024/02/28(水) 23:21:09.16

>>282
>>292とは別の方法で>>290を高速化
https://ideone.com/QxjmyT

1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を
Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを
区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。
Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは
それぞれD = 10002, 15009になる。

**291** · 2024/02/29(木) 22:20:45.85

>>282 c
https://ideone.com/JnJpJW
・291から省メモリ化
　旧：unsigned int values[10];
　新：unsinged short values[4];

**デフォルトの名無しさん** · 2024/03/01(金) 22:22:26.10

>>282
C++
https://ideone.com/1c4s5I
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。

**デフォルトの名無しさん** · 2024/03/01(金) 22:23:18.03

>>296の続き
n = 1000000, m = 6で実行すると、12通りの解が見つかった。

[6つ組解]
424910390480793: (75978, 23919), (77385, 33768), (83482, 53935), (141705, 134268), (317982, 316575), (596001, 595602)
620174235433536: (86184, 27132), (87780, 38304), (90237, 48573), (94696, 61180), (160740, 152304), (360696, 359100)
1238805803151000: (107487, 14487), (108540, 34170), (110550, 48240), (119260, 77050), (454260, 452250), (851430, 850860)
1384074844012224: (112152, 29844), (125324, 83600), (130050, 93426), (159372, 138624), (224928, 215412), (357447, 353799)
1936290882196125: (127629, 52254), (133320, 75675), (149285, 111620), (228525, 215430), (246510, 235395), (290214, 282339)
4589726535576000: (170172, 69672), (177760, 100900), (185265, 120945), (304700, 287240), (328680, 313860), (386952, 376452)
4961393883468288: (172368, 54264), (175560, 76608), (180474, 97146), (189392, 122360), (321480, 304608), (721392, 718200)
11072598752097792: (224304, 59688), (250648, 167200), (260100, 186852), (318744, 277248), (449856, 430824), (714894, 707598)
36717812284608000: (340344, 139344), (355520, 201800), (370530, 241890), (609400, 574480), (657360, 627720), (773904, 752904)
52279853819295375: (382887, 156762), (399960, 227025), (447855, 334860), (685575, 646290), (739530, 706185), (870642, 847017)

[7つ組解]
15490327057569000: (249281, 6281), (255258, 104508), (266640, 151350), (298570, 223240), (457050, 430860), (493020, 470790), (580428, 564678)
123922616460552000: (498562, 12562), (510516, 209016), (533280, 302700), (555795, 362835), (597140, 446480), (914100, 861720), (986040, 941580)

6つ組解の(2, 7), (4, 8), (5, 10), (6, 9)番目は各括弧内で自然数比になっている。
6つ組解の5番目の2倍は7つ組解の1番目のうちの6組を構成している。

**デフォルトの名無しさん** · 2024/03/01(金) 22:24:42.81

>>282
C++
https://ideone.com/tM1cuo
>>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに
解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。

◆QZaw55cn4c · 2024/03/03(日) 19:08:39.58

>>297
出題者です。
すごいです。ありがとうございます。私の手元ではまだ6通り解、7通り解のひとつも入手できていないので、参考になりました
私のアルゴリズムは効率が悪いようですね

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

>>282
C++
https://ideone.com/LEU7EV

>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。

>>299
どんなプログラムを書いたのか見せて。

**デフォルトの名無しさん** · 2024/03/06(水) 22:35:52.23

>>282
C++
https://ideone.com/PG6UiY
>>300の実行時間を分析すると、最も時間が掛かっているのは46～と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。

https://ideone.com/6RzW0n
n = 100万の場合にはr2の値によってデータを多数の列へ振り分けるのをやめ、列を1つにして、
その内部でr2の値により2種類に区分し、それぞれの内部で2種類にさらに区分し、…と再帰的に
区分していけば（要するにクイックソートの変形版）、1つの配列内での要素のスワップだけで済み、
キャッシュの効きが改善されるとの予想通り、n = 100万で実行速度は>>296より25%速くなった。
(原理的には>>300より非効率なのでn = 5000では>>300より当然遅い)

**デフォルトの名無しさん** · 2024/03/08(金) 19:02:53.21

>>301
ハズレが多いから2passは効果ある？

**デフォルトの名無しさん** · 2024/03/09(土) 22:13:47.64

>>282
C++
https://ideone.com/xQD1W8
関数mainのループで配列A, B, Pに書き込まずdにだけ書き込むようにし、関数FindDuplicatesで
dの添字Pではなくdそのものをソートするように変えて、n = 1000000の場合に>>301より10%高速化。
関数PrintSolutionでa, bをmainでと同じ方法で再計算するのは非効率だが、PrintSolutionは僅か12回しか
呼ばれないため、全体の実行時間への影響は無視できる。

**デフォルトの名無しさん** · 2024/03/09(土) 22:47:01.30

お題

460円 580円 600円の3種類の商品があります
これらを組み合わせて合計10個買ったら5360円になりました
組み合わせを求めるプログラムを書いてください

ちなみに答えの一つは
・600円×2
・580円×4
・460円×4
だそうです

https://rio2016.5ch.net/test/read.cgi/cigaret/1706726196/56-57

**デフォルトの名無しさん** · 2024/03/09(土) 23:59:51.39

>>304
面倒なのでRで全探索
https://ideone.com/vrtYvk

**デフォルトの名無しさん** · 2024/03/10(日) 01:20:18.65

>>304
面倒なので全て460円を引くと
A=0円 B=120円 C=140円
10個で760円という問題

面倒なのでさらに20で割ると
A=0円 B=6 C=7円
10個で38円という問題

つまり唯一奇数のCは偶数個が確定
Cが6個以上だと42円以上でオーバーしてNG
Cが4個だと28円で残り10円をA,Bで作れないからNG
Cが2個だと14円で残り24円はBが4個で残り4個がA
Cが0個だと0円で残り38円をA,Bで作れないからNG
つまり解は(A,B,C)=(4,4,2)しかない

**デフォルトの名無しさん** · 2024/03/10(日) 11:20:30.42

>>306
すごすぎるだろ、日本の未来を頼む

**デフォルトの名無しさん** · 2024/03/10(日) 19:06:13.20

>>304
Rで全探索でなくちゃんと解くと
https://ideone.com/F44pCL

解が複数ある場合と全くない場合の例として、600円を540円と520円に変更したときの出力も載せた。

**デフォルトの名無しさん** · 2024/03/10(日) 20:08:55.20

2pass案は多少工夫したらかなり速い

n ␣␣m ␣296␣ ␣301-1 ␣301-2 ␣303␣ ␣2pass
5k␣␣5 ␣ 0.5s ␣ 0.1s ␣ 0.5s ␣ 0.4s ␣ 0.1s
25k ␣5 ␣12.7s ␣ 2.5s ␣13.9s ␣11.1s ␣ 1.7s
100k␣5 ␣3m52s ␣49.3s ␣4m13s ␣3m26s ␣38.9s
1M* ␣6 ␣8h23m ␣2h50m ␣8h51m ␣6h43m ␣1h11m
*n=100万は1万サンプルの部分ループ500k≦r＜510kから100倍

>>301の296と301-2の比較記述と違う傾向があるのはキャッシュ階層の違いだと思う
2passは301-1に近いけど1pass目でのランダムアクセスサイズを落としながらも
誤判定率を低く抑える(0.2%～2%)工夫をするのがお楽しみだと思う

**デフォルトの名無しさん** · 2024/03/14(木) 14:43:15.33

ｔ

**デフォルトの名無しさん** · 2024/03/27(水) 23:42:08.75

>>304

a = (600, 580, 460)
m = min(a)
h = set()

def buy(b, yen):
if yen < m: return
for i in range(0, len(a)):
v = a[i]
if yen >= v:
b[i] += 1
if yen == v:
h.add(str(b))
else:
buy(b, yen - v)
b[i] -= 1

buy([0, 0, 0], 5360)
for s in h: print(s)

**デフォルトの名無しさん** · 2024/03/27(水) 23:55:15.74

>>304
Haskell

[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a * 460 + b * 580 + c * 600 == 5360]

output: [(0,2,7),(4,4,2)]

**デフォルトの名無しさん** · 2024/03/28(木) 00:00:41.99

合計10個という条件忘れてた。

[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a + b + c == 10, a * 460 + b * 580 + c * 600 == 5360]

output: [(4,4,2)]

**デフォルトの名無しさん** · 2024/03/31(日) 11:57:53.31

大幅に手直しした
特に前回数値が一部出てこない状態になっていたので色々と手動で最適化した
新しいアイディアを思いつかない限りはシングルスレッドでの限界に近いと思う

n m 301-1 303 2pass 2pass'
5k 5 0.1s 0.4s 0.1s 0.1s
25k 5 2.5s 11.1s 2.3s* 1.7s
100k 5 49.3s 3m26s 38.9s 27.7s
1M* 6 2h50m 6h43m 1h11m 48m10s
2M* 6 17h06m 28h27m 5h47m 3h13m
Max* 6 35h51m 51h23m 11h09m 5h47m

*前回>>309 2pass n=25kの再計測値
*n=1Mは部分ループ500k<=r<510kから100倍
*n=2Mは部分ループ500k<=r<505kから400倍
*Max:=2642245は3乗がUINT64に収まる最大
*n=Maxは部分ループ500k<=r<500k+3785から2642245/3785倍

ヒント含みの数値がこちら

n D1 D2 D3 = 5000 5001 5003 5009
false_positive = 23 / 5001 = 0.46%
total_t_pass1 = 64.220 ms 2.568 ns/iter
total_t_pass2 = 0.044 ms 0.381 ns/iter
real 0m0.097s

**デフォルトの名無しさん** · 2024/03/31(日) 11:58:50.32

n D1 D2 D3 = 25000 25003 25005 25006
false_positive = 171 / 25003 = 0.68%
total_t_pass1 = 1654.681 ms 2.647 ns/iter
total_t_pass2 = 1.407 ms 0.329 ns/iter
real 0m1.709s

false_positive = 2211 / 100005 = 2.21%
total_t_pass1 = 27338.298 ms 2.734 ns/iter
total_t_pass2 = 78.402 ms 0.355 ns/iter
real 0m27.692s

n D1 D2 D3 = 1000000 1000002 1000009 1000015
false_positive = 18 / 10000 = 0.18%
total_t_pass1 = 28674.338 ms 2.867 ns/iter
total_t_pass2 = 5.642 ms 0.313 ns/iter
real 0m28.897s

n D1 D2 D3 = 2000000 2000003 2000013 2000015
false_positive = 13 / 5000 = 0.26%
total_t_pass1 = 28777.424 ms 2.878 ns/iter
total_t_pass2 = 8.620 ms 0.332 ns/iter
real 0m29.015s

n D1 D2 D3 = 2642245 2642246 2642253 2642258
false_positive = 315 / 3785 = 8.32%
total_t_pass1 = 29210.857 ms 2.921 ns/iter
total_t_pass2 = 336.864 ms 0.405 ns/iter
real 0m29.800s

**デフォルトの名無しさん** · 2024/03/31(日) 22:30:39.09

>>304
ぶっちゃけ、他の言語の人と同じっぽくないので心配なんだが…。
自分なりにHaskellで全探索じゃないバージョン書いてみた。

Haskell

[(a, b, c) | a <- [0..10], b <- [0..10 - a], c <- [0..10 - (a + b)], a * 460 + b * 580 + c * 600 == 5360, a + b + c == 10]

答えは同じ[(4,4,2)]。

**デフォルトの名無しさん** · 2024/04/01(月) 04:52:23.91

少し一般化して、N個の商品があり、i番目の商品はA_i円です
合計M個購入し、価格の合計がS円であるような購入の仕方を998244353で割った余りを求めてください
だとO(N M S)より小さい計算量で解けるのかな

**デフォルトの名無しさん** · 2024/04/01(月) 16:50:08.47

2個、4個、8個…みたいにメモ化すればMはlogMにできるかもしれんね
空間がlogM倍されそうだが

**デフォルトの名無しさん** · 2024/04/13(土) 11:43:17.27

ヘロンの公式を実装せよ

使用言語：C

17 · 2024/04/13(土) 16:57:10.76

>>319
https://paiza.io/projects/_ZdSzHtV9YdEzV-oOySQWQ

Wikipedia でヘロンの公式を調べてそのまま実装しただけで、ほとんど何も考えてない。

**デフォルトの名無しさん** · 2024/04/13(土) 23:01:22.75

>>319
https://ideone.com/YCi6qe
ヘロンが作ったもう1つの式である平方根を加算と除算の繰り返しで求める式も使用。
sqrt関数を呼び出すより実行形式ファイルサイズがほんの少しだけ小さくなる。