プログラミングのお題スレ Part22 (830ﾚｽ)
上下前次1-新
1(4): 2023/08/03(木)13:52 ID:/xW45k0z(1) AAS
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
省14
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倍遅くなってる原因は
省3
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のサイズ拡張が実行時間に
及ぼす影響を見るためのテストで、解答として使うことはできないが。
省7
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万のベクタを用いている。
省4
760: 04/17(木)00:29 ID:dz0qzhSq(2/3) AAS
>>741
2000万個すべてを素因数分解する方法とは逆に、
2025以下の素数の組み合わせを調べていく方法。
そのうち和が2025になる組み合わせの積が各解となる。
それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。
つまり和がsumとなる時の積をp[sum]に記録していく。
効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、
省5
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までの残りの数が使われていて、
省10
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)
省11
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 };
省14
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(22): 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
省3
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
省1
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] を作成
省14
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(1): 07/30(水)21:50 ID:Ug40aZKP(1) AAS
>>771 java
外部ﾘﾝｸ:ideone.com
786(1): 07/31(木)14:56 ID:cLL+G38O(1/2) AAS
>> 771
java
>> 785氏のデータも加えてみた。
外部ﾘﾝｸ:ideone.com
ideoneのjavaはバージョン古いのか...
ま、通りがかりにこのスレみつけたのでちょっと書いただけ。
787: 07/31(木)18:54 ID:cLL+G38O(2/2) AAS
ち、勘が鈍った。＞＞もつけ間違えるし、sage忘れるし。
788: 785 07/31(木)21:15 ID:R3hgrYP8(1) AAS
>>771 java compose乱用
外部ﾘﾝｸ:ideone.com
789(1): 08/03(日)22:00 ID:1jv9m6G7(1) AAS
>>771
java >>786を修正。javaが古いねぇ。
外部ﾘﾝｸ:ideone.com
790(1): 08/04(月)22:42 ID:A9zbJQ8U(1/2) AAS
>>771
java >>789を修正。何度もすいませんね。classをメソッド内に移動。
外部ﾘﾝｸ:ideone.com
791: 08/04(月)23:09 ID:A9zbJQ8U(2/2) AAS
>>771
java >>790修正。classだったらメソッドの引数がみえるので修正。recordではできない。
外部ﾘﾝｸ:ideone.com
792: 08/05(火)01:04 ID:wgx4FmLX(1) AAS
class ValueWithIndex<U /*extends Comparable<U>*/> implements Comparable<ValueWithIndex<T>> {
ジェネリックは難しい。上のextends Comparable<U>は無くてもよいのだが、無駄でも明記したほうがよさそうなので、
ソースではそうした。
明記しなくとも、Uは正しく推測されているようだ。
793: 08/06(水)17:17 ID:qE4NV2ND(1) AAS
>>771
JavaScript
外部ﾘﾝｸ:paiza.io
794: 08/07(木)07:21 ID:W/yAWgo4(1) AAS
これからはメソッドの時代
795: 08/10(日)23:18 ID:FODtZCg5(1) AAS
>>771 scala
外部ﾘﾝｸ:ideone.com
>>771 swift
外部ﾘﾝｸ:ideone.com
796: 08/11(月)20:38 ID:frWpQyFA(1) AAS
>>771 dart 2.3
外部ﾘﾝｸ:ideone.com
・拡張メソッドはDart2.7から
・ideone現状はDart (dart 2.3.0)
797: 08/12(火)21:05 ID:uRUBTkGF(1/2) AAS
>>771
PowerShell 6以降
function rank($a)
{
$n = $a.length
$r = [int[]]::new($n)
if ($n) {0..($n - 1) | sort-object -stable {$a[$_]} |% {$i = 0} {$r[$_] = $i++}}
省19
798: 08/12(火)21:05 ID:uRUBTkGF(2/2) AAS
-- 実行結果 --
入力: [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]
省6
799(20): 08/16(土)01:44 ID:VU+jlz0U(1/2) AAS
【問題Ａ】
１～９を１つずつ使用して表される９桁の数Anは全部で9!（＝362880）個存在する。
整数n（1≦n≦362880）が与えられたとき、n番目に小さいAnを求めよ。
（例）
1 → 123456789
2 → 123456798
3 → 123456879
省14
800(1): 08/16(土)13:16 ID:MUbLd8/3(1) AAS
AA省
801: 08/16(土)19:14 ID:kN4EEg8M(1/3) AAS
>>799 の問題A
1からnまでの自然数を並べてできるi番目の順列を求める関数を前に作って持っていたので、
それを流用したらすぐできた（元の関数はBigIntとiの範囲外エラーにも対応）。
R
外部ﾘﾝｸ:ideone.com
C++
外部ﾘﾝｸ:ideone.com
802(3): 08/16(土)20:29 ID:kN4EEg8M(2/3) AAS
>>799 の問題B
R
外部ﾘﾝｸ:ideone.com
C++
外部ﾘﾝｸ:ideone.com
803(1): 08/16(土)21:32 ID:kN4EEg8M(3/3) AAS
>>799
>>802 のC++のithDuplicatedPermutation関数は引数が別の値（例えばn = 5, m = 3）のとき
正しく計算できなかったので修正。Rの方はintではなくdoubleで計算しているので問題ない。
外部ﾘﾝｸ:ideone.com
804(1): 08/16(土)21:46 ID:VU+jlz0U(2/2) AAS
32bitだと階乗は12!が限界
805(1): 08/17(日)12:07 ID:R1ye1QDy(1/2) AAS
>>799 ruby
外部ﾘﾝｸ:ideone.com
>>799 c
外部ﾘﾝｸ:ideone.com
806(2): 805 08/17(日)15:08 ID:R1ye1QDy(2/2) AAS
>>799 ruby 若干の改善
外部ﾘﾝｸ:ideone.com
>>799 c 若干の改善
外部ﾘﾝｸ:ideone.com
807: 08/17(日)15:21 ID:OrBxx4uG(1) AAS
ソートが消えて>>800と同じアルゴリズムになったね
808(1): 08/17(日)20:40 ID:bUKuWE64(1) AAS
>>804
確かにそうだった。15!も14!もintの範囲内に収まらない。>>803でn = 5に変えた場合に正しい
出力になるのはたまたまだった。
>>802をBigInt化するだけで問題なかった。
R
外部ﾘﾝｸ:ideone.com
C++
省1
809: 08/19(火)21:08 ID:zFi0pntB(1) AAS
AA省
810: 08/19(火)21:28 ID:ahVErwF8(1) AAS
>>771 scheme (chicken 4.13)
外部ﾘﾝｸ:ideone.com
811(1): 806 08/21(木)22:19 ID:fAlkh9Aq(1) AAS
>>799 ruby
外部ﾘﾝｸ:ideone.com
・問題A時に若干端折る
812(4): 08/21(木)23:15 ID:0KQ1xtxb(1) AAS
>>799 の逆変換プログラム
R
外部ﾘﾝｸ:ideone.com
C++
外部ﾘﾝｸ:ideone.com
問題A, 問題Bとは違って、順列に出現するユニークな整数は1〜nの連番でなくても良いし、
出現回数はすべて同じでなくても良い。例えば、入力は [3, 1, 4, 1, 5, 9] でも良い
省1
813: 08/22(金)01:14 ID:6LYRfbyj(1) AAS
>>799
Java
外部ﾘﾝｸ:paiza.io
814(1): 08/22(金)06:55 ID:qlaiAqZd(1/2) AAS
>>812
Rust >>799の逆変換の重複順列の何番目か算出
use itertools::Itertools;
use num::{BigUint, One};
// 重複順列の何番目かを求める ex. "222331434114" → "123456"番目
fn to_nth(input: &str) -> String {
// 出現数
省19
815: 08/22(金)06:56 ID:qlaiAqZd(2/2) AAS
>>814の検証分
fn main() {
assert_eq!(to_nth("123456789"), "1");
assert_eq!(to_nth("123456798"), "2");
assert_eq!(to_nth("123456879"), "3");
assert_eq!(to_nth("416589732"), "123456");
assert_eq!(to_nth("684753219"), "234567");
省16
816(1): 811 08/22(金)20:26 ID:m9vhyo0Z(1) AAS
>>799 ruby
外部ﾘﾝｸ:ideone.com
・問題A時に全体的な規則性に着目
・部分的に着目しちゃったのが>>811
・何も工夫を入れなかったのが>>806
817(1): 816 08/23(土)20:27 ID:uyhDG+iz(1/2) AAS
>>799 ruby 問題Bもケア
外部ﾘﾝｸ:ideone.com
818: 08/23(土)21:01 ID:gxRFdG35(1) AAS
>>799
java
外部ﾘﾝｸ:ideone.com
819(1): 817 08/23(土)23:26 ID:uyhDG+iz(2/2) AAS
>>799 java
外部ﾘﾝｸ:ideone.com
820(1): 08/24(日)21:13 ID:ubCw2JoQ(1) AAS
>>812の逆変換プログラムは>>808の順変換プログラムを流用したから処理に無駄があった。
逆変換用に一から書き直したらすっきりした。
R
外部ﾘﾝｸ:ideone.com
C++
外部ﾘﾝｸ:ideone.com
821(1): 819 08/25(月)00:28 ID:IbSJkZLt(1) AAS
>>799 java Iterable<int[]>
外部ﾘﾝｸ:ideone.com
822: 08/27(水)00:40 ID:AbNZa8yo(1/2) AAS
>>799 ocaml
外部ﾘﾝｸ:ideone.com
>>799 scheme (chicken 4.13)
外部ﾘﾝｸ:ideone.com
823: 08/27(水)21:02 ID:AbNZa8yo(2/2) AAS
>>799 octave
外部ﾘﾝｸ:ideone.com
824: 08/27(水)21:46 ID:B7vE54ji(1) AAS
>>820の逆変換プログラムのC#版
外部ﾘﾝｸ:ideone.com
LINQのTakeWhileメソッドとSumメソッドを組み合わせたらすっきり書けた。
825: 821 08/28(木)21:01 ID:mnaa+hsk(1) AAS
>>799 java
外部ﾘﾝｸ:ideone.com
・next()ごとに複製しない版。する版は >>821
・hasNext()側で次を準備。next()側なのは >>821
826: 08/29(金)13:52 ID:xrZF+zBK(1) AAS
>>799
外部ﾘﾝｸ:ideone.com
C++
827: 08/29(金)20:09 ID:VEuLqGzD(1) AAS
>>812 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・tallyあるのは2.7以降
>>812 octave
外部ﾘﾝｸ:ideone.com
828: 08/29(金)22:34 ID:uVFRnDIW(1/2) AAS
AA省
829: 08/29(金)22:35 ID:uVFRnDIW(2/2) AAS
-- 実行結果 --
【問題A】
1 → 123456789
2 → 123456798
3 → 123456879
123456 → 416589732
234567 → 684753219
省8
830: 08/30(土)17:37 ID:zI+bKiSo(1) AAS
>>812 ocaml
外部ﾘﾝｸ:ideone.com
>>812 scheme (chicken 4.13)
外部ﾘﾝｸ:ideone.com
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s