スタート地点と1~nのチーズがおいてあるグリッドが与えられるので チーズを順番に取っていったときの最短経路の長さを求める問題。幅優先探索でiとi+1の間の最短経路をそれぞれ求めた。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define mp make_pair </queue></string></algorithm></vector></iostream>…

東西方向と南北方向に走る通りの名前の付け方が ありうるかどうか判定する問題。通りが平行でないかはグラフを２色に彩色して 色が異なっているかで判定。水準の判定は、交差点の入力にA-BがあればA→Bの辺を張り、 AとBが同水準ならA→BとA←Bの辺を張る。 こ…

動的計画法で解いた。 dp[i]:=長さiのメロディの得点の最大値 #include<iostream> #include<algorithm> using namespace std; int main(void){ int n,m,s[400],l[400],p[400],w[400],dp[400]; cin >> n; for(int i=0;i<n;i++) cin >> s[i] >> l[i] >> p[i]; cin >> m; for(int i=0;i<m;i++)cin >> w[i]; fil</m;i++)cin></n;i++)></algorithm></iostream>…

全てのショッピングモールのある街から グラフの辺上も含めて最長距離を求める問題。 ショッピングモールのある街を全てスタート地点として 最初にキューにプッシュしてダイクストラする。d[i]:=i番目の街からショッピングモールのある街への最短距離とする…

キャラクターの色が４つ以上揃ったら消していき、 残ったキャラクター数の最小値を出力する問題。全通り試した。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int Erase(vector<int> a){ for(int i=0,j=0;j<a.size();){ if(a[j]==a[j+1])j++; else { if(j-i>2){ a.erase(a.begin()+i,a.begin()+j+1); i=j=0; </a.size();){></int></algorithm></vector></iostream>…

戻り蝿のデータを入力とし、(1,1,1)に戻ってくる最小の移動回数を求める問題。x,y,zがそれぞれ何回の移動回数で1に戻ってくるかを求め、 その3つの最小公倍数が答えとなる。 #include<iostream> #include<vector> #include<algorithm> typedef long long ll; using namespace std; ll gcd(</algorithm></vector></iostream>…