プログラミングのお題スレ Part22
>>206 rust https://ideone.com/dO4xea ・若干の修正 fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // ' let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, p)).collect::<HashMap<_, _>>(); let mut acc = Vec::<Vec<&str>>::new(); for xy in a.iter().map(|s| s.split('=').collect::<Vec<_>>()) { match (acc.iter().position(|b| b.contains(&xy[0])), acc.iter().position(|b| b.contains(&xy[1]))) { (Some(xi), Some(yi)) => { let ys = acc[yi].clone(); acc[xi].extend(ys); acc.remove(yi); }, (Some(xi), None) => acc[xi].push(xy[1]), (None, Some(yi)) => acc[yi].push(xy[0]), _ => acc.push(xy), } } acc.iter_mut().for_each(|b| b.sort_by(|c, d| h.get(d).cmp(&h.get(c)))); acc.sort_by(|c, d| h.get(d[0]).cmp(&h.get(c[0]))); acc } >>208 Perl5 use feature qw{:5.16 signatures}; no warnings qw(experimental::signatures); @s = qw[a1=a2 b1=b2 b3=b2 c1=c2 e1=e2 a3=a4 c3=c4 e1=e3 a2=a4 c3=c1 b3=a4 c2=d1 a4=a5 d2=c1 b4=b3 d3=c3]; for (map{[sort /(\w+)=(\w+)/]} @s) { ($l, $r) = @$_; $g{$r} //= $g{$l} //= $g{$r} // $l; $h{$g{$r}} = $g{$l} if $g{$l} ne $g{$r}; } $h{$k} = sub($e){$h{$e} ? __SUB__->($h{$e}) : $e}->($v) while ($k, $v) = each %h; $g{$_} = $h{$g{$_}} // $g{$_} for keys %g; push @{$r{$v}}, $k while ($k, $v) = each %g; say "@$_" for values %r; ※見易くするためインデントを全角スペースに置換してあります 実行結果 $ perl 22_206_grouping.pl b3 a3 a5 b4 a4 a1 b1 a2 b2 c1 d1 d3 c3 c2 d2 c4 e3 e1 e2 >>208 宛てじゃなかった >>206 の回答だったわ… orz >>206 >>215 をPowerShellに移植 $in = "a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2", "a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1", "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3" $in -split "=" |% {$h = @{}; $n = 0} {if (!$h[$_]) {$h[$_] = $n++}} $eq = $in |% {, $h[$_ -split "="]} $g = 1..$n do { $changed = $false $eq |% { $i, $j = $_ switch ($g[$i] - $g[$j]) { {$_ -gt 0} {$g[$i] = $g[$j]; $changed = $true} {$_ -lt 0} {$g[$j] = $g[$i]; $changed = $true} } } } while ($changed) $h.keys | sort {$h[$_]} | group {$g[$h[$_]]} |% {"[$($_.group -join ", ")]"} -- 実行結果 -- [a1, a2, b1, b2, b3, a3, a4, a5, b4] [c1, c2, c3, c4, d1, d2, d3] [e1, e2, e3] >>218 の5行目の if (!$h[$_]) を if ($h[$_] -eq $null) に訂正 >>206 ruby https://ideone.com/2UiT8U ・>>211 から若干のアレンジ ・同一グループの収集にSortedSetを使用 >>206 Kotlin 入力データを標準入力から入力したり、クラス作ってその中でまとめる等、色々やって長くなった。 https://paiza.io/projects/zdysD5ygRDFVbY2gAGCwOw >>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(:[])} } >>206 rust https://ideone.com/Ma1WGV ・>>223 の移植 ・色々迷いアリ .map(|k| *h.get(k).unwrap())のところは当初 .map(|k| h.get(k).map(|&i| i)).flatten()などとしていたが 正解がわからないので迷った挙げ句に短く書けるほうを採用 ・これに限らずrustは不慣れなので色々珍妙なことをしている可能性アリ >>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ナシ版 ・パフォーマンス的な観点もナシ >>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のリズムのほうが眼球に入りやすい? >>206 >>230 をDで書くと https://ideone.com/9oenyq になるが、switch case 0, 1, 2の場合も3の場合と同じ処理にすると、効率は落ちるもののかなり短くできる。 https://ideone.com/ILLUdy >>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}で良かった お題:数値が入力されるのでその数値に最も近い回分数を出力せよ 回分数とは回分になっている数(負数含まず)のことである 最も近い回分数が2つある場合は2つとも出力せよ 入力 0 出力 0 入力 17 出力 22 入力 100 出力 99 出力 101 >>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)), } } >>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 >>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 >>241 last if keys %a; } @a = keys %a; は last if @a = keys %a; } とコンパクトに書けるんだった、まぁいいや >>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"; } >>234 Kotlin 何か画期的なアルゴリズムを使ったわけではなく、むしろほとんど何も考えずただ作られただけのプログラム。 https://paiza.io/projects/S5qsLnHz_pZD3um9jYRg_Q >>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} >>251 >[[0, [0]], [17, [11]], [100, [99, 101]]] 17 は、22 だよ >>235 しらみ潰しで失格 >>236 しらみ潰しで失格 >>240 しらみ潰しで失格 >>243 しらみ潰しで失格 >>244 しらみ潰しで失格 >>245 しらみ潰しで失格 >>246 しらみ潰しで失格 >>247 しらみ潰しで失格 >>248 しらみ潰しで失格 >>250 しらみ潰しで失格 >>251 しらみ潰しで失格 >>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 >>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)])); } しらみ潰しとは例えば1から順番に見つかるまで全てを試していく最悪な方法を指す 今回の場合だと与えた数から順番に見つかるまで±1を続けて全てを試していって探すプログラムが該当する >>262 私は >>248 だけれども、解法としてはそれしかないと思いますね >>249 と >>238 は しらみ潰しではなく きちんとプログラミングして算出しているようにみえますね >>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が答え 十分大きな数に対しては虱潰しに回文判定していくより速く求まる >>259 Iterable.generate(n).map(f)は単に Iterable.generate(n, f)で良かったと判明 >>234 >>249 をC++で書き換え(入力値は64ビット整数の範囲内限定) https://ideone.com/e1AM8A 元々はCで書き、4行目はなし、15行目と24行目はstrrev(s + i);だったが、Windowsのgccでは コンパイルできたのにideoneではできなかったので、仕方なくC++にしてstd::reverseで代用した。 >>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] }, } } >>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の説明が足りてなかったけど言葉で上手く言い表せないすみません(上位半分以上かつ最小の桁数を抜き出す、的な) >>234 >>269 の一部でC++の機能をどうせ使ってしまったので、この際、全部をC++流に変えたら C流よりすっきり書けた。 https://ideone.com/38bo2E >>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)] とりあえず雑に修正してみたが? (ノ∀`)アチャー >>262 >>245 のKotlinのプログラムは何も考えてなくて本当に馬鹿正直に±1して一つ一つ検査する方式で作ったんだけど、それでもあなたのテストではダメということになったの? まあ Int (符号付32bit整数) 使ってるからその限界超えたらダメではあるんだけど、そういう問題ではなく? >>276 それはしらみつぶしと言われる駄目プログラミングだよ 例えば求める解法が存在する方程式を解くのに値を±1しながら順に代入して試していくのと同じ >>277 あー。プログラムにバグがあってまともに答えが出ないっていうことではなく何の捻りもないプログラムだからダメっていう感想ね。それならわかる。 こちらもアルゴリズム思い浮かばないけどとりあえず作ってみただけだし。ダメというほどではないが良いとも思えないプログラムなので。 >>234 ruby https://ideone.com/E9VSE3 ・273の[1000, [1001]]バグ修正版 ・275とは違う方法で修正してみたがやっつけ感大 >>234 ruby 2.5.5 https://ideone.com/1zqSr1 ・いわゆる(?)ジェネレータ版 ・「終端を持たない範囲オブジェクト」はRuby 2.6.0から >>234 ruby 2.5.5 https://ideone.com/04fxGM ・ジェネレータ版ちょっとアレンジ ・to_sしてto_iするのをやめた 異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。 異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき その組(a, b)...(j, k) および三乗差自体を求めよ 異なる6通りの組で三乗差が相等しい場合があるかも検討せよ >>282 [(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)] a^3 - b^3 == 1412774811 >>282 aが5000以下限定で>>283 の解はRで5秒以内に求められた。8〜9行目は下三角行列の要素番号から 行番号と列番号を求めているだけで、>>282 を解く特別なアルゴリズムというわけではない。 https://ideone.com/w4X3DC >>282 ruby 2.5.5 https://ideone.com/4GdMaO ・285の無駄なループ回数を削減 ・でも5秒じゃ_ >>282 >>287 は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、 各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。 https://ideone.com/Tefgkh n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に 見つからなかった。 >>282 >>289 と似た手順でC++ https://ideone.com/nFRsrK Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか 使えないので使っていない。 >>282 下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290 は下三角行列の全要素を ソートして無駄なので、列のマージに変更(要するにマージソートを途中段階から開始) したら少し速くなった。 https://ideone.com/EZSvB3 n = 10000でも5秒以内に終わった。 https://ideone.com/huQiBe >>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になる。 >>282 c https://ideone.com/JnJpJW ・291から省メモリ化 旧:unsigned int values[10]; 新:unsinged short values[4]; >>282 C++ https://ideone.com/1c4s5I >>294 はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、 rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。 その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。 >>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組を構成している。 >>282 C++ https://ideone.com/tM1cuo >>296 のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに 解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。 >>297 出題者です。 すごいです。ありがとうございます。私の手元ではまだ6通り解、7通り解のひとつも入手できていないので、参考になりました 私のアルゴリズムは効率が悪いようですね >>282 C++ https://ideone.com/LEU7EV >>298 でnを大きくするにつれ>>296 に対する高速化効果が薄れていくのは、ABをvectorでなく 配列にしたらある程度改善された。n = 5000のときの実行時間は>>296 の半分以下になった。 ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。 >>299 どんなプログラムを書いたのか見せて。 >>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 より当然遅い) >>301 ハズレが多いから2passは効果ある? >>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回しか 呼ばれないため、全体の実行時間への影響は無視できる。 お題 460円 580円 600円 の3種類の商品があります これらを組み合わせて合計10個買ったら5360円になりました 組み合わせを求めるプログラムを書いてください ちなみに答えの一つは ・600円×2 ・580円×4 ・460円×4 だそうです https://rio2016.5ch.net/test/read.cgi/cigaret/1706726196/56-57 >>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)しかない >>304 Rで全探索でなくちゃんと解くと https://ideone.com/F44pCL 解が複数ある場合と全くない場合の例として、600円を540円と520円に変更したときの出力も載せた。 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%)工夫をするのがお楽しみだと思う >>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) read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる