ABC198 振り返りメモ(ABCE問題)

#結果
ABCの3完で, レート変化は 713 → 721 (+8)

#A問題 ( Div )
###概要

N 個のお菓子を2人で分け合う方法は何通りあるか求める.

###方針
A さんが x 個 ( 1 <= x <= N - 1 ) もらう時, B さんは N - x 個もらうので, 答えは N - 1通り.

C++ での実装例は以下のようになる.

a.cpp

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

int main() {
  ll N; cin >> N;
  cout << N - 1 << endl;  
  return 0;
} 

#B問題 ( Palindrome with leading zeros )
###概要

与えられた数字の先頭に0をいくつかつけることで, 元の数字を回文にすることができるか判断する.

方針

方針は2つある.
・与えられた数字を10で割れるだけ割って, 残った数字を回文かどうか判定する
・実際に0を付けて全部試す (試すのは多くても10回程度)

方針1はC++ での実装例は以下のようになる.

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

// 文字列sが回文であるかを判定する関数
bool isPalindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}

int main() {
    ll N;
    cin >> N;
    if (N == 0) {
        cout << "Yes" << endl;
        return 0;
    }
    // Nを10で割れるだけ割る
    while (N % 10 == 0) N /= 10;
    if (isPalindrome(to_string(N))) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

方針2はC++ での実装例は以下のようになる.

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

// 文字列sが回文であるかを判定する関数
bool isPalindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}

int main() {
    string N; cin >> N;
    rep(i, 10) {
        string s = "";
        rep(j, i) s += '0';
        if (isPalindrome(s + N)) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

#C問題 ( Compass Walking )
###概要

xyグラフの原点から出発し, 1回の移動で距離Rだけ移動することができるとき, 最小で何回移動することで点(X, Y)まで到達できるか考える.

方針

原点から点(X, Y)までの距離をDとすると, 答えが1になるのは, R == D の時だけだということに注意する.
R > D の場合は, １回で行けそうだが, ちょうど目的地に着くことはできず, 最低でも2回の移動が必要である.

C++ での実装例は以下のようになる.

c.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

const ll LINF = (1LL << 60) - 1;

int main() {
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

int main() {
    ll R, X, Y;
    cin >> R >> X >> Y;
    // 1歩で行ける場合（コーナーケース）を処理
    if (R * R == X * X + Y * Y) {
        cout << 1 << endl;
        return 0;
    }
    ll ans = 2;
    while (1) {
        if (ans * ans * R * R >= X * X + Y * Y) break;
        ans++;
    }
    cout << ans << endl;
} 

#E問題 ( Unique Color )
###概要

N頂点のグラフ上で, 頂点1から頂点Xまでたどる時, Xと同じ色で塗られている頂点はXだけである頂点を全て求める.

方針

頂点1からDFSする.
頂点Xまでの経路で, 通過した頂点の色の種類を配列で管理しながら進む.

C++ での実装例は以下のようになる.

d.dpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
using Graph = vector<vector<ll>>;
vector<ll> color_count, C, ans;
Graph G;

void dfs(ll c, ll p = -1) {
    if (color_count[C[c]] == 0) ans.push_back(c + 1);
    color_count[C[c]]++;
    for (auto v : G[c]) {
        if (v == p) continue;
        dfs(v, c);
    }
    color_count[C[c]]--;
}
 
int main() {
    ll N; cin >> N;
    C = vector<ll>(N);
    color_count.resize(100005);
    rep(i, N) cin >> C[i];
    G = Graph(N);
    rep(i, N - 1) {
        ll a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    dfs(0, -1);
    sort(ans.begin(), ans.end());
    for (auto v : ans) cout << v << endl;
    return 0;
}