https://bondo.hateblo.jp/entry/2021/05/02/135613

atcoder.jp

Bondo416さんのZONeエナジープログラミングコンテスト “HELLO SPACE”での成績：683位
パフォーマンス：1707相当
レーティング：1474→1499 (+25) :)#AtCoder #ZONeエナジープログラミングコンテスト“HELLOSPACE” https://t.co/1bGujlmpIZ
— ボンド@競プロ (@bond_cmprog) May 1, 2021

A - UFO襲来

全探索で判定する
提出コード

void solve(){
    string S;
    cin >> S;
    int ans = 0;
    REP(i,9){
        if(S.substr(i, 4) == "ZONe") ans++;
    }
    cout << ans << endl;
}

B - 友好の印

むずかしい
$ i $ 番目の遮蔽物に対してUFOが見えるギリギリの高さを求める
これは $ i $ 番目遮蔽物とUFOの傾きを求めてその直線の切片を求めればいい
傾きは $ \frac{D - d_i}{H - h_i} $ となり、切片は $ h_i - d_i \frac{D - d_i}{H-h} $ となる
すべての遮蔽物に対しこれを求め、その最大が答え
提出コード

void solve(){
    int N;
    double D, H;
    cin >> N >> D >> H;
    double ans = 0;
    REP(i,N){
        double d, h;
        cin >> d >> h;
        double dx = D - d;
        double dh = H - h;
        double p = dh / dx;
        double c = h - p * d;
        chmax(ans, c);
    }
    printf("%.12lf\n", ans);
}

C - MAD TEAM

むずかしい
答えを決め打つ二分探索をする
ある整数 $ x $ が答えになるかどうかを考えるとそれぞれの能力値は$ x $ 以上なら1、そうでないなら0として状態を圧縮できる
そうするとすべての状態数は$ 2^5 = 32 $ 通りになるので、この中から3組選ぶ組み合わせを全探索しても十分に間に合う
提出コード

void solve(){
    int N;
    cin >> N;
    vector abcde(N, vector(5, 0LL));
    REP(i,N) REP(j,5) cin >> abcde[i][j];

    auto check = [&](int x) -> bool{
        set<int> st;
        REP(i,N){
            int bit = 0;
            REP(j,5) if(abcde[i][j] >= x) bit |= (1 << j);
            st.insert(bit);
        }
        bool ok = false;
        for(auto a : st) for(auto b : st) for(auto c : st){
            if((a | b | c) == ((1 << 5) - 1)) ok = true;
        }
        return ok;
    };

    int l = 0, r = INF + 10;
    while(r - l > 1){
        int m = (l + r) >> 1;
        if(check(m)) l = m;
        else r = m;
    }
    cout << l << endl;
}

D - 宇宙人からのメッセージ

文字列を実際に反転させる代わりに今反転しているかどうかのフラグをもたせる
反転しているときに文字列を追加するときは文字列の先頭に、そうでないなら後ろに追加する
追加が終わったあとに反転フラグが立っていれば文字列をreverseさせる
最後に、stackなどで同じ文字が隣り合っていればその部分を消していき残った文字列を出力する
提出コード

void solve(){
    string S;
    cin >> S;
    int x = 0;
    deque<char> dq;
    for(char c : S){
        if(c == 'R') x = 1 - x;
        else{
            if(x == 0) dq.push_back(c);
            else dq.push_front(c);
        }
    }
    string tmp;
    while(!dq.empty()){
        tmp += dq.front();
        dq.pop_front();
    }
    if(x) reverse(tmp.begin(), tmp.end());
    string ans = "";
    for(char c : tmp){
        if(ans == "") ans += c;
        else{
            if(ans.back() == c) ans.pop_back();
            else ans += c;
        }
    }
    cout << ans << endl;
}

E - 潜入

愚直で通しちゃった
想定解は4つ目の操作を行っている途中かどうかの頂点を増やしてあげてそのグラフ上でダイクストラをすればいい
提出コード

void solve(){
    int R, C;
    cin >> R >> C;
    vector<vector<ll>> A(R+1, vector<ll>(C+1));
    vector<vector<ll>> B(R+1, vector<ll>(C+1));
    REP(i,R) REP(j,C-1) cin >> A[i+1][j+1];
    REP(i,R-1) REP(j,C) cin >> B[i+1][j+1];
    vector dist(R+1, vector(C+1, LINF));
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    pq.emplace(0, 1, 1);
    dist[1][1] = 0;
    while(!pq.empty()){
        auto [d, nr, nc] = pq.top(); pq.pop();
        if(dist[nr][nc] < d) continue;
        chmin(dist[nr][nc], d);
        if(nc < C){
            if(chmin(dist[nr][nc+1], A[nr][nc] + d)) pq.emplace(dist[nr][nc+1], nr, nc+1);
        }
        if(nc > 1){
            if(chmin(dist[nr][nc-1], A[nr][nc-1] + d)) pq.emplace(dist[nr][nc-1], nr, nc-1);
        }
        if(nr  < R){
            if(chmin(dist[nr+1][nc], B[nr][nc] + d)) pq.emplace(dist[nr+1][nc], nr+1, nc);
        }
        for(int i=1;i<nr;i++){
            if(chmin(dist[nr-i][nc], i + d + 1)) pq.emplace(dist[nr-i][nc], nr-i, nc);
        }
    }
    cout << dist[R][C] << endl;
}