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)
