ABC077C - Strorkisのブログ

問題

C - Snuke Festival

$A_i,\ B_i,\ C_i(1 \leq i \leq N)$ において、 $A_i < B_i < C_i$ となる組み合わせは何通りあるか。]

解法

解説では二分探索で解いていたが、頭に尺取り法しか無かったため、尺取り法で解いた。

まず、単調減少である必要があるため、降順にソートする。

次に、 $A_i,\ B_i$ が大きい順に $A_i < B_i$ となる組み合わせを求める。

この時、 $B_i < C_i$ となる $C_i$ の個数を調べるのだが、 $A_i >= A_j$ の全ての場合において $A_j < B_i$ となるので、 $A_i >= A_j$ の個数を $C_i$ の個数に掛ければ良い。

$A_i < B_i$ となる組み合わせや、 $B_i < C_i$ となる $C_i$ の個数は、大きい順に見ていくことから、一つ前でどこまで見たかを覚えておけば、合計 $O(N)$ で求めることができる。

計算量は、尺取り法が $O(N)$ だが、ソートで $O(NlogN)$ 要するので、全体で $O(NlogN)$ である。]

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) cin >> c[i];
  sort(a.begin(), a.end(), greater<int>());
  sort(b.begin(), b.end(), greater<int>());
  sort(c.begin(), c.end(), greater<int>());

  long long ans = 0;
  int i = 0, j = 0, k = 0;
  while (i < n) {
    while (j < n && a[i] < b[j]) {
      while (k < n && b[j] < c[k]) k++;
      ans += 1LL * (n - i) * k;
      j++;
    }
    i++;
  }
  cout << ans << endl;
}

感想

Bを軸とする発想が浮かばなかったので、二分探索を思いつくことができなかった。

尺取り法を考えていくうちにBを軸とすれば良いことはわかったが、解く時間が長くなってしまったため、考察力を磨く必要がある。

また、最近解いた問題の解法に引きずられる傾向があるので、頭をリセットして取り組めるようになりたいところ。