Skip to main content

すべての質問

でタグ付けされた
絞り込み
並べ替え
タグ付けされた
11
4 回答
4万 閲覧数

vectorとlistどのように使い分けますか

vectorとlistどのように使い分けますか?この様な質問を受けました。 そこで私は、vectorは配列でlistはリストだろう。 具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。 けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。 中間地点への一つのデータを頻繁に削除・...
user avatar
11
5 回答
2,043 閲覧数

高橋の数の算出について

各桁を並び替えてできる最大の数と 各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が 自身と一致するとき、高橋の数と呼びます。 (http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6) 以下のコードで、9桁までの高橋の数を 求めようとしたのですが、 9桁の高橋の数の算出に何時間も かかっています。 ...
TOM's user avatar
  • 1,582
6
1 回答
1,162 閲覧数

C++での自己参照構造体におけるポインタにおいて

C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照) この場合、p,l,rの型はNodeではなくてNode*です。 これはNodeではいけないのでしょうか? ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、 ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。 struct Node { int key; ...
Haruna Ojima's user avatar
3
7 回答
1万 閲覧数

四則演算はどういう順番で実行すると計算誤差が発生/伝搬しにくいですか

今ある問題は足し算と掛け算とわり算のみで構成されている演算です。 double c, m, d1, d2; /*それぞれに値を代入*/ double x = (c* m + ( d1 + 1.0/ d2 )/ 2.0 )/ (c + 1.0 ); という式です。この式をMaximaに投げると double x = (c* m + 0.5*( d1 + 1.0/ d2 ))/ (c + 1.0)...
user avatar
2
1 回答
424 閲覧数

経路長を求めポイントを多く稼ぐ方法

こんにちは。いつもお世話になっています。 いまパックマンのようなゲームを作ってまして敵のキャラのAIのようなものを作っています。 その際にアイテムを取る最短経路を求めることはできるのですがそうではなくただ最短を求めないで効率の良いと自分の思いついた作りたいプログラムの書き方がわからなくて質問しました。 前提として、ルールとして ...
take's user avatar
  • 69
2
3 回答
489 閲覧数

なぜこのコードはTLEになる?

下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。 同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。 しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか? 自分で書いたコード #...
Ranger's user avatar
  • 71
2
2 回答
514 閲覧数

2つの確率変数X,Yをとる確率関数 ​を表現するのに適したデータ構造を教えて下さい

C++言語において、確率P(x,y)を実装しています。 P(x)については実装してみました。といってもmapを利用してkeyが何回出現したかをsecondのカウンターを利用して全体で割ったものですが、 std::map<int,int> P; for(int i=0;i<10;i++) P.insert(std::make_pair(i,0)); P.find(rand())...
user avatar
2
1 回答
1,567 閲覧数

多面体の頂点群もしくは平面群から三角ポリゴンメッシュの作成

3Dグラフィックスで凸型多面体を描画したいと考えています。 多面体はそれを囲む平面(境界無し)で定義されているため、順序を問わないのであればすべての頂点を取得することが出来ますが、三角ポリゴンメッシュをねじれ等なく作成するスマートな方法が分かりません。
v..snow's user avatar
  • 980
2
1 回答
171 閲覧数

3次元の立方体同士の衝突検知で、GJKアルゴリズムを使ったが、誤検知される

私は、現在主に、c++とvulkan、glmを使って、3Dのゲームを作成しています。 現在、直方体同士の衝突判定を行うためにGJKアルゴリズムを作製しました。 しかし、下の画像のように立方体同士が離れているのに、衝突していると検知されます。下の画像の場合は衝突していると、コマンドライン上に表示されています。 私は以下の画像のような場合は、衝突していないと検知されるようにしたいです。 なお、...
siwameron's user avatar
1
2 回答
1,053 閲覧数

グラフ構造で節点にデータを入れたい

グラフ構造を実装しようとしています。 枝の距離をデータとして格納する方法はどの教科書を見ても詳細に記載されていましたが、節点の場合どうすればよいか分かりません。 O'Reilly Japan - アルゴリズムクイックリファレンスP.154 隣接行列のデータ構造 int A[][]= { {0, 0, 0, 0, 0, 0}, {6, 0,18, 0, 0, 0}, ...
user avatar
1
1 回答
788 閲覧数

ビットDPの思考回路について

以下のコードのアルゴリズムの思考回路がよくわかりません。 ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。 また、どのようにすればこのような思考でコードをかけるのでしょうか? どなたか分かる方はいらっしゃるでしょうか? コード元: 第16回日本情報オリンピック 予選4 #include<...
Ranger's user avatar
  • 71
1
0 回答
1,802 閲覧数

Levenberg-Marquardt法の結果がEigenとGnuplotで異なるのはなぜでしょうか

C++の数値計算ライブラリEigenに含まれる、非線形最小二乗法(Levenberg-Marquardt法)で関数フィッティングを実行してみました 開発環境はVisual Studio 2015です フィッティング対象の関数は、y = a×cos(x)^b で、ノイズを含む観測データx,yからパラメータa,bを求めます #include <iostream> #include <...
stlz's user avatar
  • 11
0
1 回答
572 閲覧数

Judy arrayとは何ですか?

連想配列のようですが 連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが なぜ、Judy arrayというものが生まれたのですか mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
user avatar
0
1 回答
334 閲覧数

C++での深さ優先探索が無限に終わらない

https://atcoder.jp/contests/abc074/tasks/arc083_a この問題をDFS(深さ優先探索)で解こうと思い、実装してみたのですが、下記の入力例3で無限ループになってしまい解けません。 なぜでしょうか? 書いたコード: #include <bits/stdc++.h> int a, b, c, d, e, f; std::vector<...
KiYugadgeter's user avatar
  • 4,358
0
3 回答
675 閲覧数

配列の中央値を求めるプログラムで毎回0しか出力されない問題について

繰り返し処理の各処理におけるパフォーマンスの中央値を求めるプログラムを書いています。 以下の記事を参考にして、配列から中央値を求める部分を書きました。 Vectorの平均値と中央値を求める コンパイルエラーはなく、実行時の出力において、中央値の箇所が毎回「0」になってしまうという問題があります。 どのように、プログラムを修正すべきか検討がつかず、教えていただきたいです。 出力 173, ...
user avatar
0
3 回答
3,812 閲覧数

幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?

質問 グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか? 深さ優先探索の場合、スタックか再帰関数を使って実装ができます。 一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。 参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、...
Haruna Ojima's user avatar
0
1 回答
150 閲覧数

C++で挿入ソートを実装する際、一時変数の役目が分からない

挿入ソートについて学習しており、一つ疑問があるのですが、なぜ temp の変数を使わなけばならないのでしょうか? 挿入ソート | Programming Place Plus アルゴリズムとデータ構造編 正しい挙動のコード:   int arry[] = {5,2,8,3,1}; for (int i = 1; i < 5; i++) {     int temp = ...
Shun Takahashi's user avatar
0
1 回答
335 閲覧数

最小全域木問題のプリム法のプライオリティキューを使った方法での入力と出力に関する問題

最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。 addEdgeにcinを挿入して実行してみましたが出力が上手くいきません。 g.addEdge()のような形で入力の内容を代入できますか?解る方お願いします。 入力: 7 9 0 1 1 1 2 2 1 3 3 1 5 7 2 4 10 3 5 1 3 6 5 4 5 5 5 6 ...
yn95ny's user avatar
  • 298
0
1 回答
133 閲覧数

AtCoder Beginner Contest 180 Takahashi Unevolved D問題

D - Takahashi Unevolved 解説リンク https://atcoder.jp/contests/abc180/editorial/219 上記リンク先に掲載されている解答コードで ans+(y-1-x)//b の部分がありますが、ここで-1をする理由がわかりませんでした。 こちらの意味を教えていただけないでしょうか。 よろしくお願いします
ジョンドゥ's user avatar
0
2 回答
235 閲覧数

キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか

概要 キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています 例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます これと同じような計算方法で分散を求めることはできますでしょうか? できる場合はどのようなアルゴリズムになりますでしょうか?
codeZ's user avatar
  • 429
0
1 回答
275 閲覧数

c++でのスタック構造について

逆ポーランドを実装しようとした際に、 while(scanf("%s", s) != EOF) で入力を受け取った後に if(s[0] == '+') で条件分岐が始まるのですが、なぜ s[0] と配列 s のインデックスを 0 に固定したままでも良いのでしょうか? s[0] の次は s[1] 、さらに s[2] とインデックスを増やしていき、最終的に s[n] が EOF ...
Nis's user avatar
  • 31
0
1 回答
184 閲覧数

動的計画法でナップサック問題を解く

動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。 なぜでしょうか? 1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。 多くの解説ではdpテーブルの遷移を dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値 としていますが、これを i番目(i-...
KiYugadgeter's user avatar
  • 4,358
0
1 回答
620 閲覧数

C++で2進数文字列を10進数文字列に直接変換したい

現在、c++で多倍長整数クラスBigIntを作成しているのですが、toString()の実装に行き詰まっています。数値を2進数文字列に変換するのはできましたが、それを更に10進数文字列に変換する方法がわかりません。 2進数文字列を10進数文字列に直接変換する方法がありましたらご教授ください。
user avatar
0
1 回答
200 閲覧数

蟻本P.164の問題のセグメント木での累積和の計算で意図した内容と異なる内容が出力される。

セグメント木での累積和の計算を入力してみましたが意図した内容と合いません。 出力される内容をresではなく、datb[k] * (r - l) + datc[k]の内容のように正しくしたいです。 #include <iostream> using namespace std; typedef long long ll; const int MAX_N = 100000; const ...
yn95ny's user avatar
  • 298
0
2 回答
300 閲覧数

ワーシャルフロイド法を使った経路復元のコードをまとめてみましたが結果の出力が思うようにいきません。

ワーシャルフロイド法を使って経路復元のプログラムを書いてみましたが結果の出力が思うようにいきません。 vector get_path(int s,int t)のvector ansへのまとめ方が悪いと思うのですがどうでしょうか? #include <iostream> #include <vector> using namespace std; const int ...
yn95ny's user avatar
  • 298
0
2 回答
207 閲覧数

最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。

コードを書いてみましたが出力が意図した通りになりません。 コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。 解る方よろしくお願します。 #include <iostream> #include <vector> using namespace std; const long long MAX_V = ...
yn95ny's user avatar
  • 298
0
0 回答
110 閲覧数

Atcoder abc165_c 期待する答えが出力されません

以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。 方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。 Atcoder abc165_c 問題概要  Q ...
user avatar
0
0 回答
253 閲覧数

1枚の画像からワールド座標を取得する

F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします. 何かよい導出方法ありませんか? 考えたこととして, カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが, ワールド座標と画面座標の3つの対応付けが必要で行き詰りました. よろしくお願いします.
jun j's user avatar
  • 1
-1
1 回答
401 閲覧数

深さ優先探索の問題(競技プログラミングの練習)

競技プログラミングの過去問を解いているのですがテストケースで期待した出力をしません。 なぜでしょうか? この問題は全探索の問題な感じなので深さ優先探索を使って解こうとしていますが答えと違う値が表示されてしまいます。 Problem B: 島はいくつある? この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる. この地図は,ある海域を表しており,...
KiYugadgeter's user avatar
  • 4,358
-1
1 回答
220 閲覧数

ある条件を満たす、matrixクラスのオブジェクトを生成したい

C++でmatrixクラスのオブジェクトで、以下の条件を満たすものを作成したいです。 オブジェクトの列数はSである オブジェクトは0か1を成分に持つ オブジェクトのそれぞれの行の要素の和はNである ここで、S個の成分のうち、N個、1を選ぶ組み合わせは、M = S C N (Cはコンビネーション)通り、存在します。したがって、 オブジェクトの行数はMである ...
user56056's user avatar
-1
1 回答
396 閲覧数

Atcoder ATC001 A 深さ優先探索をC++で再帰を用いて実装したがTLEになってしまう

ATC001 A 深さ優先探索をC++で以下のように実装しましたが、88個中12個TLE、2個MLEになってしまいました。 再帰を用いています。 goalの座標も引数に渡して、v=goalとなったらreturnするというのも試しましたが、ダメでした。 どう直せば良いでしょうか。 #include <bits/stdc++.h> using namespace std; vector&...
Tom's user avatar
  • 1
-1
1 回答
277 閲覧数

C++でソートした配列から中央値を求める時のエラー

繰り返し処理の各処理におけるパフォーマンスを配列に入れて、その中央値を求めるプログラムを書いています。繰り返し処理は、行列の足し算で各要素を足す処理を指しています。 前回までの質問に続いて、こちらの質問をします。 解決したいこと 中央値を求める部分で関数呼び出し後の型に関するエラーを解決したい コンパイルエラー(errorのみ抜粋、warningは除く) ...
user avatar
-1
2 回答
499 閲覧数

なぜこのコードは非効率なのか?

F - ヘビの JOI 君に挑戦したのですがTLEになります。 しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。 int N, M,X,T[10000]; struct edge{ int to,cost; }; struct situ { int cost,v,dist,type; ...
Ranger's user avatar
  • 71