初めに

久しぶりにコンテストに参加したのでこれからは参加するごとに記録を残しておこうと考えました。

A - Star

100の倍数なら100、そうでないなら繰り上げて差をとるだけのはずが、誤読してなぜか1WAしました。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int x;
    cin >> x;
    if(x % 100 == 0) cout << 100 << endl;
    else cout << (x + 99) / 100 * 100 - x << endl;
    return 0;
}

B - uNrEaDaBlE sTrInG

シンプルに交互に見ていくだけです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < (int)s.size(); i++) {
        if(i % 2  && 'a' <= s[i] && s[i] <= 'z') {
            cout << "No\n";
            return 0;
        }
        if(i % 2 == 0 && 'A' <= s[i] && s[i] <= 'Z') {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

C - Kaprekar Number

Kが小さいのでK回くりかえすだけです。
文字列としてソートして整数に変換すると簡単でした。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < k; i++) {
        string s = to_string(n);
        string t = s;
        sort(s.begin(), s.end());
        sort(t.rbegin(), t.rend());
        n = stoi(t) - stoi(s);
    }
    cout << n << endl;
    return 0;
}

D - Base n

二分探索することまでは分かったのですが、オーバーフローまわりの実装が難しくて実装しきれませんでした。

E - Train

ダイクストラの移動の遷移にTを考慮するだけでいけるのかなと思って書いたら解けました。

#include<bits/stdc++.h>
using namespace std;

const long long INF = ((1LL << 62) - (1LL << 31));

using P = pair<long long,long long>;

struct edge{
    long long to;
    long long cost;
    long long clock;
};

vector<long long> dijkstra(int x, vector<vector<edge>> G){
    priority_queue<P, vector<P>, greater<P>> que;
    vector<long long> dist(G.size(), INF);
    dist[x] = 0;
    que.push(P(0, x));
    while(!que.empty()) {
        P tmp = que.top();
        que.pop();
        int v = tmp.second;
        if(dist[v] < tmp.first) continue;
        for(edge e : G[v]) {
            // 今の時間から次の遷移をするまでの待ち時間を考慮して遷移。
            long long nextCost = dist[v] + e.cost + ((tmp.first + e.clock - 1) / e.clock * e.clock - dist[v]);
            if(dist[e.to] > nextCost) {
                dist[e.to] = nextCost;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
    return dist;
}

int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--;
    y--;
    vector<vector<edge>> G(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        long long t, k;
        cin >> a >> b >> t >> k;
        a--;
        b--;
        G[a].push_back(edge{b, t, k});
        G[b].push_back(edge{a, t, k});
    }
    vector<long long> dist = dijkstra(x, G);
    if(dist[y] == INF) cout << -1 << endl;
    else cout << dist[y] << endl;
    return 0;
}

F - Potion

使う個数の決め打ちかなとまでは思ったのですがその後の考察が思いつかなかったので解けませんでした。

終わりに

知っているアルゴリズムを応用して問題を解けたので多少は成長しているのかなと感じました。

Amami’s competitive diary

ABC192参加記

初めに