2587 - 대푯값2 (초1, Bronze II)
문제
- 5개의 수의 평균과 중앙값을 출력한다.
풀이
더보기
그대로 해주면 된다. accumulate()를 써도 된다. 시간복잡도는 O(1)이다.
#include <bits/stdc++.h>
using namespace std;
int arr[5], sum;
int main(){
for(int i = 0 ; i < 5 ; i++)cin>>arr[i], sum += arr[i];
sort(arr, arr+5);
cout<<sum/5<<"\n"<<arr[2];
}
2588 - 곱셈 (초2, Bronze III)
문제
- 두 세 자리 수가 주어질 때, 세로로 곱셈하는 과정에 적히는 수들을 차례대로 구하시오.
풀이
더보기
abc * def = abc * (f + 10*e + 100*d)이므로 abc*f,abc*e,abc*d,abc*def를 차례대로 출력하면 된다. 시간복잡도는 O(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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
int main(){
fast;
ll a; string s; cin>>a>>s; reverse(all(s));
for(auto i : s)cout<<(i-'0')*a<<"\n";
reverse(all(s));
cout<<a*stoll(s);
}
2589 - 보물섬 (초3, Gold V)
문제
- 격자판에서 상하좌우로 L이 인접한 곳끼리 이동할 수 있을 때, 같은 곳을 다시 지나지 않는 최장경로를 출력한다.
풀이
더보기
간단한 브루트포스 + bfs로 풀린다. L이 나올때마다 그 L에서 가장 먼 L을 구하면 된다.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll visited[55][55];
ll dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
string s[55];
ll n,m;
ll bfs(ll x, ll y){
memset(visited,-1,sizeof(visited));
queue<P> q;
q.push({x,y});
visited[x][y]=0;
ll ret=0;
while(q.size()){
auto [x,y] = q.front(); q.pop();
ret = max(ret,visited[x][y]);
for(int i = 0 ; i < 4 ; i++){
ll nx = x+dx[i], ny = y+dy[i];
if(nx<0 or ny<0 or nx>n-1 or ny>m-1)continue;
if(visited[nx][ny]>=0 or s[nx][ny]=='W')continue;
visited[nx][ny] = visited[x][y]+1;
q.push({nx,ny});
}
}
return ret;
}
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < n ; i++)cin>>s[i];
ll ans=0;
for(int i = 0 ; i < n ; i++)for(int j = 0 ; j < m ; j++)if(s[i][j]=='L')ans = max(ans,bfs(i,j));
cout<<ans;
}
2590 - 색종이 (초4/중2, Gold IV)
문제
- 1*1,2*2,3*3,4*4,5*5,6*6의 정사각형 색종이의 개수가 각각 주어질 때, 모든 정사각형 색종이를 사용하는데 드는 6*6 판의 최소 개수를 출력하시오.
풀이
더보기
정말 더러운 근본 case work 문제이다.
그리디한 접근을 전제로 한다.(큰 색종이부터, 구석에 배치하는 것이 이득)
크기 6은 하나 쓰는데 한개씩 든다.
크기 5는 한개 들고 남는 부분에 1을 채울 수 있다.
4는 한개 들고 남는 부분에 2를 채우고, 그래도 남는경우 1을 채울 수 있다.
3은 4개씩 묶어서 써준다음, 남는 개수에 따라 처리해준다.
1개 남는 경우, 2개 남는 경우, 3개 남는 경우 각각 채울 수 있는 최대 2의 개수와 1의 개수를 구해서 처리한다.
이래도 1,2가 남으면 2를 1칸 4개로 변환해주고 ceil(1의 개수/36)을 더해준다.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll a[7];
int main(){
fast;
cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6];
ll ans = a[6];
ans += a[5];
a[1] -= a[5]*11;
ans += a[4];
while(a[4]-->0){
ll c = 20;
while(a[2]>0 and c>0)a[2]--, c -= 4;
a[1] -= c;
}
ans += a[3]/4+bool(a[3]%4);
a[3] %= 4;
if(a[3]==1){
ll c = 20;
while(a[2]>0 and c>0)a[2]--, c -= 4;
a[1] -= c+7;
}
if(a[3]==2){
ll c = 12;
while(a[2]>0 and c>0)a[2]--, c -= 4;
a[1] -= c+6;
}
if(a[3]==3){
ll c = 4;
while(a[2]>0 and c>0)a[2]--, c -= 4;
a[1] -= c+5;
}
a[1] = max(a[1],0LL);
if(a[2]>0)a[1] += a[2]*4;
if(a[1]>0)ans += ceil(1.0*a[1]/36);
cout<<ans;
}
2591 - 숫자카드 (초5/중3, Gold V)
문제
- 수로 이루어진 문자열이 주어진다. 이 문자열을 1~34 사이의 수 여러개로 분할하는 경우의 수를 구하시오.
풀이
더보기
전형적인 dp이다.
dp[i] := 1...i까지 분할하는 경우의 수라고 세우고 점화식을 세워주면 된다. 0으로 시작하는 경우를 주의하자.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll dp[44];
string s;
ll f(ll x){
if(x==s.size())return 1;
if(s[x]=='0')return 0;
ll &ret = dp[x];
if(~ret)return ret; ret = f(x+1);
if(x<s.size()-1 and stoll(s.substr(x,2)) <= 34)ret += f(x+2);
return ret;
}
int main(){
fast;
cin>>s;
memset(dp,-1,sizeof(dp));
cout<<f(0);
}
2592 - 대표값 (중1/고1, Bronze II)
문제
- 10개의 수의 평균과 최빈값을 구하시오.
풀이
더보기
그대로 해주면 된다.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll a[11];
ll cnt[1010];
int main(){
fast;
ll n; n=10;
ll ans=0,c=0;
for(int i = 0 ; i < n ; i++){
cin>>a[i], cnt[a[i]]++;
if(cnt[a[i]]>c)ans=a[i],c=cnt[a[i]];
}
sort(a,a+n);
cout<<(ll)accumulate(a,a+n,0LL)/n<<"\n"<<ans;
}
2593 - 엘리베이터 (중4, Platinum V)
문제
- N(<=10^5)층 아파트에 엘리베이터가 M(<=100)대 있다. 각 엘리베이터는 b층부터 n층 이하까지 ax+b 꼴의 층을 지난다. 이 때 A층에서 B층까지 가는 데 타야하는 최소 엘리베이터의 개수를 구하고, 사용하는 엘리베이터를 순서대로 출력하시오.
풀이
더보기
그래프 모델링 문제이다. N+M개의 정점을 만들자. 이때 N개의 정점은 층을 의미하고, M개의 정점은 엘리베이터를 의미한다. 이제 엘리베이터 x로 y층에 갈 수 있으면 x<->y를 이어준다. 이 그래프에서 A층에서 시작하는 bfs를 수행하고, B층까지 가는데 드는 거리/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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n, m;
const ll D = 100000;
ll visited[101010];
ll prv[101010];
vector<ll> adj[101010];
int main(){
memset(visited,-1,sizeof(visited));
fast;
cin>>n>>m;
for(int i = 1 ; i <= m ; i++){
ll a,b; cin>>a>>b;
for(int j = a ; j <= n ; j += b)adj[j].push_back(i+D), adj[i+D].push_back(j);
}
ll s,e; cin>>s>>e;
queue<ll> q;
visited[s]=0;
q.push(s);
while(q.size()){
auto cur = q.front(); q.pop();
for(auto next : adj[cur])if(visited[next]<0){
visited[next] = visited[cur]+1;
q.push(next);
prv[next]=cur;
}
}
if(visited[e]<0)return cout<<-1,0;
cout<<visited[e]/2<<"\n";
vector<ll> v;
for(ll i = e ; i != s ; i = prv[i])if(i>D)v.push_back(i-D);
for(int i = v.size()-1 ; i >= 0 ; i--)cout<<v[i]<<"\n";
}
2594 - 놀이공원 (고2, Silver III)
문제
- 놀이공원은 10시에 열리고 22시에 닫힌다. N개의 놀이기구가 있고 운행 시작,종료 시간이 [hhmm] 꼴로 주어진다. 어떤 놀이기구의 운행 시간과 운행 시작 10분 전, 운행 종료 10분 후엔 쉴 수 없다. 놀이공원이 열려 있을 때 연속하게 쉴 수 있는 최대 시간을 분단위로 구하시오.
풀이
더보기
모두 분단위로 통일하고 imos법을 이용하면 된다.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll arr[1444];
int main(){
arr[600]++; arr[1321]--;
fast;
cin>>n;
while(n--){
ll a,b; cin>>a>>b;
a = a/100*60 + a%100;
b = b/100*60 + b%100;
arr[a-10]++; arr[b+10]--;
}
ll cnt=0,ans=0;
ll cur=0;
for(int i = 1 ; i <= 1440 ; i++){
cur += arr[i];
if(cur!=1)ans = max(ans,cnt),cnt=0;
else if(600<=i and i<1320)cnt++;
}
cout<<ans;
}
1665 - 화물열차 (중5/고4, Platinum I)
문제
- 크기 10^9인 두 화물열차가 앞부분끼리 마주보며 위치하고 있다. 각 화물열차에는 화물이 있는 연속한 구간이 각각 N,M(<=1000)개 있다. 한 화물열차를 옮겨서 최대한 화물이 많이 겹치게 하는 이동 횟수를 출력하시오.
풀이
더보기
imos 느낌의 스위핑을 해줘야 한다. 핵심 아이디어는, 2개의 화물 덩어리'만' 보았을 때 겹치는 화물의 개수가 어떻게 변화하는지 보는 것이다. 크게 5가지 정도의 경우가 있다.
(1) 아직 둘이 겹치지 않은 경우
(2) 겹쳤고 아직 겹칠게 남은 경우
(3) 겹쳤고 겹치는 개수에 변화가 없는 경우
(4) 겹쳤고 앞으로 겹친게 점점 사라지는 경우
(5) 다시 겹치지 않는 경우
누적합 관점에서 봤을 때 (2)가 처음 시작되는 지점부터 (3)이 시작되는 지점까지는 +1씩 해줘야 하고, (3)부터 (4)까지는 0, (4)부터 (5)까지는 -1, (5)부터는 다시 0이다. 근데 구간 크기가 10^9이므로 저 큰 구간에 다 1씩 더하고 뺄 순 없다. 따라서 시작지점에만 +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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n, m;
vector<P> v, e;
vector<P> c;
int main(){
fast;
cin>>n;
v.resize(n);
for(auto &[a,b] : v)cin>>a>>b;
cin>>m;
e.resize(m);
for(auto &[a,b] : e)cin>>a>>b;
//a+b-1에 a,b 만남
for(auto [si,ei] : v){
for(auto [sj,ej] : e){
c.push_back({si+sj-1,1}); //si,sj가 만날 때 imos +1
c.push_back({si+ej-1+1,-1}); //만나고 바로 뒤부터 -1.
c.push_back({sj+ei-1+1,-1}); //위와 순서는 고려안해도 됨, 만나고 바로 뒤부터 -1.
c.push_back({ei+ej-1+1+1,1}); //만나고 1칸뒤까지 -1되므로 그 다음칸에 +1
}
}
sort(all(c));
ll ans = 0, p = 0, mv=0;
ll imos = 0;
ll prvx = 0;
for(auto &[X,d] : c){
p += imos*(X-prvx);
if(p>ans)ans = p, mv = X-1;
prvx = X;
imos += d;
}
cout<<mv;
}
2595 - 배수 (고5, Platinum I)
문제
- N(<=30000)의 배수 중 자릿수를 이루는 숫자의 종류가 가장 작은 수를 구하시오. 여러개 있다면 가장 작은 수를 출력한다.
풀이
더보기
이딴 문제가 그래프 모델링이다. 0~N-1까지의 정점을 만들자. 이는 N으로 나눈 나머지를 의미한다. 그리고 간선을 잇기 전에, 자릿수를 구성할 숫자 집합을 미리 설정해둔다. 이 집합은 최대 2^10개(0~9)가 가능하다. 이제 bfs를 수행해줄 건데, i번 정점에서는 (10i+s) mod N(s:숫자 집합에 있는 수)으로 간선을 이어준다. 이는 자릿수에 s를 추가함을 의미한다. 이제 0을 제외한 s를 큐에 넣고 0번 정점까지 bfs를 해준 후 역추적하여 수를 구성해주면 된다. 이 때 간선 추가 순서와 정렬을 통해 최소이면서 최소 개수인 수를 구해주면 된다.
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 998244353
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
bool visited[30303];
ll POW10[30303];
pair<ll,ll> prv[30303]; //이전, 쓴거
string NO="#";
string bfs(vector<ll> &v){
memset(visited,0,sizeof(visited));
memset(prv,-1,sizeof(prv));
queue<ll> q;
for(auto i : v)if(i>0)q.push(i%n), visited[i%n]=1;
while(q.size()){
ll cur = q.front(); q.pop();
if(!cur){
string ret;
for(ll i = cur ; i != -1 ;){
if(prv[i].second==-1)ret += char(i+'0');
else ret += char(prv[i].second+'0');
i = prv[i].first;
}
reverse(all(ret));
return ret;
}
for(auto next : v){
ll nxt = (cur*10+next)%n;
if(visited[nxt])continue;
visited[nxt]=1;
prv[nxt] = {cur,next};
q.push(nxt);
}
}
return NO;
}
vector<vector<ll>> candidate;
bool cmp(vector<ll> a, vector<ll> b){
if(a.size()^b.size())return a.size()<b.size();
return a<b;
}
bool cmp2(string s, string t){
ll bit=0,bit2=0;
for(auto i : s)bit |= (1<<i-'0');
for(auto j : t)bit2 |= (1<<j-'0');
if(__builtin_popcount(bit) != __builtin_popcount(bit2))return __builtin_popcount(bit) < __builtin_popcount(bit2);
if(s.size()^t.size())return s.size()<t.size();
return s<t;
}
void init(){
for(int i = 0 ; i < (1<<10) ; i++){
vector<ll> v;
for(int j = 0 ; j < 10 ; j++){
if(i&(1<<j))v.push_back(j);
}
candidate.push_back(v);
}
sort(all(candidate),cmp);
}
int main(){
fast;
init();
cin>>n;
vector<string> ans;
for(auto v : candidate){
string s = bfs(v);
if(s!=NO)ans.push_back(s);
}
sort(all(ans),cmp2);
cout<<ans[0];
}'대회 > KOI' 카테고리의 다른 글
| 와 이걸 왜 대회 때 못풀었지 (0) | 2024.07.06 |
|---|---|
| KOI 2024 일기 (1) | 2024.05.12 |
| KOI 지역본선 2004 (0) | 2023.10.09 |
| KOI 2023 2차 대회 중등부 후기 (2) | 2023.07.17 |
