【c++】ABC362 A-E問題解説【ACコード付き】（毎日ABC day26）

AtCoder Beginner Contest 362

A,B,C,D,Eの5完。

レートは783→851の+68となり、前回の失速を取り戻すことができた。

水色パフォで、目標であった7月中の入緑も達成することができたので非常に嬉しい。

また来週からは水色へ向けて精進したい。目指せ9月中の入水。

A - Buy a Pen

3色のペンが売られており、1色買えない色が指定される。一番安いペンは何円か、という問題。

シンプル条件分岐。

ll R,G,B;
string C;

int main()
{
	cin >> R >> G >> B >> C;
	if (C == "Red") cout << min(B, G) << endl;
	if (C == "Blue") cout << min(R, G) << endl;
	if (C == "Green") cout << min(B, R) << endl;
	return 0;
}

B - Right Triangle

xy平面上に同一直線上にない3点が与えられるので、直角三角形であるか判定せよ、という問題。

2辺の距離の2乗の和が1辺の距離の2乗と一致する場合は直角三角形であるので、対辺3パターンを調べてどれにも当てはまらなかったら直角三角形でない。

ll xa, ya, xb, yb, xc, yc;

int main()
{
	cin >> xa >> ya >> xb >> yb >> xc >> yc;
	ll a = pow(xa - xb, 2) + pow(ya - yb, 2);
	ll b = pow(xc - xb, 2) + pow(yc - yb, 2);
	ll c = pow(xa - xc, 2) + pow(ya - yc, 2);
	if ((a + b == c) || (a + c == b) || (b + c == a)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

C - Sum = 0

$N$ 個の整数の組 $L_i, R_i$ が与えられる。以下左式を満たすようにXを選択し、右式のようにその合計が0となるような $X_i$ の選び方は存在しているか判定し、存在するのであれば出力せよ、という問題。
$$
L_i \leq X_i \leq R_i ; ; ; \sum_{i=1}^{N}X_{i}=0
$$

$L_i$ を全て足した値と$R_i$ を全て足した値の範囲にしか $\sum_{i=1}^{N}X_{i}$ の値は取り得ない。そのためそれらの値の間に0が含まれていることが $\sum_{i=1}^{N}X_{i}=0$ が存在する条件である。

また、存在する場合は全て一番小さな値 $L_i$ を選択したとして合計を計算し、合計が0になるまで、そこから要素1つずつ可能な限り大きな数字$R_i$に変更していけば $\sum_{i=1}^{N}X_{i}=0$ を満たす $X_i$ の選び方が得られる。

int main()
{
    // 入力
    ll N;
    cin >> N;
    vector<pair<ll, ll>> intervals(N);
    ll min_sum = 0;
    ll max_sum = 0;
    for (int i = 0; i < N; i++)
    {
        ll L, R;
        cin >> L >> R;
        intervals[i] = make_pair(L, R);
        min_sum += L;
        max_sum += R;
    }
    // Xの合計が0にできる場合
    if (min_sum <= 0 && max_sum >= 0)
    {
        cout << "Yes" << endl;
        vector<ll> result(N);
        // 一旦全ての左端を選択
        ll current_sum = min_sum;
        for (int i = 0; i < N; i++) result[i] = intervals[i].first;
        // current_sumが0になるまで右端を選択していく
        for (int i = 0; i < N && current_sum < 0; i++)
        {
            ll L = intervals[i].first;
            ll R = intervals[i].second;
            ll diff = min(R - L, -current_sum);
            result[i] += diff;
            current_sum += diff;
        }
        // 1つずつXを出力
        for (int i = 0; i < N; i++)
        {
            if (i > 0) cout << " ";
            cout << result[i];
        }
        cout << endl;
    }
    // Xの合計が0にできない場合
    else cout << "No" << endl;
    return 0;
}

D - Shortest Path 3

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる。各頂点と辺がそれぞれ重みを持つ時、頂点 1 から頂点 2 ~ N までのパスの最小重みをそれぞれ答えよ、という問題。

辺の向かう先の頂点の重みを辺の重みに加えてグラフを構築すると、単純なダイクストラ法に帰着できる。

ll N, M;
ll A[200009];
ll U[200009];
ll V[200009];
ll B[200009];
const ll INF = 1e18;
vector<pair<ll, ll>> Graph[200009];
vector<ll> cur(200009, INF);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++)
    {
        cin >> U[i] >> V[i] >> B[i];
        Graph[U[i]].push_back(make_pair(V[i], B[i] + A[V[i]]));
        Graph[V[i]].push_back(make_pair(U[i], B[i] + A[U[i]]));
    }
    // 初期値の設定
    for (int i = 1; i <= N; i++) cur[i] = INF;
    // スタート
    cur[1] = A[1];
    Q.push(make_pair(cur[1], 1));
    // ダイクストラ法
    while (!Q.empty())
    {
        pair<ll, ll> top = Q.top();
        Q.pop();
        ll pos = top.second;
        if (cur[pos] < top.first) continue;
        for (int i = 0; i < Graph[pos].size(); i++)
        {
            ll next_place = Graph[pos][i].first;
            ll next_time = Graph[pos][i].second;
            if (cur[next_place] > cur[pos] + next_time)
            {
                cur[next_place] = cur[pos] + next_time;
                Q.push(make_pair(cur[next_place], next_place));
            }
        }
    }
    // 出力
    for (int i = 2; i <= N; i++)
    {
        if (i > 2) cout << " ";
        cout << cur[i];
    }
    cout << endl;
    return 0;
}

E - Count Arithmetic Subsequences

長さ $N$ の数列 $A = \left( A_{1}, A_{2}, \ldots, A_{N} \right)$ が与えられます。各 $k=1,2,…,N$ について、$A$ の長さ $k$ の（連続するとは限らない）部分列であって等差数列であるようなものの個数を $998244353$ で割ったあまりを求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

ll N;
ll A[89];
const ll mod = 998244353;

int main()
{
    // 入力
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    // dp[i][len][diff] : 項数len, 項差diffの等差数列がi番目の要素を終点とする部分列の数
    vector<vector<unordered_map<ll, ll>>> dp(N, vector<unordered_map<ll, ll>>(N + 1));
    // resultで各項差の等差数列の数を格納
    vector<ll> result(N, 0);
    // 全ての要素のペアに対してdiffを計算し、項数lenの等差数列の数を更新
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            ll diff = A[i] - A[j];
            // 項数3以上のdpの更新
            for (int len = 3; len <= N; ++len) dp[i][len][diff] = (dp[i][len][diff] + dp[j][len - 1][diff]) % mod;
            // 項数2の要素はどの要素のペアでも1つ存在する
            dp[i][2][diff] = (dp[i][2][diff] + 1) % mod;
        }
    }
    // 結果を集計
    for (int i = 0; i < N; ++i)
    {
        for (int len = 1; len <= N; ++len)
        {
            for (auto& p : dp[i][len]) result[len - 1] = (result[len - 1] + p.second) % mod;
        }
    }
    // 長さ1の部分列は全て等差数列
    for (int i = 0; i < N; ++i) result[0] = (result[0] + 1) % mod;
    // 各長さkの等差数列の数を空白区切りで出力
    for (int k = 0; k < N; k++)
    {
        if (k > 0) cout << " ";
        cout << result[k];
    }
    cout << endl;

    return 0;
}