概要

自分用にまとめました。

2025.9.16 C-D

C Who is missing? C

問題

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

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

解法

全てのカードを数え上げる。
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 は . は白、# は黒

解法

パターンを用意する
全探索して条件を満たす箇所を出力する。

サンプルコード

#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 から N ごとに、現れた時の位置を記録する。
i についてそれぞれ 2 番目に現れた時の位置とi を、ペア ( f(i), i ) にして、昇順に並べ替える。
ペアの 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 から N ごとに、現れた時の数を数える。
2 回目に現れた時に ans に追加する。
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 階から順に繋がっている階を調べていく。
調べた階の中で一番高い階を出力する。

サンプルコード

#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 から一番遠い頂点への距離 c1 を求める。
N1 + N2 から一番遠い頂点への距離 c2 を求める。
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;
}