문제 링크
1번 - 박 터트리기
단순 수학입니다. $N < \frac{K(K+1)}{2}$라면 불가능하고, 아닐 경우에는 N%K의 값을 확인하여 적당히 처리해주면 됩니다.
#include<bits/stdc++.h>
using namespace std;
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
int N,K;
cin>>N>>K;
if(K*(K+1)/2>N){
cout<<-1;
return 0;
}
N-=K*(K+1)/2;
cout<<K+(N%K?1:0)-1;
}
2번 - 햄버거 분배
그리디입니다. 가능한 한 왼쪽에 있는 햄버거를 먹게끔 짜면 됩니다. 전체 시간복잡도는 $O(NK)$지만, 이는 $2\times10^5$ 정도로 0.5초 이내에 작동하기에 충분합니다.
#include<bits/stdc++.h>
using namespace std;
int arr[20010];
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
int N,K;
cin>>N>>K;
string s;
cin>>s;
for(int i=0;i<N;i++){
arr[i+1]=2*(s[i]=='P');
}
int cnt=0;
for(int i=1;i<=N;i++){
if(arr[i]!=2)continue;
for(int j=max(1,i-K);j<=min(N,i+K);j++){
if(!arr[j]){
cnt++;
arr[j]=1;
break;
}
}
}
cout<<cnt;
}
3번 - 조명등
IOI16에 출제되었던 Aliens의 하위호환 문제입니다.
다른 조각품이 조명등에 포함될 때 반드시 그 안에 포함되는 조각품을 우선 지운 후, dp 식을 세웁니다.
dp[i]를 x[i]+h[i]에 대한 직선꼴로 나타낼 수 있으므로 CHT로 해결할 수 있습니다.
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using lll=__int128_t;
using pii=pair<int,int>;
using pll=pair<lll,lll>;
#define fi first
#define se second
const int NMAX=100010;
const ll inf=1e18;
struct line{
ll a,b;
lll get(lll x){
return a*x+b;
}
};
struct node{
int l,r;
ll s,e;//[s,e]
line li;
};
int chk(line a,line b,ll x){
lll A=a.get(x);
lll B=b.get(x);
if(A<B)return -1;
if(A==B)return 0;
if(A>B)return 1;
}
struct LiChao{
vector<node> tree;
void init(ll s,ll e){
tree.push_back({-1,-1,s,e,{0,inf}});
}
void ins(int i,line v){
ll s=tree[i].s,e=tree[i].e;
ll m=(s+e)/2;
line lo=v,hi=tree[i].li;
if(chk(lo,hi,s)==1)swap(lo,hi);
if(chk(lo,hi,e)!=1){
tree[i].li=lo;
return;
}
if(chk(lo,hi,m)==-1){
tree[i].li=lo;
if(tree[i].r==-1){
tree[i].r=tree.size();
tree.push_back({-1,-1,m+1,e,{0,inf}});
}
ins(tree[i].r,hi);
}
else{
tree[i].li=hi;
if(tree[i].l==-1){
tree[i].l=tree.size();
tree.push_back({-1,-1,s,m,{0,inf}});
}
ins(tree[i].l,lo);
}
}
ll get(int i,ll x){
if(i==-1)return inf;
ll s=tree[i].s,e=tree[i].e;
ll m=(s+e)/2;
if(x<=m)return min((ll)tree[i].li.get(x),get(tree[i].l,x));
else return min((ll)tree[i].li.get(x),get(tree[i].r,x));
}
};
int N;
ll x[NMAX+10],h[NMAX+10];
ll dp[NMAX+10];
void remove(){
int pv=1,top;
for(int i=2;i<=N;i++){
while(pv>0&&h[pv]-x[pv]<=h[i]-x[i])pv--;
pv++;
x[pv]=x[i];
h[pv]=h[i];
}
N=top=pv;
for(int i=N-1;i>0;i--){
while(top<=pv&&h[top]+x[top]<=h[i]+x[i])top++;
top--;
x[top]=x[i];
h[top]=h[i];
}
for(int i=1;i+top<N+2;i++){
x[i]=x[i+top-1];
h[i]=h[i+top-1];
}
N=pv-top+1;
}
void TC(){
//By sean9892
//sean9892.github.io
LiChao cht;
cht.init(-2e8,2e8);
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%lld%lld",x+i,h+i);
}
remove();
dp[0]=0;
cht.ins(0,{2*(h[1]-x[1]),(h[1]-x[1])*(h[1]-x[1])});
for(int i=1;i<=N;i++){
ll k=x[i]+h[i];
dp[i]=cht.get(0,k)+k*k;
cht.ins(0,{2*(h[i+1]-x[i+1]),(h[i+1]-x[i+1])*(h[i+1]-x[i+1])+dp[i]});
}
printf("%lld.%02lld\n",(ll)dp[N]/4,(ll)dp[N]%4*25);
}
int main(){
int tc;
scanf("%d",&tc);
while(tc--){
TC();
}
}