수학을 잘하고 싶다.
로봇이 원점에서 시작해서 $LRDU$각 방향으로 움직일 때, $(x, y)$지점에 $i$번째로 방문할 때 마다 다음의 점수를 얻는다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[300005];
int r[300005], c[300005];
char d[] = {'U', 'R', 'D', 'L'};
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};
map<pair<int, int>, ll> cnt;
ll base = 1;
ll res[300005];
int main(){
scanf("%d %s", &n, s);
cnt[{0, 0}] = 1;
for(int i=0; i<n; i++){
r[i] = r[i-1]; c[i] = c[i-1];
if(s[i] == 'U') r[i]++;
if(s[i] == 'D') r[i]--;
if(s[i] == 'R') c[i]++;
if(s[i] == 'L') c[i]--;
cnt[{r[i], c[i]}]++;
base += cnt[{r[i], c[i]}]*((((abs(r[i])+1)^(abs(c[i])+1)))+1);
}
for(int j=0; j<4; j++){
ll base_ = base;
map<pair<int, int>, ll> cnt_ = cnt;
for(int i=n-1; i>=0; i--){
base_ -= cnt_[{r[i], c[i]}]*((((abs(r[i])+1)^(abs(c[i])+1)))+1);
cnt_[{r[i], c[i]}]--;
if(d[j] == s[i]){
res[i] = base_;
}
cnt_[{r[i]+dr[j], c[i]+dc[j]}]++;
base_ += cnt_[{r[i]+dr[j], c[i]+dc[j]}]*((((abs(r[i]+dr[j])+1)^(abs(c[i]+dc[j])+1)))+1);
}
}
for(int i=0; i<n; i++){
printf("%lld\n", res[i]);
}
}
$N \cdot M$크기의 격자가 있다. $(i, j)$위치에 $(i-1)*N+j$가 적혀 있다. 이 격자에 세로선 또는 가로선을 하나 그어 두 개의 직사각형으로 분할하는 경우들 중 분할한 각 구역의 수들의 합의 차이의 최소를 구하시오.
대충 가로선의 위치를 아래로 내릴수록 위쪽 영역의 합은 증가하고, 세로선의 위치를 오른쪽으로 옮길수록 왼쪽 영역의 합은 증가하고, 단조성이 있으니 이분탐색을 돌리고 싶다.
분할하는 위치에 따른 한쪽 영역의 값을 손으로 열심히 계산하고, 그 값을 토대로 이분탐색을 돌려 근처만 확인하면 된다.
별개로 그냥 O(1)에 계산해버리는 방법도 있는듯 하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
void solve(){
scanf("%lld %lld", &n, &m);
ll mn = 1e18;
ll s = (n*m)*(n*m+1)/2;
ll l = 0, r = m, r1 = 0;
while(l <= r){
ll mid = (l+r)/2;
ll cur = mid*n*(n*m-m+mid+1)/2;
if(cur <= s/2){
r1 = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
char d; ll p;
ll tmp = r1*n*(n*m-m+r1+1)/2;
if(mn > abs(2*tmp-s)){
mn = abs(2*tmp-s);
d = 'V';
p = r1;
}
tmp = (r1+1)*n*(n*m-m+r1+1+1)/2;
if(mn > abs(2*tmp-s)){
mn = abs(2*tmp-s);
d = 'V';
p = r1+1;
}
l = 0, r = n;
ll r2 = 0;
while(l <= r){
ll mid = (l+r)/2;
ll cur = (mid*m)*(mid*m+1)/2;
if(cur <= s/2){
r2 = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
tmp = (r2*m)*(r2*m+1)/2;
if(mn > abs(2*tmp-s)){
mn = abs(2*tmp-s);
d = 'H';
p = r2;
}
tmp = ((r2+1)*m)*((r2+1)*m+1)/2;
if(mn > abs(2*tmp-s)){
mn = abs(2*tmp-s);
d = 'H';
p = r2+1;
}
printf("%c %lld\n", d, p+1);
}
int main() {
int t;
scanf("%d", &t);
while(t--){
solve();
}
for (int k = 0; k < t; k++) {
cin >> n >> m;
}
}
$(i, i+p, i+p+q)$ 또는 $(i, i+q, i+p+q)$를 색칠할 수 있을 때, 모든 색칠이 겹치지 않으면서 $1$부터 $N$까지의 모든 칸이 칠해지도록 구성하시오.
얼마전에 누군가에게 수올 조합론 책을 받아서 읽고 있는데, 거기에서 똑같은 문제를 봤어서 날먹했다.
WLOG. $p < q$라고 하자. $1$부터 $N$까지 순서대로 보면서 현재 칸이 채워져 있다면 넘기고, 아니라면 $i+p$칸이 채워지지 않았다면 $(i, i+p, i+p+q)$를, 아니라면 $(i, i+q, i+p+q)$를 그리디하게 채우면 되고, 이는 항상 가능하다.
이를 증명해보자. 만약 이것이 불가능하다고 해보자. 불가능하려면 $i$번째 칸이 채워지지 않았을 때 $i+p$칸과 $i+q$칸 둘 다 칠해져 있어야 한다.
만약 $i+q$칸이 칠해져 있다면, 그 칸을 칠했을 때 $i+q$는 칠한 $3$개의 값 중 가장 큰 값이었을 것이다. 또한 그때의 가장 작은 값은 $i+q-(p+q) = i-p$일 것이다. 또한 $i$칸도 칠해지지 않은 상태였을 것이기 때문에 $i-p$번 칸에 대해 $(i-p, (i-p)+p, (i-p)+p+q)$를 무조건 칠하고 넘어왔어야 하므로 현재 $i$번 칸이 칠해지지 않은 상태일 수 없다. 따라서 불가능에 모순이 있으므로 이는 항상 가능하다.
암튼 그래서 대충 짜면 되고, 수올에서는 [IMO shortlist 2001, C4]에서 나왔다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int p, q, n;
int s[400005];
vector<pair<int, pair<int, int>>> v;
int main(){
scanf("%d %d %d", &p, &q, &n);
if(p > q) swap(p, q);
for(int i=1; i<=n; i++){
if(s[i]) continue;
s[i] = 1;
if(!s[i+p]){
s[i+p] = s[i+p+q] = 1;
v.push_back({i, {i+p, i+p+q}});
}
else{
s[i+q] = s[i+q+p] = 1;
v.push_back({i, {i+q, i+p+q}});
}
}
printf("%d\n", v.size());
for(auto [x, t] : v){
auto [y, z] = t;
printf("%d %d %d\n", x, y, z);
}
}'Problem Solving > boj' 카테고리의 다른 글
| [BOJ 33160] 꽃 풀이 (0) | 2025.01.16 |
|---|---|
| 2025. 01. 14 (2) | 2025.01.15 |
| 2025. 01. 11 플랜디 (0) | 2025.01.12 |
| 2025. 01. 10 플랜디 (0) | 2025.01.11 |
| 2025. 01. 09 플랜디 (3) | 2025.01.10 |