주어진 수열의 모든 수는 서로 다르므로, 홀수 길이의 부분수열들 가운데 중앙값이 B인 부분수열의 개수는 다음과 같은 관찰을 통해 계산할 수 있다.
1) 이 부분수열은 B보다 큰 수와 B보다 작은 수의 개수가 같은 개수로 구성되어야한다.
2) 부분수열은 B를 포함해야하므로 (시작~B의 앞에 적힌 숫자), B, (B의 뒤에 적힌 숫자) 와 같은 구성을 가진다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
typedef long long ll;
int arr[100000];
int diff[200001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll ans = 0;
int N, B; cin >> N >> B;
int idx;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (arr[i] == B) idx = i;
}
int cnt = 1;
for (int i = idx; i < N; i++) {
if (arr[i] > B) cnt++;
else cnt--;
diff[100000 + cnt]++;
}
cnt = -1;
for (int i = idx; i >= 0; i--) {
if (arr[i] > B) cnt--;
else cnt++;
ans += diff[100000 + cnt];
}
cout << ans;
}
레스토랑의 출입구와 주방을 각각 source와 sink로 두고 각 방들을 노드로, 두 방을 잇는 연결통로를 각 방에 해당하는 두 노드를 이으면서 가중치가 (해당 통로에 air lock과 hatch를 설치할 때 필요한 비용)인 에지로 모델링을 하여 minimal cut을 구하면 문제를 해결할 수 있다.
벽에는 hatch가 필요없다는 조건이 레스토랑 전체를 나타내는 전체 직사각형의 바깥둘레를 의미하는 것으로 잘못 해석하여 매우 많은 오답을 제출했다(...). (연결통로의 크기가 0이라면 통로가 없으니 벽으로 생각해야하는 듯하다.)
아래는 제출한 소스코드이다.
#define INF 1000000007
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int R, C, RC;
int source, sink;
int edge[1000000][4];
vector<int> G[1000000];
int level[1000000];
bool bfs() {
memset(level, 0, sizeof(level));
level[source] = 1;
queue<int> que;
que.push(source);
while(!que.empty()) {
int current = que.front(); que.pop();
for (auto node : G[current]) {
int n;
if (node == 0) n = current - C;
else if (node == 1) n = current + C;
else if (node == 2) n = current - 1;
else n = current + 1;
if (edge[current][node] && level[n] == 0) {
level[n] = level[current] + 1;
que.push(n);
}
}
}
return level[sink];
}
int turn[1000000];
int dfs(int current, int flow) {
if (current == sink) return flow;
int cursize = G[current].size();
for (int &i = turn[current]; i < cursize; i++) {
int node = G[current][i];
int n;
if (node == 0) n = current - C;
else if (node == 1) n = current + C;
else if (node == 2) n = current - 1;
else n = current + 1;
if (edge[current][node] && level[n] == level[current] + 1) {
int f = dfs(n, min(edge[current][node], flow));
if (f) {
edge[current][node] -= f;
if (node == 0) edge[n][1] += f;
else if (node == 1) edge[n][0] += f;
else if (node == 2) edge[n][3] += f;
else edge[n][2] += f;
return f;
}
}
}
return 0;
}
void solve() {
cin >> R >> C; RC = R * C;
for (int i = 0; i < RC; i++) G[i].clear();
memset(edge, 0, sizeof(edge));
int sr, sc; cin >> sr >> sc; source = sr * C + sc;
int tr, tc; cin >> tr >> tc; sink = tr * C + tc;
for (int r = 0; r < R; r++) {
for (int c = 1; c < C; c++) {
int w; cin >> w;
if (w) {
w = w * 1000 + 1000;
edge[r * C + c][2] = w;
edge[r * C + c - 1][3] = w;
G[r * C + c].push_back(2);
G[r * C + c - 1].push_back(3);
}
}
}
for (int r = 1; r < R; r++) {
for (int c = 0; c < C; c++) {
int w; cin >> w;
if (w) {
w = w * 1000 + 1000;
edge[r * C + c][0] = w;
edge[(r - 1) * C + c][1] = w;
G[r * C + c].push_back(0);
G[(r - 1) * C + c].push_back(1);
}
}
}
int flow = 0;
while (bfs()) {
memset(turn, 0, sizeof(turn));
int f;
while (f = dfs(source, INF)) flow += f;
}
cout << flow << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while (T--) {
solve();
}
}
각 주어진 좌표별로, 각 좌표를 "직각인 각을 갖는" 꼭짓점으로 하는 직각삼각형의 개수를 센다고 생각하면 식을 세울 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int X[100001];
int Y[100001];
pair<int, int> points[100000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
int x, y; cin >> x >> y;
points[i] = { x,y };
X[x]++;
Y[y]++;
}
ll ans = 0;
for (int i = 0; i < N; i++) {
ans += ((ll)X[points[i].first] - 1) * ((ll)Y[points[i].second] - 1);
}
cout << ans;
}