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

プログラミングのお題スレ Part22 (785ﾚｽ)
上下前次 1-新

1(4): 2023/08/03(木)13:52 ID:/xW45k0z(1) AAS
プログラミングのお題スレです。

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

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

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
外部ﾘﾝｸ:ideone.com
省11

659: 02/27(木)08:26 ID:LSRTW28H(1) AAS
>>656 Rust

trait BitCount {
　fn bit_count(&self) -> usize;
}
impl BitCount for i32 {
　fn bit_count(&self) -> usize {
　　self.unsigned_abs().count_ones() as usize
　}
}
use num::{BigInt, One};
省12

660: 02/28(金)01:30 ID:1HSOHgVq(1) AAS
intは処理単位のことなんだけどな
何ビットで表現できるかという意味ではない

661: 9 02/28(金)03:12 ID:MEvV9q87(1) AAS
負の場合に表現可能なビット数を配慮しないとPython の int.bit_count()と同じ結果にならないんジャマイカじゃまいか
たぶんPythonの整数がbigintのせいだとおもう
絶対値とってpopcountとかやらないと意外とあれこれ書いてﾌﾟﾁ長めのコードになりそうなおかん

662: 02/28(金)23:07 ID:SRu+xdWw(1) AAS
よく見たらみんな絶対値をとったりbigintを使ったりしてるな

663(1): 03/01(土)20:18 ID:H8RpZRUP(1/2) AAS
>>656
PowerShellのBigIntなら、

$b = @(0)
1..8 |% {$b += $b |% {$_ + 1}}

function bit_count([BigInt]$n)
{
　　($b[[BigInt]::Abs($n).ToByteArray()] | measure -sum).Sum
}

65535, 15, 6, 1, 0, -1, -6, -15, -65535, [BigInt]::Pow(123, 45) |% {
　　"$_ → $(bit_count $_)"
省12

664: 03/01(土)20:19 ID:H8RpZRUP(2/2) AAS
お題：1からnまでの自然数のビット単位での総排他的論理和1 ⊕ 2 ⊕ 3 ⊕ … ⊕ nを求める
関数を作り、n = 123456789, 12345678901234567890のときの値を表示せよ。

665: 03/01(土)21:19 ID:5VrbV50/(1) AAS
A003815かな

666: 03/01(土)21:32 ID:UfbLQAky(1) AAS
数学の試験で中間式を省いて解答だけ書くタイプw

667: 03/01(土)23:41 ID:+HRoh0yF(1) AAS
まあ数列の問題ならOEISを見てみるよな

668: 03/02(日)01:21 ID:xdmIFouH(1) AAS
>> 664 　Rust
fn f(n: u64) -> u64 {
　// f(n) = 1⊕2⊕3⊕...⊕n とすると (2k)⊕(2k+1)=1 であるから 1⊕1=0 より
　// f(4k+1) = (4k+1)⊕(4k)⊕(4k-1)⊕(4k-2)⊕f(4k-3) = f(4(k-1)+1) = ... = f(1) = 1
　// f(4k+3) = (4k+3)⊕(4k+2)⊕f(4k+1) = 0
　// f(4k) = (4k)⊕f(4k-1) = 4k
　// f(4k+2) = (4k+2)⊕f(4k+1) = (4k+2)⊕1 = 4k+3
　match n % 4 {
　　0 => n,
　　1 => 1,
省13

669: 03/11(火)21:18 ID:Qmk3F8/1(1) AAS
>>656
PowerShellでもPopCountがいつの間にか使えるようになっていた。Version 7.5.0で動作確認。

function bit_count($n)
{
　　[BigInt]::PopCount([BigInt]::Abs($n))
}

65535, 15, 6, 1, 0, -1, -6, -15, -65535, [BigInt]::Pow(123, 45) |% {
　　"$_ → $(bit_count $_)"
}

実行結果は>>663と同じ。

670(6): 03/13(木)20:35 ID:QP/8WHEA(1) AAS
お題：数列が入力される。元の数列に逆順にした数列を減算したときの値を出力せよ

In < 12345
OUt > -41976 (12345 - 54321)

671(2): 03/13(木)21:13 ID:SRpNsp20(1) AAS
>>670
PowerShell

function f([BigInt]$n)
{
　　$c = [char[]][string]$n
　　$n - [BigInt]-join $c[-1..-$c.length]
}

12345, [BigInt]::Pow(12, 34) |% {"$_ → $(f $_)"}

[実行結果]
12345 → -41976
省1

672(1): 03/14(金)02:10 ID:wjeVVi0w(1/2) AAS
>>671
12の34乗は合っているけどその後の差がおかしくない？
4922235242952026704037113243122008064 から
4608002213423117304076202592425322294 を引いて
314233029528909399960910650696685770 が正解のところ
314233029528909439273950854852378624 となっているよ
正解は1の位が「4 - 4 = 0」になるはずだよね

>>670 Rust 逆文字列を生成する版

use num::BigInt;

fn odai(input: &str) -> Option<String> {
省9

673(1): 03/14(金)02:30 ID:wjeVVi0w(2/2) AAS
>>670 Rust 逆文字列を生成しない＆整数ジェネリック版
use num::{BigInt, CheckedAdd, CheckedMul, CheckedSub, FromPrimitive};

fn chars_to_integer<X>(input: impl Iterator<Item = char>) -> Option<X>
　where X: FromPrimitive + CheckedMul + CheckedAdd,
{
　let (zero, ten) = (X::from_u32(0).unwrap(), X::from_u32(10).unwrap());
　input
　　.map(|c| X::from_u32(c.to_digit(10)?))
　　.try_fold(zero, |acc, x| acc.checked_mul(&ten)?.checked_add(&x?))
}
省11

674: 03/14(金)20:19 ID:Imul3vYR(1) AAS
>>672
確かに間違っていた。PowerShellの旧ヴァージョンでは [BigInt]文字列と書くだけで
文字列をBigInt型に正確に変換できるから>>671のプログラムでも正しい結果が得られるが、
新ヴァージョンではdouble経由での変換に仕様変更されたようで誤差が生じてしまうから
[BigInt]::Parse(文字列) と書かなければならなくなった。

675: 03/14(金)21:36 ID:pC/XkvI4(1) AAS
数列の長さは指定されていない。

10 INPUT "0-9";I
20 PRINT "0"
30 END

676(1): 03/15(土)19:04 ID:GCbQqql0(1) AAS
>>673
これらのwhere~は何という名称ですか？

>　where X: FromPrimitive + CheckedMul + CheckedAdd,
>　where X: FromPrimitive + CheckedMul + CheckedAdd + CheckedSub,

677: 9 03/16(日)00:12 ID:8GU62dKf(1) AAS
>>670 Perl5

use bigint;
print $_ - reverse($_), "\n" for 12345, 4922235242952026704037113243122008064;

実行結果

$ perl 22_670_reverse_minus_biginit.pl
-41976
314233029528909399960910650696685770

678: 警備員[Lv.23] 03/16(日)17:25 ID:wlGuyFJ7(1) AAS
>>670
Kotlin

文字列にしてひっくり返しているだけの何の捻りもないプログラム

外部ﾘﾝｸ:paiza.io

679: 03/16(日)22:59 ID:wtk+s/+W(1) AAS
>>670
PowerShellでジェネリック化(もどき?)
途中式や結果が入力値の型で表せない場合は$nullを返す。

function f($n)
{
　　$T = $n.GetType()
　　$s = [string]$n
　　try {
　　　　$n - $T::Parse(-join $s[-1..-$s.Length]) -as $T
　　} catch {
省13

680(5): 03/16(日)23:01 ID:6JX6mCC/(1) AAS
お題：36桁以下の負でない整数で16進表記が10進表記の部分文字列であるものをすべて求めて下さい。

(例)
・1の16進表記1は10進表記1の部分文字列です
・123の16進表記7Bは10進表記123の部分文字列ではありません
・357440の16進表記57440は10進表記357440の部分文字列です

※遅い言語では15桁以下で解いても構いません

681: 03/16(日)23:59 ID:qWmLE6LP(1) AAS
>>676
where句だよ
型Xのトレイト境界を宣言してる

682(1): 9 03/18(火)16:05 ID:GYPHuJM6(1/5) AAS
>>680 Perl5、ナイーブな処理方式だと時間がかかり過ぎで最後まで解けないおそれがあるが、なかなかほかに回答者が現れないし、
出現傾向を見るだけでも…と思って、16進数の桁にa-fの現れる値をskipするナイーブな処理方法で。

$m = sprintf '%x', 9 x 15; # 10進で15桁まで
print $m . ' '. hex($m)."\n";
$m =~ s/[a-f]/9/g;
print "1 .. 0x$m\n";
print "".localtime."\n";
for (1 .. $m) {
　$d = hex($_);
　if (0 <= index($d, $_)) {
省6

683(2): 9 03/18(火)16:07 ID:GYPHuJM6(2/5) AAS
>>682
実行結果 (改行数を減らすため適度につなげてます)
$ perl 22_680_hex_substr_1.pl
38d7ea4c67fff 999999999999999
1 .. 0x3897994967999
Tue Mar 18 09:15:31 2025
1, 0x1　　 2, 0x2　　 3, 0x3　　 4, 0x4　　 5, 0x5　　 6, 0x6　　 7, 0x7　　 8, 0x8　　 9, 0x9
357440, 0x57440　　 357441, 0x57441　　 357442, 0x57442　　 357443, 0x57443　　 357444, 0x57444
357445, 0x57445　　 357446, 0x57446　　 357447, 0x57447　　 357448, 0x57448　　 357449, 0x57449
1079653, 0x107965　　 1081713, 0x108171　　 1122966, 0x112296　　 1123079, 0x112307　　 1123080, 0x112308
省14

684(1): 03/18(火)16:35 ID:lVLkTjWA(1) AAS
>>680
ruby
(0..10**16-1).each{|e| puts "#{e},0x#{e.to_s(16)}" if %r|[a-f]|!~e.to_s(16)}

685(4): 03/18(火)21:39 ID:9hwr8+MV(1) AAS
>>683
14桁と15桁には該当値がないので、そこに列挙された数に0を追加した72個が15桁以下の答で
結果的には合っているよ。

出題時に作ったC++プログラムはideoneで36桁以下を0.43秒で完了した。これをPowerShellに
移植したプログラムは15桁以下を0.5秒未満、36桁以下を数分で完了した。

その後、改良したC++プログラムではideoneで36桁以下を0.23秒に短縮できた。

686(2): 9 03/18(火)21:41 ID:GYPHuJM6(3/5) AAS
>>683
>やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。

そのﾋﾝﾄになるかいな…？
・16進数を10進数に変換すると桁数は同じまたは高々1桁増えるのみ（だともう、証明略）
・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明
・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる

687: 9 03/18(火)21:42 ID:GYPHuJM6(4/5) AAS
>>685
あそうなんだ。じゃオレ様が一番乗りということでヨロ
ﾉｼ

688: 9 03/18(火)21:52 ID:GYPHuJM6(5/5) AAS
>>686
>・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる

二桁増える場合があるのでこれは誤りでした

689(1): 684 03/19(水)06:18 ID:khMnA4jS(1/2) AAS
ようやく題意は理解したけど良い解法が思いつかない
ちなみに36桁以下だと答えはいくつありますか？

690: 03/19(水)08:44 ID:khMnA4jS(2/2) AAS
>>680
ruby 遅いけど
i=0
while i<10**16
if %r|[a-f]|=~i.to_s(16)
i=i.to_s(16).gsub(%r|[a-f].*|){|e| e.gsub(%r|.|,"f")}.hex
else
puts "#{i},0x#{i.to_s(16)}" if %r|#{i.to_s(16)}|=~i.to_s
end
i+=1
省1

691(1): 9 03/19(水)16:33 ID:kDrq13vm(1) AAS
>>686
> ・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明

大間違い。16進数と10進数で桁数が同じ値のうち、一桁のものは、16進も10審も同じだった…orz

結局、高速解放はあるんだろうか？
あるいはコラッツ予想みたいに「無いかもしれない」類の、考えるだけ無駄な問題なのだろうか？

692: 03/19(水)21:08 ID:VtmjGkS9(1) AAS
>>689
167個で最大値は697786638998562641695629924526065234

>>691
時間をかけて64桁以下で解いたら、405個で最大値は

　2714476666993915057605587441263923823484611431446449961712093492

だった。これはナイーヴな解法ではC++ですら到底求められない値だから、高速解法が
実在する証になっているだろう。

解答例は1週間くらい経ったら載せるので、それまでよく考えてみて下さい。

693(3): 03/19(水)22:39 ID:P0JLFopv(1/2) AAS
お題：単位分数のエジプト風分解(2進数風味)
1/aを、1/a=1/b+c/dを満たす1/bとc/dに分解する。
aは1以上の整数とする。
c, dは整数とし、bは2の整べき乗(1, 2, 4,...)とする。
c/dは絶対値が最小である事(負数であってもよい)。

例：
1/3→1/4+1/12 : b=4, c=1, d=12
1/7→1/8+1/56 : b=8, c=1, d=56
1/9→1/8-1/72 : b=8, c=-1, d=72(c=1, d=-72も可)
1/13→1/16+3/208 : b=16, c=3, d=288
省1

694: 693 03/19(水)22:42 ID:P0JLFopv(2/2) AAS
aは2以上の整数とする。
に訂正します。

695: 03/19(水)23:16 ID:G4dDQ6P7(1) AAS
>>693
R
外部ﾘﾝｸ:ideone.com

aが2の整べき乗の場合の出力形式に指定がなかったので適当に決めた。

696: 03/20(木)08:21 ID:6IEA4H0O(1) AAS
>>693 Rust
fn f(a: i64) -> String {
　let b = (a as u64).next_power_of_two() as i64;
　let b = if 3 * a > 2 * b { b } else { b >> 1 };
　let (c, d) = (b - a, a * b);
　let shift = c.trailing_zeros().min(d.trailing_zeros());
　let (c, d) = (c >> shift, d >> shift);
　if a == b {
　　format!("1/{a}=1/{b}")
　} else {
省13

697(6): 03/21(金)12:56 ID:CgJbZEAu(1/2) AAS
AA省

698(4): 03/21(金)12:58 ID:CgJbZEAu(2/2) AAS
>>697
// 略記
fn pow16(x: u32) -> i128 { 16_i128.pow(x) }
fn pow10(x: u32) -> i128 { 10_i128.pow(x) }

// 結果検証
fn main() {
　let answer = odai_680();
　assert_eq!(167, answer.len());
　for &a in &answer {
　　assert!(a.to_string().contains(&format!("{a:x}")));
省10

699(2): 03/21(金)20:49 ID:uwhksDTb(1) AAS
>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。

700(4): 03/23(日)23:00 ID:pi1bImlR(1) AAS
>>680から1週間経ったので解答例を掲載

>>685を書いたときに作ってあった2つのC++プログラム
外部ﾘﾝｸ:ideone.com
外部ﾘﾝｸ:ideone.com

1番目ではsolve関数の再帰呼び出しの対象とするx[p]の下限と上限を線形探索するが、
2番目では二分探索する。要素数10では二分探索の効果は薄いと思いきや、大分速くなった。

2番目を読み返していたらバグを発見してしまった。i = N - 1のとき63行目のa[i + 1]はa[N]となり
配列の添字範囲外アクセス。0との比較だけだし、if文の評価がどっちでも以降の処理は結局同じだから、
実害も解への影響もないが、厳格さが必要ならif ((i + 1 < N ? a[i + 1] : 0) >= 0) {と書き換えるべきだな。
実行時間への影響は無視できる。
省5

701: 03/24(月)22:16 ID:/lNBwDBZ(1) AAS
非素数であることが既知の巨大整数を素因数分解するときの
最速のアルゴリズムって何がある？

702(1): 03/25(火)15:25 ID:Yc/egiP0(1/3) AAS
>>699
> 実行時間はC++プログラムの数倍かかるようだが

rustc -C opt-level=2 でコンパイルしたら
g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ

703: 03/25(火)15:54 ID:GZ5kfx5g(1) AAS
>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？

あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ

704(1): 03/25(火)16:11 ID:Yc/egiP0(2/3) AAS
そこまでは興味ないや
「数倍」だったのはもしかして最適化オプション付けてなかったんじゃない?ってだけの話

705(1): 03/25(火)17:30 ID:Yc/egiP0(3/3) AAS
>>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので
>>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた

改変版 | オリジナル
外部ﾘﾝｸ:ideone.com 0.12s | 外部ﾘﾝｸ:ideone.com 0.43s
外部ﾘﾝｸ:ideone.com 0.11s | 外部ﾘﾝｸ:ideone.com 0.23s

706: 03/25(火)20:18 ID:oTGl9wWX(1) AAS
>>705
感心した、出題者回答C++コードはほんの少し変更するだけで簡単にBigInt/i128切り替え出来るのか

>>697-698
Rustはどうなのかな？

707: 03/25(火)23:43 ID:V/NXIH+S(1) AAS
>>704
>>699では最適化オプションを付けてrustc -O a.rsでコンパイルした。最適化なしでは
ありの4.6倍くらい掛かった。もしやと思ってコンパイラをアップデートしてみたら、
実行時間は約3分の1に激減し、>>700の1番目と大差ない1.3倍ほどに収まった。

Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…

708: 03/27(木)11:39 ID:vU3T1Sq/(1) AAS
>>697
crateのnumを使う

709: 03/27(木)20:29 ID:DyGv4jyd(1) AAS
c言語で実用的なプログラムを作りたい。
いいテーマはありますか？

710(2): 03/27(木)20:35 ID:cvPlHeM5(1) AAS
お題：＃（シャープ）を入力の段数でウンコ状に並べて出力せよ
出力は全角でも半角でもどちらでもよしとする（5ch は半角スペース表示できない）

in < 3
out >
　　＃
　＃＃＃
＃＃＃＃＃

711: 03/27(木)21:06 ID:AGn6MWSp(1) AAS
>>710
PowerShell

function unko($n)
{
　　if ($n -ge 1) {1..$n |% {"　" * ($n - $_) + "＃" * (2 * $_ - 1)}}
}

unko 3

-- 実行結果 --
　　＃
　＃＃＃
省1

712(4): 03/28(金)21:33 ID:VDfNaTNz(1/3) AAS
お題：素因数の総和が2025である2000万以下の自然数をすべて求めて下さい。

例)
32272
　素因数分解すると32272 = 2 × 2 × 2 × 2 × 2017で、
　素因数の総和は2 + 2 + 2 + 2 + 2017 = 2025となります。

※20億以下でもC++で5秒以内に余裕で完了できますが、出力が長すぎるため2000万以下としました。
　その結果、Rでも5秒以内に余裕で完了できる問題になりました。

713: 03/28(金)21:54 ID:e6/uDocq(1) AAS
>>710
山状ではだめだったのか
俺にはわからない

714(4): 03/28(金)22:12 ID:g08AymBh(1) AAS
お題
AさんがBさんに惚れてることを
A-B
と表します

両思いのペアを出力してください

入力
D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S

出力
B,E
R,W

715: 03/28(金)22:28 ID:VDfNaTNz(2/3) AAS
>>714
PowerShell

$s = "D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S"
$h = @{}
$s -split "," |% {
　　$a, $b = $_ -split "-"
　　$h[$a] += , $b
}

foreach ($a in $h.keys) {
　　foreach ($b in $h[$a]) {
省6

716: 03/28(金)23:19 ID:VDfNaTNz(3/3) AAS
>>714
PowerShellでもう少し短く

$s = "D-L,U-X,U-Y,U-R,Z-B,B-E,B-M,B-N,V-H,V-X,W-F,W-R,R-B,R-W,O-W,O-S,F-A,Q-X,P-E,P-L,X-X,Y-M,Y-C,L-U,L-V,I-X,E-B,H-M,A-S"
$h = @{}
$s -split "," |% {
　　$a, $b = $_ -split "-"
　　$i, $t = if ($a -lt $b) {1, "$a,$b"} else {2, "$b,$a"}
　　$h[$t] = $h[$t] -bor $i
}

$h.keys |? {$h[$_] -eq 3} | sort
省3

717: 03/29(土)11:51 ID:UeqVkFR5(1) AAS
AA省

718(5): 03/30(日)01:28 ID:KrBJAiIU(1) AAS
お題：1〜10までの範囲の乱数生成をn回行ったとき出た値の積が20の倍数になる確率Pnを出力せよ

n=2
2, 10 ... 20
4, 5 ... 20
Pn=???

n=3
2, 5, 2 ... 20
4, 5, 2 ... 40
Pn=???

719(1): 03/30(日)15:24 ID:6QsLEZYT(1) AAS
>>718
ん？
何千回も試行してその実際の発生率を出すの？
それとも数学的に確率の理論値を出すの？

720: 03/30(日)15:35 ID:bQF7/1H+(1) AAS
後者で学校の課題な予感がするな

721(1): 03/30(日)20:11 ID:qyCZpZxd(1/2) AAS
>>718
R Version4
外部ﾘﾝｸ:ideone.com

ideoneのRは古すぎてエラーが出てしまうので、出力は入力欄に記載した。

巨大整数型を使わなければideoneでも実行できる。
外部ﾘﾝｸ:ideone.com

722(1): 03/30(日)20:58 ID:qyCZpZxd(2/2) AAS
>>718
C++への移植版
外部ﾘﾝｸ:ideone.com

これもideoneのC++が古すぎて10行目をm = size(d)と書けず変更せざるを得なかった。

723: 警備員[Lv.4] 03/31(月)03:24 ID:V+SeThnI(1) AAS
>>714
Kotlin
//paiza.io/projects/WMZL8ULLNxc0zJQPI2uUsA
URLあると書けなかったので先頭のhttps:を抜いた。

724: 03/31(月)05:32 ID:lZyiUZP+(1) AAS
>>718
学校の課題をここに書くなって教わらなかったの？

725(2): 03/31(月)22:37 ID:eEIz6yDp(1) AAS
AA省

726(1): 04/01(火)22:39 ID:9GVSWQu0(1) AAS
半角スペースの意味がわからない
そういうこだわりは古臭いよ

727: 04/02(水)13:29 ID:k9Y5euIy(1) AAS
いまどきのプログラミングなら出力はHTMLだよな

728: 04/02(水)13:47 ID:hi8l+lAW(1/2) AAS
PHPさえその動作禁止だぞ

729: 04/02(水)14:31 ID:vIYRPSqy(1/3) AAS
>>725
変数名がa、b、cの時点でプロじゃねえな

730: 04/02(水)15:10 ID:hi8l+lAW(2/2) AAS
行列演算は数学でもa,b,c,dだから…

731: 04/02(水)19:51 ID:7MGV8+qg(1) AAS
俺が言ってるのは5chのプロじゃねえなってことだから
数学は関係ない

732: 04/02(水)19:56 ID:/hTkauy0(1) AAS
5chのプロ笑

733: 04/02(水)20:14 ID:ZWpp3MuE(1) AAS
5chのプロはどんな変数名使うのか教えて

734(2): 04/02(水)21:11 ID:HCJVcqu8(1) AAS
>>726
>>725の全角空白のこと?　項の書き忘れや書き間違いがないか分かりやすくするため。余分な空白や長い変数名が
ディスク・メモリ空間やコンパイル・インタプリト時間を無駄に増やすと気にする方が古臭くない?

とはいえ、今でもインタプリタ言語のPowerShellでは変数名を長くすると顕著に遅くなる。例えば、

$t1 = measure-command {for ($i = 0; $i -lt 1000000; $i++) {}}
$t2 = measure-command {for ($AnExtraordinarilyLongVariableName = 0; $AnExtraordinarilyLongVariableName -lt 1000000; $AnExtraordinarilyLongVariableName++) {}}
$t2.Ticks / $t1.Ticks

をPowerShell Ver.7で実行すると1.56前後の値が表示される。奇妙なことに、かなり古いVer.2では1前後の値になる。
実時間ではVer.7の$t2とVer.2の$t2が同程度なので、Ver.7では短い変数名での最適化が施されているということか。

それはさておき、>>712を解く人はいませんか?

735: 04/02(水)23:31 ID:vIYRPSqy(2/3) AAS
>>734
縦に揃えるのは無駄に横に長くなる

736: 04/02(水)23:33 ID:vIYRPSqy(3/3) AAS
>>734
ループは毎回、構文を解析しているわけじゃねえぞ？

737(1): 警備員[Lv.5] 04/05(土)14:46 ID:bpkT9prW(1) AAS
>>719
このお題の場合は数学的に答えを出そうとするとプログラムを作る必要がなくなってしまわないか？
人が普通に数学的に考えて行くと答えが出てしまいそうな気がするんだが。
またはAIに聞いたらすぐ答えが出そうな感じが。

738(7): 04/08(火)23:28 ID:OzdBhfzQ(1/2) AAS
AA省

739(3): 04/08(火)23:30 ID:OzdBhfzQ(2/2) AAS
AA省

740: 04/09(水)14:40 ID:jYixYFG8(1) AAS
>>737
AIも同じこと言ってた

741(4): 04/09(水)22:22 ID:Ip5PiQSs(1/3) AAS
>>738-739
出題時に作成した解答例

C++
外部ﾘﾝｸ:ideone.com
R
外部ﾘﾝｸ:ideone.com

と解の個数と最小値・最大値が一致するので正解だろう。

ローカルでコンパイルしようとしたら、

　error[E0425]: cannot find function `generate_primes` in this scope
省1

742: 04/09(水)22:57 ID:R3DmBa+t(1/3) AAS
>>741
すみません
素数の一覧を返すだけなので素数列挙でもライブラリ利用でも何でもいいのですが
例えばエラトステネスの篩ならこんな感じの関数で

// 素数の一覧を返す [2, 3, 5, 7, 11, ... , (最大max)]
fn generate_primes(max: usize) -> Vec<usize> {
　// maxの平方根までの素数の倍数を篩にかければ全ての素数が見つかる
　let limit = max.isqrt() + 1;
　let mut is_prime = vec![true; max + 1];
　is_prime[0] = false;
省12

743(1): 04/09(水)23:40 ID:Ip5PiQSs(2/3) AAS
>>738-739 742と>>741のC++を解の標準出力なしに変更したものの実行速度を比較したら、
前者の方が2000万以下では27%、20億以下では11%速かった。

744(1): 04/09(水)23:43 ID:R3DmBa+t(2/3) AAS
前者はどっち？
アルゴリズムが違うのかちょっと見てみる

745: 04/09(水)23:50 ID:Ip5PiQSs(3/3) AAS
>>744
前者は>>738-739 742のRustプログラム。後者 (C++プログラム) はvectorへの要素追加回数が
多いので時間が掛かっていそう。

746(1): 04/09(水)23:59 ID:R3DmBa+t(3/3) AAS
たしかにC++の20億だと数秒かかりますね
何がそんなに違うのかな

747(1): 04/10(木)00:43 ID:1pFQYAQA(1) AAS
vectorのメモリは必要分を最初に確保すると速くならない?
vectorの最初のサイズの初期値は要素10個分だったはず。11個目が追加されたら20個確保して全要素コピーんｓんてやってたら遅いよ

748: 04/10(木)02:19 ID:Zvxe3V8x(1) AAS
ベクタはC++もRustも他でもほぼ同じ仕様で埋まると倍の新たなエリアを確保してコピー
これは2^n個が埋まった時点でそれ以前の累積コピー個数は
最悪の1個スタートでも1+2+4+ ... + 2^(n-2)+2^(n-1) =2^n - 1個しかない
つまりO(1)とみなせるため問題になることは少ない
言語による詳細な差もC++とRustならほぼ無いと思われる

一方で今回の20億以内で素数和が2025になる数を求める問題
C++版がRust版より約10倍遅くなってる原因は
・pushしていくベクタがRust版は1個でC++版は2026個のベクタを利用
・pushしていく回数がRust版は解の個数と同じ49942回でC++版は134621081回
ワーキングメモリ使用量の差が効いてる

749: 04/10(木)22:03 ID:Y2N8/SQw(1) AAS
>>747
vector p[0]〜p[S]のサイズの最大値4499個（20億以下では88876個）分のメモリを

　　for (auto &v : p) v.reserve(4499);

で最初に割り付けておくと、>>743ではRustの方が2000万以下で27%、20億以下で11%速かったのが、
2000万以下では差が縮まりRustの方が14%速く、20億以下では逆転しRustの方が20%遅くなった。
サイズの最大値は実行前には分からないから、上記の改変はあくまでもvectorのサイズ拡張が実行時間に
及ぼす影響を見るためのテストで、解答として使うことはできないが。

vectorのサイズ拡張は、新しいメモリ割り付けとそこへの要素コピーに掛かる時間によってだけではなく、
要素の格納アドレスが変わることによるキャッシュ有効率の低下によっても、速度低下をもたらしそう。

>>746 748
省4

750(3): 04/11(金)07:38 ID:oaeJuxMT(1) AAS
AA省

751: 04/11(金)22:07 ID:CMM29JI3(1) AAS
すごいな
アルゴリズムの違いでそんなに速度差変わるものなんだな

752: 04/11(金)22:44 ID:4wK2/GRg(1) AAS
>>750
これはとても速いな。ローカルで実行してみたら、>>738のRustプログラムと比較して
2000万以下で16倍、20億以下で55倍の速さだった。

753(1): 04/12(土)09:11 ID:xiQsTIG2(1) AAS
>>712
@Wolfram
外部ﾘﾝｸ:ideone.com

754(2): 04/12(土)21:18 ID:RVQAocGC(1) AAS
>>741のC++プログラムは for (int i = S; i >= 2; i--) のループの最後のi = 2の場合を
ループの外に出して最適化 (p[S]以外のp[_]への要素追加をしないように) するだけで、
20億以下で解の出力なしのときの実行時間が元のプログラムの半分未満になるな。

外部ﾘﾝｸ:ideone.com (1.02秒)
　↓
外部ﾘﾝｸ:ideone.com (0.44秒)

755: 04/12(土)21:26 ID:csJOBVaF(1) AAS
>>754
それに気づいたけど
まだ>>750と比べて20倍遅いからメモ化の方針が徒となってるのかな

756(2): 753 04/13(日)11:09 ID:vq5HB/06(1) AAS
>>712
初Rust
外部ﾘﾝｸ:ideone.com

757: 04/13(日)23:46 ID:bmEZDV0H(1) AAS
>>756
遅い原因は長さ2000万のベクタ利用？

758: 04/13(日)23:53 ID:fz+Jdq57(1) AAS
配列にするとどうかね

759: 04/17(木)00:27 ID:dz0qzhSq(1/3) AAS
素因数和2025のお題の3系統のコードを読み解いてみた

>>756
2000万まで各々で素因数の和を求めて2025になるかを確認する方法。
ただし各数の素因数分解を工夫せずにすると大変なので、
各数の最小素因数(SPF)を先に一気にエラトステネスの篩で求めてる。
それを用いれば各数の素因数分解はその分解数回の割算だけで求まる。

ただしそのSPF表のために長さ2000万のベクタを用いている。
もし20億までなら32bit✕20億で8GBが許容できるとしても、
あるいはこのSPF一覧のベクタを用いなくても、
20億回の処理を劇的に減らす枝刈り方法を組み込めないと厳しい。
省1

760: 04/17(木)00:29 ID:dz0qzhSq(2/3) AAS
>>741
2000万個すべてを素因数分解する方法とは逆に、
2025以下の素数の組み合わせを調べていく方法。
そのうち和が2025になる組み合わせの積が各解となる。

それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。
つまり和がsumとなる時の積をp[sum]に記録していく。
効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、
ベクタp[j]にxがある時、ベクタp[i+j]にx*iをpushしていく。
ここでjの上限は 2025 - i、処理するxの上限は 2000万 / i の枝刈りができる。
最終的にベクタp[2025]の一覧が解となる。
省2

761: 04/17(木)00:32 ID:dz0qzhSq(3/3) AAS
>>738
これも2025以下の素数を組み合わせて和が2025になる解を調べる方法。
解一覧を収めるベクタ以外は、固定の長さ305のベクタのみが使われている。
この長さの 305 とは2025以下～3以上の素数[2017, 2011, ... 5, 3]の数になってる。
各素数の冪乗の和 2017^e2017 + 2011^e2011 + ... + 5^e5 + 3^e3 及び積を計算していくが、
各指数のe2017などは解に不要なので使われておらず、
各冪乗の和自体も不要なので2025までの残りの数が使われていて、
固定長ベクタの値は(素数, 残りの数, ここまでの積)の3つ組となっている。
その素数を1つ使うと残りの数が減算されてて積が乗算されるのを繰り返していく。
素数2だけ特別扱いされており、残りの数の半分だけ左シフトすると解の積が出来上がる。
省7

762: 05/03(土)06:56 ID:Hs+w1scb(1) AAS
お題：0か1のランダムな要素を持つW*Hの行列と二点の座標x, yとp, qが入力される
直線(x,y)→(p, q) を行列内で要素1に当たらないように任意の位置に合同変換したい
合同変換できる座標があればその二点の座標を出力し、なければ「なし」と出力せよ

763: 05/03(土)14:00 ID:2KurydQy(1) AAS
？

764: 05/03(土)14:59 ID:LoSO6jC9(1) AAS
行列の1は格子点上の印なのかクロスワードの黒マスなのか
(x,y)、(p,q)は任意の点なのか格子点なのか
合同変換される直線(x,y)→(p,q)は実は線分だったりしないのか

無限の可能性を感じさせるお題だな

765: 05/03(土)15:10 ID:OINldK7L(1) AAS
検証用のデータを書いていないお題は失格
入力例とその時の出力例が必要
もし出力が複数個で長いならその特例の一部や個数など

766(2): 06/21(土)16:41 ID:muNvYhtO(1) AAS
お題
2次元の配列があったときに
一番左上を起点として右上方向、左下方向、右上方向…
というふうに斜めに配列の要素をたどることを
ジグザグスキャンと名付けます

たとえば、3 * 3の配列の場合は次の順番で配列の要素にアクセスします

(1, 2, 6)
(3, 5, 7)
(4, 8, 9)

二次元の配列を入力としてジグザグスキャンを行ってください
省8

767: 06/21(土)19:44 ID:jAwJC0YX(1) AAS
>>766
R
外部ﾘﾝｸ:wandbox.org

768: 06/21(土)23:05 ID:awm9eire(1) AAS
>>766
Rust

fn f<T: Clone, const M: usize, const N: usize>(input: &[[T; N]; M]) -> Vec<T> {
　let mut output = Vec::<T>::new();
　for x in 0..(M + N - 1) {
　　let start = if x < N { 0 } else { x + 1 - N };
　　let end = if x < M { x } else { M - 1 };
　　let iter = (start..=end).map(|m| input[m][x - m].clone());
　　if x & 1 == 1 {
　　　output.extend(iter.clone());
省11

769(1): 06/29(日)20:45 ID:f7vmTtNq(1) AAS
お題：W*Hの行列に迷路を生成してください（アルゴリズムは任意）

770: 06/29(日)21:58 ID:HlaloW8+(1) AAS
>>769
解がないため不成立
inputとoutputの事例などがないため不成立

771(13): 07/25(金)12:30 ID:CjDQVF2B(1) AAS
【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（0開始）を対応させたリストを作成せよ

【例】
入力： 1 100 10 10000 1000
出力： 0 2 1 4 3

入力： 3 1 4 1 5 9 2
出力： 3 0 4 1 5 6 2

入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7

実際に必要になって実装したけどスマートな方法があったら知りたい

772(1): 07/25(金)20:46 ID:dyl0C+2U(1) AAS
>>771
例がおかしい
わかりやすい最後の例で示すと

入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7　間違い
出力： 0 2 4 6 1 3 5 7　正解

安定ソートなので同値は順序を保ってこうなる

773: 07/25(金)21:30 ID:Z69qH9vG(1) AAS
>>771 C++ 特にひねりは無い
外部ﾘﾝｸ:ideone.com

774: 07/26(土)12:26 ID:xCVVpUlx(1) AAS
>>772
出題者だけど「各要素の移動先のインデクス」って書いた方がよかったか
文言削りすぎた

775: 07/26(土)15:08 ID:T78ZrTu7(1/2) AAS
>>771
SQL

select
　row_number() over(order by arrayValue, arrayIndex) - 1
from
　arrayTable
order by
　arrayIndex

776(1): 07/26(土)19:25 ID:T78ZrTu7(2/2) AAS
>>771
Java 24
外部ﾘﾝｸ:text.is

777(1): 07/27(日)10:09 ID:vFJ24xnO(1/3) AAS
>>771 ocaml
外部ﾘﾝｸ:ideone.com

>>771 octave
外部ﾘﾝｸ:ideone.com

>>771 ruby
外部ﾘﾝｸ:ideone.com

778: 07/27(日)17:05 ID:vFJ24xnO(2/3) AAS
>>771 c
外部ﾘﾝｸ:ideone.com

779: 07/27(日)17:08 ID:vFJ24xnO(3/3) AAS
>>771 ruby 2.6以降？
sorti = ->a {a.map.with_index.sort.map &:last}
f = sorti << sorti
g = method(:p) << f

780: 07/27(日)20:19 ID:uFbo+/2v(1) AAS
>>771
R
外部ﾘﾝｸ:ideone.com

統計用言語だけあってライブラリ関数rankを呼び出すだけ。ties.method = "min"を指定すれば
同値を同順位（例えば2番目の例では出力が3 0 4 0 5 6 2となる）にもできる。

781: 07/27(日)21:43 ID:w39E9j9Q(1) AAS
>>771
Rust
既に色々と出ているため別の観点からのコード
一時作業メモリ最小＆ソートは1回＆ジェネリック

fn f<T: std::cmp::Ord>(input: &[T]) -> Vec<usize> {
　let len = input.len();

　// ポジションのリスト [0, 1, 2, 3, ... , len-1] を作成
　let mut pos_list: Vec<usize> = (0..len).collect();
　// inputを利用してそのポジションだけをソート
　pos_list.sort_by_key(|&pos| &input[pos]);
省11

782: 777 07/27(日)22:54 ID:YfUjoiLt(1) AAS
>>771 octave ソート一回
外部ﾘﾝｸ:ideone.com

>>771 ruby 2.5 ソート一回
外部ﾘﾝｸ:ideone.com

783: 警備員[Lv.11] 07/28(月)23:30 ID:uO5vEij8(1) AAS
>>771
>>776をKotlinに変換してKotlinらしくなるように色々省略しただけのもの。
やはり最初からラムダとか考慮されている言語だと色々省略できて分り易くなるね。
外部ﾘﾝｸ:paiza.io

784: 07/29(火)00:12 ID:9AXsNEm+(1) AAS
>>771
Rust
外部ﾘﾝｸ:ideone.com

バイナリヒープ使うとソート過程で直接リスト作れるけどコード量増えるしヒープソート遅いから実用性は微妙か
C言語ならありかもしれない

785: 07/30(水)21:50 ID:Ug40aZKP(1) AAS
>>771 java
外部ﾘﾝｸ:ideone.com

上下前次 1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 1.373s*