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++] ABC424 #AtCoder

Posted at

概要

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

  • 未 F-G
  • 2025.9.22 A-E

A Isosceles ABC424-A

問題

三角形 ABC の三辺の長さはそれぞれ $a$ 、$b$ 、$c$ である。三角形 ABC が二等辺三角形であるか判定する。

  • $1 \leq a, b, c \leq 10$
  • 三辺の長さが $a$ 、$b$ 、$c$ であるような三角形が存在し、その面積は正
  • $a$ 、$b$ 、$c$ は整数

解法

  1. $a$ 、$b$ 、$c$ のうち二辺が等しかったら二等辺三角形
サンプルコード
#include <bits/stdc++.h>
using namespace std;

int a, b, c;

int main() {
  cin >> a >> b >> c;
  
  bool ans = false;
  if (a == b || b == c || c == a) ans = true; //二辺が等しかったら二等辺三角形
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

B Perfect ABC424-B

問題

$N$ 人の人が $M$ 問の問題を解く。$K$ 個のイベントでは、$A_i$ の人が問題 $B_i$ に正解する。同じイベントが二回起きることはない。全ての問題に正解した人の番号を、正解したタイミングが早い順に出力する。

  • $1 \leq N \leq 10$
  • $1 \leq M \leq 10$
  • $K \geq 1$
  • $1 \leq A_i \leq N$
  • $1 \leq B_i \leq M$
  • $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
  • 入力は全て整数

解法

bit演算

  1. 誰が何問目を正解したかを保持しておく。
  2. 解いた問題の数と問題数が等しい場合に、全問正解した人の番号を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N, M, K;

int main() {
  cin >> N >> M >> K;
  
  vector<bitset<10>> S(10);
  rep(_, K) {
    int A, B; cin >> A >> B;
    S.at(A-1).set(B-1); //人 A が問題 B を正解したとき
    if (S.at(A-1).count() == M) cout << A << ' '; //全問正解した人の番号を出力
  }
  cout << endl;
  return 0;
}

C New Skill Acquired ABC424-C

問題

$N$ 個のスキルがある。$(A_i, B_i) = (0, 0)$ の時スキル $i$ は習得済み。そうでない時、スキル $A_i$ または $B_i$ の少なくとも一方を習得済みの時、スキル $i$ を習得できる。最終的に習得することができるスキルの個数を求める。

  • $1 \leq N \leq 1 \times 10^5$
  • $(A_i, B_i) = (0, 0)$ または $1 \leq A_i, B_i \leq N$
  • 入力は全て整数

解法

優先度付きキュー、幅優先探索

  1. スキル $i$ を取得することによって覚えることができるスキルを書き出していく。
  2. 取得したスキルの保持と、取得したスキルによって覚えることができるスキルを順番に調べていく。
  3. 取得したスキルの数を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N;
vector<vector<int>> T(200010);

int main() {
  cin >> N;
  rep(i, N) {
    int A, B; cin >> A >> B;
    if (A == 0) T.at(0).push_back(i+1); //初めから取得しているスキルは T.at(0) に追加
    else { T.at(A).push_back(i+1); T.at(B).push_back(i+1); } //A と B のスキルをそれぞれ獲得したら i + 1 のスキルを取得できる
  }
  
  bitset<200010> ans; //保持しているスキル
  queue<int> Q; Q.push(0); //取得しているスキル、T.at(0) は初めから取得しているスキル
  while (!Q.empty()) {
    int t = Q.front(); Q.pop();
    for (int i : T.at(t)) { //スキル t を取得することによって取得できるスキル
      if (!ans.test(i)) { ans.set(i); Q.push(i); } //まだ取得していなかったスキルを取得
    }
  }
  cout << ans.count() << endl; //取得しているスキルの数
  return 0;
}

D 2x2 Erasing 2 ABC424-D

問題

$H \times W$ のマス目があり、各マスは白または黒に塗られている。$2 \times 2$ の黒く塗られた部分を持たないようにする必要がある時、白く塗らなければならないマスが最小でいくつあるかを求める。

  • $1 \leq T \leq 100$
  • $2 \leq H \leq 7$
  • $2 \leq W \leq 7$
  • $S_i$ は「.」と「#」のみからなる長さ $W$ の文字列
  • $T$、$H$、$W$ は整数

解法

全探索

  1. 文字列を「 . 」を $0$ に、「 # 」を $1$ に置き換えて、bit 演算できるように整数で表す。
  2. 上下の列を並べたときに、$2 \times 2$ の黒いマスができない組み合わせを $true$ 、できる組み合わせを $false$ にする。
  3. $i - 1$ 番目の列と $i$ 番目の列を見る。$j$ の組み合わせが $S.at(i)$ からいくつかのマスを白に塗り替えることでできて、かつ $2 \times 2$ の黒いマスができない場合、$dp2.at(j)$ の値を更新する。
  4. 条件を満たした上で、白く塗り替えたマスの数が一番小さいものを出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

const int INF = 1e9;
int T;

int main() {
  cin >> T;
  
  rep(_, T) {
    int H, W; cin >> H >> W;
    vector<int> S(H); //最初の白いマスと黒いマスの状態を整数で表す
    rep(i, H) {
      int t = 0;
      rep(j, W) { char c; cin >> c; t <<= 1; if (c == '#') t++; }
      S.at(i) = t;
    }
    
    int K = 1 << W; //列の白いマスと黒いマスの組み合わせ
    vector<vector<bool>> allow(K, vector<bool>(K, true));
    rep(i, K) rep(j, K) rep(k, W-1) { //列が i の組み合わせと j の組み合わせが縦に並んだ時、2 * 2 の黒いマスができるかどうか
      if (((i>>k) & 3) == 3 && ((j>>k) & 3) == 3) { //2 * 2 の黒いマスがある時
        allow.at(i).at(j) = false; //問題の条件を満たさないので false
        break;
      }
    }
    
    vector<int> dp(K, INF); //最後の列が j の時、それまでに黒いマスを白いマスに塗り替えた数、条件を満たさない場合は INF
    dp.at(0) = 0;
    rep(i, H) {
      vector<int> dp2(K, INF); //更新する列
      rep(j, K) if ((j & S.at(i)) == j) { //S.at(i) からいくつかのマスを白く塗りつぶして j にできる時
        rep(k, K) if (allow.at(k).at(j)) { //2 * 2 の黒いマスがない時
          chmin(dp2.at(j), dp.at(k) + popcount((unsigned int)(j^S.at(i)))); //前列までに白く塗り替えたマスの数と、現在の列で白く塗り替えたマスの数を足す
        }
      }
      dp = dp2; //次の列に移動
    }
    
    int ans = INF;
    rep(i, K) chmin(ans, dp.at(i)); //白く塗り替えたマスの数が最も小さいものを見つける
    cout << ans << endl;
  }
  return 0;
}

E Cut in Half ABC424-E

問題

長さが $A_i$ の $N$ 本の棒が袋に入っている。最も長いものを 1 本取り出し、二等分して袋に戻す操作を $K$ 回する。操作が全て終わった後、長い方から $X$ 番目のものの長さを求める。$T$ 個のテストケースがある。

  • $1 \leq T \leq 10^5$
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^9$
  • $1 \leq K \leq 10^9$
  • $1 \leq X \leq N + K$
  • 全てのテストケースについての $N$ の総和は $10^5$ を超えない
  • 入力は全て整数

解法

優先度付きキュー

  1. 優先度付きキューに、入っている棒の長さと本数のペアを入れる。
  2. 棒の長さが長い順に取り出し、$K$ 回分の操作を行う。
  3. $X$ 番目の長さの棒を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int T, N, K, X;

int main() {
  cin >> T;
  cout << fixed << setprecision(10);
  
  rep(_, T) {
    cin >> N >> K >> X;
    priority_queue<pair<double, int>> A; //棒が入っている袋、長い順に出してくれる
    rep(i, N) { double a; cin >> a; A.emplace(a, 1); }
    
    while (K) {
      double a; int count; tie(a, count) = A.top(); A.pop();
      
      if (K <= count) { //K 回目の操作が終わる時
        A.emplace(a / 2, K * 2); //半分にした棒を袋に戻す
        A.emplace(a, count - K); //半分にしなかった棒を袋に戻す
        break;
      }
      else { //K 回以内の操作
        A.emplace(a / 2, count * 2); //半分にして袋に戻す
        K -= count; //棒の本数 = 操作した回数を引く
      }
    }
    
    while (X) {
      double a; int count; tie(a, count) = A.top(); A.pop();
      
      if (X <= count) { cout << a << endl; break; } //X 番目の棒
      X -= count; //X 番目より長い棒の数を引いていく
    }
  }
  return 0;
}

F Adding ChordsABC424-F

問題

解法

セグメント木

サンプルコード

G Set list ABC424-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?