プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
266(3): デフォルトの名無しさん [sage] 2024/02/21(水)13:54:29.89 ID:ve9Dz9D8(1)
>>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が答え
十分大きな数に対しては虱潰しに回文判定していくより速く求まる
513: デフォルトの名無しさん [sage] 01/31(金)00:36:51.89 ID:MBodgIXJ(1)
>>510 ruby
https://ideone.com/K7lxJe
528: デフォルトの名無しさん [sage] 02/02(日)19:41:14.89 ID:NpAQnhYs(1)
リンクリストならindex番目の操作(挿入or切除)は
index番目で分解して操作して合体するだけなのでこれで動くよ
use std::collections::LinkedList;
trait LinkedListExt<T> {
fn insert_at(&mut self, index: usize, value: T);
fn remove_at(&mut self, index: usize) -> Option<T>;
}
impl<T> LinkedListExt<T> for LinkedList<T> {
fn insert_at(&mut self, index: usize, value: T) {
let mut tail = self.split_off(index);
self.push_back(value);
self.append(&mut tail);
}
fn remove_at(&mut self, index: usize) -> Option<T> {
let mut tail = self.split_off(index);
let value = tail.pop_front();
self.append(&mut tail);
value
}
}
570(2): デフォルトの名無しさん [] 02/11(火)20:45:09.89 ID:hMHygfcC(1)
>>561
R
https://ideone.com/3beF1j
C++
https://ideone.com/A8hp2f
それぞれ3通りの方法で、大きなデータでの実行時間を比較
621(3): デフォルトの名無しさん [] 02/15(土)21:06:37.89 ID:rssRTGdz(3/9)
>>561
C++
https://ideone.com/bQBKIM
C#のヌル許容型と同じ挙動のnullable型を自作し、>>593のC#のmin2関数をジェネリック化、
ポインタ参照化して移植した。
https://ideone.com/p2LNC9
593のC++のmin2関数と実行速度を比較する¹と30%ほど遅い。文字列型や可変長数値型と
違って最大値が存在する固定長数値型では、それを利用するf593の方が良い。
──
¹ Microsoft C++では100回繰り返しテストが最適化され1回しか実行されない
724: デフォルトの名無しさん [sage] 03/31(月)05:32:04.89 ID:lZyiUZP+(1)
>>718
学校の課題をここに書くなって教わらなかったの？
752: デフォルトの名無しさん [] 04/11(金)22:44:47.89 ID:4wK2/GRg(1)
>>750
これはとても速いな。ローカルで実行してみたら、>>738のRustプログラムと比較して
2000万以下で16倍、20億以下で55倍の速さだった。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.028s