Educational Codeforces Round 27
A問題 Chess Tourney
問題文
2*n個の数字が与えられ、それをn個ずつの2組に分割します。そして2組からそれぞれ一つずつ取り出しn個のペアを作ります。
ここで、1つのペアの中で数字が大きい方が勝ちとします。そしてn個のペアで全て勝つような組が作れればYESを、作れなければNOを出力する.
解説
数字をソートして、真ん中の2つの数が等しくなっていないかを判定すれば良いだけです。
コード
#include <iostream> #include <algorithm> using namespace std; int main(void){ int n, r[1001]; cin >> n; for(int i=0; i<2*n; i++){ cin >> r[i]; } sort(r, r+n); if(r[n-1] == r[n]){ cout << "NO" << endl; }else{ cout << "YES" << endl; } return 0; }
Chokudai Speed Run G問題
Chokudai Speed Run001 G問題解説
問題
数列 aが与えられ a を連結させた整数を、 1,000,000,007 で割った余りを求めなさい。
サンプル
Input
7
7 6 5 4 3 2 1
Output
7654321
解説
全てを加えて剰余をとるという方針はlong long では所持できないので不可能です
そこで剰余の性質の以下2つを使います。
(x*y)%MOD = ( (x%MOD) * (y%MOD) ) % MOD
(x+y)%MOD = ( (x%MOD) + (y%MOD) ) % MOD
この二つの性質を使うことによって桁を一つづつ見ていくことによって連結した数列の剰余を正しく求めることができます。
以下コード
#include <iostream> using namespace std; #define MOD 1000000007 int main(void){ int n; string s; cin >> n; for(int i=0; i<n; i++){ string tmp; cin >> tmp; s += tmp; } long long ans = 0; for(int i=0; i<s.length(); i++){ ans = ans * 10 + (s[i]-'0'); ans %= MOD; } cout << ans << endl; return 0; }
ダイクストラ法(priority_queue)、経路復元
経路復元(ダイクストラ法)
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; struct edge { int to, cost; }; typedef vector<vector<edge> > AdjList; AdjList graph; typedef pair<int, int> P; const int INF = 10000000; vector<int> dist; vector<int> prever; void dijkstra(int n, int s){ dist = vector<int>(n,INF); prever = vector<int>(n,-1); dist[s] = 0; priority_queue<P, vector<P>, greater<P> > que; que.push(P(0,s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first){ continue; } for(int i=0;i<graph[v].size();i++){ edge e = graph[v][i]; if(dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; prever[e.to] = v; que.push(P(dist[e.to],e.to)); } } } } vector<int> get_path(int t){ //頂点tへの最短路 vector<int> path; for(; t != -1;t=prever[t]){ path.push_back(t); } reverse(path.begin(), path.end()); return path; } int main(void){ int n, m; cin >> n >> m; graph = AdjList(n); for(int i=0;i<m;i++){ int from, to, cost; cin >> from >> to >> cost; graph[from].push_back((edge){to,cost}); } dijkstra(n,0); vector<int> ans = get_path(3); for(int i=0;i<ans.size();i++){ cout << ans[i] << endl; } return 0; }
ベルマンフォード法とダイクストラ法をvectorで実装
ベルマンフォード法
#include <iostream> #include <vector> using namespace std; struct Edge { int to, cost; }; typedef vector<vector<Edge> > AdjList; // 隣接リストの型 AdjList graph; const int INF = 1000000; vector<int> dist; bool bellman_ford(int n, int s){ dist = vector<int>(n,INF); dist[s] = 0; for(int i=0;i<n;i++){ for(int v=0;v<n;v++){ for(int k=0;k<graph[v].size();k++){ Edge e = graph[v][k]; if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; if(i == n-1) return true; } } } } return false; } int main(void){ int n, m; cin >> n >> m; graph = AdjList(n); for(int i=0;i<m;i++){ int from, to, cost; cin >> from >> to >> cost; graph[from].push_back((Edge){to,cost}); } bellman_ford(n,0); for (int i = 1; i < n; i++){ if(dist[i] != INF){ cout << "0から" << i << "へのコスト:" << dist[i] << endl; } } return 0; }
ダイクストラ法
#include <iostream> #include <vector> #include <queue> using namespace std; typedef pair<int, int> P; struct edge { int to, cost; }; typedef vector<vector<edge> > AdjList; AdjList graph; const int INF = 10000000; vector<int> dist; void dijkstra(int n, int s){ dist = vector<int>(n,INF); dist[s] = 0; priority_queue<P, vector<P>, greater<P> > que; que.push(P(0,s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first){ continue; } for(int i=0;i < graph[v].size();i++){ edge e = graph[v][i]; if(dist[e.to] > dist[v] + e.cost){ dist[e.to] = dist[v] + e.cost; que.push(P(dist[e.to],e.to)); } } } } int main(void){ int n, m; cin >> n >> m; graph = AdjList(n); for(int i=1;i<m;i++){ int from, to, cost; cin >> from >> to >> cost; graph[from].push_back((edge){to,cost}); } dijkstra(n,0); for(int i=0;i<n;i++){ if(dist[i] != INF){ cout << "0から" << i << "へのコスト:" << endl; } } return 0; }
参考
最短経路問題(ベルマンフォード法・ワーシャルフロイド法) - アルゴリズム講習会
蟻本
055ABC D問題D - Menagerie
問題D - Menagerie
この問題は1番目と2番目を決めてあげれば3番目がSかWかが決定できます。
そこで1番目、2番目を 『S、S』『S、W』『W、S』『W、W』と決めてあげれば与えられた文字列から全体を決定することができます。 そして完成した文字列が与えられた文字列と矛盾していないか最後には判定します。文字列を作成するのにはox文字列の最後から一つ前まで見てあげれば良いです。 したがって矛盾判定を行う箇所はox文字列最後の要素を含んだ3組を判定してあげれば良いです。 具体的には以下の3組ようになります。
n-3 n-2 n-1
n-2 n-1 0
n-1 0 1
これらの3組が全て矛盾していないか判定し、一例を示せば良いです
ソースコードは以下のようになります。
#include <iostream> #include <string> using namespace std; char a[4][100005]; char s[100005]; bool check(int x, int y, int z, int j){ bool flag = false; if(s[y] == 'o'){ if(a[j][y] == 'S'){ if(a[j][x] == 'S' && a[j][z] == 'S'){ flag = true; }else if(a[j][x] == 'W' && a[j][z] == 'W'){ flag = true; } }else if(a[j][y] == 'W'){ if(a[j][x] == 'S' && a[j][z] == 'W'){ flag = true; }else if(a[j][x] == 'W' && a[j][z] == 'S'){ flag = true; } } }else if(s[y] == 'x'){ if(a[j][y] == 'S'){ if(a[j][x] == 'S' && a[j][z] == 'W'){ flag = true; }else if(a[j][x] == 'W' && a[j][z] == 'S'){ flag = true; } }else if(a[j][y] == 'W'){ if(a[j][x] == 'S' && a[j][z] == 'S'){ flag = true; }else if(a[j][x] == 'W' && a[j][z] == 'W'){ flag = true; } } } return flag; } int main(void){ long n; int cnt = 0; bool flag2 = false; cin >> n; for(int i=0;i<n;i++){ cin >> s[i]; } a[0][0] = 'S'; a[0][1] = 'S'; a[1][0] = 'S'; a[1][1] = 'W'; a[2][0] = 'W'; a[2][1] = 'S'; a[3][0] = 'W'; a[3][1] = 'W'; for(int j=0;j<4;j++){ for(int i=2;i<n;i++){ if(a[j][i-2] == 'S'){ if(a[j][i-1] == 'S'){ if(s[i-1] == 'o'){ a[j][i] = 'S'; }else if(s[i-1] == 'x'){ a[j][i] = 'W'; } }else if(a[j][i-1] == 'W'){ if(s[i-1] == 'o'){ a[j][i] = 'W'; }else if(s[i-1] == 'x'){ a[j][i] = 'S'; } } }else if(a[j][i-2] == 'W'){ if(a[j][i-1] == 'S'){ if(s[i-1] == 'o'){ a[j][i] = 'W'; }else if(s[i-1] == 'x'){ a[j][i] = 'S'; } }else if(a[j][i-1] == 'W'){ if(s[i-1] == 'o'){ a[j][i] = 'S'; }else if(s[i-1] == 'x'){ a[j][i] = 'W'; } } } } if(check(n-3,n-2,n-1,j) == true && check(n-2,n-1,0,j) == true && check(n-1,0,1,j) == true){ for(int i=0;i<n;i++){ cout << a[j][i]; } cout << endl; return 0; } } cout << "-1" << endl; return 0; }
TokenMismatchException in compiled.php line3227
No4 おもりと天秤
No4 おもりと天秤 解説
問題
NとWがN個与えられ、2組に重りを分け、その2組の重さが等しくなるようにできるのかどうかを調べる問題です。
解答
まず2組が等しくなるためには全ての重りの和が偶数でなければいけません。
その場合にその半分の和となる選び方ができれば重りを等しくすることができます。
この問題は動的計画法で解くことができるためbool型の以下のようなdp配列を用意します。
dp[i番目までの重りを選んだ時][重さ]
まず全てfalseを入れておきdp[0][0]にはtrueを入れておきます。
そしてdp[i][j]がtrueの時、次の重り、つまりi+1番目まで選択した時そのi+1番目の重りを加えた重さまでは作ることができるのでtrueを入れます。
反対にi+1番目の重りを入れない場合でもtrueにします。
dp[i+1][j+w[i]] = true;
dp[i+1][j] =true;
そのようにして0≦ i < n, 0≦j≦mの範囲で繰り返すとdp[n][m]には答えが入っています。
以上解説でした。
以下ソースこーどです。
#include <iostream> using namespace std; int main(void){ int n,w[1005], sum = 0, m; bool dp[105][10001]; cin >> n; for(int i=0;i<n;i++){ cin >> w[i]; sum += w[i]; } m = sum/2; for(int i=0; i<n;i++){ for(int j=0;j<=m;j++){ dp[i][j] = false; } } if(sum %2 == 1){ cout << "impossible" << endl; return 0; }else{ dp[0][0] = true; for(int i=0; i<n;i++){ for(int j=0;j<=m;j++){ if(dp[i][j] == true){ dp[i+1][j+w[i]] =true; dp[i+1][j] = true; } } } } if(dp[n][m] == true){ cout << "possible" << endl; }else{ cout << "impossible" << endl; } return 0; }