TOC
- 250407
- 250408
- 250409
- 250412
- BOJ 1786 : 찾기 (Platinum 5)
- AtCoder Beginner Contest 400A : ABC400 Party
- AtCoder Beginner Contest 400B : Sum of Geometric Series
- AtCoder Beginner Contest 400C : 2^a b^2
- Project Euler 1 : Multiples of 3 and 5
- Project Euler 2 : Even Fibonacci numbers
- Project Euler 3 : Largest prime factor
- Project Euler 4 : Largest palindrome product
- Project Euler 5 : Smallest multiple
- Project Euler 6 : Sum square difference
- Project Euler 7 : 10001st prime
- Project Euler 8 : Largest product in a series
- AtCoder Beginner Contest 401
- 250415
- 250417
250407
BOJ 1112 : 진법 변환 (Gold 3)
-
양의 진법은 할 만하다. 음의 진법이 문제다.
-
-10진법을 가지고 예시를 만들어보자.
-
규칙을 쉽게 찾을 수 있다.
진법으로 양수를 바꿀 때에는 각 자릿수 ( )에 대해, 가 짝수일 때 를 그대로 사용하고, 가 홀수일 때 를 로 바꾸고 다음 자릿수에 필요하다면 1을 더해준다.
진법으로 음수를 바꿀 때에는 양수로 바꾼 각 자릿수 에 대해, 가 짝수일 때 를 로 바꾸고 다음 자릿수에 필요하다면 1을 더해주고, 가 홀수일 때 를 그대로 사용한다.
-
발견한 규칙을 바탕으로 코드를 작성해보자.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int x, b; cin >> x >> b;
vi ans;
if (b>0) {
int y=abs(x);
while (y>0) {
ans.insert(ans.begin(), y%b);
y/=b;
}
if (x<0)
cout << '-';
} else {
int i=0;
b*=-1;
while (x!=0) {
if (i%2==(x<0)) {
ans.insert(ans.begin(), abs(x)%b);
} else {
int d=b-abs(x)%b;
if (d==b) d=0;
ans.insert(ans.begin(), d);
x+=d*(x/abs(x));
}
x/=b; i++;
}
}
for (int a : ans)
cout << a;
if (ans.empty())
cout << 0;
return 0;
}
BOJ 3665 : 최종 순위 (Gold 1)
- 위상 정렬을 이용해서 풀 수 있다.
- 사이클의 존재를 확인해야 하는데, 이를 위해 비트셋을 이용했다.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
bool dfs(vector<vi>& G, vi& topo, vector<bool> &visited, bitset<501> st, int u) {
if (st[u]) return false;
if (visited[u]) return true;
visited[u] = true;
st[u] = true;
for (int v : G[u]) {
if (!dfs(G, topo, visited, st, v)) return false;
}
topo.insert(topo.begin(), u);
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
int n; cin >> n;
vector<vi> G(n+1);
vi order(n);
for (int i=0;i<n;i++)
cin >> order[i];
int m; cin >> m;
map<pi, bool> swapped;
for (int i=0;i<m;i++) {
int a, b; cin >> a >> b;
swapped[{a, b}] = true;
}
vi in_deg(n+1,0);
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
if (swapped[{order[i], order[j]}] || swapped[{order[j], order[i]}]){
G[order[j]].push_back(order[i]);
in_deg[order[i]]++;
} else {
G[order[i]].push_back(order[j]);
in_deg[order[j]]++;
}
}
}
int start=-1;
for (int i=1;i<=n;i++) {
if (in_deg[i]==0) {
start = i; break;
}
}
if (start == -1) {
cout << "IMPOSSIBLE\n";
continue;
}
vi ans;
vector<bool> visited(n+1,false);
if (dfs(G, ans, visited, 0, start)) {
for (int u : ans)
cout << u << ' ';
cout << '\n';
} else {
cout << "IMPOSSIBLE\n";
}
}
return 0;
}
BOJ 3273 : 두 수의 합 (Silver 3)
- 투 포인터가 아닌 방법으로 해결할 수 있다.
- 각 원소의 개수를 세어놓고, 각 원소에 대해
의 개수를 합산하면 된다. - 단,
일 때에는 중복으로 세어지므로 1을 빼준다. - 서로 다른 원소의 쌍을 세어야 하므로, 최종적으로 2로 나누어준다.
- 내 풀이는
가 서로 다르지 않아도 셀 수 있지만, 굳이 그럴 필요는 없다.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int cnt[1'000'001] = {0, };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vi arr(n);
for (int i=0;i<n;i++) {
cin >> arr[i];
cnt[arr[i]]++;
}
int x; cin >> x;
int ans=0;
for (int i=0;i<n;i++) {
int j=x-arr[i];
if (j<1||j>1'000'000) continue;
ans += cnt[j];
if (arr[i]*2 == x)
ans--;
}
cout << (ans/2);
return 0;
}
250408
BOJ 12100 : 2048 (Easy) (Gold 1)
가지 경우의 수를 모두 탐색하면 된다. - 배열 관리 때문에 곤란할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int n;
int dfs(int cnt, int dir, int** board) {
if (cnt == 5) {
int m=0;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
m = max(m, board[i][j]);
return m;
}
int **mat = new int*[20];
for (int i=0;i<20;i++) {
mat[i] = new int[20];
memset(mat[i], 0, sizeof(int)*20);
}
if (dir == 0) { // <-
for (int i=0;i<n;i++) {
int lastNum=0, lastIdx=-1;
for (int j=0;j<n;j++) {
if (board[i][j]==0) continue;
if (board[i][j] == lastNum) {
mat[i][lastIdx] = board[i][j]*2;
lastNum=0;
} else {
mat[i][++lastIdx] = board[i][j];
lastNum = board[i][j];
}
}
}
} else if (dir == 1) { // ->
for (int i=0;i<n;i++) {
int lastNum=0, lastIdx=n;
for (int j=n-1;j>=0;j--) {
if (board[i][j]==0) continue;
if (board[i][j] == lastNum) {
mat[i][lastIdx] = board[i][j]*2;
lastNum=0;
} else {
mat[i][--lastIdx] = board[i][j];
lastNum = board[i][j];
}
}
}
} else if (dir == 2) { // ^
for (int i=0;i<n;i++) {
int lastNum=0, lastIdx=-1;
for (int j=0;j<n;j++) {
if (board[j][i]==0) continue;
if (board[j][i] == lastNum) {
mat[lastIdx][i] = board[j][i]*2;
lastNum=0;
} else {
mat[++lastIdx][i] = board[j][i];
lastNum = board[j][i];
}
}
}
} else if (dir == 3) { // v
for (int i=0;i<n;i++) {
int lastNum=0, lastIdx=n;
for (int j=n-1;j>=0;j--) {
if (board[j][i]==0) continue;
if (board[j][i] == lastNum) {
mat[lastIdx][i] = board[j][i]*2;
lastNum=0;
} else {
mat[--lastIdx][i] = board[j][i];
lastNum = board[j][i];
}
}
}
}
int m=0;
for (int d=0;d<4;d++)
m=max(m,dfs(cnt+1, d, mat));
free(mat);
return m;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int **board = new int*[20];
for (int i=0;i<n;i++) {
board[i] = new int[20];
for (int j=0;j<n;j++) {
cin >> board[i][j];
}
}
int m=0;
for (int d=0;d<4;d++)
m=max(m,dfs(0,d,board));
cout << m;
free(board);
return 0;
}
250409
BOJ 1007 : 벡터 매칭 (Gold 2)
- 조금만 생각하면
개의 점에 대해 벡터의 시점으로 할 점 개와 종점으로 할 점 개를 정해야 함을 알 수 있다. - 최종 벡터는 시점으로 정한 점의 좌표를 빼고, 종점으로 정한 점의 좌표를 더함으로써 구할 수 있다.
이므로 이라서 브루트포스 해도 된다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
int n; cin >> n;
vector<pi> p(n);
for (int i=0;i<n;i++) {
int x, y; cin >> x >> y;
p[i] = {x, y};
}
vi perm(n, 0);
fill(perm.begin()+n/2,perm.end(),1);
ll m = numeric_limits<ll>::max();
do {
ll x=0, y=0;
for (int i=0;i<n;i++) {
if (perm[i]) {
x+=p[i].first;
y+=p[i].second;
} else {
x-=p[i].first;
y-=p[i].second;
}
}
m = min(m, x*x+y*y);
} while (next_permutation(perm.begin(), perm.end()));
cout << setprecision(20) << sqrt((double) m) << '\n';
}
return 0;
}
250412
BOJ 1786 : 찾기 (Platinum 5)
- KMP 알고리즘을 이용해서 풀 수 있다.
- 문제 설명에 KMP 알고리즘에 대해 잘 설명되어 있다.
- 대신
-배열을 에 구하는 방법을 알아내야 하는데, 그냥 포기하고 찾아봤다.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string t, p;
getline(cin, t);
getline(cin, p);
int n=t.length(), m=p.length();
vi pi(m,0);
int j=0;
for (int i=1;i<m;i++) {
while (j>0 && p[i] != p[j])
j=pi[j-1];
if (p[i]==p[j])
pi[i]=++j;
}
j=0;
vi ans;
for (int i=0;i<n;i++) {
while (j>0 && t[i]!=p[j])
j=pi[j-1];
if (t[i]==p[j]) {
if (j==m-1) {
ans.push_back(i-m+1);
j=pi[j];
} else {
j++;
}
}
}
cout << ans.size() << '\n';
for (int i : ans)
cout << i+1 << ' ';
return 0;
}
AtCoder Beginner Contest 400A : ABC400 Party
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int a; cin >> a;
if (400 % a == 0) {
cout << (400 / a);
} else {
cout << "-1";
}
return 0;
}
AtCoder Beginner Contest 400B : Sum of Geometric Series
n, m = map(int, input().split())
x = 0
for i in range(m+1):
x += pow(n, i)
if x > 1_000_000_000:
print('inf')
break
else:
print(x)
AtCoder Beginner Contest 400C : 2^a b^2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n; cin >> n;
ll cnt=0;
for (ll a=2;a<=n;a<<=1) {
for (ll b=1;a*b*b<=n;b+=2) {
cnt++;
}
}
cout << cnt;
return 0;
}
Project Euler 1 : Multiples of 3 and 5
sieve = [False] * 1000
for i in range(3, 1000, 3):
sieve[i] = True
for i in range(5, 1000, 5):
sieve[i] = True
s = 0
for i in range(1, 1000):
if sieve[i]:
s += i
print(s)
Project Euler 2 : Even Fibonacci numbers
a, b = 1, 1
ans=0
while True:
c = a+b
if c%2==0:
ans+=c
if c>4_000_000:
break
a=b
b=c
print(ans)
Project Euler 3 : Largest prime factor
sieve=[True]*775147
for i in range(2, 775147):
if not sieve[i]:
continue
for j in range(i*i, 775147, i):
sieve[j]=False
n=600851475143
ans=0
for i in range(2, 775147):
if n % i == 0 and sieve[i]:
ans=i
# print(i)
print(ans)
Project Euler 4 : Largest palindrome product
sieve=[False]*1_000_000
for i in range(100, 999):
for j in range(100, 999):
sieve[i*j]=True
# ignore 5-digit case
# 6-digit
ans = 0
for i in range(1,10):
for j in range(10):
for k in range(10):
num = i*100001 + j*10010 + k*1100
if sieve[num]:
ans = num
print(ans)
Project Euler 5 : Smallest multiple
primes = [2, 3, 5, 7, 11, 13, 17, 19]
res = {}
for i in range(2, 21):
for p in primes:
e = 1
while i % (p ** e) == 0:
e += 1
e -= 1
if p in res:
res[p] = max(res[p], e)
else:
res[p] = e
print(res)
ans = 1
for p, e in res.items():
ans *= p ** e
print(ans)
Project Euler 6 : Sum square difference
s1 = lambda n: n*n*(n+1)*(n+1)//4
s2 = lambda n: n*(n+1)*(2*n+1)//6
print(s1(100)-s2(100))
Project Euler 7 : 10001st prime
N = 1000000
sieve=[True]*N
cnt=0
for i in range(2, N):
if not sieve[i]:
continue
for j in range(i*i, N, i):
sieve[j]=False
cnt+=1
if cnt == 10001:
print(i)
break
Project Euler 8 : Largest product in a series
s="""
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace('\n','')
ans=0
for i in range(1000-12):
prod=1
for j in range(i,i+13):
prod*=int(s[j])
ans=max(ans, prod)
print(ans)
AtCoder Beginner Contest 401
- ABC 401에 참가했다. 후기는 이 문서 참고.
250415
ABC 401E (업솔빙)
- 해당 문서 참조.
BOJ 1504 : 특정한 최단 경로 (Gold 4)
과 의 경로 중 최솟값을 내보내면 된다. - 다익스트라를 3번 사용하면 되므로 시간복잡도는
이다.
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
constexpr int INF = numeric_limits<int>::max() / 4;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, e;
cin >> n >> e;
vector<vector<pi>> G(n+1);
while (e--) {
int a, b, c; cin >> a >> b >> c;
G[a].emplace_back(c, b);
G[b].emplace_back(c, a);
}
int v1, v2; cin >> v1 >> v2;
auto dijkstra = [&G, n](int src) {
vi dist(n+1, INF);
dist[src]=0;
priority_queue<pi, vector<pi>, greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [w, u] = pq.top(); pq.pop();
if (dist[u] < w) continue;
for (auto [w2, v] : G[u]) {
if (dist[v] > w+w2) {
dist[v] = w+w2;
pq.push({w+w2, v});
}
}
}
return dist;
};
vi d_1 = dijkstra(1);
vi d_v1 = dijkstra(v1);
vi d_v2 = dijkstra(v2);
int ans=min(d_1[v1] + d_v1[v2] + d_v2[n], d_1[v2] + d_v2[v1] + d_v1[n]);
if (ans >= INF)
cout << "-1";
else
cout << ans;
return 0;
}
250417
BOJ 27172 : 수 나누기 게임
- 나이브하게는
가 떠오른다. 더 나은 방법이 없을까? - 처음에는 배수들의 카운트를 미리 깎아주는 식으로 처리하려고 했으나, TLE가 떴다. 뜨고 나니
, , 의 worst case가 떠올랐다. - 약수를 카운트를 올려주면 된다.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vi arr(n);
unordered_map<int, int> cnt_map;
for (int i=0;i<n;i++) {
cin >> arr[i];
cnt_map[arr[i]]=0;
}
for (int i=0;i<n;i++) {
int x=arr[i];
for (int j=1;j*j<=x;j++) {
if (x%j!=0) continue;
if (cnt_map.count(j))
cnt_map[j]++; cnt_map[x]--;
if (j*j!=x && cnt_map.count(x/j))
cnt_map[x/j]++; cnt_map[x]--;
}
}
for (int i=0;i<n;i++)
cout << cnt_map[arr[i]] << ' ';
return 0;
}
BOJ 12015 : 가장 긴 증가하는 부분 수열 2 (Gold 2)
- [longest_increasing_subsequence:LIS] 문서를 참고하자.
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
using vi = vector<int>;
constexpr int INF = numeric_limits<int>::max();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vi d(n+1, INF);
d[0]=-INF;
int ans=0;
for (int i=0;i<n;i++) {
int x; cin >> x;
auto l=lower_bound(d.begin(), d.end(), x);
*l=min(*l, x);
ans=max(ans, (int) (l-d.begin()));
}
cout << ans;
return 0;
}
BOJ 12738 : 가장 긴 증가하는 부분 수열 3 (Gold 2)
- 바로 위 문제와 크게 다르지 않다.
BOJ 14003 : 가장 긴 증가하는 부분 수열 5 (Platinum 5)
- 우선
으로 LIS를 구한다. - 원래 LIS를 복원하는 것이 빡세다. 내가 생각해낸 알고리즘은 다음과 같다.
- 우선 LIS를 구할 때,
를 변화시키는 각 에 대해 와 을 에 저장시킨다. - 그런 뒤, 다음 과정을 통해 LIS를 복원한다.
for l=(LIS 길이) to 1 do S에서 l에 대해 i<=i_prev이면서 최대인 i를 찾는다. lcs[l] <- (위에서 찾은 i에 대해 a_i)
- 우선 LIS를 구할 때,
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
constexpr int INF = numeric_limits<int>::max();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vi d(n+1, INF);
d[0]=-INF;
unordered_map<int, vector<pi>> lis;
int m=0;
for (int i=0;i<n;i++) {
int x; cin >> x;
auto l=lower_bound(d.begin(), d.end(), x);
int l_idx = l-d.begin();
if (*l > x) {
*l=x;
lis[l_idx].emplace_back(i, *l);
}
m=max(m, l_idx);
}
cout << m << '\n';
int i_prev=n;
vi ans(m);
for (int l=m;l>=1;l--) {
auto x = upper_bound(lis[l].begin(), lis[l].end(), i_prev, [](int i, const pi& a) {
return i < a.first;
});
x--;
ans[l-1]=(*x).second;
i_prev = (*x).first;
}
for (int x : ans)
cout << x << ' ';
return 0;
}
BOJ 11779 : 최소비용 구하기 2 (Gold 3)
- 다익스트라 + 복원 문제다.
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
constexpr int INF = numeric_limits<int>::max()/2;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<vector<pi>> G(n+1);
while (m--) {
int a, b, c; cin >> a >> b >> c;
G[a].emplace_back(c, b);
}
int src, dst; cin >> src >> dst;
priority_queue<pi, vector<pi>, greater<>> pq;
pq.emplace(0, src);
vi d(n+1, INF);
vi pred(n+1, -1);
d[src]=0;
while (!pq.empty()) {
auto [w, u] = pq.top(); pq.pop();
if (d[u]<w) continue;
for (auto [w2, v] : G[u]) {
if (d[v]>w+w2) {
d[v]=w+w2;
pred[v]=u;
pq.emplace(w+w2, v);
}
}
}
cout << d[dst] << '\n';
vi ans;
int prev=dst;
while (prev != -1) {
ans.insert(ans.begin(), prev);
prev = pred[prev];
}
cout << sz(ans) << '\n';
for (int x : ans)
cout << x << ' ';
return 0;
}
BOJ 2143 : 두 배열의 합 (Gold 3)
- 해시맵과 누적합을 사용해서 해결하면 된다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
int n; cin >> n;
vi A_sum(n+1);
A_sum[0]=0;
for (int i=1;i<=n;i++) {
int x; cin >> x;
A_sum[i]=A_sum[i-1]+x;
}
int m; cin >> m;
vi B_sum(m+1);
B_sum[0]=0;
for (int i=1;i<=m;i++) {
int x; cin >> x;
B_sum[i]=B_sum[i-1]+x;
}
unordered_map<int, int> cnt;
for (int i=0;i<=n;i++)
for (int j=i+1;j<=n;j++)
cnt[A_sum[j]-A_sum[i]]++;
ll ans=0;
for (int i=0;i<=m;i++) {
for (int j=i+1;j<=m;j++) {
int x = T-(B_sum[j]-B_sum[i]);
if (cnt.count(x)) {
ans += cnt[x];
}
}
}
cout << ans;
return 0;
}