はじめに

えっと....BとD、間違えないでくれません...?()
ガチ目に困惑した...

A - Not Overflow

-2³¹≤N<2³¹か判定するだけ

int main(){
    ll n;
    cin >> n;
    if(-pow(2,31)<=n && n < pow(2,31)) cout << "Yes";
    else cout << "No";
}

B - Matrix Transposition

2通りの解法がある

入力を普通に受け取って、行と列を入れ替えて出力
入力を行と列を入れ替えて受け取って、普通に出力

僕は後者で解きました

int main(){
    ll h, w;
    cin >> h >> w;
    vector<vector<ll>>G(w, vector<ll>(h));
    rep(i, h){
        rep(j, w) cin >> G[j][i];
    }
 
    for(auto i : G){
        for(auto j : i) cout << j << " ";
        cout << endl;
    }
}

C - kasaka

先頭にaをいくつかつけて回文にできるかどうか

まず、末尾のaをカウントしながら消していき、カウントした分だけ先頭からaを消す
そして、出来上がった文字列が回文かどうか判定する(dequeを使うと便利)

int main(){
    string s;
    cin >> s;
    deque<char>c;
    bool ok = false;
    ll cnt = 0;
    rep(i, s.length()){
        ll t = s.length()-i-1;
        if(s[t] != 'a' || ok) c.push_front(s[t]);
        else ++cnt;
        if(s[t] != 'a') ok = true;
    }
 
    rep(i, cnt){
        if(c.front() == 'a') c.pop_front();
    }
 
    rep(i, c.size()){
        ll t = c.size()-i-1;
        if(c[i] != c[t]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}

D(B) - LR insertion

挿入位置を移動させながら数字を入れていく
愚直にやるとO(N²)で間に合わない...
なので、文字列を逆順にしてみようと思う。
そうすると、Rの時列の最も左、Lの時列の最も右に追加すればいいことがわかる。
これを実装すればO(N)で処理可能

int main(){
    ll n;
    cin >> n;
    vector<char>c(n);
    rep(i, n) cin >> c[i];
    reverse(ALL(c));
    deque<ll>que;
    que.push_back(n);
    rep(i, n){
        if(c[i] == 'R') que.push_front(n-i-1);
        else que.push_back(n-i-1);
    }
    for(auto i : que) cout << i << " ";
}

いやぁこれがB問題だったとは()

E - Skiing

今いる場所より低ければその差分だけ嬉しく、高かったらその差分の2倍悲しくなる時、達成できる嬉しさの最大値

重み付きグラフとしてみると最長経路問題を解けば良さそうということがわかる。
でも、正負の辺があるからダイクストラは使えなさそう...?

実は、そんなことない。
まず、なぜダイクストラでは負の辺がある時最短経路問題を解けないのかを考えてみよう。
これは、負の辺があると、総和が負になるサイクルができることがあり、そうなるとそこをループすればいくらでも短くできてしまうからだ。

では、今回はどうだろう。道を登る時、差分の2倍だけ悲しくなるので、ループするとどんどん悲しくなる。つまり、ループすれば嬉しくなるサイクルはないので、普通にダイクストラが使える。
大嘘。after_contestで落ちました.. 最長経路問題であることに注意して実装

int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll>h(n);
    rep(i, n) cin >> h[i];
    vector<vector<pair<ll,ll>>>G(n);
    rep(i, m){
        ll a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back({b, (h[a]-h[b]) * (h[a] < h[b] ? 2 : 1)});
        G[b].push_back({a, (h[b]-h[a]) * (h[b] < h[a] ? 2 : 1)});
    }
 
    priority_queue<pair<ll,ll>>que;
    vector<ll>dist(n, -INF);
    dist[0] = 0;
    que.push({0, 0});
 
    while(!que.empty()){
        auto [d, now] = que.top(); que.pop();
        if(dist[now] > d) continue;
        for(auto [i, j] : G[now]){
            if(chmax(dist[i], dist[now]+j)) que.push({dist[i], i});
        }
    }
 
    cout << *max_element(ALL(dist));
}

F解きたかった....

Lukeの競プロ日記

主にAtCoderの問題の解説を書いています

ABC-237 後記