[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
272
質問
0
票
2回答
368 件の閲覧数
なぜこのコードは非効率なのか?
F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。
int N, M,X,T[10000];
struct edge{
int to,cost;
};
struct situ {
int cost,v,dist,type;
...
0
票
1回答
71 件の閲覧数
エラー: 'closure' 型のオブジェクトは部分代入可能ではありません
Bootstrap法によって機械学習アルゴリズムの精度を検証するプログラムを作っています。
以下のコードをテキストで作成し、CSVdataをread.csvで読み込んで、以下のように実行すると
> source("text.txt")
> exdata=read.csv("final_output.csv",header=TRUE)
> ...
0
票
1回答
67 件の閲覧数
AtCoder Beginner Contest 180 Takahashi Unevolved D問題
D - Takahashi Unevolved 解説リンク
https://atcoder.jp/contests/abc180/editorial/219
上記リンク先に掲載されている解答コードで
ans+(y-1-x)//b
の部分がありますが、ここで-1をする理由がわかりませんでした。
こちらの意味を教えていただけないでしょうか。
よろしくお願いします
2
票
2回答
118 件の閲覧数
キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか
概要
キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
1
票
2回答
180 件の閲覧数
python のitertools.permutationsの使い方を教えて下さい。全部の組み合わせの作り方を教えて下さい。
1年前の問題ですけど、確かめてみたい。
(参考)小学生のみなさんへ、場合の数「2020年度京都大学理系学部数学第5問」にチャレンジしてみて下さい。
https://qiita.com/mrrclb48z/items/a97086d25b3d0bee7125
①[1234]×[1234]×[1234]×[1234]/直積(デカルト積,Cartesian Product)の使い方を教えて下さい。
②...
7
票
1回答
2,677 件の閲覧数
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
Git のドキュメントによると、git merge は内部で 3-way merge を行います。
2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git ...
0
票
1回答
122 件の閲覧数
平方数の判定を、sympyの素因数分解factorintでできますか?
目的は、平方数の判定を一行でできますか?よろしくお願いします。
print(factorint(9))
{3: 2}
print(factorint(81))
{3: 4}
参考nが平方数かどうか調べる時
https://teratail.com/questions/200122
参考:Wolfram|Alpha
81は平方数ですか
https://ja.wolframalpha.com/...
0
票
1回答
131 件の閲覧数
Pythonでの単方向リストの実装
Pythonを用いてリストを実装しようとしています。
Linked List のようにして実装しています。
以下のコードの「ここ!!」とした部分ですが、なぜreturnする必要があるのでしょうか。self.headにnew_nodeが入ってif文は終わりなのではないでしょうか。
試しにreturnを消してみると、プログラムが止まらず、同関数内のwhileから抜けられていないことがわかりました。
...
0
票
1回答
119 件の閲覧数
多角形同士の衝突判定のアルゴリズムについて
多角形同士の衝突判定のアルゴリズムを検討しています。
愚直に衝突判定を行う場合、多角形の各直線が別の多角形と衝突していないか、全直線同士組み合わせでチェックしていくのかと思います。
ただし、この方法だと多角形の頂点数が多い場合や、多角形が多い場合に処理が非常に多くなってしまうと思われます。(多少は処理を間引きできるとは思いますが)
高速で衝突判定ができるようなアルゴリズムはあるでしょうか?
0
票
0回答
78 件の閲覧数
Atcoder abc165_c 期待する答えが出力されません
以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q ...
1
票
0回答
65 件の閲覧数
ノードの長さを自由に持てるツリーの最適配置アルゴリズム
現在、マインドマップを自作しようとしておりますが、ノードの配置のアルゴリズムについて困っています。
作ろうとしているツリーの条件は以下を考えています。
Y軸のトップにルートノードを1つ持つ
親ノードから、子ノードを複数持つことができる
ノードとそれを連結する線は重ならないが、可能な限り近くに配置される
親ノードのX軸の位置は、その子ノードの中央になる
X軸方向で、...
3
票
1回答
106 件の閲覧数
マインドマップの図形最適配置のアルゴリズム
マインドマップを作成しようとしています。
以下のルールで配置しようと思っています。
・各要素は長方形
・ルート要素は1つ
・親要素の下にぶら下がるように、直下の子要素がずらっと横一列に並ぶ
・親要素は、並んだ直下の子要素の中央に配置される
この条件を満たしつつ、なるべく全体としてコンパクトに配置するにはどうすれば良いでしょうか?
良いアルゴリズムなどはありますでしょうか?
3
票
3回答
189 件の閲覧数
rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?
rsa の素数のペアはどのように生成される? の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA 鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass ...
1
票
1回答
167 件の閲覧数
(openssl の) RSA 秘密鍵の中身はそれぞれ何を表す?
openssl で rsa の鍵を適当に test.pem で生成して、その中身を openssl rsa -in test.pem -text -noout で眺めていました。(長いので、この質問の末尾に付与します)
この中で、prime1, prime2 はそれぞれ 1536 == 3072/2bit 長の素数(以降、p, q と呼びます)、 modulus は p * q のかけ算の結果(...
0
票
2回答
672 件の閲覧数
ダイクストラ法の実装
ダイクストラ法をmain関数内の「課題追加部分」で実装するのですが方法がわかりません...
実装方法を見ても①から意味がわからない状態です...
import java.util.*;
public class Dijkstra {
public static void main(String[] args) {
final List<LocatedVertex&...
5
票
0回答
186 件の閲覧数
Git のマージ戦略 “resolve” とはどのような戦略ですか?
git merge のマージ戦略には resolve というものがあります。
resolve
This can only resolve two heads (i.e. the current branch and another branch you pulled from) using a 3-way merge algorithm. It tries to carefully ...
2
票
2回答
161 件の閲覧数
rsa の素数のペアはどのように生成される?
RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
質問
今ある RSA ...
0
票
0回答
108 件の閲覧数
分析のためにゲーム木を描写したくなったとき、利用可能なライブラリ・フレームワークは何がありますか?
ターン制の対戦ゲームは、基本的にゲーム木を構築できます。たとえば○×ゲーム(tic-tac-toe)のゲーム木はこちらです。
Game tree for Tic-Tac-Toe game using MiniMax algorithm.
今、ふとした分析のために、このようにゲーム木を描写したくなりました。
質問
ゲーム木を描写する機能を持った、つまり、ゲーム木の可視化ができる、...
0
票
1回答
203 件の閲覧数
二次元配列に条件付きで数字を代入
与えられた数字を二次元で保存したいです。例えば、数列{3,12,4,1,5,8}を与えられたとして、一番目の数字3を配列1に挿入、二番目の数字12は、3より大きいので別の配列2に挿入、左から走査し、4は12より小さいので配列2に挿入、1は左から走査し3より小さいので配列1に挿入...ということを行いたいです。
構造的には、二次元リスト
int s = {3,12,4,1,5,8}
int ...
2
票
1回答
147 件の閲覧数
弧を描いて指定位置で止まりたい
弧を描いて指定位置で止まりたい
ゆるやかに減速しながら直進する物体を
境界線を超えたら一気に減速しつつ
入射角に見合った弧を描きながら境界線まで戻ってきて
ちょうど境界線で止まる(動きが止まったときの位置がちょうど境界線上になる)
ようにしたいです
1と2まではできました(まだGoogle Chromeでしか確認していませんが)
3と4はどうすればいいですか?
...
1
票
1回答
65 件の閲覧数
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
ぱっと思いつくのはSQLのGROUP BYを使うことですが、
数十万件ヒットする結果でも、非常に高速に表示されていて、
なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
2
票
0回答
47 件の閲覧数
matlabでnsga2を実装.目的関数の範囲指定,設計変数と目的変数の最大化を行いたい.
NSGA2をmatlabで動かせるよう以下のURLからダウンロードし実装.
https://jp.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm
実際に動かしてみて,成功はしたのですが
目的変数はすべて最小化
設計変数の範囲のみが指定可能
...
1
票
1回答
214 件の閲覧数
Can someone solve level 12 of this logic game
I run into this game and manage to solve level one to eleven but not able to solve level twelve, I think it is recursive algorithm, sorry if this is not question for this site :)
Here is the link
http:...
2
票
1回答
182 件の閲覧数
3剤3期クロスオーバーの分散分析:誤差をエクセルで算出したい
3剤3期クロスオーバーの分散分析を、Rで実行しました(以下Rプログラム)。
この分散分析表の誤差「8.5089」をエクセルで算出したいのですが、結果が合いません。(誤差以外は検算できました)
以下に、エクセルの画像を添付しました。
どこの解釈が違うのか、どなたかアドバイスをお願いしてもよろしいでしょうか。
※データは「医薬品開発のための統計解析 第2部p.282」です。
※ 同じ質問を ...
2
票
1回答
152 件の閲覧数
fileの読み込みや、書き込みで出てくるstreamとは何でしょうか?
言葉の意味がよくわからないのでご質問させてください。
例えば、nim言語(おそらくPHPなどでも同じでしょうが)では、
ファイルの書き込みは以下の様に実現できます。
var fw = open("test.txt" , FileMode.fmWrite)
fw.write("hoge")
fw.close
また以下のように書いても同じ動作をしているようです。...
0
票
0回答
87 件の閲覧数
平叙文(穴埋め問題)から疑問文(一問一答問題)を作成したい
教科書の文から作った穴埋め問題を一問一答形式の問題にしたいです。
例)(文)メフメト2世はビザンツ帝国を滅ぼした (空所単語)ビザンツ帝国
→(問)メフメト2世が滅ぼしたのはどこ。(答)ビザンツ帝国
現実的に可能かどうか教えてください。
以下のような手順で作成しようと思っています。
品詞分解(形態素解析)
↓
単文・複文・重文の判別(主語述語の個数、並べ方から判別。...
0
票
1回答
89 件の閲覧数
Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい
概要
タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。
テーブルに木構造を表示するために、データを一次元配列で提供できる
その際、Orderを保持できる(画像のイメージ)
定数時間での検索が可能O(1)
AppendToParent, ...
1
票
1回答
175 件の閲覧数
クイックソートと同時にランキングを作ることはできますか?
A,10,50,32
B,30,60,21
C,15,45,61
というcsvファイルを読み込んで、A~Cの順番を崩さずに次の条件を満たしたdat、csvファイルを出力したいです。順番を崩したくない理由は、A, B, Cの並び順によって一意な値(配列の添え字)を割り振るためです。
降順にソートした結果の4列目のデータだけのdatファイル
期待する出力:
61
32
21
...
1
票
2回答
150 件の閲覧数
Excel VBA の1回の実行で、通過した通過しなかったfunction、subを分類する方法を教えて下さい
全てのfunction, subに一行ずつ debug.print”function1通過” と書く方法しかありませんか?
書くとしたら、正規表現置き換えの方法で、対応可能ですか?
全エクスポートで、エディタの正規表現置換後、全インポートを予定しています。
例) 全てのfunction, sub2行目に debug.print "なまえ通過” を挿入する方法がありますか?
他言語でも、...
0
票
0回答
86 件の閲覧数
ASCIIで記述した回路を図面に変換するアルゴリズムを探す
現在ASCIIで記述したノードとノードとのつながりを図面に変換するアルゴリズムを探します。
特に、Synopsys VerdiのようにVerilog HDL/VHDLコードからきれいな理解しやすい回路図を生成したい。どんなアルゴリズムでこれを果たすことができますか。
ノードの形は何でも構いません。
0
票
0回答
46 件の閲覧数
クロスオーバー試験におけるSAS proc glm 2段階の解析方法:absorbステートメントについて
「SASによる実験データの解析(初版)」を参照しています。「8-2分散分析」の項で、「2段階にGLMプロシジャを分割する」方法が紹介されています。一般的な方法(分割しない)でできますが、クロスオーバー試験における分散分析を勉強するため確認しています。2段階の方法で分からないことが以下2点あります。どなたかアドバイスをお願いしてもよろしいでしょうか。
1.1段階目のproc ...
0
票
1回答
117 件の閲覧数
クイックソートのpivotが中央値が最も良いとされる理由
クイックソートのpivotが中央値が最もいいとされる理由の認識は下記の通りであっていますでしょうか
以下のような配列があった場合、下のようにpivotに中央値を選び均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
よって中央値で分割できると高速で処理できる。
[4,3,...
4
票
2回答
472 件の閲覧数
クイックソートのpivotの決め方について
情報系学生です
クイックソートではpivotの決め方が非常に重要だと思うのですが、それぞれにどのようなメリットがあるのでしょうか?
①配列から3つ選び、その中の中央値をpivotとする
②配列の先頭2要素を比べ大きい方をpivotとする
③ランダム
④①を繰り返し、①で得られた中央値候補の中央値をpivotとする
正直優先順位的には
④>①>③>②だと思うのですがどうでしょうか
...
3
票
0回答
78 件の閲覧数
R木系(特に PR 木)のアルゴリズムを理解したい
位置情報などを効率的にインデックスするための手法として、R木があります。
質問
R木(特に、 PR 木)をどうやって実装するのか、とくに、そのアルゴリズムを知りたいと思っています。当たれる書籍などはありますか?
0
票
1回答
71 件の閲覧数
有向グラフの表現で、E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} の表すものが分からない
有向グラフG=(V,E)の時、V = {1, 3, 4, 5, 6, 12} and E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} といった表現がされていた場合のEの右辺の表現が理解できません。この場合はどのようなグラフが期待されるのでしょうか?ご教示いただけると幸いです。
2
票
0回答
74 件の閲覧数
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて
数理最適化に関するアルゴリズムに関して学習しています。
0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、
調べても連続変数の2次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。
0-1整数2次計画問題に関して
https://www.letsopt.com/entry/2019/08/18/131125
...
3
票
2回答
184 件の閲覧数
注文IDなどユーザーに見せるユニークなIDの作成方法
プログラムの内部でユニークなIDが欲しい場合は、UUIDが多く用いられると思いますが、
桁数が32桁と、ユーザーに見せる場合、少し桁数が多く複雑すぎるように感じます。
実際、ECサイトなどで購入したさいに得られる注文IDなどははUUIDではなさそうに見えます。
どのようなアルゴリズムで10-15桁程度の注文ID(ユニークID)を生成しているのでしょうか?
0
票
0回答
46 件の閲覧数
backlog 的なウェブアプリを開発する際に、そのイベントと永続化のモデルはどう実装するのが良い?
シンプルな todo リストに、任意に順番を付与できるようなウェブアプリを開発するとします。さらに、その順番は Drag & Drop で移動可能であるとします。
今、この機能を、 UX の目的で、フロントとバックエンドの処理を非同期に行いたいとします。つまり、フロントの状態は Drag の後の Drop の際に update してしまい、...
0
票
1回答
167 件の閲覧数
c++でのスタック構造について
逆ポーランドを実装しようとした際に、 while(scanf("%s", s) != EOF) で入力を受け取った後に if(s[0] == '+') で条件分岐が始まるのですが、なぜ s[0] と配列 s のインデックスを 0 に固定したままでも良いのでしょうか?
s[0] の次は s[1] 、さらに s[2] とインデックスを増やしていき、最終的に s[n] が EOF ...
0
票
1回答
95 件の閲覧数
二分探索木を分割する際の計算量
https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar
こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
2
票
1回答
782 件の閲覧数
eddsa による暗号化は、 rsa の上位互換ですか?
ssh で利用される暗号化鍵には、長らく RSA が利用されてきました。RSA と比べれば最近になって、 EdDSA の暗号化方式が追加されたようです。
質問
EdDSA による暗号化は、アルゴリズム的には RSA の上位互換ですか? 具体的には、
暗号を破るための計算を行う際の計算量クラスは RSA 以上で
同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で
...
2
票
0回答
110 件の閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
2
票
2回答
168 件の閲覧数
計数ソートを入力順にソートした際の安定性
下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-...
2
票
2回答
134 件の閲覧数
計算量O(1)とO(n)
https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/?ref=lbp
上記のサイトには、計算量O(1)の例では
// Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) ...
0
票
3回答
183 件の閲覧数
異なる文字列の接頭語と接尾語を比較
ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。
現在は、
S1,S2を読み込む
S1を反転
S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。
...
3
票
1回答
138 件の閲覧数
帰りがけ順から二分探索木の生成
ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか?また、その場合どういったアルゴリズムになりますか?
0
票
2回答
300 件の閲覧数
python 配車問題
pythonを最近学習し始めた者です。
pythonを使用してやりたいことがあるのですが、キーワードがわからない為、やり方を検索できずにいます。
以下やりたい内容となります。
やりたいこと:ある地域の中に3つのタクシー会社があるとします。(会社A・会社B・会社C)各会社の所有タクシー数は、[会社A:2台][会社B:2台][会社C:1台]
タクシーを呼ぶ人は地域内の建物にいることとし、...
0
票
2回答
93 件の閲覧数
2つのいくつかのノードを共有する連結リストをソートしたい
最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?
たとえば
-900->120->200->230
\
452->700
/
-10->200
...
0
票
1回答
265 件の閲覧数
プログラムの実行時間をできるだけ短くしたい
プログラムの実行時間をできるだけ短くしたいです。
最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです
入力の条件は、
The first line contains the integer N. The second line contains N integers, a0,a1,...,aN−1. The integers ...
0
票
1回答
212 件の閲覧数
一つのプログラムで複数の連結リストの作成
配列を使わず、連結リスト(単方向)のみでキューのデータ構造を実装したいです。 C言語を用いて、一つのプログラムで複数の連結リストを実装することは可能でしょうか?structの定義で行き詰まってしまったので、実例も教えてくださると嬉しいです…。
追記
struct node1
{
int data1;
struct node1 *next1;
};
struct node2
...