Amedeo
SYMBIOSYS OF
PURPOSE & STYLE
Follow us

Search

ekusiadadus
  -  Programming   -  Competitive Programming   -  ABC184
abc184e

ABC184

AtCoder Beginner Contest 184(ABC184)

問題名実行時間制限メモリ制限
ADeterminant2 sec1024 MB
BQuizzes2 sec1024 MB
CSuper Ryuma2 sec1024 MB
Dincrement of coins2 sec1024 MB
EThird Avenue3 sec1024 MB
FProgramming Contest2 sec1024 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)とする。

  1. (x,y) = 0のとき0手で移動できる
  2. x+y = 0, x-y = 0, |x|+|y| <= 3 のとき、条件から1手で移動できる
  3. 2.の3通りの動きを2回おこなって到達できる地点、(x+y)と同じパリティ、|x|+|y| <= 6、角の動きをして|x|+|y| <= 3と なるようなとき(|x+y| <= 3, |x-y| <= 3)は2手で移動できる
  4. 上以外は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)

Leave a Comment