すべての質問
33 件の質問
11
票
4
回答
4万
閲覧数
vectorとlistどのように使い分けますか
vectorとlistどのように使い分けますか?この様な質問を受けました。
そこで私は、vectorは配列でlistはリストだろう。
具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。
けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。
中間地点への一つのデータを頻繁に削除・...
11
票
5
回答
2,043
閲覧数
高橋の数の算出について
各桁を並び替えてできる最大の数と
各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が
自身と一致するとき、高橋の数と呼びます。
(http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6)
以下のコードで、9桁までの高橋の数を
求めようとしたのですが、
9桁の高橋の数の算出に何時間も
かかっています。
...
6
票
1
回答
1,162
閲覧数
C++での自己参照構造体におけるポインタにおいて
C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照)
この場合、p,l,rの型はNodeではなくてNode*です。
これはNodeではいけないのでしょうか?
ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、
ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。
struct Node {
int key;
...
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)...
2
票
1
回答
424
閲覧数
経路長を求めポイントを多く稼ぐ方法
こんにちは。いつもお世話になっています。
いまパックマンのようなゲームを作ってまして敵のキャラのAIのようなものを作っています。
その際にアイテムを取る最短経路を求めることはできるのですがそうではなくただ最短を求めないで効率の良いと自分の思いついた作りたいプログラムの書き方がわからなくて質問しました。
前提として、ルールとして
...
2
票
3
回答
489
閲覧数
なぜこのコードはTLEになる?
下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか?
自分で書いたコード
#...
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())...
2
票
1
回答
1,567
閲覧数
多面体の頂点群もしくは平面群から三角ポリゴンメッシュの作成
3Dグラフィックスで凸型多面体を描画したいと考えています。
多面体はそれを囲む平面(境界無し)で定義されているため、順序を問わないのであればすべての頂点を取得することが出来ますが、三角ポリゴンメッシュをねじれ等なく作成するスマートな方法が分かりません。
2
票
1
回答
171
閲覧数
3次元の立方体同士の衝突検知で、GJKアルゴリズムを使ったが、誤検知される
私は、現在主に、c++とvulkan、glmを使って、3Dのゲームを作成しています。
現在、直方体同士の衝突判定を行うためにGJKアルゴリズムを作製しました。
しかし、下の画像のように立方体同士が離れているのに、衝突していると検知されます。下の画像の場合は衝突していると、コマンドライン上に表示されています。
私は以下の画像のような場合は、衝突していないと検知されるようにしたいです。
なお、...
1
票
2
回答
1,053
閲覧数
グラフ構造で節点にデータを入れたい
グラフ構造を実装しようとしています。
枝の距離をデータとして格納する方法はどの教科書を見ても詳細に記載されていましたが、節点の場合どうすればよいか分かりません。
O'Reilly Japan - アルゴリズムクイックリファレンスP.154
隣接行列のデータ構造
int A[][]=
{
{0, 0, 0, 0, 0, 0},
{6, 0,18, 0, 0, 0},
...
1
票
1
回答
788
閲覧数
ビットDPの思考回路について
以下のコードのアルゴリズムの思考回路がよくわかりません。
ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。
また、どのようにすればこのような思考でコードをかけるのでしょうか?
どなたか分かる方はいらっしゃるでしょうか?
コード元: 第16回日本情報オリンピック 予選4
#include<...
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 <...
0
票
1
回答
572
閲覧数
Judy arrayとは何ですか?
連想配列のようですが
連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが
なぜ、Judy arrayというものが生まれたのですか
mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
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<...
0
票
3
回答
675
閲覧数
配列の中央値を求めるプログラムで毎回0しか出力されない問題について
繰り返し処理の各処理におけるパフォーマンスの中央値を求めるプログラムを書いています。
以下の記事を参考にして、配列から中央値を求める部分を書きました。
Vectorの平均値と中央値を求める
コンパイルエラーはなく、実行時の出力において、中央値の箇所が毎回「0」になってしまうという問題があります。
どのように、プログラムを修正すべきか検討がつかず、教えていただきたいです。
出力
173,
...
0
票
3
回答
3,812
閲覧数
幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?
質問
グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか?
深さ優先探索の場合、スタックか再帰関数を使って実装ができます。
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。
参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、...
0
票
1
回答
150
閲覧数
C++で挿入ソートを実装する際、一時変数の役目が分からない
挿入ソートについて学習しており、一つ疑問があるのですが、なぜ temp の変数を使わなけばならないのでしょうか?
挿入ソート | Programming Place Plus アルゴリズムとデータ構造編
正しい挙動のコード:
int arry[] = {5,2,8,3,1};
for (int i = 1; i < 5; i++)
{
int temp = ...
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 ...
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をする理由がわかりませんでした。
こちらの意味を教えていただけないでしょうか。
よろしくお願いします
0
票
2
回答
235
閲覧数
キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか
概要
キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
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 ...
0
票
1
回答
184
閲覧数
動的計画法でナップサック問題を解く
動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。
なぜでしょうか?
1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。
多くの解説ではdpテーブルの遷移を
dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値
としていますが、これを
i番目(i-...
0
票
1
回答
620
閲覧数
C++で2進数文字列を10進数文字列に直接変換したい
現在、c++で多倍長整数クラスBigIntを作成しているのですが、toString()の実装に行き詰まっています。数値を2進数文字列に変換するのはできましたが、それを更に10進数文字列に変換する方法がわかりません。
2進数文字列を10進数文字列に直接変換する方法がありましたらご教授ください。
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 ...
0
票
2
回答
300
閲覧数
ワーシャルフロイド法を使った経路復元のコードをまとめてみましたが結果の出力が思うようにいきません。
ワーシャルフロイド法を使って経路復元のプログラムを書いてみましたが結果の出力が思うようにいきません。
vector get_path(int s,int t)のvector ansへのまとめ方が悪いと思うのですがどうでしょうか?
#include <iostream>
#include <vector>
using namespace std;
const int ...
0
票
2
回答
207
閲覧数
最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。
コードを書いてみましたが出力が意図した通りになりません。
コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。
解る方よろしくお願します。
#include <iostream>
#include <vector>
using namespace std;
const long long MAX_V = ...
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 ...
0
票
0
回答
253
閲覧数
1枚の画像からワールド座標を取得する
F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします.
何かよい導出方法ありませんか?
考えたこととして,
カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが,
ワールド座標と画面座標の3つの対応付けが必要で行き詰りました.
よろしくお願いします.
-1
票
1
回答
401
閲覧数
深さ優先探索の問題(競技プログラミングの練習)
競技プログラミングの過去問を解いているのですがテストケースで期待した出力をしません。
なぜでしょうか?
この問題は全探索の問題な感じなので深さ優先探索を使って解こうとしていますが答えと違う値が表示されてしまいます。
Problem B: 島はいくつある?
この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる.
この地図は,ある海域を表しており,...
-1
票
1
回答
220
閲覧数
ある条件を満たす、matrixクラスのオブジェクトを生成したい
C++でmatrixクラスのオブジェクトで、以下の条件を満たすものを作成したいです。
オブジェクトの列数はSである
オブジェクトは0か1を成分に持つ
オブジェクトのそれぞれの行の要素の和はNである
ここで、S個の成分のうち、N個、1を選ぶ組み合わせは、M = S C N (Cはコンビネーション)通り、存在します。したがって、
オブジェクトの行数はMである
...
-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&...
-1
票
1
回答
277
閲覧数
C++でソートした配列から中央値を求める時のエラー
繰り返し処理の各処理におけるパフォーマンスを配列に入れて、その中央値を求めるプログラムを書いています。繰り返し処理は、行列の足し算で各要素を足す処理を指しています。
前回までの質問に続いて、こちらの質問をします。
解決したいこと
中央値を求める部分で関数呼び出し後の型に関するエラーを解決したい
コンパイルエラー(errorのみ抜粋、warningは除く)
...
-1
票
2
回答
499
閲覧数
なぜこのコードは非効率なのか?
F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。
int N, M,X,T[10000];
struct edge{
int to,cost;
};
struct situ {
int cost,v,dist,type;
...