Featured image of post AtCoder Beginning Contest 237

AtCoder Beginning Contest 237

A. Not Overflow

 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4typedef long long ll;
 5typedef pair<int, int> pii;
 6#define pb push_back
 7
 8int main() {
 9    ios::sync_with_stdio(0), cin.tie(0);
10    ll N;
11    cin >> N;
12    ll min = -(1ll << 31);
13    ll max = (1ll << 31) - 1;
14    if (min <= N && N <= max) {
15        cout << "Yes\n";
16    } else {
17        cout << "No\n";
18    }
19    return 0;
20}

B. Matrix Transposition

 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4typedef long long ll;
 5typedef pair<int, int> pii;
 6#define pb push_back
 7
 8int main() {
 9    ios::sync_with_stdio(0), cin.tie(0);
10    int H, W;
11    cin >> H >> W;
12    vector<vector<int>> A(H, vector<int>(W));
13    for (int i = 0; i < H; i++) {
14        for (int j = 0; j < W; j++) {
15            cin >> A[i][j];
16        }
17    }
18    for (int i = 0; i < W; i++) {
19        for (int j = 0; j < H; j++) {
20            cout << A[j][i] << " \n"[j == H - 1];
21        }
22    }
23    return 0;
24}

C. kasaka

 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4typedef long long ll;
 5typedef pair<int, int> pii;
 6#define pb push_back
 7
 8bool ispal(string s) {
 9    for (int i = 0; i < s.length() / 2; i++) {
10        if (s[i] != s[s.length() - 1 - i]) {
11            return false;
12        }
13    }
14    return true;
15}
16
17int main() {
18    ios::sync_with_stdio(0), cin.tie(0);
19    string s;
20    cin >> s;
21    int cnt = 0;
22    for (int i = 0; s[i]; i++) {
23        if (s[i] == 'a') cnt--;
24        else break;
25    }
26    for (int i = s.length() - 1; i >= 0; i--) {
27        if (s[i] == 'a') cnt++;
28        else break;
29    }
30    string str = "";
31    for (int i = cnt; i > 0; i--) {
32        str += "a";
33    }
34    str += s;
35    if (ispal(str)) {
36        cout << "Yes\n";
37    } else {
38        cout << "No\n";
39    }
40    return 0;
41}

D. LR insertion

  • Linked List。
 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4typedef long long ll;
 5typedef pair<int, int> pii;
 6#define pb push_back
 7
 8int main() {
 9    ios::sync_with_stdio(0), cin.tie(0);
10    int N;
11    cin >> N;
12    string s;
13    cin >> s;
14    vector<int> left(N + 1, -1), right(N + 1, -1);
15    for (int i = 0; s[i]; i++) {
16        if (s[i] == 'L') {
17            left[i + 1] = left[i];
18            if (left[i] != -1) right[left[i]] = i + 1;
19            right[i + 1] = i;
20            left[i] = i + 1;
21        } else {
22            right[i + 1] = right[i];
23            if (right[i] != -1) left[right[i]] = i + 1;
24            left[i + 1] = i;
25            right[i] = i + 1;
26        }
27    }
28    int head = 0;
29    for (int i = 0; i <= N; i++) {
30        if (left[i] == -1) head = i;
31    }
32    for (int i = head; i != -1; i = right[i]) {
33        cout << i << " ";
34    }
35    return 0;
36}

E. Skiing

  • Dijkstra。
 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4typedef long long ll;
 5typedef pair<ll, int> pii;
 6#define pb push_back
 7
 8#define INF 1000000000000000000ll
 9
10int main() {
11    ios::sync_with_stdio(0), cin.tie(0);
12    int N, M;
13    cin >> N >> M;
14    vector<int> h(N);
15    for (int i = 0; i < N; i++)
16        cin >> h[i];
17    vector<vector<int>> edge(N);
18    for (int i = 0; i < M; i++) {
19        int u, v;
20        cin >> u >> v;
21        u--, v--;
22        edge[u].push_back(v);
23        edge[v].push_back(u);
24    }
25    vector<ll> dis(N, -INF);
26    ll ans = 0;
27    dis[0] = 0;
28    priority_queue<pii> pq;
29    pq.emplace(0, 0);
30    while (!pq.empty()) {
31        int u = pq.top().second;
32        pq.pop();
33        for (int uu : edge[u]) {
34            int value;
35            if (h[u] >= h[uu]) {
36                value = h[u] - h[uu];
37            } else {
38                value = 2 * (h[u] - h[uu]);
39            }
40            if (dis[u] + value > dis[uu]) {
41                dis[uu] = dis[u] + value;
42                pq.emplace(dis[uu], uu);
43                ans = max(dis[uu], ans);
44            }
45        }
46    }
47    cout << ans << "\n";
48    return 0;
49}
Built with Hugo
Theme Stack designed by Jimmy