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

1デフォルトの名無しさん
垢版 |
2023/08/03(木) 13:52:13.20ID:/xW45k0z
プログラミングのお題スレです。

【出題と回答例】
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/
2025/02/15(土) 21:52:48.39ID:qa0m30Tb
>>621
最大値をundefined代わりに使ってはいけないと指摘があったのにまだ使っているのかいな
そのコードで入力数列がこうだった場合
vector<int> a = {IntMax - 1, IntMax};
2番目に小さい数として正解のintMaxを返さなければならない
623デフォルトの名無しさん
垢版 |
2025/02/15(土) 22:00:12.34ID:rssRTGdz
>>622
>>593のC++プログラムの実行結果を参照。入力数列にINT_MAXが含まれる場合でも問題ない。
2025/02/15(土) 22:09:09.66ID:qa0m30Tb
>>623
それはm1とm2を間接にポインタで持つために遅くなっているf593()
m1とm2を直接に整数で持つため速いf3()はIntMaxに対応できていない
625デフォルトの名無しさん
垢版 |
2025/02/15(土) 22:24:28.09ID:rssRTGdz
>>624
>>621の速度比較テストに>>570のf3も追加
https://ideone.com/scnfdu

ポインタで持つf593との比で、整数で持つf570は6%速いだけ。一方、null許容型のf621は29%も遅い。
最大値が存在する型ではそれを利用する方が良いという結論に変わりはない。
626デフォルトの名無しさん
垢版 |
2025/02/15(土) 22:29:41.23ID:rssRTGdz
まあ、同じ値の要素が大量に存在する入力データではf570は遅くなるが、平均的な速度はf570の方が速い。
627デフォルトの名無しさん
垢版 |
2025/02/15(土) 22:31:16.05ID:rssRTGdz
>>626はf570じゃなくてf593だった。
2025/02/15(土) 22:42:01.35ID:v2QOLp/q
f593でローカル変数へのポインタを返し得るのは如何かと
629デフォルトの名無しさん
垢版 |
2025/02/15(土) 23:34:59.77ID:rssRTGdz
>>628
返しえないでしょ。
2025/02/15(土) 23:46:12.83ID:qa0m30Tb
>>625
まずnullableのコードがおかしい
例えばoverload(op)のこれ

if (y.isNull) return false; \
return x op y.value; \

Nullだとfals eとなり
opの計算結果次第でもfal seとなり
両者を区別できない
2025/02/15(土) 23:47:32.80ID:qa0m30Tb
>>625
あとvector扱うコードは倫理的に際どいかな
長さ0でないことを調べずに
いきなりint *m1 = &a[0], m2 = &y;
今回は長さ0の時に*m1をアクセスしないから論理的にギリセーフだけど際どい

そのへんのトリッキーさも含めて
(もしあれば)最小値も返す場合
(もしあれば)3番目の最小値も返す場合など
このIntMax方式は破綻すると思う
632デフォルトの名無しさん
垢版 |
2025/02/15(土) 23:52:31.08ID:rssRTGdz
>>630
>>621に書いた通り、C#のヌル許容型T? (Nullable<T>のエイリアス) の挙動に従っただけだから。
文句があるならMicrosoftに言ってくれ。
6339
垢版 |
2025/02/16(日) 06:28:07.79ID:GnMUCCm7
qa0m30Tb の回答はどれよ？
634デフォルトの名無しさん
垢版 |
2025/02/16(日) 08:09:49.66ID:v+IcfGmt
いるよねえ他人の回答に文句だけつけて自分では回答しないやつ
635デフォルトの名無しさん
垢版 |
2025/02/16(日) 08:16:54.29ID:v+IcfGmt
他人の回答が間違いとなるようにお題を解釈するのは知的なことではないよバカの所業だよ
2025/02/16(日) 08:20:29.71ID:eNZyrnPC
そんなことより>>616のワンライナーがカッコよくてほれぼれする
2025/02/16(日) 10:58:48.51ID:EXJYkLn8
帰ったと思ったらまたやってんのｗ
2025/02/16(日) 15:14:38.18ID:8bpH8MuA
コンパイラ警告無視するのが知的な事だと思ってそうだな
6399
垢版 |
2025/02/16(日) 15:45:59.98ID:GnMUCCm7
回答のｺｰﾄﾞでもって語ってほしいなぁ
2025/02/17(月) 13:08:08.60ID:lz3iaMcC
お題：ランダムな数列が与えられる。隣り合う数字が偶数同士の時、あいだに0を。奇数同士の時は1を挿入し、それ以外は何も挿入しない

In < 123346
Out > 12313406
2025/02/17(月) 13:47:54.59ID:1CKZ5rpi
>>640 ruby
DATA.readlines(chomp:1).map{|e|
a=e.split("").map{|f| f.to_i}
(0..a.size-2).each{|n|
a[n]=a[n]*10 if (a[n]%2==0 && a[n+1]%2==0)
a[n+1]=a[n+1]+10 if (a[n]%2==1 && a[n+1]%2==1)}
puts "IN < #{e}\nOUT > #{a.map{|f| f.to_s}.join}"}
__END__
123346
2025/02/17(月) 20:02:39.61ID:SzDlV4TD
>>640 lisp
https://ideone.com/DV9DeR
643デフォルトの名無しさん
垢版 |
2025/02/17(月) 20:47:46.22ID:2enU2rA/
>>640
PowerShell (一般的な文字コードを想定)

function f([string]$s)
{
　　$rprev = 2
　　-join ([char[]]$s |% {
　　　　$r = $_ % 2
　　　　if ($r -eq $rprev) {$r}
　　　　$rprev = $r
　　　　$_
　　})
}

123346, 12333468, 1, "" |% {"$_ → $(f $_)"}

[実行結果]
123346 → 12313406
12333468 → 123131340608
1 → 1
→
644デフォルトの名無しさん
垢版 |
2025/02/17(月) 20:48:16.10ID:2enU2rA/
正規表現置換なら、

function f($s)
{
　　$s -replace "[02468](?=[02468])", "$&0" -replace "[13579](?=[13579])", "$&1"
}

1回で済ますなら、

function f($s)
{
　　[RegEx]::Replace($s, "[02468](?=[02468])|[13579](?=[13579])", {$_ = $args[0].value[0]; "$_$($_ % 2)"})
}
2025/02/17(月) 20:58:11.16ID:UxhkW11K
>>640　Rust

fn f(input: &[u8]) -> Vec<u8> {
　input.windows(2).fold(Vec::new(), |mut vec, w| {
　　if vec.is_empty() {
　　　vec.push(w[0]);
　　}
　　if (w[0] ^ w[1]) & 1 == 0 {
　　　vec.push(w[0] & 1 + b'0');
　　}
　　vec.push(w[1]);
　　vec
　})
}

fn main() {
　assert_eq!(f(b"123346"), b"12313406");
　assert_eq!(f(b"12333468"), b"123131340608");
}
646デフォルトの名無しさん
垢版 |
2025/02/18(火) 10:32:01.38ID:Spp0fdd/
>>645
そうやればいいのか、なるほどね
2025/02/18(火) 17:51:16.96ID:ZRfTlf8i
Vecのnewやpushなど普通にcollectに任せる手もあるね
条件付き挿入は汎用にOptionで取捨を示してflat_mapとflattenでも可能
前値など状態を保ちつつ1つにまとめるならfoldでイテレータに流すならscan
一例としてこんな感じ

fn f(input: &[u8]) -> Vec<u8> {
　input
　　.iter()
　　.scan(None, |pre, &x| {
　　　Some([
　　　　pre.replace(x & 1)
　　　　　.and_then(|p| (p == x & 1).then_some(p + b'0')),
　　　　Some(x),
　　　])
　　})
　　.flat_map(|list| list.into_iter().flatten())
　　.collect()
}

>>640
Rust
648デフォルトの名無しさん
垢版 |
2025/02/19(水) 21:30:14.30ID:LKzHskwz
>>640
>>643-644の3つのfを上から順にf1, f2, f3とし、長い文字列を引数として呼び出したときの
実行時間を比較すると、

$s = -join (1..10000)
$t = 1..3 |% {(iex "measure-command {f$_ $s}").ticks}
$tmin = ($t | measure -min).minimum
1..3 |% {"f$_`: {0:0.00}倍" -f ($t[$_ - 1] / $tmin)}

[実行結果の一例]
f1: 34.78倍
f2: 1.00倍
f3: 14.93倍

大差でf2 < f3 < f1となった。インタプリタ言語のコード実行は遅いので、処理を自分で
書くほど遅くなり、ライブラリ関数等に丸投げすれば速くなることによる。

https://ideone.com/GVewWL
コンパイラ言語のC#で同様の比較をすると (PowerShellより速いので文字列を長くし、
f1の改良版としてStringBuilder使用のf4を追加した)、当然f4< f1 < f2 < f3になった。
2025/02/19(水) 21:58:22.55ID:Hs/awmG/
>>647
関数型でタブーの可変な変数宣言してもよいなら、もっと簡単になるね。

fn f(input: &[u8]) -> Vec<u8> {
　let mut pre = None;
　input
　　.iter()
　　.flat_map(|&x| {
　　　[
　　　　pre.replace(x & 1)
　　　　　.and_then(|p| (p == x & 1).then_some(p + b'0')),
　　　　Some(x),
　　　]
　　　.into_iter()
　　　.flatten()
　　})
　　.collect()
}
2025/02/20(木) 23:25:43.81ID:Zfo8kSSQ
mutableの使用は必要最小限が望ましいが
mutableを使えない言語は実用的ではない
651 警備員[Lv.21]
垢版 |
2025/02/22(土) 15:11:12.54ID:nEyoRU5r
>>640
Perl5
https://paiza.io/projects/gW_sI1_VqokddmYSJ6Lj2A
652 警備員[Lv.21]
垢版 |
2025/02/22(土) 15:42:54.65ID:nEyoRU5r
>>640
Kotlin
https://paiza.io/projects/mAEXhhFdJiHVQWYtHvIP-g
653 警備員[Lv.21]
垢版 |
2025/02/22(土) 15:53:04.03ID:nEyoRU5r
>>640
C
https://paiza.io/projects/7L9vpqOvFcbZfv9vO5GPvA
654デフォルトの名無しさん
垢版 |
2025/02/22(土) 23:33:07.08ID:k7PDvk0j
>>640
Haskell
https://ideone.com/U3SvTZ
655 警備員[Lv.21]
垢版 |
2025/02/24(月) 18:11:14.44ID:Ikw9MrIX
>>608

>>651とかとアルゴリズムはほぼ同じ。これといった捻りはない。
よく分からないが5chに書き込みがブロックされたのでURLのコロンまでは削った。

Perl
//paiza.io/projects/zAqms-VVEWIMhcgr8AV6Pw
Kotlin
//paiza.io/projects/iu8mTSyKsxqWx_T51Wpj4Q
C
//paiza.io/projects/bDkj3tRF_KmiBL67miRxyA
656デフォルトの名無しさん
垢版 |
2025/02/26(水) 21:33:47.93ID:rkiIsmEI
お題: Python の int.bit_count()

65535 → 16
15 → 4
6 → 2
1 → 1
0 → 0
-1 → 1
-6 → 2
-15 → 4
-65535 → 16
657デフォルトの名無しさん
垢版 |
2025/02/26(水) 23:29:03.38ID:Gl9HHMVG
>>656
C++20
https://paiza.io/projects/R-sSq9oCAOmG17wk6c5naw
2025/02/27(木) 00:23:41.10ID:TOGelnHV
>>656
Rust

fn bit_count(x: i64) -> usize {
const MAGIC_1: u64 = 0x5555555555555555; // 0101..0101
const MAGIC_2: u64 = 0x3333333333333333; // 0011..0011
const MAGIC_3: u64 = 0x0f0f0f0f0f0f0f0f;
const MAGIC_4: u64 = 0x00ff00ff00ff00ff;
const MAGIC_5: u64 = 0x0000ffff0000ffff;
const MAGIC_6: u64 = 0x00000000ffffffff;

let x = x.unsigned_abs();
let x = (x & MAGIC_1) + ((x >> 1) & MAGIC_1);
let x = (x & MAGIC_2) + ((x >> 2) & MAGIC_2);
let x = (x & MAGIC_3) + ((x >> 4) & MAGIC_3);
let x = (x & MAGIC_4) + ((x >> 8) & MAGIC_4);
let x = (x & MAGIC_5) + ((x >> 16) & MAGIC_5);
let x = (x & MAGIC_6) + ((x >> 32) & MAGIC_6);
x as usize
}

fn main() {
assert_eq!(bit_count(65535), 16);
assert_eq!(bit_count(15), 4);
assert_eq!(bit_count(6), 2);
assert_eq!(bit_count(1), 1);
assert_eq!(bit_count(0), 0);
assert_eq!(bit_count(-1), 1);
assert_eq!(bit_count(-6), 2);
assert_eq!(bit_count(-15), 4);
assert_eq!(bit_count(-65535), 16);
}
2025/02/27(木) 08:26:19.30ID:LSRTW28H
>>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};
impl BitCount for BigInt {
　fn bit_count(&self) -> usize {
　　self.iter_u64_digits().map(|x| x.count_ones() as usize).sum()
　}
}

fn main() {
　for (input, output) in [(65535, 16), (15, 4), (6, 2), (1, 1), (0, 0), (-1, 1), (-6, 2), (-15, 4), (-65535, 16)] {
　　assert_eq!(input.bit_count(), output);
　}
　assert_eq!(BigInt::from(-1).bit_count(), 1);
　assert_eq!((BigInt::from(2).pow(1_000_000_000) - BigInt::one()).bit_count(), 1_000_000_000);
}
660デフォルトの名無しさん
垢版 |
2025/02/28(金) 01:30:55.49ID:1HSOHgVq
intは処理単位のことなんだけどな
何ビットで表現できるかという意味ではない
6619
垢版 |
2025/02/28(金) 03:12:43.15ID:MEvV9q87
負の場合に表現可能なビット数を配慮しないとPython の int.bit_count()と同じ結果にならないんジャマイカじゃまいか
たぶんPythonの整数がbigintのせいだとおもう
絶対値とってpopcountとかやらないと意外とあれこれ書いてﾌﾟﾁ長めのコードになりそうなおかん
2025/02/28(金) 23:07:16.17ID:SRu+xdWw
よく見たらみんな絶対値をとったりbigintを使ったりしてるな
663デフォルトの名無しさん
垢版 |
2025/03/01(土) 20:18:20.34ID:H8RpZRUP
>>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 $_)"
}

[実行結果]
65535 → 16
15 → 4
6 → 2
1 → 1
0 → 0
-1 → 1
-6 → 2
-15 → 4
-65535 → 16
11110408185131956285910790587176451918559153212268021823629073199866111001242743283966127048043 → 159
664デフォルトの名無しさん
垢版 |
2025/03/01(土) 20:19:24.06ID:H8RpZRUP
お題：1からnまでの自然数のビット単位での総排他的論理和1 ⊕ 2 ⊕ 3 ⊕ … ⊕ nを求める
関数を作り、n = 123456789, 12345678901234567890のときの値を表示せよ。
665デフォルトの名無しさん
垢版 |
2025/03/01(土) 21:19:28.22ID:5VrbV50/
A003815かな
2025/03/01(土) 21:32:49.43ID:UfbLQAky
数学の試験で中間式を省いて解答だけ書くタイプw
667デフォルトの名無しさん
垢版 |
2025/03/01(土) 23:41:19.76ID:+HRoh0yF
まあ数列の問題ならOEISを見てみるよな
2025/03/02(日) 01:21:29.93ID:xdmIFouH
>> 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,
　　2 => n + 1,
　　3 => 0,
　　_ => unreachable!(),
　}
}

fn main() {
　for n in [123456789, 12345678901234567890] {
　　println!("f({n}) = {fn}", fn = f(n));
　}
}
出力
f(123456789) = 1
f(12345678901234567890) = 12345678901234567891
669デフォルトの名無しさん
垢版 |
2025/03/11(火) 21:18:30.26ID:Qmk3F8/1
>>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デフォルトの名無しさん
垢版 |
2025/03/13(木) 20:35:03.45ID:QP/8WHEA
お題：数列が入力される。元の数列に逆順にした数列を減算したときの値を出力せよ

In < 12345
OUt > -41976 (12345 - 54321)
671デフォルトの名無しさん
垢版 |
2025/03/13(木) 21:13:53.77ID:SRpNsp20
>>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
4922235242952026704037113243122008064 → 314233029528909439273950854852378624
2025/03/14(金) 02:10:51.25ID:wjeVVi0w
>>671
12の34乗は合っているけどその後の差がおかしくない？
4922235242952026704037113243122008064 から
4608002213423117304076202592425322294 を引いて
314233029528909399960910650696685770 が正解のところ
314233029528909439273950854852378624 となっているよ
正解は1の位が「4 - 4 = 0」になるはずだよね

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

use num::BigInt;

fn odai(input: &str) -> Option<String> {
　let rev_input: String = input.chars().rev().collect();
　let x: BigInt = input.parse().ok()?;
　let y: BigInt = rev_input.parse().ok()?;
　Some((x - y).to_string())
}

fn main() {
　assert_eq!(odai("12345"), Some("-41976".to_string()));
　assert_eq!(odai("4922235242952026704037113243122008064"), Some("314233029528909399960910650696685770".to_string()));
}
2025/03/14(金) 02:30:00.58ID:wjeVVi0w
>>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?))
}

fn odai<X>(input: &str) -> Option<X>
　where X: FromPrimitive + CheckedMul + CheckedAdd + CheckedSub,
{
　let x = chars_to_integer::<X>(input.chars())?;
　let y = chars_to_integer::<X>(input.chars().rev())?;
　x.checked_sub(&y)
}

fn main() {
　assert_eq!(odai::<i64>("12345"), Some(-41976));
　assert_eq!(odai::<BigInt>("4922235242952026704037113243122008064"), Some("314233029528909399960910650696685770".parse::<BigInt>().unwrap()));
}
674デフォルトの名無しさん
垢版 |
2025/03/14(金) 20:19:17.17ID:Imul3vYR
>>672
確かに間違っていた。PowerShellの旧ヴァージョンでは [BigInt]文字列 と書くだけで
文字列をBigInt型に正確に変換できるから>>671のプログラムでも正しい結果が得られるが、
新ヴァージョンではdouble経由での変換に仕様変更されたようで誤差が生じてしまうから
[BigInt]::Parse(文字列) と書かなければならなくなった。
675デフォルトの名無しさん
垢版 |
2025/03/14(金) 21:36:16.55ID:pC/XkvI4
数列の長さは指定されていない。

10 INPUT "0-9";I
20 PRINT "0"
30 END
2025/03/15(土) 19:04:58.28ID:GCbQqql0
>>673
これらのwhere~は何という名称ですか？

>　where X: FromPrimitive + CheckedMul + CheckedAdd,
>　where X: FromPrimitive + CheckedMul + CheckedAdd + CheckedSub,
6779
垢版 |
2025/03/16(日) 00:12:31.12ID:8GU62dKf
>>670 Perl5

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


実行結果

$ perl 22_670_reverse_minus_biginit.pl
-41976
314233029528909399960910650696685770
678 警備員[Lv.23]
垢版 |
2025/03/16(日) 17:25:01.96ID:wlGuyFJ7
>>670
Kotlin

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

https://paiza.io/projects/VBq2l9lhzmUxVo6xAMuAHg
679デフォルトの名無しさん
垢版 |
2025/03/16(日) 22:59:41.54ID:wtk+s/+W
>>670
PowerShellでジェネリック化(もどき?)
途中式や結果が入力値の型で表せない場合は$nullを返す。

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

12345, [BigInt]::Pow(12, 34), [byte]12, [sbyte]12, [sbyte]123, -123 |% {
　　"[$($_.GetType())]$_ → $(f $_)"
}

-- 実行結果 --
[int]12345 → -41976
[bigint]4922235242952026704037113243122008064 → 314233029528909399960910650696685770
[byte]12 →
[sbyte]12 → -9
[sbyte]123 →
[int]-123 →
680デフォルトの名無しさん
垢版 |
2025/03/16(日) 23:01:39.52ID:6JX6mCC/
お題：36桁以下の負でない整数で16進表記が10進表記の部分文字列であるものをすべて求めて下さい。

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

※遅い言語では15桁以下で解いても構いません
2025/03/16(日) 23:59:39.36ID:qWmLE6LP
>>676
where句だよ
型Xのトレイト境界を宣言してる
6829
垢版 |
2025/03/18(火) 16:05:22.66ID:GYPHuJM6
>>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, $_)) {
　　$n++;
　　print "$d, 0x$_\n";
　}
}
print "".localtime."\n";
print "$n count found";
6839
垢版 |
2025/03/18(火) 16:07:07.28ID:GYPHuJM6
>>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
2246166, 0x224616　　 3369253, 0x336925　　 3371313, 0x337131　　 3412566, 0x341256
4494393, 0x449439　　 4494400, 0x449440　　 4535653, 0x453565
5658739, 0x565873　　 5658740, 0x565874　　 5660793, 0x566079　　 5660800, 0x566080　　 5702166, 0x570216
6783879, 0x678387　　 6783880, 0x678388　　 6784000, 0x678400
6825253, 0x682525　　 7948339, 0x794833　　 7948340, 0x794834　　 7950393, 0x795039　　 7950400, 0x795040
2182104640, 0x82104640　　 2182104641, 0x82104641　　 2182104642, 0x82104642　　 2182104643, 0x82104643　　 2182104644, 0x82104644
2182104645, 0x82104645　　 2182104646, 0x82104646　　 2182104647, 0x82104647　　 2182104648, 0x82104648　　 2182104649, 0x82104649
1263629042727, 0x12636290427　　 1307655353654, 0x13076553536　　 2573583194436, 0x25735831944　　 2617616245848, 0x26176162458
3330782168640, 0x30782168640　　 3330782168641, 0x30782168641　　 3330782168642, 0x30782168642　　 3330782168643, 0x30782168643
3330782168644, 0x30782168644　　 3330782168645, 0x30782168645　　 3330782168646, 0x30782168646　　 3330782168647, 0x30782168647
3330782168648, 0x30782168648　　 3330782168649, 0x30782168649　　 3883544086630, 0x38835440866　　 3927569962533, 0x39275699625
3927570397557, 0x39275703975

Core i7-8559U で6時間ほど実行してここまで高々13桁。
やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。
2025/03/18(火) 16:35:06.57ID:lVLkTjWA
>>680
ruby
(0..10**16-1).each{|e| puts "#{e},0x#{e.to_s(16)}" if %r|[a-f]|!~e.to_s(16)}
685デフォルトの名無しさん
垢版 |
2025/03/18(火) 21:39:06.90ID:9hwr8+MV
>>683
14桁と15桁には該当値がないので、そこに列挙された数に0を追加した72個が15桁以下の答で
結果的には合っているよ。

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

その後、改良したC++プログラムではideoneで36桁以下を0.23秒に短縮できた。
6869
垢版 |
2025/03/18(火) 21:41:48.53ID:GYPHuJM6
>>683
>やはり想定通り気の利いた高速解放が要りますﾃﾍﾍﾟﾛ。

そのﾋﾝﾄになるかいな…？
・16進数を10進数に変換すると桁数は同じまたは高々1桁増えるのみ（だともう、証明略）
・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明
・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる
6879
垢版 |
2025/03/18(火) 21:42:49.00ID:GYPHuJM6
>>685
あそうなんだ。じゃオレ様が一番乗りということでヨロ
ﾉｼ
6889
垢版 |
2025/03/18(火) 21:52:10.05ID:GYPHuJM6
>>686
>・一桁増える場合は先頭または末尾に一桁増える。残りが16進数と同じ部分文字列であるかが評価対象となる

二桁増える場合があるのでこれは誤りでした
689684
垢版 |
2025/03/19(水) 06:18:11.44ID:khMnA4jS
ようやく題意は理解したけど良い解法が思いつかない
ちなみに36桁以下だと答えはいくつありますか？
2025/03/19(水) 08:44:27.79ID:khMnA4jS
>>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
end
6919
垢版 |
2025/03/19(水) 16:33:58.47ID:kDrq13vm
>>686
> ・桁数が同じ場合、16進数と10進数が同じということはあり得ない、自明

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

結局、高速解放はあるんだろうか？
あるいはコラッツ予想みたいに「無いかもしれない」類の、考えるだけ無駄な問題なのだろうか？
692デフォルトの名無しさん
垢版 |
2025/03/19(水) 21:08:24.40ID:VtmjGkS9
>>689
167個で最大値は697786638998562641695629924526065234

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

　2714476666993915057605587441263923823484611431446449961712093492

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

解答例は1週間くらい経ったら載せるので、それまでよく考えてみて下さい。
693デフォルトの名無しさん
垢版 |
2025/03/19(水) 22:39:07.36ID:P0JLFopv
お題：単位分数のエジプト風分解(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/60→1/64+1/960 : b=64, c=1, d=960
694693
垢版 |
2025/03/19(水) 22:42:43.02ID:P0JLFopv
aは2以上の整数とする。
に訂正します。
695デフォルトの名無しさん
垢版 |
2025/03/19(水) 23:16:25.83ID:G4dDQ6P7
>>693
R
https://ideone.com/TaaAw2

aが2の整べき乗の場合の出力形式に指定がなかったので適当に決めた。
2025/03/20(木) 08:21:38.87ID:6IEA4H0O
>>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 {
　　format!("1/{a}=1/{b}{c:+}/{d}")
　}
}

fn main() {
　assert_eq!("1/3=1/4+1/12", f(3));
　assert_eq!("1/7=1/8+1/56", f(7));
　assert_eq!("1/9=1/8-1/72", f(9));
　assert_eq!("1/13=1/16+3/208", f(13));
　assert_eq!("1/60=1/64+1/960", f(60));
　assert_eq!("1/64=1/64", f(64));
　assert_eq!("1/6718464=1/8388608+1631/55037657088", f(6718464));
　assert_eq!("1/123456789=1/134217728+10760939/16570089725755392", f(123456789));
}
2025/03/21(金) 12:56:29.73ID:CgJbZEAu
>>680 　Rust
fn odai_680() -> Vec<i128> {
　let mut answer = vec![0];
　let n_max = (0..).find(|&n| pow16(n + 1) > pow10(36)).unwrap();
　for s in (0..).take_while(|&s| pow16(n_max) >= pow10(n_max + s + 1)) {
　　let c = (0..=n_max).map(|i| pow16(i) - pow10(i + s)).collect::<Vec<_>>();
　　let rmax = c.iter().scan(0, |s, &c| { *s += if c > 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
　　let rmin = c.iter().scan(0, |s, &c| { *s += if c < 0 { c * 9 } else { 0 }; Some(*s) }).collect::<Vec<_>>();
　　let (mut i, mut n, mut d, mut ct) = (0, 1, vec![0; c.len()], vec![0; c.len() + 1]);
　　loop {
　　　d[i] += 1;
　　　if d[i] < 10 {
　　　　let m = pow10(n as u32 + s); ct[i] = c[i] * d[i] + ct[i+1];
　　　　if i == 0 {
　　　　　if ct[0] >= 0 && ct[0] % m < pow10(s) { answer.push(d.iter().take(n).rev().fold(0, |sum, &d| sum * 16 + d)) }
　　　　} else {
　　　　　let (max, min) = (ct[i] + rmax[i-1], ct[i] + rmin[i-1]);
　　　　　if max >= 0 && (max - min > m || pow10(s) > min % m || min % m > max % m) { i -= 1; }
　　　　}
　　　} else { d[i] = -1; i += 1; if i == n { if n == d.len() { break; } n += 1; } }
　　}
　}
　answer.sort(); answer
}
2025/03/21(金) 12:58:11.47ID:CgJbZEAu
>>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}")));
　}
　assert_eq!(0, answer[0]);
　assert_eq!(1, answer[1]);
　assert_eq!(357440, answer[10]);
　assert_eq!(2182104649, answer[54]);
　assert_eq!(3927570397557, answer[71]);
　assert_eq!(38135630558262267902210, answer[99]);
　assert_eq!(331052794565713975838768757043267, answer[152]);
　assert_eq!(697786638998562641695629924526065234, answer[answer.len() - 1]);
}
699デフォルトの名無しさん
垢版 |
2025/03/21(金) 20:49:29.98ID:uwhksDTb
>>697-698
Rustはよく知らないが、mainのforループ内をprintln!("{}", a);に置き換えれば解が表示されるんだよね?
実行結果を>>685で述べたC++プログラムのものと照合したら167個の解すべてが一致した。見事正解!
実行時間はC++プログラムの数倍かかるようだが、ideoneでの実行時間も見たいので載せて下さい。
700デフォルトの名無しさん
垢版 |
2025/03/23(日) 23:00:51.13ID:pi1bImlR
>>680から1週間経ったので解答例を掲載

>>685を書いたときに作ってあった2つのC++プログラム
https://ideone.com/KID2jR
https://ideone.com/ysdd6b

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) {と書き換えるべきだな。
実行時間への影響は無視できる。

それぞれのPowerShellへの移植版
https://ideone.com/vEGZ3D
https://ideone.com/azzMa4

完全な逐語訳ではなく、PowerShellで書くと遅くなったり煩雑になったりする箇所は適宜改変した。
15桁以下の場合は64ビット整数でも桁溢れしないので、BigIntの代わりにInt64を使えば少し速くなる。
701デフォルトの名無しさん
垢版 |
2025/03/24(月) 22:16:36.44ID:/lNBwDBZ
非素数であることが既知の巨大整数を素因数分解するときの
最速のアルゴリズムって何がある？
702デフォルトの名無しさん
垢版 |
2025/03/25(火) 15:25:56.57ID:Yc/egiP0
>>699
> 実行時間はC++プログラムの数倍かかるようだが

rustc -C opt-level=2 でコンパイルしたら
g++ -O2 でコンパイルした ideone_KID2jR.cpp (>>700の一つめ) とほぼ同じ速度出たよ
2025/03/25(火) 15:54:47.24ID:GZ5kfx5g
>>702
データ精度を揃えたアルゴリズム比較のために
>>697-698をi128固定ではなくnum::BigIntにして計測して見ては？

あと出題者>>685は>>700の二つ目で(倍速以上に)短縮出来たと言っているよ
704デフォルトの名無しさん
垢版 |
2025/03/25(火) 16:11:02.68ID:Yc/egiP0
そこまでは興味ないや
「数倍」だったのはもしかして最適化オプション付けてなかったんじゃない?ってだけの話
705デフォルトの名無しさん
垢版 |
2025/03/25(火) 17:30:47.40ID:Yc/egiP0
>>697-698をBigIntに変えるのはどうしたらいいのか分かんなかったので
>>700の方を boost::multiprecision::cpp_int から boost::multiprecision::int128_t に変えてみた

改変版 | オリジナル
https://ideone.com/Ie0HhO 0.12s | https://ideone.com/KID2jR 0.43s
https://ideone.com/np3p5h 0.11s | https://ideone.com/ysdd6b 0.23s
2025/03/25(火) 20:18:24.92ID:oTGl9wWX
>>705
感心した、出題者回答C++コードはほんの少し変更するだけで簡単にBigInt/i128切り替え出来るのか

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

Rustの古いコンパイラ（5年前のもの）がこんなに低性能だったとは…
2025/03/27(木) 11:39:31.21ID:vU3T1Sq/
>>697
crateのnumを使う
709デフォルトの名無しさん
垢版 |
2025/03/27(木) 20:29:20.38ID:DyGv4jyd
c言語で実用的なプログラムを作りたい。
いいテーマはありますか？
2025/03/27(木) 20:35:59.71ID:cvPlHeM5
お題：＃（シャープ）を入力の段数でウンコ状に並べて出力せよ
出力は全角でも半角でもどちらでもよしとする（5ch は半角スペース表示できない）

in < 3
out >
　　＃
　＃＃＃
＃＃＃＃＃
711デフォルトの名無しさん
垢版 |
2025/03/27(木) 21:06:27.50ID:AGn6MWSp
>>710
PowerShell

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

unko 3

-- 実行結果 --
　　＃
　＃＃＃
＃＃＃＃＃
712デフォルトの名無しさん
垢版 |
2025/03/28(金) 21:33:35.13ID:VDfNaTNz
お題：素因数の総和が2025である2000万以下の自然数をすべて求めて下さい。

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

※20億以下でもC++で5秒以内に余裕で完了できますが、出力が長すぎるため2000万以下としました。
　その結果、Rでも5秒以内に余裕で完了できる問題になりました。
713デフォルトの名無しさん
垢版 |
2025/03/28(金) 21:54:52.53ID:e6/uDocq
>>710
山状ではだめだったのか
俺にはわからない
714デフォルトの名無しさん
垢版 |
2025/03/28(金) 22:12:15.09ID:g08AymBh
お題
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デフォルトの名無しさん
垢版 |
2025/03/28(金) 22:28:49.68ID:VDfNaTNz
>>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]) {
　　　　if ($a -lt $b -and $h[$b] -contains $a) {"$a,$b"}
　　}
}

-- 実行結果 --
B,E
R,W
716デフォルトの名無しさん
垢版 |
2025/03/28(金) 23:19:47.32ID:VDfNaTNz
>>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

-- 実行結果 --
B,E
R,W
2025/03/29(土) 11:51:50.06ID:UeqVkFR5
>>714
Rust

use itertools::Itertools;

fn f(input: &str) -> impl Iterator<Item = &str> {
　input.split(',')
　　.map(|pair| (pair, pair.splitn(2, '-').collect_tuple().unwrap()))
　　.filter(|(_, (a, b))| a < b)
　　.flat_map(|(pair, (a, b))| {
　　　input.split(',')
　　　　.map(|pair| pair.splitn(2, '-').collect_tuple().unwrap())
　　　　.filter_map(move |(x, y)| (a == y && b == x).then_some(pair))
　　})
}

fn main() {
　let input = "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";
　itertools::assert_equal(["B-E", "R-W"], f(input).sorted());
}
2025/03/30(日) 01:28:45.68ID:KrBJAiIU
お題：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デフォルトの名無しさん
垢版 |
2025/03/30(日) 15:24:52.85ID:6QsLEZYT
>>718
ん？
何千回も試行してその実際の発生率を出すの？
それとも数学的に確率の理論値を出すの？
2025/03/30(日) 15:35:52.69ID:bQF7/1H+
後者で学校の課題な予感がするな
721デフォルトの名無しさん
垢版 |
2025/03/30(日) 20:11:24.72ID:qyCZpZxd
>>718
R Version4
https://ideone.com/r03zEZ

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

巨大整数型を使わなければideoneでも実行できる。
https://ideone.com/K0RefY
新着レスの表示
レスを投稿する

5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況