【AtCoder】黒〜緑のためのABC解説 | ABC309 A~F

コンテスト概要

問題	配点	Diff
A. Nine	100	22
B. Rotate	200	124
C. Medicine	350	348
D. Add One Edge	400	621
E. Family and Insurance	425	957
F. Box in Box	525	1619
G. Ban Permutation	575	2372
Ex. Simple Path Counting Problem	650	3029

難易度降下はこんな感じです。(横軸=AC時間、縦軸=相当レート)

問題解説

A. Nine

概要

図のような盤面があります。

1	2	3
4	5	6
7	8	9

A, Bが与えられるので、そのマスが隣り合っているかどうか判定してください。

制約

$1 \leq A \leq B \leq 9$

必要技術

• 余り

方針

全部の場合を考えてifを大量に書いてもできるのですが、せっかくなので少し短く書く方法を考えます。
隣り合うには、少なくとも差が1である必要があります。
しかし、Aが1の場合のみこれは成り立ちません。
なので、「B-A=1」かつ「Aが3の倍数でない」を判定すればよいです。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int A, B;
  cin >> A >> B;
  if(B-A == 1 && A%3 != 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

B. Rotate

概要

$N \times N$のマス目が与えられます。
外側のマスを時計回りに1個ずつずらしたものを出力してください。

制約

$2 \leq N \leq 100$
$A_{i,j} = 0, 1$

必要技術

• 二次元配列
• 平面操作

方針

ずらす向きと配列のズレ方に気をつけながらやっていきましょう。
Aをずらした結果をAに書き込んでしまうと、データを失ってしまったり、操作がめんどくさくなったりするので、別の配列Bを用意して操作することにします。

ずらすとき、4辺のそれぞれについて移動方向が違うので、4つに分けて操作するのがおすすめです。
今回は、このように分割・移動します。

移動後の座標で「値をもらう」処理を書くか、移動前の座標で「値を渡す」処理を書くか、どちらでもほぼ変わらないです。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<string> A(N);
  for(int i=0; i<N; i++) cin >> A[i];
  auto B = A;
  for(int i=0; i<N-1; i++) B[0][i+1] = A[0][i]; // 赤
  for(int i=0; i<N-1; i++) B[i+1][N-1] = A[i][N-1]; // 青
  for(int i=0; i<N-1; i++) B[N-1][N-2-i] = A[N-1][N-1-i]; // 紫
  for(int i=0; i<N-1; i++) B[N-2-i][0] = A[N-1-i][0]; // 緑

  for(int i=0; i<N; i++) {
    cout << B[i] << endl;
  }
}

値を渡すような処理で書いてみました。
N-1-i、N-2-iあたりの操作に気をつけましょう。(困ったときは具体例を考えてどうにかしましょう)

C. Medicine

概要

N種類の薬があります。
それぞれ、$a_i$日間、$b_i$錠ずつ飲まなければいけません。
その日に飲む薬がK錠以下になるのはいつですか。

制約

$1 \leq N \leq 3 \times 10^5$
$0 \leq K \leq 10^9$
$1 \leq a_i, b_i \leq 10^9$

必要技術

• ソート
• pair
• (番兵)
• (座標圧縮)
• (累積和)
• (二分探索)

方針

飲まなければいけない薬の種類はだんだん減っていきます。
そこで、「飲まなくても良いようになる順番」、すなわち「$a_i$が小さい順」に並べておけば、x日目に飲む錠数は$(前日に飲んだ錠数)-(a_i=x-1であるすべてのiについてのb_iの総和)$で計算できます。

これで1日ずつ見ていけば答えが求まりますが、時間に間に合いません。
計算量は、ソートに$O(N \log{N})$、一日ずつ見ていくのに$O(a_i)$なので、全体では$O(10^9)$です。

そこで、例えば$a_i = {1,1,1,100}$である場合、薬の錠数が(前日と比べて)減るのは2日目、101日目だけであるということを考えます。
こうすると、答えとなる可能性のある日付は、$a_i+1$日目だけですね。
なので、すべての日付を探索するのではなく、N個の日付のみを探索すればいいことがわかるので、$O(N\log{N}) + O(N) \fallingdotseq O(N\log{N}) \fallingdotseq O(5 \times 10^6)$となり間に合いそうです。

このような考え方を座標圧縮と言うこともあります。(少し違う気もしますが)

Sample2のような、1日目の時点ですでに条件を満たしている場合に注意しましょう。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> ab(N);
  for(int i=0; i<N; i++) cin >> ab[i].first >> ab[i].second;
  sort(ab.begin(), ab.end());
  long long now = 0;
  for(int i=0; i<N; i++) now += ab[i].second;
  // Sample2対策
  if(now <= K) {
    cout << 1 << endl;
    return 0;
  }
  for(int i=0; i<N; i++) {
    now -= ab[i].second;
    if(now <= K) {
      cout << ab[i].first+1 << endl;
      return 0;
    }
  }
}

今回、$a_i$についてソートしつつ、$a_i$に対する$b_i$も求める必要があります。
このような場合は、$a_i$、$b_i$を一つのペアにして管理すると良いです。
pair<int, int>が使いやすいです。なお、ソート時には「1つ目の値でソート、同じなら2つ目の値を考慮」となっています。

また、飲まなければいけない薬の錠数(now)は$\sum\limits_{k=1}^{N} a_k \leq10^9 \cdot N \leq 3 \times 10^{14}$となるので、intには入りません。long longなどを使う必要があります。

番兵のようなものを使ってSample2対策をする方法

if(now <= K)が2回も登場しているのは美しくありません。
そこで、存在しない$a_i=0, b_i=0$というペアを勝手に追加し、後者のif(now <= K)でSample2に対応できるようにします。
(このペアは追加しても結果に影響はありません)

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> ab(N+1);
  for(int i=0; i<N; i++) cin >> ab[i].first >> ab[i].second;
  ab[N] = {0,0};
  sort(ab.begin(), ab.end());
  long long now = 0;
  for(int i=0; i<N+1; i++) now += ab[i].second;
  for(int i=0; i<N+1; i++) {
    now -= ab[i].second;
    if(now <= K) {
      cout << ab[i].first+1 << endl;
      return 0;
    }
  }
}

二分探索で解く方法

この問題はつまり、下のように表を書いたとき、「$\Sigma$の欄がK以下のもの(緑色)の日付のうち最も小さい値」を答えるということです。

このとき、$\Sigma$の欄は単調に減少します。($1\leq b_i$なので当然です)
このように単調に増加または減少する関数の、ある値以上か未満かの境目を求めるときは、二分探索が利用できます。

ただし、そのままでは日付の最大値が$10^9$であるため、本解と同様に必要な部分だけを利用します。

このデータを作成した後、二分探索をすれば解くことができます。
ただし、ソートに$O(N\log{N})$、データ作成に$O(N)$、二分探索に$O(\log{N}) \fallingdotseq O(18)$かかるので、実際は殆ど実行時間は変わりません。逆に遅くなるかもです。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> ab(N);
  for(int i=0; i<N; i++) cin >> ab[i].first >> ab[i].second;
  sort(ab.begin(), ab.end());
  long long now = 0;
  vector<long long> sum(N+1, 0);
  for(int i=N-1; i>=0; i--) {
    sum[i] = sum[i+1] - ab[i].second;
  }
  auto found = lower_bound(sum.begin(), sum.end(), -K);
  if(found == sum.begin()) cout << 1 << endl;
  else cout << ab[found - sum.begin() - 1].first+1 << endl;
}

lower_boundは二分探索をしてくれる便利な関数です。
「〇〇以上」のものを求めるので、sumの値はすべて-1倍していることに気をつけてください。

ちなみに、この解法に対して「番兵のようなものを使ってSample2対策をする方法」を使うこともできます。

二分探索で解く方法(おまけ)

sumを-1倍した値で保存するのではなく、二分探索時にでリバースイテレータを使うことで、逆順に探索させることもできます。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> ab(N);
  for(int i=0; i<N; i++) cin >> ab[i].first >> ab[i].second;
  sort(ab.begin(), ab.end());
  long long now = 0;
  vector<long long> sum(N+1, 0);
  for(int i=N-1; i>=0; i--) {
    sum[i] = sum[i+1] + ab[i].second;
  }
  auto found = upper_bound(sum.rbegin(), sum.rend(), K);
  if(found == sum.rend()) cout << 1 << endl;
  else cout << ab[sum.rend() - found - 1].first+1 << endl;
}

また、sumを逆順にして探索するのでも良いです。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> ab(N);
  for(int i=0; i<N; i++) cin >> ab[i].first >> ab[i].second;
  sort(ab.begin(), ab.end());
  long long now = 0;
  vector<long long> sum(N+1, 0);
  for(int i=1; i<N+1; i++) {
    sum[i] = sum[i-1] + ab[N-i].second;
  }
  auto found = upper_bound(sum.begin(), sum.end(), K);
  if(found == sum.end()) cout << 1 << endl;
  else cout << ab[sum.end() - found-1].first+1 << endl;
}

D. Add One Edge

概要

頂点数が$N_1$、$N_2$の連結な無向グラフが(2つ)与えられます。
このグラフに辺を1本追加し、2つのグラフを連結するとき、頂点1から頂点$N_1+N_2$までの最短経路の長さとしてあり得るもののうち、最大のものを求めてください。

制約

$1 \leq N_1, N_2 \leq 1.5 \times 10^5$
$0 \leq M \leq 3 \times 10^5$
$1 \leq a_i \leq b_i \leq N_1 + N_2$

必要技術

• 読解
• 無向グラフ
• BFS

方針

専門用語だらけなので読解が大変ですが...

Sample1を見てみるとこうなりますね。

このうち、1の含まれている方のグラフと、2の含まれている方のグラフの間に辺を1本引いてつなげるという話です。

1と5、とか2と4、とかに辺を貼るよりも、2と5の間に辺を貼ったほうが、1から7への最短経路を長くすることができます。

サンプル2ではこうなります。

問題は、どうやってこのように頂点を分けるか、です。

このように、ある点からの距離を求めたい場合、幅優先探索(BFS)という方法が極めて有効です。

BFSとは、グラフを無駄なく探し回る方法の一つです。
深さ優先探索(DFS)というのもありますが、BFSはDFSと比べて「最短経路を求められる」という非常に強力な性質があります。

実際にやってみましょう。Sample2の1が含まれる方のグラフについて考えます。
まずは、頂点を「未処理」「TODO」「処理済」の3グループに分けます。最初はすべて未処理です。

スタート位置を決め、それをTODOに入れます。
スタート位置は1にしましょう。また、頂点1からの距離も一緒に保存しておきます。距離は0ですね。

次に、TODOリストの一番下、つまり「1」を処理済みに移動します。
このときついでに、「今操作した頂点(1)から1マスで行ける頂点」をすべてTODOに入れます。
距離は、「今移動した頂点の距離データ+1」としておきます。

また同じことをします。
TODOに移動させるのは未処理のものだけなことに注意しましょう。
つまり、1をTODOに戻してはいけないし、4や5は一度取り出してTODOに入れ直した訳ではない、ということです。

同じことを繰り返します。

同じことを繰り返します。
ただし、TODOリストは一番底から取り出すことに気をつけましょう。

あとは省略です。TODOが空になるまで続けます。
未処理は0にならなくても構いません、グラフが連結でない場合、つまり2つ以上に別れている場合は未処理に(1と連結していない頂点が)残ります。

これで完成です。
それぞれの頂点が頂点1からどれだけ離れているかが分かりました。

実装時は、queueという物を使うことで簡単に実装できます。

(ちなみに、TODOからの取り出しを上から行うとDFSとなります)

で、話を戻しましょう。
それぞれのグラフに対して「スタートから最も離れている頂点とスタートとの距離」を求めます。
それぞれx, yとおくと、答えはx+y+1です。

BFSの計算量は、「各頂点はちょうど1回ずつTODO→処理済みに動かす」ことと「TODO→処理済みに動かすときに、自分と繋がっている辺の数だけ探索を行う」ことから考えられます。
辺の数は$M$ですが、各頂点から見ることとなるので探索回数は$2\times M$です。
グラフ1に関わる辺の数を$M_1$、グラフ2に関わる辺の数を$M_2$とすると、$M_1+M_2=M$です。
よって、計算量は$O(N_1+2\times M_1) + O(N_2+2\times M_2) = O(N_1 + N_2 + 2 \times M) \fallingdotseq O(3\times 10^5 + 6 \times 10^5) = O(9 \times 10^5)$となります。
間に合いそうですね。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N1, N2, M;
  cin >> N1 >> N2 >> M;

  // graph[i]は、頂点iと連結している頂点のリスト
  vector<vector<int>> graph(N1 + N2);
  for(int i=0; i<M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  // bfs 1回目
  vector<int> visited(N1 + N2, 0);
  queue<int> todo;
  vector<int> cost(N1 + N2);
  vector<int> max_cost(2, 0);
  visited[0] = 1;
  todo.push(0);
  cost[0] = 0;
  while(!todo.empty()) {
    int current = todo.front();
    todo.pop();
    for(int next : graph[current]) {
      if(visited[next]) continue;
      visited[next] = 1;
      cost[next] = cost[current] + 1;
      todo.push(next);
      max_cost[0] = max(max_cost[0], cost[next]);
    }
  }
  // bfs 2回目
  visited[N1+N2-1] = 1;
  todo.push(N1+N2-1);
  cost[N1+N2-1] = 0;
  while(!todo.empty()) {
    int current = todo.front();
    todo.pop();
    for(int next : graph[current]) {
      if(visited[next]) continue;
      visited[next] = 1;
      cost[next] = cost[current] + 1;
      todo.push(next);
      max_cost[1] = max(max_cost[1], cost[next]);
    }
  }
  cout << max_cost[0] + max_cost[1] + 1 << endl;
}

入力される頂点番号は1始まりですが、実装時は0始まりとして考えているので注意しましょう。
気になる人は、visitedやcostといった変数を2つ準備しても良いです。

E. Family and Insurance

概要

人1~Nがいて、人$i(i\leq2)$の親は$p_i$です。
ここで、保険1~Mがあり、保険$i$の加入者は$x_i$、適用範囲は$y_i$代先までです。
保険対象者は何人いますか?

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq M \leq 3 \times 10^5$
$1 \leq p_i \leq i-1$
$1 \leq x_i \leq N$
$1 \leq y_i \leq 3 \times 10^5$

必要技術

• DP
• (応用ダイクストラ法)
• (超頂点+BFS)

方針

まず、家系図を有向グラフとして保存し、各保険についてBFSで探索すれば、それぞれの頂点が保険の対象になっているかどうかを探索できます。
(各保険について、契約者から適用範囲分以内の距離にいる人は保険が適用されます)
しかし、BFSの計算量は$O(頂点数+辺数)$程度であるので、これを各保険について行うと、最悪$O(M \times (N + N)) \fallingdotseq O(18 \times 10^10)$程度となり、どう考えても間に合いません。

ここで、$p_i \leq i-1$という条件に注目します。
これは「6の親が5」はあり得るけれども「5の親が6」はありえない、という制限です。
番号は生まれた順みたいな把握をしておけばいいんですかね。
これを使うと、iが保険の対象になっているかどうかは、人$1\sim(i-1)$のみで決定されます。
(子供が保険を契約したかどうかは親に影響を与えません)

また、ある人が「3世代下まで有効な保険」、「10世代下まで有効な保険」の両方の対象になっている場合、10世代下まで有効な保険だけを考えればよいです。

この条件を用いることで、「あと何世代有効な保険を持っているか」を配列として管理すれば、前から決定していくことができます。

この表のように、自分の保険の残量は、「親の残り-1」と「自分の入っている保険の残量のmax」のうちm大きい方となります。
これを人1から順番に見ていけばOKです。

つまり、1次元DPです。

コード

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  vector<int> p(N);
  for(int i=1; i<N; i++) {
    cin >> p[i];
    p[i]--;
  }
  // 自分で保険を持っている場合、その量
  // 持っていない場合、-1
  vector<int> own(N, -1);
  for(int i=0; i<M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    own[x] = max(own[x], y);
  }
  // 最終的な保険の残量
  vector<int> dp(N, -1);
  dp[0] = own[0];
  for(int i=1; i<N; i++) dp[i] = max(dp[p[i]]-1, own[i]);

  int ans = 0;
  for(int i=0; i<N; i++) if(dp[i] >= 0) ans++;
  cout << ans << endl;
}

1始まり or 0始まりに気をつけましょう。

おまけ: 最後の集計のところを、cout << count_if(dp.begin(), dp.end(), [](int x){return x>=0;}) << endl;としてもよいです。

ダイクストラ法を応用した解法

ABC305 E. Art Gallery on Graphのやり方です。
この親子の順番が決まっていない場合、つまり無向グラフのような場合でも利用できる方法です。

まずダイクストラ法というのは重み付きグラフの最短経路を求める方法です。

軽く解説します。
まず、頂点1から1へ移動するコストは0です。これは確定です。
つぎに、確定した頂点と直接繋がっている頂点について、暫定コストを出しておきます。
頂点2, 3ですね。

このとき、2,3どちらかが確定してくれれば、話が前に進みます。
ここで、暫定コストが変化する、というのは、どういうことでしょうか?
これは、未知の道、すなわち他の赤い頂点を通ってたどり着く道で、より低コストな物がある、ということです。
しかし、この状況で、2に10以下のコストでたどり着く道があるでしょうか?
そのためには、1から2以外を経由してから2に到達する必要があります。
しかしそのためには、2以外の赤い頂点に進まなければならず、2に到達する際のコストはどうやっても20以上になってしまいます。
このように、「仮の値を計算し、仮となっているもののうち最小のものはその値に決定して良い」というふうにすすめていくのがダイクストラ法です。
ちなみにこの後の遷移はこのようになります。

最小のものばかり取り出していくという操作は、優先度付きキューというデータ構造を用いることで楽に実装できます。

これを保険に応用します。
自分の保険残量(仮)を計算しておき、それが小さいものから確定させつつ、子供に継承させていけばよいですね。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> children(N);
  for(int i=1; i<N; i++) {
    int p;
    cin >> p;
    p--;
    children[p].push_back(i);
  }
  vector<int> confirmed(N, 0);
  vector<int> result(N, -1);
  // [保険残量, 頂点番号]で保存する
  priority_queue<pair<int, int>> q;
  for(int i=0; i<M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    q.push({y, x});
  }
  while(!q.empty()) {
    auto target = q.top();
    q.pop();
    if(confirmed[target.second]) continue;
    confirmed[target.second] = 1;
    result[target.second] = target.first;
    if(target.first == 0) continue;
    for(auto child : children[target.second]) {
      q.push({target.first-1, child});
    }
  }

  int ans = 0;
  for(int i=0; i<N; i++) if(result[i] >= 0) ans++;
  cout << ans << endl;
}

priority_queueは、そのままでは値が大きなものから順に取り出せるように設計されていることに注意しましょう。

超頂点を応用した解法

ABC305 E. Art Gallery on Graphのときの、りーふさんの解法を参考にしています。

この解法でポイントとなるのは超頂点です。
超頂点とは、実際には存在しない頂点を勝手に作り出して解くようなやり方です。(多分)

今回の問題の場合、家系図グラフに対して、以下の図の青・緑の頂点、そして青・赤の辺を追加します。

赤の辺は、(from→toとして)fromの保険をtoが購入した、ということを表します。
このようにすれば、「保険残1」から2回以下の移動で到達できる頂点には、その保険が適用される事がわかります。
同様に、「保険残x」からx+1回以下の移動で到達できる頂点には、その保険が適用される事がわかります。

よって、この有効グラフに対して、「Startから3+1+1=5回以内の移動で到達できる頂点」には保険が適用されるということです。
これは、BFSを1回行うだけで解くことができます。

もう少し一般化しましょう。
保険の期間、すなわち$y_i$は$y_i \leq 3 \times 10^5$であるため、頂点をいっぱい作っておきます。

この場合、BFSの計算量を$O(頂点数+辺数)$とすると、$O((3\times 10^5 + 3 \times 10^5 + 1) + (3 \times 10^5 + 3 \times 10^5 + 3 \times 10^5)) \fallingdotseq O(1.5 \times 10^6)$となり、間に合いそうです。

実装時には、追加した頂点をどう管理するかを考えましょう。
今回は、

• $i=0$は人$1$、$i=1$は人$2$、…、$i=N-1$は人$N$
• $i=N$は$保険残1$、$i=N+1$は$保険残2$、…、$i=N+3\times10^5-1$は$保険残3×10^5$
• $i=N+3\times10^5$は$Start$

として実装してみます。
この場合、Startから$3\times 10^5+1+1$回以内の移動で行ける頂点を探索することになります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> graph(N+300001);
  for(int i=0; i<300000; i++) graph[N+i+1].push_back(N+i);
  for(int i=1; i<N; i++) {
    int p;
    cin >> p;
    p--;
    graph[p].push_back(i);
  }
  for(int i=0; i<M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    graph[N+y-1].push_back(x);
  }
  // BFS
  queue<int> q;
  vector<int> result(N+300001, -1);
  q.push(N+300000);
  result[N+300000] = 300002;
  while(!q.empty()) {
    int current = q.front();
    q.pop();
    if(result[current] == 0) continue;
    for(int next : graph[current]) {
      if(result[next] >= 0) continue;
      result[next] = result[current] - 1;
      q.push(next);
    }
  }
  int ans = 0;
  for(int i=0; i<N; i++) if(result[i] >= 0) ans++;
  cout << ans << endl;
}

F. Box in Box

概要

N個の長方形の箱があります。
高さ・幅・奥行きは、それぞれ$h_i, w_i, d_i$です。
箱Aが箱Bに入るようなA,Bの組は存在しますか?

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq h_i, w_i, d_i \leq 10^9$

必要技術

• 立体図形
• 座標圧縮
• セグメント木

方針

まず、直方体は回転させることで、高さ・幅・奥行きを自由に並べ替えられます。
(実際にお菓子の箱とか消しゴムとか回してみるとわかります)
なので、$h_i, w_i, d_i$を昇順に並べて$x_i, y_i, z_i$としておき、「$x_i\leq x_j$かつ$y_i\leq y_j$かつ$z_i\leq z_j$を満たす(i, j)が存在するか」という問題として考えても良いです。

この条件を満たすために、全部をチェックしていては$O(N(N-1))\fallingdotseq O(4\times 10^10)$となり間に合いません。
まずxから考えていきましょう。$x_i\leq x_j$が必要であり、N個の箱は並べ得ても良いので、$x_i$を照準に並べておきます。
こうしておけば、$x_j$を考えているときに、これまでに見た箱だけを考えれば良くなります。

次に、「今まで見たすべての$(y_i, z_i)$の組の中で、$y_i < y_j$かつ$z_i < z_j$」を満たすものがあるかを考えなければなりません。
これを、yz平面として考えてみると、「順番に点を打っていきます。このとき、$0 \leq y < y_j$かつ$0 \leq z < z_j$を満たす長方形の領域に点は存在しますか?」と言い換えられます。

ここでポイントになるのが、$0 \leq z < z_j$という条件です。
つまり、$0 \leq y < y_j$の領域でのzの最小値が$z_m$であるとき、$z_m < z_j$であれば条件を満たします。

このためには、「区間の最小値」を求めれば良いです。すなわち、セグメント木を使えば良いです。

また、$1 \leq y_i \leq 10^9$であるため、これをセグメント木に直接入れようとすると、長さ$10^9$のセグメント木が必要になります。
これは作れないので、座標圧縮を行い、$0 \leq y_i' < N$に収めましょう。
(x,zは座圧してもしなくても良いと思います)

ただし、$x_i=x_j$かつ $y_i<y_j$ かつ $z_i<z_j$ の場合、本来は条件を満たしていないのに間違って判定されてしまいます。
そこで、xが前回と同じ場合はsegtreeへの書き込みは行わず、queueやstackに積んでおくことにします。

計算量は、ソート、座標圧縮、セグ木の操作にそれぞれ$O(N\log{N})$で、全体でも$O(N\log{N})$となります。いけそうですね。

コード

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

int op(int a, int b) {
    return min(a, b);
}

int e() {
    return (int)(1e9+1);
}

int main() {
  int N;
  cin >> N;
  vector<vector<int>> xyz(N, vector<int>(3));
  for(int i=0; i<N; i++){
    cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
    sort(xyz[i].begin(), xyz[i].end());
  }
  sort(xyz.begin(), xyz.end());

  // yを座標圧縮
  vector<int> y(N);
  for(int i=0; i<N; i++) y[i] = xyz[i][1];
  sort(y.begin(), y.end());
  y.erase(unique(y.begin(), y.end()), y.end());
  vector<int> y_compressed(N);
  for(int i=0; i<N; i++) {
    y_compressed[i] = lower_bound(y.begin(), y.end(), xyz[i][1]) - y.begin();
  }

  // xを順番に探索
  segtree<int, op, e> seg(N);
  int prev_x = -1;
  queue<pair<int, int>> todo_yz;
  for(int i=0; i<N; i++) {
    if(prev_x == xyz[i][0]) todo_yz.push({y_compressed[i], xyz[i][2]});
    else {
      // TODO消化
      while(!todo_yz.empty()) {
        auto [y, z] = todo_yz.front();
        todo_yz.pop();
        seg.set(y, min(seg.get(y), z));
      }
      todo_yz.push({y_compressed[i], xyz[i][2]});
      prev_x = xyz[i][0];
    }
    int z_min = seg.prod(0, y_compressed[i]);
    if(z_min < xyz[i][2]) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

まとめ

BFS、DP、Segtreeと、まあいつも通りの感じですね。
この解説記事書いてるときに初めてSegtree使ったのですが、これ便利ですね...!