ABC453の記録

AtCoderBeginnerContest453の感想と自分が解いたところまでの解説を書いていきます
今回はA,B,C,DをC++,A,Bをpythonで解きます
AtCoder Beginner Contest 453

1.感想

A問題
少しめんどくさい
B問題
簡単
C問題
簡単
D問題
めんどい
E問題
分からん
G問題
永続セグ木あれば解けた

2.結果

とりあえず4完でも耐えた

3.解説

A問題 Trimo

入力して反転してoを消していく

C++での例

#include <iostream>
#include <string>
using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;
    reverse(S.begin(), S.end());
    while (!S.empty() && S.back() == 'o') S.pop_back();
    reverse(S.begin(), S.end());
    cout << S << endl;
}

pythonでの例

N = int(input())
S = list(reversed(list(input())))
while S and S[-1] == 'o':
    S.pop()
S.reverse()
for i in S:
    print(i, end='')
print()

B問題 Sensor Data Logging

入力して確かめる

C++での例

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int T, X;
    cin >> T >> X;
    vector<int> A(T+1);
    for (int& i : A) cin >> i;

    vector<pair<int, int>> ans;
    for (int i = 0; i <= T; i++){
        if (i == 0) ans.emplace_back(i, A[i]);
        else if (abs(ans.back().second-A[i]) >= X) ans.emplace_back(i, A[i]);
    }

    for (auto a : ans) cout << a.first << ' ' << a.second << endl;
}

pythonでの例

T, X = map(int, input().split())
A = list(map(int, input().split()))
ans = []

for i in range(T+1):
    if i == 0:
        ans.append((i, A[i]))
    elif abs(ans[-1][1]-A[i]) >= X:
        ans.append((i, A[i]))

for a in ans:
    print(*a)

C問題 Sneaking Glances

bit全探索

C++での例

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for (int& i : A) cin >> i;

    int ans = 0;
    for (int bit = 0; bit < (1<<N); bit++){
        vector<double> a;
        double now = 0.5;
        int count = 1;
        for (int i = 0; i < N; i++){
            if (bit>>i&1) now += A[i];
            else now -= A[i];
            a.push_back(now);
        }
        for (int i = 0; i < N-1; i++){
            if (a[i] < 0 && a[i+1] > 0) count++;
            if (a[i] > 0 && a[i+1] < 0) count++;
        }
        ans = max(ans, count);
    }

    cout << ans << endl;
}

D問題 Go Straight

BFSと復元

C++での例

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define out(x, y) (!(0 <= x && x < H && 0 <= y && y < W))
using namespace std;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };
const string dd = "DRUL";

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto& i : S) cin >> i;
    pair<int, int> start, goal;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++){
        if (S[i][j] == 'S') start = {i, j};
        if (S[i][j] == 'G') goal = {i, j};
    }

    vector visited(H, vector(W, vector<bool>(4, false)));
    vector parent(H, vector(W, vector<tuple<int, int, int>>(4)));
    queue<tuple<int, int, int>> Q;
    for (int i = 0; i < 4; i++){
        int nx = start.first+dx[i], ny = start.second+dy[i];
        if (out(nx, ny) || S[nx][ny] == '#') continue;
        visited[nx][ny][i] = true;
        parent[nx][ny][i] = {start.first, start.second, -1};
        Q.emplace(nx, ny, i);
    }

    int fx = -1, fy = -1, fd = -1;
    while (!Q.empty()){
        auto [x, y, d] = Q.front();
        Q.pop();
        if (x == goal.first && y == goal.second){
            fx = x, fy = y , fd = d;
            break;
        }
        for (int i = 0; i < 4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if (out(nx, ny) || S[nx][ny] == '#') continue;
            char c = S[x][y];
            if (c == 'o' && i != d) continue;
            if (c == 'x' && i == d) continue;
            if (visited[nx][ny][i]) continue;
            visited[nx][ny][i] = true;
            parent[nx][ny][i] = {x, y, d};
            Q.emplace(nx, ny, i);
        }
    }

    if (fx == -1){
        cout << "No" << endl;
        return 0;
    }

    string ans;
    int x = fx, y = fy, d = fd;
    while (d != -1){
        ans.push_back(dd[d]);
        auto [px, py, pd] = parent[x][y][d];
        x = px, y = py, d = pd;
    }
    reverse(ans.begin(), ans.end());
    cout << "Yes" << endl << ans << endl;
}