[c++] ABC076 #AtCoder

概要

問題の解き方をまとめました。

• 2025.9.19 A-D

A Rating Goal ABC076-A

問題

現在のレーティングと次のコンテストのパフォーマンスの平均が新しいレーティングになる。現在のレーティングが $R$ の時、次のコンテストでレーティングを $G$ にするために取るべきパフォーマンスを求める。

• $0 \leq R, G \leq 4500$
• 入力は全て整数

解法

1. 取るべきパフォーマンスを $x$ とする。

   (R + x) / 2 = G
   

   これを $x$ について解くと、

   x = 2 \times G - R
   

2. 上記より答えを出力する。

サンプルコード

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

int R, G;

int main() {
  cin >> R >> G;
  
  cout << 2*G - R << endl; //取るべきパフォーマンス
  return 0;
}

B Addition and Multiplication ABC076-B

問題

最初掲示板には $1$ が表示されている。この整数を $2$ 倍するか、 $K$ を足すか、を $N$ 回繰り返す。掲示板に表示される最小の値を求める。

• $1 \leq N, K \leq 10$
• 入力は全て整数

解法

1. 足される数が小さい方の操作を $N$ 回繰り返す。

サンプルコード

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

int N, K;

int main() {
  cin >> N >> K;
  
  int ans = 1; //初期値
  rep(i, N) {
    if (ans < K) ans <<= 1; //2 倍するということは左に 1 シフトするということ
    else ans += K;
    //2 倍にするということは ans を足すということだから、ans と K の小さい方を足していく
  }
  cout << ans << endl;
  return 0;
}

C Dubious Document 2 ABC076-C

問題

文字列 $S$ のいくつかの文字が「 ? 」に置き換わった文字列 $S'$ がある。$S$ には文字列 $T$ が含まれている。これらの条件を満たす文字列の中で、辞書順で最小の文字列が $S$ である。文字列が存在する場合は $S$ を求め、存在しない場合は「 UNRESTORABLE 」を出力する。

• $1 \leq |S'|, |T| \leq 50$
• $S'$ は英小文字と「 ? 」から成る
• $T$ は英小文字から成る

解法

1. $S'$ の最初から順に $T$ にマッチしていく箇所を探していく。
2. マッチする箇所を見つけたらその箇所を $T$ に置き換え、その他の「 ? 」を辞書順で一番小さな「 a 」に置き換える。
3. $ans$ が空な場合は、条件に合う文字列が存在しないということだから、「 UNRESTORABLE 」を出力する。空でない場合は、辞書順で一番小さな文字列を出力する。

サンプルコード

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

string S, T;

int main() {
  cin >> S >> T;
  
  set<string> ans; //答えの候補
  rep(i, S.size()-T.size()+1) { //S.size()-T.size()+1 個の部分文字列を調べる
    bool judge = true; //部分文字列が T である可能性があるかどうか
    rep(j, T.size()) {
      if (S.at(i+j) != '?' && S.at(i+j) != T.at(j)) { judge = false; break; }
    }
    if (judge) { //部分文字列が T である時
      string temp = S; temp.replace(i, T.size(), T); //一致した部分を T に置き換える
      for (auto it = temp.begin(); it != temp.end(); it++) {
        if (*it == '?') *it = 'a'; //? の部分を全て a に置き換える
      }
      ans.insert(temp); //候補に追加
    }
  }
  if (ans.empty()) cout << "UNRESTORABLE" << endl; //条件に合う文字列が一つもなかった場合
  else cout << *ans.begin() << endl; //条件に合う文字列の中で辞書順で一番小さいものを出力
  return 0;
}

D AtCoder Express ABC076-D

問題

列車の走行時間は $t_i$ 秒で、$v_i$ $m/s$ 以内で走っていなければならない。加速度は $\pm 1$ $m/s^2$。走行開始時と走行終了時には止まる。列車が発車してから停車するまでに走れる最大の距離を求める。

• $1 \leq N \leq 100$
• $1 \leq t_i \leq 200$
• $1 \leq v_i \leq 100$
• 入力は全て整数

解法

スタック

1. ある t 秒間の速度変化を求める。
   1. 速度 $v_i$ を超えて走行してはならないので、もし現在の速度がそれを超えていたら、過去に遡って速度を遅くする必要がある。
      1. 速度を $v_i$ に落とせる時間まで遡る。
      2. 速度がちょうど $v_i$ になるように走行する。
   2. 現在の速度から、距離が最大になるように走行する。
2. 区間を走った時間と初速度、最終速度がわかっているので、実際に走った距離を計算していく。

サンプルコード

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

typedef tuple<double, double, double> TP; //時間、初速度、最終速度

int N;
vector<double> T(101), V(101);

int main() {
  cin >> N;
  rep(i, N) cin >> T.at(i);
  rep(i, N) cin >> V.at(i); V.at(N) = 0; //N に着いたときの速度
  
  stack<TP> S; //走行記録
  double now_v = 0; //現在の速度
  rep(i, N+1) {
    if (now_v > V.at(i)) { //速度制限 V.at(i) より now_v が大きかった時、過去に遡って速度を遅くする
      double sum_t = 0, t, ev;
      while (now_v - sum_t > V.at(i)) { //now_v から sum_t 時間かけて速度を V.at(i) にできるかどうか、できなかったらさらに遡る
        tie(t, now_v, ev) = S.top(); S.pop();
        sum_t += t;
      }
      double d = now_v - V.at(i);
      if (sum_t == d) S.push(make_tuple(sum_t, now_v, V.at(i)));
      //now_v から減速し sum_t 秒後に速度 V.at(i) になる時
      else if (now_v == ev) { //now_v で sum_t - d 秒走行した後、減速し d 秒後に速度 V.at(i) になる時
        S.push(make_tuple(sum_t-d, now_v, now_v));
        S.push(make_tuple(d, now_v, V.at(i)));
      }
      else { //now_v から now_v + m まで加速した後、減速し d + m 秒後に速度 V.at(i) になる時
        double m = (sum_t - d) / 2.0;
        S.push(make_tuple(m, now_v, now_v+m));
        S.push(make_tuple(d+m, now_v+m, V.at(i)));
      }
      now_v = V.at(i); //現在の速度はいずれも V.at(i) になる
    }
    if (i == N) break; //地点 N がゴールなので終了
    
    if (now_v + T.at(i) <= V.at(i)) { //加速しても上限速度を超えない場合
      S.push(make_tuple(T.at(i), now_v, now_v+T.at(i)));
      now_v += T.at(i);
    }
    else { //上限速度まで加速し、その後は上限速度で走行する場合
      double d = V.at(i) - now_v;
      S.push(make_tuple(d, now_v, V.at(i)));
      S.push(make_tuple(T.at(i)-d, V.at(i), V.at(i)));
      now_v = V.at(i);
    }
  }
  
  double ans = 0, t, sv, ev; //ans は走行距離の総和
  while (!S.empty()) {
    tie(t, sv, ev) = S.top(); S.pop();
    if (sv == ev) ans += t * sv; //速度が一定の場合の走行距離
    else ans += t * (min(sv, ev) + (abs(sv-ev)/2.0)); //加速または減速した場合の走行距離
  }
  cout << fixed << setprecision(10) << ans << endl; //最大走行距離
  return 0;
}