0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 472

0
Posted at

A - A

問題文

forにて'A'の時だけアルファベット、それ以外は'.'を表示します。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string s;
    cin >> s;
    rep(i, s.size()){
        if(s[i] == 'A') cout << 'A';
        else cout << '.';
    }
    cout << endl;
    return 0;
}

B - Break a Stick

問題文

問題文の通り、シミュレーションしましょう。
差分更新の問題になります。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int ans = 1000000007;
    rep(i, n){
        int left = 0;
        int right = 0;
        for(int j=0; j<=i; j++) left += a[j];
        for(int k=i+1; k<n; k++) right += a[k];
        ans = min(ans, abs(right - left));
    }
    cout << ans << endl;
    return 0;
}

C - On a Diet

問題文

問題文の通り、シミュレーションしましょう。
差分更新の問題になります。
コンテスト中は尺取り法のようなコードをイメージして記載しました。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    ll right = 0;
    ll total = 0;
    for(int left=0; left<n; left++){
        while(right < n && right - m < left){
            if(total + a[right] <= k){
                total += a[right];
                b[right] = a[right];
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
            right++;
        }
        total -= b[left];
    }
    return 0;
}

コードを整理しましょう。
差分更新を意識してコードを書きます。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll total = 0;
    for(int i=0; i<n; i++){
        if(i-m>-1) total -= a[i-m];
        if(total + a[i] <= k){
            total += a[i];
            cout << "Yes" << endl;
        }else{
            a[i] = 0;
            cout << "No" << endl;
        } 
    }
    return 0;
}

D - Bomber Mad

問題文

問題文から前処理が必要な多始点BFSだと分かります。

  1. '#'がある列と行を探索しましょう
  2. 安全なマスを探索して、多始点BFSの多始点を探索します
  3. BFSを行います
  4. 安全なマスからK以下で移動できるマスを探索します。
C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
    int INF = 1000000007;
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    set<int> hb, wb;
    rep(i, h) rep(j, w){
        if(s[i][j] == '#') hb.insert(i), wb.insert(j);
    }
    vector<vector<int>> dict(h, vector<int>(w, -1));
    queue<pair<int,int>> que;
    rep(i, h){
        rep(j, w){
            if(wb.find(j) == wb.end() && hb.find(i) == hb.end()){
                que.push({i, j});
                dict[i][j] = 0;
            }
        }
    }

    while(que.size()){
        auto [y, x] = que.front();
        que.pop();

        for(int i=0; i<4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(xx < 0 || w <= xx || yy < 0 || h <= yy) continue;
            if(s[yy][xx] == '#') continue;
            if(dict[yy][xx] != -1) continue;
            dict[yy][xx] = dict[y][x] + 1;
            que.push({yy, xx});
        }
    }
    int ans = 0;
    rep(i, h){
        rep(j, w){
            if(-1 < dict[i][j] && dict[i][j] <= k){
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?