타일 밟기
좋은 문제다. 요약하자면 배열에 존재하는 각 등차수열들의 원소의 합 중 최대를 구하는 것이다.
$N\le 3000$이고 원소들은 $10^6$ 이하이다.
풀이 & 코드
Solution 1
더보기
DP + 이진탐색
#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define Mup(x,y) x = max(x,y)
const int N = 3003;
int n, a[N];
ll dp[N][N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
REP(i,1,n) cin >> a[i];
ll answer = 0;
REP(i,1,n) REP(j,1,i-1) {
dp[i][j] = a[i]+a[j];
int k = lower_bound(a+1,a+j,2*a[j]-a[i])-a;
if (a[i]+a[k] != 2*a[j]) continue;
Mup(dp[i][j],dp[j][k]+a[i]);
Mup(answer,dp[j][k]+a[i]);
}
cout << answer;
}
Solution 2
더보기
조화 수열의 합
#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
const int N = 3003, X = 1000003;
int n;
bool e[X];
ll x, a[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
REP(i,1,n) cin >> a[i], e[a[i]] = 1;
REP(i,1,n) REP(j,i+1,n) {
ll d = a[j]-a[i], v = a[i], w = 0, c = 0;
while (v < X and e[v]) w += v, ++c, v += d;
if (c > 2) x = max(x,w);
}
cout << x;
}
Perimeter
미루다가 4월 24일에 마저 작성중인데... 무슨 문제였는지 기억이 안 난다 ㅋㅋ
대충 전체를 감싸는 둘레를 구하는 거였던 것 같다.
특징은 Data structure를 잘 활용할 수 있어야 한다는 것이다.
풀이
더보기
hay 주변만 탐색하도록 짜면 시간 안에 돌아갈 것이므로, hay를 set에 넣고 잘 확인하면서 dfs를 해주면 된다.
코드
더보기
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
const int N = 5e4+3;
int n, answer;
set<ii> hay;
map<ii,bool> visited;
bool alone(int r, int c) {
REP(i,-1,+1) REP(j,-1,+1) {
if (hay.count({r+i,c+j})) return false;
}
return true;
}
void dfs(int r, int c) {
if (hay.count({r,c})) answer++;
else {
if (alone(r,c) or visited[{r,c}]) return;
visited[{r,c}] = true;
dfs(r-1,c),dfs(r+1,c),dfs(r,c-1),dfs(r,c+1);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
REP(i,1,n) {
int r, c; cin >> r >> c;
hay.insert({r,c});
}
dfs(hay.begin()->first-1,hay.begin()->second);
cout << answer;
}
Flowerpot
그냥 쉽고 왜 플래인지 납득 못하겠다. 골3 정도가 적당하다고 생각한다.
풀이 & 코드
더보기
슬라이딩 윈도우 + 멀티셋으로 풀린다.
#include <bits/stdc++.h>
using namespace std;
const int X = 1e6+3;
int n, d;
multiset<int> ms;
vector<int> drops[X];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> d;
for (int i = 1; i <= n; ++i) {
int x, y; cin >> x >> y;
drops[x].push_back(y);
}
int a = 0, b = -1, answer = 1e9;
while (b < X-1) {
if (not empty(ms) and *rbegin(ms) - *begin(ms) >= d) {
answer = min(answer,b-a);
for (auto drop : drops[a]) ms.erase(ms.find(drop));
a++;
} else {
b++;
for (auto drop : drops[b]) ms.insert(drop);
}
}
if (answer == 1e9) cout << -1;
else cout << answer;
}
이항 계수 4
풀이 & 코드..
더보기
윌슨 정리를 변형하면 된다.
소수 $p$를 인수로 갖는 수들만 묶어내는 과정을 재귀적으로 하면 된다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, k, p;
template <typename...Ts> ll mul(Ts... xs) {return (ll(xs)*...)%p;}
void Mul(ll &x, ll y) {x = mul(x,y);}
ll my_pow(ll x, ll e) {
ll r = 1;
while (e > 0) {
if (e%2) r = mul(r,x);
e /= 2, x = mul(x,x);
}
return r;
}
ll inv(ll x) {return my_pow(x,p-2);}
ll fac[2000] {1};
pair<ll,ll> fact(ll n) {
ll f = 1, e = 0;
while (n > 0) {
if ((n/p)%2) Mul(f,p-1);
e += n/p;
if (n%p) Mul(f,fac[n%p]);
n /= p;
}
return {f,e};
}
ll C(ll n, ll k) {
ll F = 1, E = 0, f, e;
tie(f,e) = fact(n); Mul(F,f), E += e;
tie(f,e) = fact(k); Mul(F,inv(f)), E -= e;
tie(f,e) = fact(n-k); Mul(F,inv(f)), E -= e;
return E > 0 ? F : 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> p;
for (int i = 1; i < p; ++i)
fac[i] = mul(fac[i-1],i);
cout << C(n,k);
}
'PS 기록들' 카테고리의 다른 글
Codeforces 블루 달성 (2) | 2022.04.24 |
---|---|
Educational Codeforces Round 126 (Div. 2) (0) | 2022.04.10 |
CSA OI 세트 (0) | 2022.03.03 |
2022년 2월 PS일지 ★ (BOJ 7040, 12630, 7915) (2) | 2022.02.28 |
Codeforces Round #750 (Div. 2) (0) | 2021.10.26 |