티스토리 뷰

문제:icpc.me/3172


어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다.


단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다.


그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 


나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다.


이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int n, seg[400040];
long long r;
string s[100010];
pair<string, int> rs[100010];
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)return seg[node];
    if (x == y)return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)return 0;
    if (lo <= x&&<= hi)return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    sort(s, s + n);
    for (int i = 0; i < n; i++) {
        reverse(s[i].begin(), s[i].end());
        rs[i] = { s[i],i };
    }
    sort(rs, rs + n);
    for (int i = 0; i < n; i++) {
        r += (long long)query(rs[i].second, n - 110, n - 1);
        update(rs[i].second, 110, n - 1);
    }
    cout << r;
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10272 현상금 사냥꾼 김정은  (1) 2017.08.19
BOJ)8462 배열의 힘  (0) 2017.08.15
BOJ)3172 현주와 윤주의 재미있는 단어 게임  (0) 2017.08.15
BOJ)14675 단절점과 단절선  (1) 2017.08.06
BOJ)14426 접두사 찾기  (0) 2017.08.04
BOJ)1938 통나무 옮기기  (0) 2017.08.03
댓글
댓글쓰기 폼