Neunomizuの日記

俺だけが俺だけじゃない

｢AtCoder Beginner Contest 146｣に出た

競技プログラミング
tags: 競技プログラミング

感想

  • ページ
  • C問題に時間を掛けすぎました...
  • グラフ系の問題が苦手だという認識から抜け出せないです

A問題

  • 考えるのが面倒なので愚直に条件分岐しました
  • C++のswitch構文でstring型を使えるかどうか忘れていたのでif-elseで書きました

コード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string S;
    cin >> S;
    if (S == "SAT") {
        cout << 1 << endl;
    } else if (S == "FRI") {
        cout << 2 << endl;
    } else if (S == "THU") {
        cout << 3 << endl;
    } else if (S == "WED") {
        cout << 4 << endl;
    } else if (S == "TUE") {
        cout << 5 << endl;
    } else if (S == "MON") {
        cout << 6 << endl;
    } else {
        cout << 7 << endl;
    }
    return 0;
}

B問題

  • ROTなんたらの実装
  • ちょうど今日の朝実装しようとしていたので偶然ってすごいですね(偶然がなくても解けると思いますが)

コード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

char rot(char ch, int n)
{
    unsigned num = 0;
    if ('a' <= ch && ch <= 'z') {
        num = (ch - 'a' + n) % 26;
        return num + 'a';
    } else {
        num = (ch - 'A' + n) % 26;
        return num + 'A';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        s[i] = rot(s[i], n);
    }
    cout << s << endl;
    return 0;
}

C問題

  • オーダーが$O(n)$だと間に合わないなぁと思ったので2分探索をするのかなと思って実装したのですがバグが中々取れなかったです...
  • コードもめちゃくちゃ雑に書いています

コード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
ll A, B, X;

ll digi(ll n)
{
    ll num = 1;
    while (n / 10) {
        num++;
        n /= 10;
    }
    return num;
}

ll getMax()
{
    ll left = 0, right = 1e9;
    ll mid;
    ll cnt = 0;
    while (left < right) {
        cnt++;
        mid = (left + right) / 2;
        if (X < A * mid + B * digi(mid)) {
            right = mid;
        } else if (X > A * mid + B * digi(mid)) {
            left = mid + 1;
        } else if (A * mid + B * digi(mid) == X) {
            return mid;
        }
    }
    return mid;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> B >> X;
    if (A > X || B > X) {
        cout << 0 << endl;
        return 0;
    }
    ll num = getMax();
    num++;
    if (A * num + B * digi(num) <= X) {
        cout << num << endl;
    } else if (A * (num - 1) + B * digi(num - 1) <= X) {
        cout << num - 1 << endl;
    } else {
        cout << num - 2 << endl;
    }
    return 0;
}

D問題

  • 木に関する問題なので定義的に閉路はないです
  • だから最初のノードからBFSしていけばいいのかなぁと思ったんですが,実装ができなかったです...
    • やろうとしていたことは間違っていなかったっぽいです
  • 以下解説のソースコードを改変してにコメント付けたコードです
    • こういう長いコードを書くのが苦手なのでできるようにしていきたいと思いました(丸)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<vector<ll>> graph(N);
    vector<pair<int, int>> vp;
    rep(i, N - 1)
    {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
        vp.emplace_back(a, b);
    }

    ll k = 0;
    map<pair<ll, ll>, ll> mp; // 辺をキーにして,その色を値にしている
    vector<ll> c(N); // c[i]: iからの辺の色
    vector<bool> used(N); // iへ移動済みかどうか

    // 0からBFS
    queue<ll> que;
    used[0] = true;
    que.emplace(0);
    while (!que.empty()) {
        ll v = que.front();
        que.pop();
        // kは最大の次数
        k = max(k, (ll)graph[v].size());
        ll cur = 1; // 現在の色
        for (auto u : graph[v]) {
            // もし移動済みならスキップ
            if (used[u]) {
                continue;
            }
            // vからの辺の色が現在の色と同じなら色を変える
            if (cur == c[v]) {
                cur++;
            }
            c[u] = mp[make_pair(u, v)] = mp[make_pair(v, u)] = cur++; // 辺の色を変える
            used[u] = true; // uは通った
            que.emplace(u); // 次はuから別の辺に行く
        }
    }
    cout << k << endl;
    for (auto k : vp) { // 辺から色を出力
        cout << mp[k] << endl;
    }
    return 0;
}

まとめ

  • レートが上がったので結果オーライですが,D問題がコンテストで解けるようになりたいですToT
  • ギリギリ持ちこたえた感じになっています...