A (0:00 ~ 0:58)
반복문 기초 문제
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
int main(){
fast;
ll n,m,k;
string s,t;
vector<ll> v,e;
cin>>n>>m>>k;
ll cnt=0;
for(int i = m ; i <= n ; i+=k)cnt++;
cout<<cnt;
}
B (0:58 ~ 2:56)
직사각형 합집합인데 제한이 100*100이라서 그냥 배열에 하나하나 추가하면 된다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll arr[101][101];
int main(){
fast;
ll n; cin>>n;
while(n--){
ll a,b,c,d; cin>>a>>b>>c>>d; b--; d--;
for(int i = a ; i <= b ; i++){
for(int j = c ; j <= d ; j++)arr[i][j]=1;
}
}
ll ans=0;
for(int i = 0 ; i <= 100 ; i++)for(int j = 0 ; j <= 100 ; j++)ans += arr[i][j];
cout<<ans;
}
C (2:56 ~ 9:27)
정해는 아니지만 생각하기 귀찮아서 펜윅으로 풀었다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, d, p;
ll f[101010*2];
ll cur = 0; //d 누적
ll ans = 0;
ll tree[202020];
void upd(ll i, ll x){
while(i<=n)tree[i] += x, i += (i&-i);
}
ll sum(ll i){
ll ret=0;
while(i)ret += tree[i], i -= (i&-i);
return ret;
}
int main(){
fast;
cin>>n>>d>>p;
for(int i = 1 ; i <= n ; i++)cin>>f[i];
sort(f+1,f+n+1,greater<>());
for(int i = 1 ; i <= n ; i++)upd(i,f[i]);
ans = sum(n);
for(int i = 1 ; i <= n ; i++){
cur += p;
ll cnt=0;
while(i<=n and cnt<d)cnt++, upd(i++,p-f[i]);
i--;
ans = min(ans, cur + sum(n)-sum(i));
}
cout<<ans;
}
D (9:27 ~ 17:33)
여기서 시간이 좀 걸렸는데, 브루트포스가 될지 엄청 고민하고 있었는데 결론은 그냥 비트마스킹 dp를 하기로 했다.
dp[bit] := bit가 켜진 정점들은 방문한 상태일때, 가중치 합의 최대
두 정점을 골라서 다음 상태로 전이시키면 된다. 시간복잡도는 \( O(2^N * N^2) \)
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll dp[1<<17];
ll n;
ll d[17][17];
ll f(ll bit){
ll x = __builtin_popcount(bit);
if((x==n-1 and n&1) or (x==n and n%2==0))return 0;
ll &ret = dp[bit];
if(~ret)return ret; ret=0;
for(int i = 1 ; i <= n ; i++){
if(bit&(1<<i))continue;
for(int j = i+1 ; j <= n ; j++){
if(bit&(1<<j))continue;
ret = max(ret, f(bit|(1<<i)|(1<<j))+d[i][j]);
}
}
return ret;
}
int main(){
fast;
cin>>n;
for(int i = 1 ; i <= n ; i++){
for(int j = i+1 ; j <= n ; j++){
cin>>d[i][j]; d[j][i] = d[i][j];
}
}
memset(dp,-1,sizeof(dp));
cout<<f(0);
}
E (17:33 ~ 23:19)
일단 적어도 O(NlogN)에 해야 한다. 보통 세 쌍을 카운팅하는 문제는 중간 값을 기준으로 왼쪽 오른쪽을 세는 경우가 많은데, 얘는 약간 다른 느낌이지만 비슷하게 해주면 된다.
V[x]를 값이 x인 인덱스들을 오름차순으로 정렬한 배열이라고 하자. 그러면 V[x][i-1]과 V[x][i] 사이에는 x가 아닌 다른 값이 존재할 것이다. 따라서 쌍을 (x, (V[x][i-1]~V[x][i] 사이 값), x)로 구성할 수 있으므로 (V[x][i-1] 앞에 있는 x의 개수) * (V[x][i] 뒤에 있는 x의 개수) * (V[x][i-1] ~ V[x][i] 사이에 있는 수 개수) = (V[x].size() - i) * i * (V[x][i] - V[x][i-1]-1)이다. 이 값들을 모두 더하면 된다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
vector<ll> v[303030];
int main(){
fast;
cin>>n;
for(int i = 1 ; i <= n ; i++){
ll a; cin>>a;
v[a].push_back(i);
}
ll ans = 0;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j < v[i].size() ; j++){
ans += (v[i][j] - v[i][j-1] - 1) * j * (v[i].size()-j);
}
}
cout<<ans;
}upsolving
F (23:19 ~)
처음에 dp[l][r][j]로 접근해서 현재 l+1~r-1까지의 보물은 얻었고, k는 j~j+1 사이의 어떤 값일 때 가능한 k 범위(부등식) 꼴로 나타내서 부등식을 조합하려 했으나, 부등식 개수가 2개씩 늘어나서 조합하는데 O(N)이 걸려 O(N^4)으로 불가능하다는 사실을 깨달았다. (사실 구현이 매우매우 귀찮아서 포기했다.)
공식 풀이는 다음과 같다.
k는 답으로 가능한데 k+1은 답으로 불가능하거나, k는 답으로 불가능한데 k+1은 답으로 가능한 구간(즉, 정답이 바뀌는 구간)의 개수는 O(N^2)이다.
증명은 주어진 부등식을 풀면, 부등식의 해가 \( k = X_{i} + L_{j} \)와 \(k = X_{i} - L_{j} - 1 \) 로 나온다. 따라서 서로 다른 k의 개수는 O(N^2)개이다.
이제 저러한 k를 모아놓은 배열 v를 고려하자. v를 오름차순으로 정렬했을 때, \( v_{i} \)에서 모든 보물을 얻을 수 있으면 \(v_{i-1}+1\) ~ \( v_{i} \) 사이의 어떤 x에 대해서도 보물을 얻을 수 있다. 왜냐하면 위에서 말했듯이 k는 정답이 바뀌는 구간인데, 그 사이에 있는 구간은 반드시 같은 정답을 가지므로 그 중 하나에서만 확인하면 되기 때문이다. (따라서 \( v_{i} \)가 아니라 \( v_{i-1}+1 \) 에서 확인해도 AC가 나온다.)
따라서 \( v_{i} \)에서 모든 보물을 얻을 수 있으면 \( v_{i} - v_{i-1} \) 만큼 답을 더하면 된다. 시간복잡도는 O(N^2)개의 v 원소에 대해서 보물을 얻는게 가능한지 O(NlogN)에 확인하므로 O(N^3logN)이다. 가능한지 O(N)에 확인하면 O(N^3)도 가능하다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
ll X[202];
ll L[202];
bool chk(ll x){
vector<ll> v;
for(int i = 0 ; i < n ; i++)v.push_back(abs(x-X[i+1]));
sort(all(v));
for(int i = 0 ; i < n ; i++){
if(L[i+1]<v[i])return 0;
}
return 1;
}
int main(){
fast;
cin>>n;
for(int i = 1 ; i <= n ; i++)cin>>X[i];
for(int i = 1 ; i <= n ; i++)cin>>L[i];
vector<ll> v;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)v.push_back(X[i]+L[j]), v.push_back(X[i]-L[j]-1);
}
sort(all(v));
ll ans = 0;
for(int i = 1 ; i < v.size() ; i++)if(chk(v[i]))ans += v[i]-v[i-1];
cout<<ans;
}
G
플로우라고 한다(???).
max flow가 2로 매우 작아서 그래프에 정점, 간선이 많아도 금방 돈다. 플로우를 제대로 하지도 않았지만 이런데서 쓸수도 있다는 걸 알아둬야겠다.
잡담)F같은 문제들은 어떤 발상을 해야하는지 모르겠다. 풀이는 분명 알겠는데, 저런 생각을 어떻게 하는건지 궁금하다. 그냥 부등식 건드리다보니 나온걸까?
