Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Hiyoni

[c++] ABC423 #AtCoder

Posted at

概要

自分用にまとめました。

  • 2025.9.17 A-F

A Scary Fee ABC423-A

問題

$1000$ 円引き出すのに $C$ 円かかる。残高が $X$ 円ある時、最大で何円引き出せるかを求める。

  • $1 \leq X \leq 10^7$
  • $1 \leq C \leq 999$

解法

  1. $1000 + C$ で $X$ を割って、$1000$ をかける。
サンプルコード
#include <bits/stdc++.h>
using namespace std;

int X, C;

int main() {
  cin >> X >> C;
  
  cout << 1000 * (X / (1000+C)) << endl; //1000 + C で X を割って 1000 をかける
  return 0;
}

B Locked Rooms ABC423-B

問題

一列に並んだ部屋の、$0$ と $N$ の部屋に人がいる。鍵がかかっていて 2 人とも入れない部屋はいくつあるかを求める。

  • $2 \leq N \leq 100$
  • $Li \in \{0, 1\}$

解法

  1. 左から順に調べていき、鍵がかかっているドア $l$ を見つける。
  2. 右から順に調べていき、鍵がかかっているドア $r$ を見つける。
  3. $l == r$ つまり鍵がかかっているドアが $0$ 個か $1$ 個の場合は入れない部屋は無し。それ以外だと入れない部屋は $r - l$ 個。まとめて $r - l$ で答えを求められる。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repd(i, s, t) for (int i = (int)s-1; i >= (int)t; i--)

int N;
vector<int> L;

int main() {
  cin >> N;
  L.resize(N);
  rep(i, N) cin >> L.at(i);
  
  int l = -1, r = -1; //鍵がかかったドアが無い状態
  rep(i, N) if (L.at(i) == 1) { l = i; break; } //右から調べる
  repd(i, N, 0) if (L.at(i) == 1) { r = i; break; } //左から調べる
  cout << r - l << endl; //入れない部屋の数 r - l
  return 0;
}

C Lock All Doors ABC423-C

問題

$N + 1$ 個の部屋が並んでいる。最初部屋 $R$ にいるとき、すべてのドアを閉めるには、何回ドアを開け閉めする必要があるかを求める。

  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq R \leq N$
  • $Li \in \{0, 1\}$

解法

  1. 一番左の鍵がかかっていないドア $l$ を見つける。
  2. 一番右の鍵がかかっていないドア $r$ を見つける。
  3. $l \leq i \leq r$ の範囲で、鍵がかかっていないドアの数 $open$ を数えて、鍵がかかっているドアの数 $close$ も計算する。
  4. $l \leq R \leq r + 1$ の場合、$close$ の数は変わらない。$R < l$ の場合、余分に鍵がかかっているドアを開ける必要があるから、$close$ に $R - l$ を足す。$r + 1 < R$ の場合も、余分に鍵がかかっているドアを開ける必要があるから、$close$ に $R - r - 1$ を足す。
  5. 開ける必要があるドアを全て開けて、最後に開いているドアを全て閉じればいいので、求める答えは $open + close \times 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++)
#define repd(i, s, t) for (int i = (int)s-1; i >= (int)t; i--)

int N, R;
vector<int> L;

int main() {
  cin >> N >> R;
  L.resize(N);
  rep(i, N) cin >> L.at(i);
  
  int l = -1, r = -1; //鍵がかかっていないドアがない状態
  rep(i, N) if (L.at(i) == 0) { l = i; break; } //左から調べる
  repd(i, N, 0) if (L.at(i) == 0) { r = i; break; } //右から調べる
  if (l == -1) { cout << 0 << endl; return 0; } //鍵がかかっていないドアが無い場合は 0 を返して終了
  
  int open = 0;
  repu(i, l, r+1) if (L.at(i) == 0) open++; //鍵がかかっていないドアの数
  int close = r + 1 - l - open; //l <= i <= r の範囲で鍵がかかっているドアの数
  if (R < l) close += l - R; //左端の鍵がかかっていないドアの左側の部屋より R が左だった場合
  else if (r + 1 < R) close += R - r - 1; //右端の鍵がかかっていないドアの右側の部屋より R が右だった場合
  cout << open + close*2 << endl; //必要なドアの開閉操作の回数
  return 0;
}

D Long Waiting ABC423-D

問題

最大 $K$ 人の客を入れられるレストラン店がある。$i$ 番目の客の人数は $C_i$ 人で、時刻 $A_i$ に待ち行列の末尾に加わり、入店してから $B_i$ 時間後に退店する。それぞれの団体客が入店する時刻を求める。

  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq K \leq 10^7$
  • $1 \leq Ai \leq 10^7$
  • $1 \leq Bi \leq 10^7$
  • $A_1 < ... < A_N$
  • $1 \leq C_i \leq K$

解法

  1. 現在時刻 $now = 0$ 、レストランに入店している客の数 $sum = 0$ 、レストランに入店している客の退店時間と人数のペアを管理するための優先度付きキューを用意する。
  2. $i$ 番目の客は、列に並ぶより前に入店することはないので、最低でも列に並ぶ時刻を過ぎている必要がある。
  3. $i$ 番目の客がレストランに入りきらない場合は、すでにレストランに入っている客が退店するのを待つ必要がある。
  4. $i$ 番目の客が入店した後は、退店時刻と人数を $Q$ に追加する。
  5. $i$ 番目の客が入店した時の現在時刻を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef pair<int64_t, int> P; //退店時刻と客の人数のペアの型

int N, K;
vector<int64_t> A;
vector<int> B, C;

int main() {
  cin >> N >> K;
  A.resize(N); B.resize(N); C.resize(N);
  rep(i, N) cin >> A.at(i) >> B.at(i) >> C.at(i);
  
  int64_t now = 0; //現在の時刻
  int sum = 0; //レストランに入店している客の人数
  priority_queue<P, vector<P>, greater<P>> Q; //レストランに入店している客が退店する時刻とその人数、優先度付きキューなので退店時刻が早い順に取り出せる
  rep(i, N) {
    now = max(now, A.at(i)); sum += C.at(i);
    //最低でも行列に並ぶ時刻は過ぎている必要がある
    while (sum > K) { //客が入店すると最大人数を超えてしまう場合
      P p = Q.top(); Q.pop(); //退店時刻が最も早い客
      now = max(now, p.first); sum -= p.second;
      //客が退店する時刻を過ぎている必要がある
    }
    Q.push(make_pair(now + B.at(i), C.at(i))); //入店した客の退店時刻と人数を追加
    cout << now << endl; //現在の時刻を出力
  }
  return 0;
}

E Sum of Subarrays ABC423-E

問題

長さ $N$ の整数列 $A$ がある。$i$ 番目のクエリについて $L_i$ と $R_i$ が与えられるので、

\sum_{l=L_i}^{R_i} \sum_{r=l}^{R_i} \sum_{j=l}^r A_j

の値を求める。

  • $1 \leq N \leq 3 \times {10}^5$
  • $1 \leq A_i \leq 100$
  • $1 \leq L_i \leq R_i \leq N$

解法

  1. まず数式を変形する。
    1. $\sum_{l=L_i}^{R_i}$ より、$L_i \leq l \leq R_i$
    2. $\sum_{r=l}^{R_i}$ より、$l \leq r \leq R_i$
    3. $\sum_{j=l}^r$ より、$l \leq j \leq r$
    4. 以上より、$L_i \leq l \leq j \leq r \leq R_i$ が成り立つ。
    5. l は (j - $L_i$ + 1) 通り、r は ($R_i$ - j + 1) 通りあるので、$L_i \leq j \leq R_i$ の時それぞれ $(j - L_i + 1) \times (R_i - j + 1)$ 個の $A_j$ を足していく。 
      \sum_{l=L_i}^{R_i} \sum_{r=l}^{R_i} \sum_{j=l}^r A_j
= \sum_{j=L_i}^{R_i} (j - L_i + 1 ) (R_i - j + 1) A_j
= \sum_{j=L_i}^{R_i} -j^2 A_j + (L_i + R_i) A_j + (-Li + 1) (R_i + 1) A_j
  2. $A_j$ と $j A_j$ と $j^2 A_j$ の累積和 A0、A1、A2 を求める。
  3. $L_i \leq j \leq R_i$ の時、変形した数式と累積和から答えを求める。

int型 $\times$ int型 $=$ int型になることに注意！
int型の最小値 -2,147,483,648 ~ 最大値 2,147,483,647 を超える場合は $1ll$ を最初にかけるか、元から int64_t 型にしておく。これで何回も引っかかった…。

サンプルコード
#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++)

int N, Q;
vector<int64_t> A0(300010, 0), A1(300010, 0), A2(300010, 0);

int main() {
  cin >> N >> Q;
  repu(i, 1, N+1) {
    int64_t a; cin >> a;
    A0.at(i) = A0.at(i-1) + a; //Aj の累積和
    A1.at(i) = A1.at(i-1) + a * i; //j * Aj の累積和
    A2.at(i) = A2.at(i-1) + a * i * i; //j^2 * Aj の累積和、a が int型だと正しく計算できない
  }
  
  rep(i, Q) {
    int64_t L, R; cin >> L >> R;
    int64_t ans = -(A2.at(R)-A2.at(L-1))
                  + (L+R) * (A1.at(R)-A1.at(L-1))
                  + (-L+1) * (R+1) * (A0.at(R)-A0.at(L-1)); //L と R が両方 int型だと正しく計算できない
    //累積和を使って -j^2 * Aj + (Li + Ri) * Aj + (-Li + 1)(Ri + 1) * Aj を求める
    cout << ans << endl;
  }
  
  return 0;
}

F Loud Cicada ABC423-F

問題

$N$ 種類のセミは $A_i$ の倍数年のみ大量発生する。$1$ 年から $Y$ 年までのうち、ちょうど $M$ 種類のセミが大量発生する年が何回あるかを求める。

  • $1 \leq M \leq N \leq 20$
  • $1 \leq Y \leq 10^{18}$
  • $1 \leq A_i \leq 10^{18}$

解法

最大公倍数、bit演算

  1. 全ての組み合わせについて、最小公倍数を求め、$Y$ 年のうち何回大量発生するかを求める。
  2. ある組み合わせにおいて、組み合わせ以外のセミも大量発生する年を引いていく。（例えば、それぞれ 2 年と 3 年と 12 年に大量発生するセミ 1 とセミ 2 とセミ 3 がいるとする。セミ 1 とセミ 2 が大量発生する回数は、2 と 3 の最小公倍数が 6 だから、$Y / 6$ 回。ただし、12 年周期でセミ 3 も大量発生してしまうので、セミ 1 とセミ 2 だけが同時に大量発生する回数を求めるには、 $Y / 6 - Y / 12$ となる）
  3. ちょうど $M$ 種類のセミが大量発生する回数を求める。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N, M;
int64_t Y;
vector<int64_t> A(30);

int main() {
  cin >> N >> M >> Y;
  rep(i, N) cin >> A.at(i);
  
  vector<int64_t> B(1ll<<N); //全ての組み合わせの大量発生回数
  for (int64_t tmp = 0; !(tmp >> N); tmp++) { //全ての組み合わせを調べる
    int64_t t = 1; //最小公倍数
    rep(i, N) {
      if (tmp & (1ll << i)) { //大量発生するセミについて
        int64_t g = gcd(t, A.at(i)); //0 ~ i - 1 までの最小公倍数との最大公約数
        if ((t / g) > Y / A.at(i)) { t = Y + 1; break; }
        //t と A.at(i) の最小公倍数 t * A.at(i) / g が Y を超えるとき、この組み合わせの大量発生は起きないので t = Y + 1 にする
        //(t * A.at(i)) / g > Y を変形すると t / g > Y / A.at(i)
        //t = Y + 1 の時、Y / t == 0 になる
        else t = (t / g) * A.at(i); //最小公倍数を更新
      }
    }
    B.at(tmp) = Y / t; //大量発生が何回発生するか
  }
  
  rep(i, N) for (int64_t tmp = 0; !(tmp >> N); tmp++) {
    if (!(tmp & (1ll << i))) B.at(tmp) -= B.at(tmp | (1ll << i));
    //i 番目のセミが大量発生しない組み合わせの時、大量発生する時の組み合わせの回数を引く
  }
  
  vector<int64_t> ans(N+1, 0); //i 種類のセミが大量発生した時の回数
  for (int64_t tmp = 0; !(tmp >> N); tmp++) { //全ての組み合わせを調べる
    int64_t count = 0; //大量発生したセミの種類数
    rep(i, N) if (tmp & (1ll << i)) count++;
    ans.at(count) += B.at(tmp); //組み合わせが tmp である時 count 種類のセミが大量発生しているので回数を加算していく
  }
  cout << ans.at(M) << endl; //M 種類のセミが大量発生した時の回数
  return 0;
}

G Small Multiple 2 ABC423-G

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?