[c++] ABC080 #AtCoder

概要

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

• 2025.9.24 A-D
• 2025.10.5 D

A Parking #ABC080-A

問題

$T$ 時間駐車した時 $A \times T$ 円になる駐車場と、駐車した時間に関わらず $B$ 円になる駐車場がある。駐車料金は最小でいくらか求める。

• $1 \leq N \leq 20$
• $1 \leq A \leq 100$
• $1 \leq B \leq 2000$
• 入力は全て整数

解法

1. 小さい方を出力する。

サンプルコード

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

int N, A, B;

int main() {
  cin >> N >> A >> B;
  
  cout << min(A * N, B) << endl;
  return 0;
}

B Harshad Number #ABC080-B

問題

整数 $X$ の各桁の和を $f(x)$ とする。$X$ が $f(x)$ で割り切れる場合、$X$ はハーシャッド数。整数 $N$ がハーシャッド数か判定する。

• $1 \leq N \leq 10^8$
• 入力は全て整数

解法

1. 各桁の和を計算する。
2. ハーシャッド数かどうか判定する。

サンプルコード

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

int N;

int main() {
  cin >> N;
  
  int t = N, s = 0;
  while (t > 0) { s += t % 10; t /= 10; } //各桁の和
  cout << (N % s == 0 ? "Yes" : "No") << endl; //ハーシャッド数かどうか
  return 0;
}

C Shopping Street #ABC080-C

問題

商店街には $N$ 個の店があり、10 個の時間帯に店を営業するか否かを決めることになっている。1 つ以上の時間帯で店を営業しなければならない。他の店と同じ時間帯に何回店を開くかによって、利益が決まる。この商店街に店を開いた場合の利益の最大値を求める。

• $1 \leq N \leq 100$
• $0 \leq F_{i, j, k} \leq 1$
• $1 \leq i \leq N$ を満たす全ての $i$ に対して、$F_{i, j, k} = 1$ を満たす $( j, k )$ が必ず一つ以上存在する。
• $-10^7 \leq P_{i, j} \leq 10^7$

解法

bit全探索

1. 10 個の時間帯について、開く日を全探索する。
2. 最も利益が大きかったものが答え。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repu(i, s, t) for (int i = (int)s; i < (int)t; i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

int N;
vector<vector<int>> F(100, vector<int>(10)), P(100, vector<int>(11, 0));
//F は i, j, k の三要素からなっているが、j と k をまとめて 10 個の時間帯としている

int main() {
  cin >> N;
  rep(i, N) rep(j, 10) cin >> F.at(i).at(j);
  rep(i, N) rep(j, 11) cin >> P.at(i).at(j);
  
  int ans = -1.1e9; //利益の最大値
  repu(tmp, 1, (1<<10)) { //全探索する
    bitset<10> p(tmp); //店を開く時間帯
    int sum = 0; //p のパターンでの利益
    rep(i, N) {
      int count = 0; //店 i と何回店を開く日が被るか
      rep(j, 10) if (p.test(j) && F.at(i).at(j)) count++;
      sum += P.at(i).at(count);
    }
    chmax(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

D Recording #ABC080-D

問題

$N$ 個のテレビ番組を録画する。チャンネルは $C$ 個ある。$i$ 個目のテレビ番組は、時刻 $s_i$ から時刻 $t_i$ まで、チャンネル $c_i$ で放送される。同じチャンネルで複数のテレビ番組が同時に放送されることはない。録画機は時刻 $S - 0.5$ から時刻 $T$ までの間、他のチャンネルの録画に使うことはできない。$N$ 個のテレビ番組の全ての放送内容が含まれるように録画するとき、必要な録画機の最小個数を求める。

• $1 \leq N \leq 10^5$
• $1 \leq C \leq 30$
• $1 \leq s_i \leq t_i \leq 10^5$
• $1 \leq c_i \leq C$
• $c_i = c_j$ かつ $i \neq j$ ならば $t_i \leq s_j$ か $s_i \geq t_j$ が成り立つ
• 入力は全て整数

解法 1

優先度付きキュー

1. 番組の開始時間が早いものから録画する。
2. 番組の開始前の時間で、録画終了時間が最も遅かった録画機を調べる。
3. どの録画機も使用中だったら、新しい録画機を用意する。
4. 最終的に用意した録画機の数を調べる。

サンプルコード

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

typedef tuple<int, int, int> T;
int N, C;

int main() {
  cin >> N >> C;
  priority_queue<T, vector<T>, greater<T>> Q; //開始時間が早い番組順
  rep(i, N) { int s, t, c; cin >> s >> t >> c; Q.emplace(s, t, c); }
  
  vector<pair<int, int>> A; //録画機 -> 終了時間とチャンネル
  rep(i, N) {
    int s, t, c; tie(s, t, c) = Q.top(); Q.pop(); //開始時間、終了時間、チャンネル
    int k = -1, max_t = 0; //何番目の録画機か
    rep(j, A.size()) {
      if ((A.at(j).second == c && A.at(j).first <= s) ||
          (A.at(j).second != c && A.at(j).first <= s - 0.5)) { //番組 i を録画できる録画機
        if (A.at(j).first > max_t) { k = j; max_t = A.at(j).first; } //録画終了時間が最も遅かった録画機
      }
    }
    if (k == -1) A.emplace_back(t, c); //録画できる録画機が無かったら新しく用意する
    else A.at(k) = make_pair(t, c); //録画機の録画終了時間を更新
  }
  cout << A.size() << endl; //録画機の数
  return 0;
}

解法 2

imos法

1. チャンネルごとに、番組が始まった時間には 1 を足して、番組が終わった後の時間から 1 を引く。
2. チャンネルごとに、番組を録画している時間を 1 にする。
3. 番組の放送時間が重なっている部分で、最も多く重なっている部分を見つける。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repu(i, s, t) for (int i = (int)s; i < (int)t; i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

int N, C;
vector<vector<int>> imos(30, vector<int>(100010, 0));

int main() {
  cin >> N >> C;
  
  rep(i, N) {
    int s, t, c; cin >> s >> t >> c;
    s--; c--;
    imos.at(c).at(s)++; //番組が始まる時間に 1 を足す
    imos.at(c).at(t)--; //番組が終わった後の時間から 1 を引く
  }
  rep(c, C) repu(i, 1, 100010) imos.at(c).at(i) += imos.at(c).at(i-1); //累積和を求める
  rep(c, C) rep(i, 100010) if (imos.at(c).at(i)) imos.at(c).at(i) = 1; //同じチャンネルで番組が重なることはないので、2 になっているところを 1 にする
  
  int ans = 0; //最も多くの番組が重なっている時の番組の数
  rep(i, 100010) {
    int count = 0; //時間ごとに重なっている番組の数
    rep(c, C) count += imos.at(c).at(i);
    chmax(ans, count);
  }
  cout << ans << endl;
  return 0;
}