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++] ADT MEDIUM 2025/09/16 15:30 #AtCoder

Posted at

概要

自分用にまとめました。

  • 2025.9.16 C-D

C Who is missing? C

問題

1 から N までの整数が書かれたカードがそれぞれ 4 枚ある。一枚選んで抜き取った後のカードの束の数字が与えられるので、抜き取ったカードの数字が何かを求める。

  • 1 <= N <= 10^5
  • 1 <= Ai <= N

解法

  1. 全てのカードを数え上げる。
  2. 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++)

int N;
vector<int> C(100010);

int main() {
  cin >> N;
  rep(i, N*4-1) { int a; cin >> a; C.at(a)++; } //全てのカードを数え上げる
  repu(i, 1, N+1) if (C.at(i) == 3) { cout << i << endl; break; } //3 枚しかないカードを見つける
  return 0;
}

D Tak Code D

問題

縦 N マス、横 M マスのグリッドで、以下の条件を満たす箇所を求める。

  • 縦 9 マス横 9 マス
  • 左上と右下の縦 3 マス横 3 マス ( 9 マスずつ ) が黒
  • 黒いマスの周り ( 7 マスずつ ) が白
  • 9 <= N <= 100
  • 9 <= M <= 100
  • N と M は整数
  • Si は . は白、# は黒

解法

  1. パターンを用意する
  2. 全探索して条件を満たす箇所を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N, M;
vector<string> S(110);

int main() {
  cin >> N >> M;
  rep(i, N) cin >> S.at(i);
  
  vector<string> B = { "###.", "###.", "###.", "...." }, E = { "....", ".###", ".###", ".###" };
  //左上と右下のパターン
  rep(i, N-8) rep(j, M-8) { //(i, j) から縦 9 マス、横 9 マス調べるから i が N-8 以上または j が M-8 以上だと条件を満たさない
    bool ans = true;
    rep(k, 4) if (S.at(i+k).substr(j, 4) != B.at(k)) ans = false; //左上のパターン
    rep(k, 4) if (S.at(i+5+k).substr(j+5, 4) != E.at(k)) ans = false; //右下のパターン
    if (ans) cout << i + 1 << ' ' << j + 1 << endl; //両方のパターンと一致したら出力
  }
  return 0;
}

E Centers E

問題

1 から N がちょうど 3 回現れる数列 A がある。3 回現れるうちの 2 番目に現れた時の位置 ( インデックス ) を f(i) とする。1 から N を f(i) の昇順に並べる。

  • 1 <= N <= 10^5
  • 1 <= Aj <= N

解法 1

  1. 1 から N ごとに、現れた時の位置を記録する。
  2. i についてそれぞれ 2 番目に現れた時の位置とi を、ペア ( f(i), i ) にして、昇順に並べ替える。
  3. ペアの 2 つ目の要素である i を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N;
vector<vector<int>> A;

int main() {
  cin >> N;
  A.resize(N);
  rep(i, 3*N) { int a; cin >> a; A.at(a-1).push_back(i); } //それぞれの値ごとに、現れた時の位置を記録する
  
  vector<pair<int, int>> ans(N);
  rep(i, N) ans.at(i) = make_pair(A.at(i).at(1), i+1); //(f(i), i)のペアを作る
  sort(ans.begin(), ans.end()); //f(i) を元に昇順に並べ替える
  rep(i, N) cout << ans.at(i).second << ' '; //ペアの 2 番目の要素 i を出力する
  cout << endl;
  return 0;
}

解法 2

  1. 1 から N ごとに、現れた時の数を数える。
  2. 2 回目に現れた時に ans に追加する。
  3. ans を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N;
vector<int> A(100010, 0);

int main() {
  cin >> N;
  
  vector<int> ans;
  rep(i, 3*N) {
    int a; cin >> a; A.at(a)++; //現れた数を足していく
    if (A.at(a) == 2) ans.push_back(a); //現れたのが 2 回目だったら ans に追加
  }
  
  rep(i, N) cout << ans.at(i) << ' '; //ans を出力する
  cout << endl;
  return 0;
}

F Ladder Takahashi F

問題

10^9 階建てのビルに N 本のはしごがかかっている。1 階からはしごを登ったり降りたりして、最高で何階まで上がることができるのかを求める。

  • 1 <= N <= 2 * 10^5
  • 1 <= Ai <= 10^9
  • 1 <= Bi <= 10^9
  • Ai と Bi は等しくない

解法

  1. 梯子がどの階とどの階を繋いでいるのかを記録する。
  2. 1 階から順に繋がっている階を調べていく。
  3. 調べた階の中で一番高い階を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N;

int main() {
  cin >> N;
  map<int, vector<int>> G;
  rep(i, N) {
    int a, b; cin >> a >> b;
    G[a].push_back(b); //a 階から b 階へ行ける
    G[b].push_back(a); //b 階から a 階へ行ける
  }
  
  queue<int> Q; Q.push(1); //調べる階
  set<int> S; S.insert(1); //調べた or 調べる予定の階
  while (!Q.empty()) { //空ということは 1 階から行ける階は全て調べたということ
    int v = Q.front(); Q.pop(); //v 階について調べる
    for (int i : G[v]) if (!S.count(i)) { Q.push(i); S.insert(i); } //v 階に繋がっている階を調べて、まだ調べていなかったら Q に追加する
  }
  cout << *S.rbegin() << endl; //set は昇順に並んでいるので、一番後ろの一番高い階を出力する
  return 0;
}

G Add One Edge G

問題

1 から N1 までと、N1 + 1 から N1 + N2 までの頂点はそれぞれ連結している。辺を一つだけ追加して 1 と N1 + N2 の頂点を連結させる時、1 と N1 + N2 の経路の長さの最小値を、最大にした時の長さを求める。

  • 1 <= N1 <= 1.5 * 10^5
  • 1 <= N2 <= 1.5 * 10^5
  • 0 <= M <= 3 * 10^5
  • 1 <= ai <= bi <= N1 + N2;

解法

  1. どの頂点とどの頂点が繋がっているか調べる。
  2. 1 から一番遠い頂点への距離 c1 を求める。
  3. N1 + N2 から一番遠い頂点への距離 c2 を求める。
  4. 1 から距離 c1 にある頂点と、 N1 + N2 から距離 c2 にある頂点を繋ぐ辺を追加して、1 から N1 + N2 の距離を出力する。
サンプルコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)

int N1, N2, M;

int main() {
  cin >> N1 >> N2 >> M;
  map<int, vector<int>> G;
  rep(i, M) {
    int a, b; cin >> a >> b;
    G[a].push_back(b); //a は b と連結している
    G[b].push_back(a); //b は a と連結している
  }
  
  int c1 = 0;
  queue<pair<int, int>> Q; Q.push(make_pair(1, 0)); //頂点と頂点 1 からの距離をメモする
  set<int> S; S.insert(1); //調べた or 調べる予定の頂点
  while (!Q.empty()) {
    int v, num; tie(v, num) = Q.front(); Q.pop(); c1 = num; //幅優先探索なので後の方に調べる頂点の方が、1 から遠いので c1 にメモしていく
    for (int i : G[v]) {
      if (!S.count(i)) { Q.push(make_pair(i, num+1)); S.insert(i); } //調べている頂点が、調べていない頂点と繋がっていたら、距離を 1 足して Q に追加する
    }
  }

  //N1 + N2 からの一番遠い頂点への距離を調べる
  int c2 = 0;
  Q.push(make_pair(N1+N2, 0));
  S.clear(); S.insert(N1+N2);
  while (!Q.empty()) {
    int v, num; tie(v, num) = Q.front(); Q.pop(); c2 = num;
    for (int i : G[v]) {
      if (!S.count(i)) { Q.push(make_pair(i, num+1)); S.insert(i); }
    }
  }
  
  cout << c1 + c2 + 1 << endl; //1 から一番遠い頂点と、N1 + N2 から一番遠い頂点を繋いだ 1 から N1 + N2 までの距離
  return 0;
}
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?