ABC184

ABC184
AtCoder Beginner Contest 184(ABC184)
問題名 | 実行時間制限 | メモリ制限 | |
---|---|---|---|
A | Determinant | 2 sec | 1024 MB |
B | Quizzes | 2 sec | 1024 MB |
C | Super Ryuma | 2 sec | 1024 MB |
D | increment of coins | 2 sec | 1024 MB |
E | Third Avenue | 3 sec | 1024 MB |
F | Programming Contest | 2 sec | 1024 MB |
A: “Determinant”
問題文:

解法:
書くだけ
計算量O(1)
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c,d; cin >> a >> b >> c >> d; cout << a*d - b*c << endl; return 0; }
B: “Quizzes”
問題文:

解法:
高橋くんの点数の遷移を追う。
はじめ、高橋君はX点もっている。
問題を解いていって、正解なら1点足す。
不正解の場合、
1.高橋君の点数が0点より大きい場合
高橋くんの点数を、-1点する
2.高橋君の点数が0点の場合
0点のままにする(0点以下にならないから)
計算量O(N)
高橋くんは、問題をはじめから順に解いていくので、遷移を追っていけばいい。
#include<bits/stdc++.h> using namespace std; int main(){ int n, x; string s; cin >> n >> x >> s; for(int i = 0; i < n; ++i){ if(s[i] == 'o'){ ++x; }else{ x = (x>0)?x-1:x; } } cout << x << endl; return 0; }
C: “Super Ryuma”
問題文:


解法:
条件を丁寧に追っていく。
(a,b) → (c,d)に移動するので、相対的な2点の関係を追えばいい。
(x,y) = (c-a, d-b)とする。
- (x,y) = 0のとき0手で移動できる
- x+y = 0, x-y = 0, |x|+|y| <= 3 のとき、条件から1手で移動できる
- 2.の3通りの動きを2回おこなって到達できる地点、(x+y)と同じパリティ、|x|+|y| <= 6、角の動きをして|x|+|y| <= 3と なるようなとき(|x+y| <= 3, |x-y| <= 3)は2手で移動できる
- 上以外は3手で移動できる
計算量O(1)
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int r1,c1,r2,c2; cin >> r1 >> c1 >> r2 >> c2; int x = r2 - r1, y = c2 - c1; int ans = 0; if(x==0 && y==0) ans = 0; else if(x+y == 0 || x-y == 0 || abs(x)+abs(y) <= 3) ans = 1; else if((x+y)%2 == 0 || abs(x)+abs(y) <= 6 || abs(x+y) <= 3 || abs(x-y) <= 3) ans = 2; else ans = 3; cout << ans << endl; return 0; }
D: “increment of coins”
問題文:

解法:
確率問題。確率遷移を考えてDPする。
O(1)
#include <bits/stdc++.h> using namespace std; double dp[101][101][101]; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); int a,b,c; cin >> a >> b >> c; for(int i = 99; i >= a; --i){ for(int j = 99; j >= b; --j){ for(int k = 99; k >= c; --k){ dp[i][j][k] += (double)(dp[i+1][j][k]+1)*i/(double)(i+j+k); dp[i][j][k] += (double)(dp[i][j+1][k]+1)*j/(double)(i+j+k); dp[i][j][k] += (double)(dp[i][j][k+1]+1)*k/(double)(i+j+k); } } } cout << fixed << setprecision(10); cout << dp[a][b][c] << endl; return 0; }
E: “Third Avenue”
問題文:

解法:
queueで、一つ一つ最短でいつ到達できるかを探していく。
ポイントは、テレポートができるところ。
ここを、文字のmapで別のテレポート地点をvectorで持っておく。
縦横移動+テレポートで探索して、一回探索されたらそれが最短なので全マス一回到達すればよい
計算量O(H*W)
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (n); i++) const int INF = 1e9; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); int h, w; cin >> h >> w; vector<string> a(h); vector<vector<int>> seen(h,vector<int> (w,0)); rep(i,h) cin >> a[i]; queue<pair<pair<int,int>,int>> q; int sy,sx; int ans = INF; map<char,vector<pair<int,int>>> m; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j){ if(a[i][j] == 'S') sy = i, sx = j; else if(a[i][j] != 'G' && a[i][j] != '.' && a[i][j] != '#') m[a[i][j]].push_back(make_pair(i,j)); } q.push(make_pair(make_pair(sy,sx),0)); while(!q.empty()){ int y = q.front().first.first, x = q.front().first.second, cnt = q.front().second; q.pop(); if(seen[y][x]) continue; seen[y][x] = 1; if(a[y][x] == 'G'){ ans = min(ans, cnt); continue; } // 縦横の探索箇所 if(y+1 < h && a[y+1][x] != '#') q.push(make_pair(make_pair(y+1,x),cnt+1)); if(x+1 < w && a[y][x+1] != '#') q.push(make_pair(make_pair(y,x+1),cnt+1)); if(y-1 >= 0 && a[y-1][x] != '#') q.push(make_pair(make_pair(y-1,x),cnt+1)); if(x-1 >= 0 && a[y][x-1] != '#') q.push(make_pair(make_pair(y,x-1),cnt+1)); // テレポートの探索箇所をmapから取り出す for(auto it = m[a[y][x]].begin(); it != m[a[y][x]].end();){ int i = it->first, j = it->second; m[a[y][x]].erase(it); if(i == y && j == x){ continue; } q.push(make_pair(make_pair(i,j),cnt+1)); } } if(ans != INF) cout << ans << endl; else puts("-1"); return 0; }
F: “Programming Contes”
問題文:

解法:
Aを2つ(B,C)に分けて、Bのすべての部分集合の和、の集合をDに格納します。
これで、Bでえられる部分和がすべてDに格納されます。
O(2^(N/2))
size(D) <= 2^(N/2) <= 2^20
Dをソートする。
Cで得られる部分和を見て行って(上と同じ)、DでTを超えない最大の要素を2分探で取得していく。
この最大の要素の、最大値が答え。
計算量O(2^(N/2)*log(2^(N/2))
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int i = 0; i < (n); i++) int main() { cin.tie(0); ios_base::sync_with_stdio(false); ll n,t; cin >> n >> t; vector<ll> a(n); vector<ll> b; //aを二つに分ける vector<ll> c; //aを二つに分ける vector<ll> d; //bの部分集合の和の集合 ll ans = 0; rep(i,n){ cin >> a[i]; if(i%2) b.push_back(a[i]); if(i%2==0) c.push_back(a[i]); } for(ll mask = 0; mask < (1<<b.size()); ++mask){ //bの部分集合の和をdに格納する ll rec = 0; for(ll i = 0; i < b.size(); ++i){ if((1<<i)&mask) rec += b[i]; } d.push_back(rec); } sort(d.begin(), d.end()); //2分探ようにソート for(ll mask = 0; mask < (1<<c.size()); ++mask){ ll rec = 0; for(ll i = 0; i < c.size(); ++i){ if((1<<i)&mask) rec += c[i]; } int l = 0, r = d.size(), mid; while(r-l > 1){ mid = (r+l)/2; if(d[mid] + rec > t) r = mid; else l = mid; } rec += d[l]; if(rec > t) continue; //tを超えている場合 ans = max(ans,rec); } cout << ans << endl; return 0; }
終わりに
今回は、E = F >= C > D > B > A
みたいな構成だったと思います。
C、Dは、しっかり実装しないとミスります。
E、Fはよくある手法です。
次は、ARCが、2020-11-28(土) 21:00 ~ 2020-11-28(土) 22:40 (100分)にあります!
是非楽しんでください!
その他のコンテスト
CodeForces: CodeForces Round #686(Div.3)