티스토리 뷰
KCPC가 모든 문제를 다 풀면 배경을 준다는 소식을 들어서, 실제로 해 보기로 했다.
아마 이 시리즈 역사상 가장 많은 문제가 등장할 것 같다. 문제들은 푼 순서대로 작성했다.
1A/2A. NEMODEMIC
그냥 구현하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
char board[55][55];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> board[i]+1;
int wall = 0;
int one_virus = 0;
int all_virus = 0;
int vaccine = 0;
int start = 0, exit = 0;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
char c = board[i][j];
switch(c){
case '#':
wall++;
break;
case 'U': case 'D': case 'L': case 'R':
one_virus++;
break;
case 'A':
all_virus++;
break;
case 'V':
vaccine++;
break;
case 'S':
start++;
break;
case 'E':
exit++;
break;
}
}
if(start != 1 || exit != 1){
cout << -1;
return 0;
}
bool p1 = wall <= 1 && one_virus <= 1 && !all_virus && !vaccine;
bool p2 = !all_virus && !vaccine;
bool p3 = !all_virus;
bool p4 = true;
if(p1) cout << 1;
else if(p2) cout << 2;
else if(p3) cout << 3;
else if(p4) cout << 4;
}PA. $2026$
Matkor 끝낸다더니, 이제 예비소집을 Matkor로 만들고 있다. kcpc를 주최하는 동아리와는 서로 다른 동아리로 알고 있었는데, 조금 신기하다.
문제 자체는 그냥 $10\dots1$ 꼴 수를 제곱한 뒤 $1905$를 더해 출력하면 된다.
n = int(input()) // 2 + 1
s = ''.join(('1' if i==0 or i==n-1 else '0') for i in range(n))
v = int(s)
print(v*v + 1905)PB. $\exists99$
이건 아예 대놓고 수학 문제를 들고 왔다. 솔직히 이런 문제를 대회에 내는 걸 좋아하진 않는다. 뭔가 재미있는 성질이 있는 문제라면 모를까, 이건 그냥 중학교 수학 숙제로 나올 만한 문제라서 조금 별로...
출력 형식 면에서도 굉장히 불친절하다. 보통 이런 문제들은 답이 유리수임이 보장된다는 조건을 달아놓거나 하는데, matkor는 많은 문제들에서 입력이 유리수면 어떻게 출력하고, 무리수면 어떻게 출력하고, 답이 없으면 어떻게 출력하라는 등 많은 부가조건을 달아놓는 것 같다. 개인적으로는 이러한 부분이 문제의 난이도를 유의미하게 올리지 않으며 불친절함만 더한다고 생각하기 때문에, 좋은 방식이라고 생각하지 않는다.
문제의 풀이는 그냥 좌표평면 위에서 열심히 계산하면 된다. 그냥 수학 문제가 따로 없다. 다만 $a=b$일 때의 예외처리에 조심해 주자. 이걸 놓쳐서 한 번 틀렸다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> a >> b;
if(a<b) swap(a, b);
if(a==b){
cout << "INF";
return 0;
}
ll p = b*b, q = a-b;
ll g = __gcd(p, q);
p /= g, q /= g;
cout << p << ' ' << q;
}PC. $39420$
정상적인 PS 문제이다. 가능한 최대 직사각형 크기가 $10$이라는 걸 이용해 브루트포스 하면 된다. 나는 비트마스킹을 써서 set 판별을 빠르게 했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int A[1002][1002];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> m;
for(int i=1; i<=n; i++){
string s;
cin >> s;
for(int j=1; j<=m; j++){
A[i][j] = 1 << (s[j-1] - '0');
}
}
int ans = 0;
for(int r=1; r<=n; r++) for(int c=1; c<=m; c++){
for(int a=1; a<=10 && r+a-1<=n; a++) for(int b=1; a*b<=10 && c+b-1<=m; b++){
int v = 0;
for(int i=0; i<a; i++) for(int j=0; j<b; j++) v |= A[r+i][c+j];
if(__builtin_popcount(v) == a*b) ans++;
}
}
cout << ans;
}PD. $02493$
...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << 1 << ' ' << n << ' ' << 10 << ' ' << 10 << '\n';
}
}PE. $-02493$
주기성을 이용해야 한다. 문제의 주기성 때문에 직사각형의 가로/세로 사이즈가 고정되면 좋은 직사각형인지 아닌지의 여부도 고정된다. 따라서 그냥 $10$ 이하의 가능한 직사각형을 하나 잡아서 다 해 보고, 좋은 직사각형이라면 그 개수만큼 답에 더해 주면 된다.
전 문제부터 계속 의문이 든 부분인데 왜 테스트케이스별 답을 한 줄에 출력시키는지 잘 모르겠다. 줄마다 하나씩 출력하는 쪽이 조금 더 일반적인 선택인 것 같은데, 이렇게 해 놓으니 로컬에서 실행시켰을 때 답을 확인하기가 조금 불편하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll n, m, a, b;
ll arr[12][12];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> t;
while(t--){
cin >> n >> m >> a >> b;
for(int i=1; i<=10 && i<=n; i++) for(int j=1; j<=10 && j<=m; j++){
arr[i][j] = 1 << ((a*i + b*j) % 10);
}
ll ans = 0;
for(int i=1; i<=10 && i<=n; i++) for(int j=1; i*j<=10 && j<=m; j++){
ll v = 0;
for(int x=1; x<=i; x++) for(int y=1; y<=j; y++) v |= arr[x][y];
if(__builtin_popcount(v) == i*j) ans += (n-i+1) * (m-j+1);
}
cout << ans << ' ';
}
}2B. 동우의 생일은?
각 방향을 반반씩 놓는 게 최적이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int a, b, n;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> t;
while(t--){
cin >> a >> b >> n;
ll p = n/2, q = n-p;
ll r = a*p+b*q, s = a*q+b*p;
cout << r*s << '\n';
}
}1H. 쿼리와 구간
자명한 constructive 문제이다. $n$, $m$을 잘못 써서 한 번 틀렸다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int A[100002], good, bad;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> A[i];
if(A[i] == 1) good++;
else bad++;
}
if(n >= 3){
cout << 1 << '\n';
for(int i=1; i<=n; i++){
int l, r;
if(i==1) l = 0, r = 2;
else if(i==2) l=1, r=3;
else if(i==3) l=4, r=6;
else l=100, r=102;
cout << 1 << ' ' << l << ' ' << r << '\n';
}
for(int i=1; i<=m; i++){
if(A[i] == 1) cout << "2 1 2\n";
else cout << "2 2 3\n";
}
}
else if(good && bad){
cout << -1;
}
else if(good){
cout << 1 << '\n';
cout << "1 0 2\n";
cout << "1 1 3\n";
for(int i=1; i<=m; i++) cout << "2 1 2\n";
}
else{
cout << 1 << '\n';
cout << "1 0 2\n";
cout << "1 4 6\n";
for(int i=1; i<=m; i++) cout << "2 1 2\n";
}
}2D. 주니어 개발자 동우의 직행 취업일기
개인적으로 무거운 정점에 대한 조건은 출력 형식 칸이 아니라 문제 본문에 쓰여 있어야 한다고 생각한다.
트리 형식을 제한해두고 생각하면 쉽다. $T(l, r)$을 간선 $(p, q)$가 있고, $p$에 추가적으로 이웃 리프 $l$개, $q$에 추가적으로 이웃 리프 $r$개가 있는 그래프라고 생각하자. $N \le M - 3$ ($M$은 정점 개수 최댓값)이면 $T(n, 1)$을 이용하고, 아니면 $lr = N$인 적당한 $(l, r)$을 잡아 $T(l, r)$을 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void gen(int l, int r){
cout << l+r+2 << '\n';
int p = l+r+1, q = l+r+2;
for(int i=1; i<=l; i++) cout << i << ' ' << p << '\n';
for(int i=1; i<=r; i++) cout << i+l << ' ' << q << '\n';
cout << p << ' ' << q << '\n';
exit(0);
}
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
int n;
cin >> n;
if(n <= 999'997) gen(n, 1);
else{
for(int i=2; i<n; i++) if(n%i == 0){
gen(n/i, i);
break;
}
}
}1D. KCPC 스티커 만들기
문제를 있는 그대로 생각하면 상당히 생각하기 싫어진다. 많은 경우 K, C, P의 문자가 어떻게 생겼는지는 상관없을 거라고 추측할 수 있다.
P는 대부분 다른 문자에 그냥 붙이면 되는 거라 크게 신경쓸 필요가 없다. C는 두 개끼리 이을 수도 있고, P나 C가 하나 있으면 그 옆에 붙일 수도 있다. 여기서 $K=0$인 경우 답을 알 수 있는데, $C + P = 1$이면 불가능, 나머지면 가능이다.
$K$가 있을 때가 문제이다. 일단 조금 찾기 쉬운 것들을 생각해보면,
- $K$ 여러 개는 일렬로 붙일 수 있다. 이러면 $K$ 하나로 생각할 수도 있다.
- $K$ 한 개가 있고, $C$가 하나 이상 있으며, $C$나 $P$가 하나 이상 추가로 있다면 이들을 모두 하나로 붙일 수 있다.
여기에서 $K \ge 1$, $C \ge 1$, $C + P \ge 2$인 경우 가능함을 알 수 있다.
이제 $K \ge 1$이고 $C = 0$이거나 $K \ge 1$이고 $C = 1$, $P = 0$인 경우를 살펴봐야 한다.
$C = 0$인 경우
$P \ge 3$이면 $K$의 개수에 상관없이 항상 가능하다. 맨 왼쪽 $K$의 왼쪽 위 / 오른쪽 아래에 $P$를 하나씩 붙이고, 맨 오른쪽 $K$ 오른쪽에 $P$를 붙인다.
$K \le 2$이면 $P \ge 2$개로도 가능하다. 위/아래에 $P$를 한 개씩 붙이면 된다.
$K = 3$, $C = 0$, $P = 2$인 경우에도 잘 붙이면 가능함을 알 수 있다.
결론적으로 $P \ge 2$면 항상 가능하다.
이제 $P = 0, P = 1$인 경우가 남아 있다. $P = 0$이라는 건 $K$밖에 없다는 뜻이다. $K \le 3$이라는 조건이 있으므로 이때 불가능함을 짐작할 수 있다. $P = 1$인 경우 $K = 1, 2$일 때는 불가능하다는 확신이 드는데, $(K, C, P) = (3, 0, 1)$일 때 조금 애매하다. 일단 보류한다.
- $P \ge 2$면 항상 가능
- $P = 0$이면 항상 불가능
- $P = 1$일 때, $K \le 2$면 불가능. $K = 3$이면 보류.
$C = 1$, $P = 0$인 경우
$K = 0, 1, 2, 3$인 네 가지 케이스만 보면 된다.
- $K = 0$: 당연히 불가능하다.
- $K = 1$: K를 C로 감싸는 게 가능하다. 그래서 가능하다.
- $K = 2, 3$: 아무리 해봐도 잘 안 됐다. 그래서 안 된다고 추측했다.
이대로 추측하고 냈더니 맞았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int k, c, p;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> t;
while(t--){
cin >> k >> c >> p;
int able = -1;
if(k == 0){
if(c + p == 1) able = 0;
else able = 1;
}
else if(k >= 1 && c >= 1 && c+p >= 2) able = 1;
else if(c == 0){
if(p >= 2) able = 1;
else if(p==0) able = 0;
else if(k <= 2) able = 0;
else able = 0; // 불확실
}
else if(c == 1 && p == 0){
if(k == 0) able = 0;
else if(k == 1) able = 1;
else able = 0; // 불확실
}
assert(able != -1);
cout << (able ? 'Y' : 'N') << '\n';
}
}2E. ProblemSolving이 아니에요
쉬운 DP 문제다.
출력 형식의 "불가능하면 -1을 대신 출력한다" 를 읽지 못해 한 번 틀렸다. 개인적으로 이 조건이 왜 있는지 이해할 수 없다. TC 중에서 경우의 수가 998 244 353의 배수인데 가능한 케이스가 있는 것도 아니었다. (그냥 mod가 0이면 -1을 출력하도록 하니 맞았다.) 쓸데없이 혼란만 늘리도록 되어 있는 세팅인 것 같아 굉장히 불쾌하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int t;
ll DP[5002][5002];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
int N = 5000;
DP[0][0] = 1;
for(int i=1; i<=N; i++){
for(int j=0; j<=i; j++){
if(i>=2 && j>=1) DP[i][j] = DP[i-2][j-1];
DP[i][j] = (DP[i][j] + DP[i-1][j+1]) % MOD;
}
}
cin >> t;
while(t--){
int n;
cin >> n;
ll ans = 0;
for(int i=0; i<=n; i++) ans += DP[n][i];
ans %= MOD;
cout << (ans == 0 ? -1 : ans) << '\n';
}
}2H. unique(str)=KCPC
간만에 그럴듯한 문제가 보인다.
일단 $C$를 앞뒤로 몇 개씩 배치하냐가 문제의 핵심이다. 이를 위해 $C$를 앞/뒤로 적당히 나눈 뒤 inversion이 최소가 되는 지점을 찾아야 할 것이다.
생각 없이 삼분 탐색을 쓰고 싶지만 $N = 10^6$인 게 조금 걸린다. 다행히 이 문제는 가능한 수가 $0, 1, 2, 3$의 네 개뿐으로 생각할 수 있어 inversion의 갱신이 어렵지 않다. $O(n)$에 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char str[1'000'005];
int A[1'000'005];
int cnt2[1'000'005];
ll ans, inv;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> (str + 1);
n = strlen(str+1);
int cnt[4] = {0};
for(int i=1; i<=n; i++){
if(str[i] == 'K') A[i] = 0;
else if(str[i] == 'C') A[i] = (!cnt[1] ? 1 : 3);
else A[i] = 2;
cnt[A[i]]++;
cnt2[i] = cnt[2];
for(int j=A[i]+1; j<4; j++) inv += cnt[j];
}
ans = inv;
vector<int> change;
for(int i=1; i<=n; i++) if(A[i] == 3) change.push_back(i);
change.pop_back();
for(int x: change){
inv -= cnt2[n] - cnt2[x];
inv += cnt2[x];
ans = min(ans, inv);
}
cout << ans;
}2C. 포켓몬 마스터 이민재
이런 류의 문제는 보통 지문을 이해하는 게 문제를 푸는 것보다 어려운 것 같다.
일단 목표는 $hrs$를 최대한 키워야 한다. 식을 보면 $hrs$가 $255$보다 커지면 별 의미가 없는 것 같다. $h$는 최대 $1$까지 커질 수 있고, $s$는 최대 $2.5$까지 커질 수 있다. $r$의 최댓값은 $765$이다. $hrs$의 최댓값이 $255$다 같은 일은 없었고, 조금 신경쓸 게 많아졌다.
일단 최종 $s$ 값을 정해 두면 $h$를 어디까지 떨어뜨려야 하는지 알 수 있다. 그럼 F를 해야 하는 횟수를 알 수 있다. $s$를 $1.5$로 만들려면 G를 한 번 해야 하고, $2.5$로 만들려면 Y를 한 번 해야 한다. 그런데 Y를 하고 나서 뭔가를 한 턴 해야 효과가 있다. 이런 것까지 다 계산해서 최적을 찾아 주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(ll r, ll H, ll f){
string ret (1500, '1');
ll MX = min((3*H-2)*r*5, 1530*H);
{ // 2
ll s = 2;
ll h = H;
while(h && (3*H-2*h) * r * s < MX) h--;
if(h){
ll c = (H - h + f - 1) / f;
string sol (c, 'F');
if(ret.size() > sol.size()) ret = sol;
}
}
{ // 3
ll s = 3;
ll h = H;
while(h && (3*H-2*h) * r * s < MX) h--;
if(h){
ll c = (H - h + f - 1) / f;
string sol (c, 'F');
sol = "G" + sol;
if(ret.size() > sol.size()) ret = sol;
}
}
{ // 5
ll s = 5;
ll h = H;
while(h && (3*H-2*h) * r * s < MX) h--;
if(h){
ll c = (H - h + f - 1) / f;
string sol (c, 'F');
sol = "Y" + sol;
if(sol.back() == 'Y') sol += "S";
if(ret.size() > sol.size()) ret = sol;
}
}
cout << ret << "C\n";
}
int t;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> t;
while(t--){
int r, h, f;
cin >> r >> h >> f;
solve(r, h, f);
}
}1F/2F. 안 보고 정렬
결국 나올 수 있는 배열의 가짓수를 구하는 문제이다. 최댓값이 $L$이고 최댓값이 $R$인 길이 $n$의 배열 가짓수를 구하면 된다.
이 개수는 포함 배제의 원리를 사용하면 $k^n - 2(k-1)^n + (k-2)^n$임을 쉽게 알 수 있다. 여기서 $k = R-L+1$이다. 단 $k$가 작은 경우의 예외 처리를 조심하자.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998'244'353;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
ll rmpow(ll x, ll y){
if(x<=0) return 0;
return mpow(x%MOD, y);
}
int t;
ll n, l, r;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> t;
while(t--){
cin >> n >> l >> r;
ll k = r-l+1;
ll ans = rmpow(k, n) - rmpow(k-1, n) * 2 + rmpow(k-2, n);
ans = (ans % MOD + MOD * 5) % MOD;
cout << ans << '\n';
}
}2G. 점 세 개 돌리기
주어지는 연산들은 모두 선형변환이므로 행렬로 나타낼 수 있다. 세그먼트 트리를 이용해 구현했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Matrix{
char m[3][3];
Matrix(){
m[0][0] = m[1][1] = m[2][2] = 1;
m[0][1] = m[0][2] = m[1][0] = m[1][2] = m[2][0] = m[2][1] = 0;
}
Matrix(char a, char b, char c, char d, char e, char f, char g, char h, char i){
m[0][0] = a, m[0][1] = b, m[0][2] = c;
m[1][0] = d, m[1][1] = e, m[1][2] = f;
m[2][0] = g, m[2][1] = h, m[2][2] = i;
}
Matrix(string s){
m[0][0] = m[0][1] = m[0][2] = m[1][0] = m[1][1] = m[1][2] = m[2][0] = m[2][1] = m[2][2] = 0;
if(s == "X") m[0][0] = 1, m[1][2] = -1, m[2][1] = 1;
if(s == "Y") m[0][2] = 1, m[1][1] = 1, m[2][0] = -1;
if(s == "Z") m[0][1] = -1, m[1][0] = 1, m[2][2] = 1;
if(s == "XX") m[0][0] = 1, m[1][1] = -1, m[2][2] = -1;
if(s == "YY") m[0][0] = -1, m[1][1] = 1, m[2][2] = -1;
if(s == "ZZ") m[0][0] = -1, m[1][1] = -1, m[2][2] = 1;
if(s == "XY" || s == "YX") m[0][0] = 1, m[1][1] = 1, m[2][2] = -1;
if(s == "YZ" || s == "ZY") m[0][0] = -1, m[1][1] = 1, m[2][2] = 1;
if(s == "ZX" || s == "XZ") m[0][0] = 1, m[1][1] = -1, m[2][2] = 1;
}
Matrix operator*(const Matrix &r)const{
Matrix ret;
ret.m[0][0] = ret.m[1][1] = ret.m[2][2] = 0;
for(int i=0; i<3; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++)
ret.m[i][j] += m[i][k] * r.m[k][j];
return ret;
}
};
struct segTree{
Matrix mat[1<<18];
void init(int i, int l, int r, string *str){
if(l==r){
mat[i] = Matrix(str[l]);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, str);
init(i*2+1, m+1, r, str);
mat[i] = mat[i*2+1] * mat[i*2];
}
Matrix query(int i, int l, int r, int s, int e){
if(r<s || e<l) return Matrix();
if(s<=l && r<=e) return mat[i];
int m = (l+r)>>1;
return query(i*2+1, m+1, r, s, e) * query(i*2, l, m, s, e);
}
} tree;
int n, q;
string strs[100005];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n;
for(int i=1; i<=n; i++) cin >> strs[i];
cin >> q;
tree.init(1, 1, n, strs);
while(q--){
int l, r;
cin >> l >> r;
Matrix p = tree.query(1, 1, n, l, r);
for(int i=0; i<3; i++){
for(int j=0; j<3; j++) cout << (int)p.m[j][i] << ' ';
cout << '\n';
}
}
}2I. 명사수
세그먼트 트리를 써서 시뮬레이션하면 쉬운 문제이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
int c;
int S[1'000'005];
ll ans;
struct segTree{
ll tree[1<<21], lazy[1<<21];
void init(int i, int l, int r, int *S){
if(l==r){
tree[i] = S[l] + max(c - l, 0);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, S);
init(i*2+1, m+1, r, S);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
void propagate(int i, int l, int r){
tree[i] += lazy[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return LLONG_MIN;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> q >> c;
for(int i=1; i<=n; i++) cin >> S[i];
tree.init(1, 1, n, S);
ans = 0;
int pnt = 1;
while(q--){
ans += tree.query(1, 1, n, 1, n);
// cout << tree.query(1, 1, n, 1, n) << '\n';
if(c < n){
tree.update(1, 1, n, pnt, pnt, -(c-1));
tree.update(1, 1, n, pnt+1, pnt+c-1, 1);
tree.update(1, 1, n, pnt+1-n, pnt+c-1-n, 1);
}
else{
tree.update(1, 1, n, pnt, pnt, -(n-1));
tree.update(1, 1, n, pnt+1, n, 1);
tree.update(1, 1, n, 1, pnt-1, 1);
}
pnt = pnt % n + 1;
}
cout << ans;
}1J/2J. # 세진아, 향기가 세진 꽃밭에서, 지는 꽃잎을 세진 않으려 해
케이스를 나눠서 관찰해야 한다. 대부분의 경우 C는 가로 또는 세로로 이어지는 경향성이 있고, 남은 칸에서 나머지 두 글자를 고르는 경우의 수가 있다. C가 홀수번째 or 짝수번째 열/행에서만 나타나는 경우의 수, 행/열 단위로 C/C가 아닌 문자가 교대하는 경우의 수, 그리고 C가 체스판 기준 검은색/흰색 칸에만 나타나는 경우의 수 등으로 5가지 케이스를 고려하면
- $A = 2^{\lfloor n/2 \rfloor} + 2^{\lceil n/2 \rceil}$
- $B = 2^{\lfloor m/2 \rfloor} + 2^{\lceil m/2 \rceil}$
- $C = (2^n - 2) \times 2$
- $D = (2^m - 2) \times 2$
를 얻고, $C$와 $D$에서 $4$가지 경우가 겹쳐서 답이 $A+B+C+D-4$가 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998'244'353;
int t;
int n, m;
ll p2[100005];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
p2[0] = 1;
for(int i=1; i<=100'000; i++) p2[i] = p2[i-1] * 2 % MOD;
cin >> t;
while(t--){
cin >> n >> m;
ll A = p2[n/2] + p2[(n+1)/2] + p2[m/2] + p2[(m+1)/2];
ll B = (p2[n] - 2 + MOD) * 2 + (p2[m] - 2 + MOD) * 2;
ll C = MOD - 4;
ll ANS = (A+B+C) % MOD;
cout << ANS << '\n';
}
}1E. 점 세게 돌리기
여기까지 16문제를 풀었는데, 슬슬 날이 저물고 다이아 스트릭을 잇고 싶어서 다이아를 하나 풀기로 했다.
그냥 보면 세그로 합치면 되는 거 아닌가 싶긴 한데, 상태의 개수가 만만치 않다. 일단 단순히 저 변환의 가짓수만 봐도 $2^3 \times 3! = 48$가지이다. 그런데 심지어 한 글자/두 글자로 쪼개는 가짓수들이 있어서 각 노드당 $48 \times 4^2$가지의 상태가 가능한지 아닌지 확인을 해 줘야 한다. 저게 768인데, 아무래도 $768$가지 상태를 빠르게 합쳐주는 게 가능할까 싶다.
아무래도 이건 좀 힘들 것 같으니, 다른 방식을 생각해 보자. 업데이트가 없으니, 세그먼트 대신 분할 정복으로 비슷한 걸 시도해볼 수 있다. 분할 정복으로 $[l, r]$에 대해 적당한 $m$으로 나누고, $m$ 왼쪽/오른쪽에서 비슷한 걸 시도해보면 $m$에 가까운 쪽 두 개를 쓸 것인가 말 것인가로 케이스를 잘 나누는 식으로 하면 상태 $48$개 정도만 관리해도 문제가 없다. 결국 $O((N+Q) \log N)$ 정도에 풀 수 있지만, 상수가 매우 크다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx) {}
};
struct Matrix{
char m[3][3];
Matrix(){
m[0][0] = m[1][1] = m[2][2] = 1;
m[0][1] = m[0][2] = m[1][0] = m[1][2] = m[2][0] = m[2][1] = 0;
}
Matrix(char a, char b, char c, char d, char e, char f, char g, char h, char i){
m[0][0] = a, m[0][1] = b, m[0][2] = c;
m[1][0] = d, m[1][1] = e, m[1][2] = f;
m[2][0] = g, m[2][1] = h, m[2][2] = i;
}
Matrix(string s){
m[0][0] = m[0][1] = m[0][2] = m[1][0] = m[1][1] = m[1][2] = m[2][0] = m[2][1] = m[2][2] = 0;
if(s == "X") m[0][0] = 1, m[1][2] = -1, m[2][1] = 1;
if(s == "Y") m[0][2] = 1, m[1][1] = 1, m[2][0] = -1;
if(s == "Z") m[0][1] = -1, m[1][0] = 1, m[2][2] = 1;
if(s == "XX") m[0][0] = 1, m[1][1] = -1, m[2][2] = -1;
if(s == "YY") m[0][0] = -1, m[1][1] = 1, m[2][2] = -1;
if(s == "ZZ") m[0][0] = -1, m[1][1] = -1, m[2][2] = 1;
if(s == "XY" || s == "YX") m[0][0] = 1, m[1][1] = 1, m[2][2] = -1;
if(s == "YZ" || s == "ZY") m[0][0] = -1, m[1][1] = 1, m[2][2] = 1;
if(s == "ZX" || s == "XZ") m[0][0] = 1, m[1][1] = -1, m[2][2] = 1;
}
Matrix operator*(const Matrix &r)const{
Matrix ret;
ret.m[0][0] = ret.m[1][1] = ret.m[2][2] = 0;
for(int i=0; i<3; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++)
ret.m[i][j] += m[i][k] * r.m[k][j];
return ret;
}
string to_string(){
return string(m[0], 3) + string(m[1], 3) + string(m[2], 3);
}
} possible_matrices[48];
map<string, int> matrix_id;
void generateAllMatrix(){
int icnt = 0;
for(int i=0; i<8; i++){
vector<int> ord = {0, 1, 2};
do {
Matrix tmp (0, 0, 0, 0, 0, 0, 0, 0, 0);
for(int a=0; a<3; a++){
tmp.m[a][ord[a]] = ((i>>a)&1) ? -1 : 1;
}
possible_matrices[icnt] = tmp;
matrix_id[tmp.to_string()] = icnt;
icnt++;
} while(next_permutation(ord.begin(), ord.end()));
}
}
int mul[48][48], mul_ex[48][12], ex_mul[12][48];
int str_id[12];
char example_strings[12][3] = {
"X", "XX", "XY", "XZ",
"Y", "YX", "YY", "YZ",
"Z", "ZX", "ZY", "ZZ"
};
void setDatabase(){
for(int i=0; i<48; i++){
for(int j=0; j<48; j++){
Matrix prod = possible_matrices[i] * possible_matrices[j];
string s = prod.to_string();
mul[i][j] = matrix_id[s];
}
}
for(int i=0; i<12; i++){
str_id[i] = matrix_id[Matrix(string(example_strings[i])).to_string()];
}
for(int i=0; i<48; i++){
for(int j=0; j<12; j++){
mul_ex[i][j] = mul[i][str_id[j]];
ex_mul[j][i] = mul[str_id[j]][i];
}
}
}
void makeData(){
generateAllMatrix();
setDatabase();
}
int X, Y, Z;
int n, q;
char str[100002];
int ans[100002];
ll DPL[100002], DPR[100002];
ll DPLE[100002], DPRE[100002];
void initDP(ll *dp, int l, int r, int where){
l = max(l, 0), r = min(r, n+1);
fill(dp+l, dp+r+1, 0LL);
dp[where] = 1;
}
inline int getID(char c){
return (c - 'X') * 4;
}
inline int getID(char c, char d){
return (c - 'X') * 4 + (d - 'X' + 1);
}
void updateDP(ll *dp, int x, int prv, int prv2, bool ord){
ll v = dp[prv], v2 = (0 <= prv2 && prv2 <= n+1 ? dp[prv2] : 0);
ll newV = 0;
if(ord == 0){
for(int i=0; i<48; i++){
if(!((v>>i)&1)) continue;
newV |= (1LL << mul_ex[i][getID(str[x])]);
}
if(v2) for(int i=0; i<48; i++){
if(!((v2>>i)&1)) continue;
newV |= (1LL << mul_ex[i][getID(str[x], str[prv])]);
}
}
else{
for(int i=0; i<48; i++){
if(!((v>>i)&1)) continue;
newV |= (1LL << ex_mul[getID(str[x])][i]);
}
if(v2) for(int i=0; i<48; i++){
if(!((v2>>i)&1)) continue;
newV |= (1LL << ex_mul[getID(str[prv], str[x])][i]);
}
}
dp[x] = newV;
}
unordered_set<int> possible;
inline int encode(int x, int y, int z){
return x*1000 + y*100 + z;
}
void solve(int l, int r, int m, vector<Query> &queries){
initDP(DPL, l-2, r+2, m+1);
initDP(DPR, l-2, r+2, m);
initDP(DPLE, l-2, r+2, m);
initDP(DPRE, l-2, r+2, m+1);
for(int i=m; i>=l; i--) updateDP(DPL, i, i+1, i+2, 0);
for(int i=m+1; i<=r; i++) updateDP(DPR, i, i-1, i-2, 1);
for(int i=m-1; i>=l; i--) updateDP(DPLE, i, i+1, i+2, 0);
for(int i=m+2; i<=r; i++) updateDP(DPRE, i, i-1, i-2, 1);
for(Query &p: queries){
ll l = DPL[p.l], r = DPR[p.r], le = DPLE[p.l], re = DPRE[p.r];
ll total = 0;
for(int a=0; a<48; a++){
if(!((l>>a)&1)) continue;
for(int b=0; b<48; b++){
if(!((r>>b)&1)) continue;
total |= (1LL << mul[b][a]);
}
}
int mid2 = getID(str[m], str[m+1]);
for(int a=0; a<48; a++){
if(!((le>>a)&1)) continue;
for(int b=0; b<48; b++){
if(!((re>>b)&1)) continue;
total |= (1LL << mul[b][ex_mul[mid2][a]]);
}
}
possible.clear();
for(int i=0; i<48; i++){
if((total>>i)&1){
Matrix &m = possible_matrices[i];
possible.insert(encode(
(int)m.m[0][0] * X + (int)m.m[0][1] * Y + (int)m.m[0][2] * Z,
(int)m.m[1][0] * X + (int)m.m[1][1] * Y + (int)m.m[1][2] * Z,
(int)m.m[2][0] * X + (int)m.m[2][1] * Y + (int)m.m[2][2] * Z
));
}
}
ans[p.idx] = possible.size();
}
}
void dnc(int l, int r, vector<Query> &queries){
if(l>r || queries.empty()) return;
if(l==r){
for(Query &p: queries){
ans[p.idx] = 1;
}
return;
}
int m = (l+r)>>1;
vector<Query> lqv, rqv, current;
for(Query &p: queries){
if(p.r <= m) lqv.push_back(p);
else if(p.l > m) rqv.push_back(p);
else current.push_back(p);
}
queries.clear();
queries.shrink_to_fit();
dnc(l, m, lqv);
dnc(m+1, r, rqv);
solve(l, r, m, current);
}
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
makeData();
cin >> X >> Y >> Z >> (str+1);
n = strlen(str+1);
cin >> q;
vector<Query> queries (q);
for(int i=0; i<q; i++){
cin >> queries[i].l >> queries[i].r;
queries[i].idx = i+1;
}
dnc(1, n, queries);
for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}여기까지 1일차에 풀었다. 2일차는 다이아 먼저 풀고 가기로 했다.
1I. Return Oriented Programming
SA/LCP를 쓰는 꽤 뻔한 유형의 문제이다.
일단 $t$의 모든 위치 $i$에 대해 $T_{[j, i]}$가 $S$의 부분문자열이 되는 최소 $j$를 구한다. 이건 LCP를 쓰면 된다.
이제 1과 2를 구해보자. 2가 더 쉽다. 2에서 중요한 관찰은 곱을 최대화하기 위해 사용하는 구간 길이의 최댓값이 $4$라는 사실이다. $4$ 이상의 구간을 쓴다면 2/3으로 나누는 게 더 낫기 때문이다. 다만, 2/2로 쪼개진 건 4로 합쳐줄 수 있으면 합쳐주는 게 최적이다. 이 부분을 조심해서 구현해야 한다.
1의 경우 이런 제한이 없어서 조금 더 어렵다. 먼저 최소 개수를 구해야 하는데 최소 개수는 그냥 세그 DP로 쉽게 된다. 이후 길이 곱의 로그 값이 아닌 그냥 곱을 최적화하는 문제로 바꾸면 CHT라는 사실을 알 수 있다. 그래서 CHT와 비슷한 방식으로 풀 수 있다. 그런데 문제는 부분문자열이 될 수 있는 범위 제한도 있어서 CHT로 짜기 많이 어렵다. 대신 dnc opt를 이용해서 짰더니 구현이 쉬웠고 정답을 받았다.
#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
typedef long long ll;
using namespace atcoder;
void input();
void makeMarker();
void solve1();
void solve2();
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
input();
makeMarker();
solve1();
solve2();
}
int n, m;
string s, t;
char S[100005], T[100005];
void input(){
cin >> s >> t;
n = s.size(), m = t.size();
copy(s.begin(), s.end(), S+1);
copy(t.begin(), t.end(), T+1);
}
struct segTree{
int tree[1<<19];
void init(int i, int l, int r, vector<int> &vec){
if(l==r){
tree[i] = vec[l];
return;
}
int m = (l+r)/2;
init(i*2, l, m, vec);
init(i*2+1, m+1, r, vec);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int s, int e){
if(r<s || e<l) return INT_MAX;
if(s<=l && r<=e) return tree[i];
int m = (l+r)/2;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int until[100005];
void makeMarker(){
string s_rev (s.rbegin(), s.rend());
string t_rev (t.rbegin(), t.rend());
string combined = s_rev + "#" + t_rev;
vector<int> sa = suffix_array(combined); // size k+1
vector<int> lcp = lcp_array(combined, sa); // size k
int k = (int)lcp.size();
tree.init(1, 0, k-1, lcp);
set<int> s_loc;
for(int i=0; i<=k; i++){
if(sa[i] < n) s_loc.insert(i);
}
for(int i=0; i<=k; i++){
if(sa[i] <= n) continue;
int idx = m - (sa[i] - n);
int val = 0;
auto it = s_loc.lower_bound(i);
if(it != s_loc.begin()){
int prv = *prev(it);
val = max(val, tree.query(1, 0, k-1, prv, i-1));
}
if(it != s_loc.end()){
int nxt = *it;
val = max(val, tree.query(1, 0, k-1, i, nxt-1));
}
until[idx+1] = idx-val+2;
}
#ifdef LOCAL
for(int i=1; i<=m; i++) cout << until[i] << ' ';
cout << '\n';
#endif
}
struct segTree2{
int tree[1<<19];
void init(int i, int l, int r){
if(l==r){
tree[i] = 0;
return;
}
int m = (l+r)/2;
init(i*2, l, m);
init(i*2+1, m+1, r);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = v;
return;
}
int m = (l+r)/2;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int s, int e){
if(r<s || e<l) return INT_MAX;
if(s<=l && r<=e) return tree[i];
int m = (l+r)/2;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree2;
int minCnt[100005];
vector<int> lists[100005];
double maxProd[100005];
void solve1(){
minCnt[0] = 0;
lists[0].push_back(0);
tree2.init(1, 0, m);
for(int i=1; i<=m; i++){
int l = until[i] - 1, r = i-1;
minCnt[i] = tree2.query(1, 0, m, l, r) + 1;
tree2.update(1, 0, m, i, minCnt[i]);
lists[minCnt[i]].push_back(i);
}
int ans = minCnt[m];
for(int C=1; C<=ans; C++){
vector<int> &prvD = lists[C-1], &curD = lists[C];
function<void(int, int, int, int)> dnc_opt = [&](int l, int r, int prvl, int prvr){
if(l>r) return;
int m = (l+r)/2;
int mv = curD[m];
double maxV = -1; int maxIdx = -1;
for(int i=prvl; i<=prvr; i++){
if(until[mv] > prvD[i]+1) continue;
double val = maxProd[prvD[i]] + log(mv - prvD[i]);
if(val > maxV) maxV = val, maxIdx = i;
}
maxProd[mv] = maxV;
dnc_opt(l, m-1, prvl, maxIdx);
dnc_opt(m+1, r, maxIdx, prvr);
};
dnc_opt(0, (int)curD.size()-1, 0, (int)prvD.size()-1);
}
cout << fixed << setprecision(15);
cout << ans << ' ' << maxProd[m] << '\n';
}
void solve2(){
vector<double> DP (m+1);
for(int i=1; i<=m; i++){
for(int j=max(0, i-4); j<i; j++){
if(until[i] > j+1) continue;
DP[i] = max(DP[i], DP[j] + log(i-j));
}
}
vector<vector<int> > nxt (m+1);
for(int i=1; i<=m; i++){
for(int j=max(0, i-4); j<i; j++){
if(until[i] > j+1) continue;
if(abs(DP[i] - (DP[j] + log(i-j))) < 1e-9){
nxt[j].push_back(i);
}
}
}
vector<int> dist (m+1, 1e9);
dist[0] = 0;
for(int i=0; i<=m; i++){
for(int v : nxt[i]){
dist[v] = min(dist[v], dist[i]+1);
}
}
cout << fixed << setprecision(15);
cout << DP[m] << ' ' << dist[m] << '\n';
}1G. 나이트 막기
최대 유량 최소 컷 정리를 생각해 보면, 답은 결국 최소 횟수로 이동할 때 사용 가능한 이동 방향의 개수라고 짐작할 수 있다. 이제 저걸 구하기만 하면 된다. 내가 쓴 방법은 일단 대충 목표 지점 근처로 가는 데 필요한 이동 방향과 횟수를 찾아둔 뒤, 그 근처는 나이브하게 탐색하며 최소 횟수로 이동하는 데 사용할 수 있는 이동 방향을 비트마스크로 관리해 줬다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 100;
int xx[]={-1, 1, 2, 2, 1, -1, -2, -2}, yy[]={2, 2, 1, -1, -2, -2, 1, -1};
int dist[202][202], state[202][202];
void init(){
for(int i=0; i<=M*2; i++) for(int j=0; j<=M*2; j++){
dist[i][j] = 1e9;
state[i][j] = 0;
}
dist[M][M] = 0;
queue<pair<int, int> > que;
que.push({M, M});
while(!que.empty()){
auto [x, y] = que.front(); que.pop();
int nd = dist[x][y] + 1;
for(int d=0; d<8; d++){
int tx = x+xx[d], ty = y+yy[d];
if(tx<0 || tx>M*2 || ty<0 || ty>M*2 || dist[tx][ty] < nd) continue;
if(dist[tx][ty] == nd){
state[tx][ty] |= state[x][y] | (1<<d);
continue;
}
dist[tx][ty] = nd, state[tx][ty] = state[x][y] | (1<<d);
que.push({tx, ty});
}
}
}
ll solve(ll x, ll y){
vector<ll> res (8);
if(y >= x*2){
ll step = 2, toGo = y, cur = (toGo + step - 1) / step;
ll other = x;
ll miss = cur - other, adjust = miss / 2;
ll t1 = cur - adjust, t0 = adjust;
res[1] = t1, res[0] = t0;
}
else{ // 사이인 경우
ll step = 3, toGo = x+y, cur = (toGo + step - 1) / step;
ll other = y-x;
ll miss = cur - other, adjust = miss / 2;
ll t1 = cur - adjust, t2 = adjust;
res[1] = t1, res[2] = t2;
}
for(int i=0; i<8; i++) res[i] = max(res[i] - 10, 0LL);
ll nx = x, ny = y, state = 0;
for(int i=0; i<8; i++){
if(!res[i]) continue;
state |= (1<<i);
nx -= xx[i] * res[i], ny -= yy[i] * res[i];
}
state |= ::state[nx+M][ny+M];
return __builtin_popcount(state);
}
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
init();
int t;
cin >> t;
while(t--){
ll x, y;
cin >> x >> y;
x = abs(x), y = abs(y);
if(!x && !y){
cout << -1 << '\n';
continue;
}
if(x>y) swap(x, y);
if(x == 1 && y == 2){
cout << -1 << '\n';
continue;
}
cout << solve(x, y) << '\n';
}
}1C. PriorityQueue가 아니에요
아래와 같이 생각해 보자.
- 변수 $v$가 있고 초기에 값이 $0$이다. 다음 두 연산 중 하나를 할 수 있다.
- 비용 $2$를 소모해 $v$를 $1$ 증가시킬 수 있다.
- 비용 $1$을 소모해 $v$를 $1$ 감소시킬 수 있다. 단, $v$를 음수로 만들 수 없다.
$P_i$는 비용 $i$를 소모하되, 처음에만 $v$가 $0$이고 이후로는 $0$이 되지 않는 방법의 수라 하자. $Q_i$는 비용 $i$를 소모하는 방법의 수라 하자. $C_i$는 $i$번째 카탈란 수로 정의한다. 이때, 아래와 같은 점화식을 세울 수 있다.
$$\begin{aligned}
P_i &= Q_{i-2} \\
Q_i &= C_0 P_i + C_1 P_{i-3} + C_2 P_{i-6} + \cdots \\
\therefore Q_i &= C_0 Q_{i-2} + C_1 P_{i-5} + C_2 P_{i-8} + \cdots
\end{aligned}$$
이제 저 점화식을 풀면 답을 얻을 수 있다. 처음에는 online FFT를 하는 방법을 생각해 봤는데 TL이 1초라 안 될 것 같았다. 그런데 OEIS에 이걸 찾아보니 있었다. ([https://oeis.org/A357654]) 이걸 보니 p-recursive solver를 돌리면 그냥 풀릴 것 같다는 생각이 들었고, 실제로도 그랬다.
p-recursive solver는 이곳에서 가져왔다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int MX = 1'000'005;
int mod_inv(int a, int mod) {
int b = mod, s = 1, t = 0, old_a = a;
while (b) {
int q = a / b;
swap(a %= b, b);
swap(s -= t * q, t);
}
return s < 0 ? s + mod : s;
}
vector<int> extended(int n, const vector<vector<int>>& coeffs, const vector<int>& terms, int mod) {
vector<int> ret(max<int>(n + 1, terms.size()));
copy(terms.begin(), terms.end(), ret.begin());
const int order = coeffs.size() - 1;
const int deg = coeffs[0].size() - 1;
for (int m = terms.size(); m <= n; ++m) {
int s = 0;
for (int i = 1; i <= order; ++i) {
int k = m - i, t = ret[k];
for (int d = 0; d <= deg; ++d) {
s = (s + ll(t) * coeffs[i][d]) % mod;
t = ll(t) * k % mod;
}
}
int denom = 0, mpow = 1;
for (int d = 0; d <= deg; ++d) {
denom = (denom + ll(mpow) * coeffs[0][d]) % mod;
mpow = ll(mpow) * m % mod;
}
ret[m] = ll(mod - s) * mod_inv(denom, mod) % mod;
}
return ret;
}
vector<int> guess_sequence(int n, const vector<int>& terms, int degree, int mod) {
vector<vector<int>> coeffs = {
{0, 1, 0},
{MOD-1, MOD-1, 0},
{MOD-2, MOD-1, 0},
{6, MOD-4, 0},
{MOD-2, 4, 0},
{2, 4, 0}
};
return extended(n, coeffs, terms, mod);
}
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1) * x % MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
ll fact[1'000'005], factInv[1'000'005];
inline ll comb(ll n, ll k){
if(k<0 || k>n) return 0;
return fact[n] * factInv[k] % MOD * factInv[n-k] % MOD;
}
int t;
ll n;
ll C[1'000'005];
int Q[5005];
ll ans[1'000'005];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
fact[0] = 1;
for(int i=1; i<=1'000'000; i++) fact[i] = fact[i-1] * i % MOD;
factInv[1'000'000] = mpow(fact[1'000'000], MOD-2);
for(int i=999'999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;
for(int i=0; i<=500'000; i++){
C[i] = (comb(2*i, i) - comb(2*i, i-1) + MOD) % MOD;
}
Q[0] = 1;
for(int i=1; i<=5000; i++){
for(int j=0; j*3+2<=i; j++){
Q[i] = (Q[i] + C[j] * Q[i-3*j-2]) % MOD;
}
}
vector<int> qv (Q, Q+5001);
vector<int> gv = guess_sequence(1'000'005, qv, 2, MOD);
for(int i=1; i<=1'000'000; i++) ans[i] = gv[i+2];
ans[1] = -1;
cin >> t;
while(t--){
cin >> n;
cout << ans[n] << "\n";
}
}PF. $151$
$N = 500$에 TL이 $6$초인 게 조금 특이하다. 아무래도 $O(N^3)$인데 상수가 꽤나 크거나, 가능성은 낮지만 $O(N^3 \log N)$도 고려해 볼만 한 제한이다.
일단 위/아래 행을 고정하자. 그러고 나면 직선에서 푸는 문제가 된다. 각 행을 위에서 읽은 것과 아래에서 읽은 것을 $A[i]$, $B[i]$로 구해 두자. 이러면 $(A[l], A[l+1], \dots, A[r]) = (B[r], B[r-1], \dots, B[l])$인 $[l, r]$의 개수를 찾는 문제가 된다. $A = B$였다면 manacher 알고리즘을 이용하면 자명한데, 이건 상황이 약간 다르긴 하다. 그래도 manacher 알고리즘의 기본 원리는 통해서 처리를 약간만 바꾸어 주면 맞을 수 있다.
해시 충돌로 인해 여러 번 틀렸다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'000'000'031;
const ll MULT = 13;
const int flip[10] = {0, 1, 2, 10, 11, 5, 9, 12, 8, 6};
int n, m;
int arr[502][502];
ll val1[502], val2[502];
ll A[1005], B[1005];
int mx[1005];
ll ans;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> m;
for(int i=0; i<n; i++){
string s;
cin >> s;
for(int j=0; j<m; j++){
arr[i][j] = s[j] - '0';
}
}
for(int u=0; u<n; u++){
for(int i=0; i<m; i++) val1[i] = val2[i] = 0;
ll p13 = 1;
for(int d=u; d<n; d++){
int L = m*2+1;
fill(A, A+L, -1);
fill(B, B+L, -1);
fill(mx, mx+L, 0);
for(int i=0; i<m; i++){
val1[i] = (val1[i] * MULT + arr[d][i]) % MOD;
val2[i] = (val2[i] + flip[arr[d][i]] * p13) % MOD;
A[i*2+1] = val1[i], B[i*2+1] = val2[i];
}
p13 = (p13 * MULT) % MOD;
int p = 0, r = 0;
for(int i=0; i<L; i++){
if(A[i] != B[i]) continue;
if(i>r){
p = r = i;
while(r+1<L && r+1<=2*p && A[r+1]==B[2*p-(r+1)]) r++;
mx[i] = r-p;
}
else{
int j = 2*p-i;
if(mx[j] < r-i) mx[i] = mx[j];
else{
p = i;
while(r+1<L && r+1<=2*p && A[r+1]==B[2*p-(r+1)]) r++;
mx[i] = r-p;
}
}
}
for(int i=0; i<L; i++){
if(A[i] != B[i]) continue;
if(i&1) ans += (mx[i] + 1) / 2;
else ans += mx[i] / 2;
}
}
}
cout << ans;
}1B. 시니어 개발자 동우의 직행 취업일기
Easy version과 연관지어 생각해 보면 결국 $xy+yz+zx = N$ 이고 $x+y+z+4 \le 10^6$인 $(x, y, z)$를 찾는 문제가 된다.
일단 $z$를 고정해 보자. 문제 상황에 의해 $xy, yz, zx$ 셋 중 하나는 $4 \times 10^{10}$ 이하여야 하고 그럼 $x$, $y$, $z$ 중 $2 \times 10^5$ 이하여야 하는 게 존재한다. $z$에 대해 문제를 바라보면 $(x+z)(y+z) = N+z^2$으로 쓸 수 있으므로 $N+z^2$를 소인수분해해 모든 약수를 빠르게 찾을 수 있으면 좋을 것 같다.
단순히 $z$를 브루트포스해 보면서 $N+z^2$를 $O(\sqrt{N})$ 정도 시간에 소인수분해 알고리즘을 돌리면 된다. 왜 되는지는 잘 모르겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 1'000'000;
ll n;
void print(ll x, ll y, ll z){
assert(x*y+y*z+z*x == n);
assert(x+y+z+4 <= LIM);
ll root = 1;
ll cnt = 1;
vector<pair<ll, ll> > ans;
for(ll v: {x, y, z}){
if(!v) continue;
ll where = ++cnt;
ans.push_back({root, where});
for(ll i=1; i<=v; i++){
ans.push_back({where, ++cnt});
}
}
// cout << x << ' ' << y << ' ' << z << '\n';
cout << (ans.size() + 1) << '\n';
for(auto [x, y]: ans) cout << x << ' ' << y << '\n';
}
void trySolve(ll K, ll z){
// (x+z)(y+z) = K = N+z^2
for(ll t=z; t*t<=K; t++){
if(K%t != 0) continue;
ll x = t - z;
ll y = K/t - z;
if(y < 0) continue;
if(x+y+z+4 > LIM) continue;
print(x, y, z);
exit(0);
}
}
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n;
for(ll x=1; x<=350'000; x++){
ll K = n+x*x;
trySolve(K, x);
}
return 1;
}후기
결국 다 풀었다. 이걸 왜 한다고 했을까...
'시리즈 > Problem Solving Diary' 카테고리의 다른 글
| Problem Solving Diary #29 (0) | 2024.12.29 |
|---|---|
| Problem Solving Diary #28 (0) | 2024.12.17 |
| Problem Solving Diary #27 (0) | 2024.11.26 |
| Problem Solving Diary #26 (0) | 2024.11.15 |
| Problem Solving Diary #25 (0) | 2024.10.13 |