티스토리 뷰
jjang36524 계정으로 가서 5솔을 했다.
A번: x가 interesting할 조건은 x에다가 1을 더할 때 자리올림이 일어나는 것이다. 자리올림이 없을 때는 합에 1이 더해지지만, 매 자리올림마다 9 하나가 0이 됨으로써 합이 작아지기 때문이다. 자리올림이 일어날 조건은 x를 10으로 나눈 나머지가 9일 때고, 이는 [(x+1)/10의 식으로 구할 수 있다.]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
int N;
cin >> N;
cout << (N + 1) / 10 << '\n';
}
}B번: 나올 가능성이 있는 문자열은 정수 i,j,k(i<=j>=k)로 정의될 수 있는데, 이 문자열은 i에서 j까지 갔다가 다시 k까지 돌아갈 때 나오는 문자열이다. 경우의 수는 N^3이지만, 매 i,j마다 가능한 k는 유일하기 때문에 실제로 비교할 경우는 N^2이고, 총 N^3 시간에 문제를 풀 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
string s,t;
cin >> s >> t;
int i;
for (i = 0; i < s.size(); i++)
{
string re;
int j;
for (j = i; j < s.size(); j++)
{
re.push_back(s[j]);
int k;
string ne=re;
for (k = j; k >= 0; k--)
{
if (k != j)
ne.push_back(s[k]);
if (j - i + 1 + j - k == t.size())
{
if (t == ne)
{
cout << "YES"<<'\n';
goto T;
}
}
}
}
}
cout << "NO" << '\n';
T:
int d;
}
}C번: 가능한 경우의 수는 2^10=1024가지이므로 모두 탐색한 다음에 시뮬레이션을 해주면 된다. 1024가지의 상태 탐색은 비트마스크로 쉽게 할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
string s,t;
cin >> s >> t;
int i;
for (i = 0; i < s.size(); i++)
{
string re;
int j;
for (j = i; j < s.size(); j++)
{
re.push_back(s[j]);
int k;
string ne=re;
for (k = j; k >= 0; k--)
{
if (k != j)
ne.push_back(s[k]);
if (j - i + 1 + j - k == t.size())
{
if (t == ne)
{
cout << "YES"<<'\n';
goto T;
}
}
}
}
}
cout << "NO" << '\n';
T:
int d;
}
}D번: 핵당했다 ㅠㅠ
E번: k번 돌렸을 때 가능하려면 그 때의 순열이 n-2*m개 이상의 위치에서 맞는 값을 가지고 있어야 한다. 이런 k는 최대 3개 있다. 이런 k에 대해서는 i와 돌려진 pi를 잇는 간선들로 이루어진 그래프를 만들었을 때 정점 개수-컴포넌트 수가 m 이하여햐 한다. 매 원소마다 이 원소를 맞출 수 있는 k값을 찾고, 그런 k값에 대해 탐색을 진행하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int succs[300100];
int arr[300100];
int uf[300100];
int f(int n)
{
return n == uf[n] ? n : uf[n] = f(uf[n]);
}
int u(int n,int m)
{
n = f(n);
m = f(m);
if (n == m)
return 0;
uf[n] = m;
return 1;
}
int main()
{
int T;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> T;
while (T--)
{
int N, M;
cin >> N >> M;
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i];
arr[i]--;
succs[(arr[i] - i + N) % N]++;
}
vector<int>x;
for (i = 0; i < N; i++)
{
if (succs[i] >= (N - 2 * M))
{
int ans = 0;
int j;
for (j = 0; j < N; j++)
uf[j] = j;
for (j = 0; j < N; j++)
{
ans+=u((j + i) % N, arr[j]);
}
if (ans <= M)
{
x.push_back((N-i)%N);
}
}
}
sort(x.begin(), x.end());
cout << x.size() << ' ';
for (i = 0; i < x.size(); i++)
cout << x[i] << ' ';
cout << '\n';
for (i = 0; i < N; i++)
{
succs[(arr[i] - i + N) % N]--;
}
}
}F번: 주의: 이 풀이는 정해가 아니며, 시간 제한에 겨우 들어가며, 상수 커팅이 필요하고, 매우 깔끔하지 않다.
1000 정도의 값 K를 잡고, Ai를 K보다 작은 것과 큰 것으로 나눌 수 있다. 이러면, Xi-X(i-1)을 계산할 수 있다.
Xi-X(i-1)은 네 부분으로 나누어진다. Ai%작은 수, Ai%큰 수, 작은 수%Ai, 큰 수%Ai
기본적으로, 작은 수에 대해서는 각각의 작은 수가 몇 번 나오는지 계산을 해 둔다.
Ai가 작을 경우에는, Ai%작은 수는 K보다 작은 모든 수에 대해 나오는 경우*값, Ai%큰 수는 Ai*(I-1), 작은 수%Ai는 Ai%작은 수와 같은 방법, 큰 수%Ai는 큰 수를 처리할 때 모든 작은 수에 대해서 계산한 결과를 참조하면 된다.
Ai가 클 경우에는 Ai%작은수는 Ai와 작은 경우와 똑같이, 작은 수%Ai는 작은 수의 합으로 하면 된다.
Ai%큰 수는 Ai*(i-1)-mod로 인해 지워지는 수로 나눌 수 있고, mod로 인해 지워지는 수는 큰 수가 나올 때마다 Ai~N에서 지워지는 수 +Ai, 2*Ai~N에서 지워지는 수 +Ai로 나타낼 수 있고, 이는 펜윅 트리로 가능하다. 큰 수%Ai는 큰 수들의 합-(Ai~(2*Ai-1))에서의 개수*Ai-(2*Ai-(3*Ai-1))에서의 개수*2Ai....으로 나타낼 수 있고, 이는 펜윅 트리로 가능하다.
시간 복잡도는 Nsqrt(NlogN)으로 추정된다.
코드에서 반복문을 안 쓴 부분이 있는데, 이는 의도적인 최적화를 위한 것이다......
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define int long long
#define DIV 725
signed ft[5000100];
#pragma GCC target ("avx,avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
inline void upd(int n, int k)
{
while (n <= 300000)
{
ft[n] += k;
n += n & -n;
ft[n] += k;
n += n & -n;
ft[n] += k;
n += n & -n;
}
}
inline int get(int n)
{
int ans = 0;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
ans += ft[n];
n -= n & -n;
return ans;
}
int ft2[5000100];
inline void upd2(int n, int k)
{
while (n <= 300000)
{
ft2[n] += k;
n += n & -n;
ft2[n] += k;
n += n & -n;
ft2[n] += k;
n += n & -n;
}
}
inline int get2(int n)
{
int ans = 0;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
ans += ft2[n];
n -= n & -n;
return ans;
}
int cousmalls[DIV+1];
int countmod[DIV + 1][DIV+1];
int modcal[DIV + 1][DIV + 1];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int i,j;
for (i = 0; i <= DIV; i++)
{
for (j = 1; j <= DIV; j++)
{
modcal[i][j] = (i % j);
}
}
int su = 0;
int bigcou = 0;
int smallsu = 0;
int bigsu = 0;
for (i = 1; i <= N; i++)
{
int a;
cin >> a;
if (a < DIV)
{
int j;
for (j = 1; j ^ DIV; j++)
{
su += cousmalls[j] * (modcal[a][j]+modcal[j][a]);
}
for (j = 0; j ^ a; j++)
{
su += countmod[a][j] * j;
}
su += bigcou*a;
cousmalls[j]++;
smallsu += a;
}
else
{
su += smallsu;
int j;
for (j = 1; j ^ DIV; j++)
{
su += cousmalls[j] * (a%j);
}
su += bigsu;
su += a * bigcou;
su += get2(a);
int c = 0;
int re = get(300000);
for (j = a; j <= 300000; j += a)
{
c++;
upd2(j, -a);
su -= (re - get(j - 1))*a;
}
for (j = 1; j ^DIV; j++)
{
countmod[j][a % j]++;
}
upd(a, 1);
bigsu+=a;
bigcou++;
}
cout << su << ' ';
}
}