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 453

0
Posted at

A - Trimo

問題文

先頭の文字列がoなら削除しましょう。
コンテスト中のコードです。

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;
    string s;
    cin >> s;
    int cnt = 0;
    rep(i, n){
        if(s[i] == 'o'){
            cnt++;
        }else{
            break;
        }
    }
    cout << s.substr(cnt, n - cnt) << endl;
    return 0;
}

先頭の文字oを数えてsubstrで取り除きます。
コードを少なくしてみましょう。

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;
    string s;
    cin >> s;
    while(s.size() && s[0] == 'o'){
        s.erase(s.begin());
    }
    cout << s << endl;
    return 0;
}

B - Sensor Data Logging

問題文

「現時刻の測定値と直前に保存された測定値」との差の絶対値がX以上か判定しましょう。
absの問題ですね。
コンテスト中のコードです。

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 t, x;
    cin >> t >> x;
    vector<int> a(t+1);
    rep(i, t+1) cin >> a[i];

    int prev = 0;
    rep(i, t+1){
        if(i == 0){
            cout << i << ' ' << a[i] << endl;
            prev = a[i];
        }else{
            if(abs(prev - a[i]) >= x){
                cout << i << ' ' << a[i] << endl;
                prev = a[i];
            }
        }
    }

    return 0;
}

int prev = 0;をint prev = -x;にすると綺麗なコードになります。

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 t, x;
    cin >> t >> x;
    vector<int> a(t+1);
    rep(i, t+1) cin >> a[i];

    int prev = -x;
    rep(i, t+1){
        if(abs(prev - a[i]) >= x){
            cout << i << ' ' << a[i] << endl;
            prev = a[i];
        }
    }

    return 0;
}

C - Sneaking Glances

問題文

bit全探索の問題です。
2^20でも10^6の単位なので間に合います。
コンテスト中のコードです。

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> l(n);
    rep(i, n) cin >> l[i];

    int ans = 0;
    for(int bit=0; bit<(1<<n); bit++){
        
        double pos = 0.5;
        int cnt = 0;
        for(int i=0; i<n; i++){
            if(bit>>i & 1){
                if(pos<0){
                    pos += l[i];
                    if(pos>0) cnt++;
                }else{
                    pos += l[i];
                }
            }else{
                if(pos>0){
                    pos -= l[i];
                    if(pos<0) cnt++;
                }else{
                    pos -= l[i];
                }
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;

    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() {
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    int ans = 0;
    for(int bit=0; bit<(1<<n); bit++){
        double pos = 0.5;
        int cnt = 0;
        for(int i=0; i<n; i++){
            double old = pos;
            if(bit>>i & 1) pos += l[i];
            else pos -= l[i];
            if(old<0 && 0<pos) cnt++;
            if(old>0 && 0>pos) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}

さらに数学的な思考で整理しましょう。
0.5という単位を使用したくないので全ての数を2倍します。

C++
rep(i, n) cin >> l[i], l[i] <<= 1;

またcnt++の条件式を見直しましょう。

C++
            ll x = pos / abs(pos);
            if(bit>>i & 1) pos += l[i];
            else pos -= l[i];
            if(x * pos < 0) cnt++;

l[i]を加算した後のposと前回の数の符号を掛け算してマイナスの時だけcntを加算します。

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> l(n);
    rep(i, n) cin >> l[i], l[i] <<= 1;

    int ans = 0;
    for(int bit=0; bit<(1<<n); bit++){
        ll pos = 1;
        int cnt = 0;
        for(int i=0; i<n; i++){
            ll x = pos / abs(pos);
            if(bit>>i & 1) pos += l[i];
            else pos -= l[i];
            if(x * pos < 0) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}

D - Go Straight

問題文

頂点倍化、多視点、経路復元を組み合わせた重実装問題です。
複雑でここ最近のBFSでは難易度が高いです。

移動方向を管理します。
4方向の移動量だけ頂点を倍化させます。
移動量が分かっているならスタート地点まで復元できます。

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 h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int INF = 1e9;
    vector<vector<vector<int>>> graph(4, vector<vector<int>>(h, vector<int>(w, INF)));
    queue<tuple<int, int, int>> que;
    rep(i, h){
        rep(j, w){
            if(s[i][j] == 'S'){
                rep(k, 4){
                    graph[k][i][j] = 9;
                    que.push({k, i, j});
                }
            }
        }
    }

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

        if(s[y][x] == 'G'){
            string ans;
            cout << "Yes" << endl;
            while (graph[d][y][x] != 9) {
                ans += "LURD"[d];
                int dd = graph[d][y][x];
                y -= dy[d]; x -= dx[d];
                d = dd;
            }
            reverse(ans.begin(), ans.end());
            cout << ans << endl;
            return 0;
        }

        for(int i=0; i<4; i++){
            if(s[y][x] == 'o' && d != i) continue;
            if(s[y][x] == 'x' && d == i) continue;
            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(graph[i][yy][xx] != INF) continue;
            graph[i][yy][xx] = d; 
            que.push({i, yy, xx});
        }
    }
    cout << "No" << 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?