KU01 2021 Round 1
KU01 2021 Round1
ในปีนี้การแข่งขัน KU01 จัดการแข่งขันในรูปแบบออนไลน์ ทำให้ผมมีโอกาสได้ลองทำโจทย์ในรอบแรกนี้
Pod
โจทย์ข้อนี้เป็นโจทย์ที่ค่อนข้างตรงคือ ในเวลา $i$ มีคนมาต่อแถวที่ $x$ โดย $1 <= x <= k <=300$ และ $1 <= i <= n <= 100,000$ ทำให้เราสามารถทำ $O(nk)$ ได้สบายๆ แต่ทว่าวิธีนี้ค่อนข้างช้าเราจึงจำเป็นต้องใช้คณิตศาสตร์มาช่วยคือ เราจะไม่ทำตรงๆ ตัดทุกๆ รอบที่ตัดได้ เราจะตัดรอบเดียวโดยหา min element ของอาเรย์ที่เราทำ counting sort ไว้ ทำให้สามารถทำใด้ใน $O(max(n, k))$
Full Soltion in C++
#include<bits/stdc++.h>
using namespace std;
int mp[333];
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int n, k;
cin >> n >> k;
for(int i=1; i<=n; ++i){
cin >> x;
mp[x]++;
}
int minn = 1e9 + 10;
for(int i=1; i<=n; ++i){
minn = min(mp[i], minn);
}
cout << n - minn * k;
return 0;
}
Running
ในข้อนี้เราได้รับระยะเวลาในการวิ่งของคน $n$ คนในหนึ่งรอบและจำนวน $k$ แทนจำนวนรอบที่จะวิ่ง
ในข้อนี้ถ้าเรามองเผินๆ ในการทำ brute force นั้นจะใช้เวลา $O(nk)$ ซึ่งมี $n <= 100,000$ และ $k<=100,000$ ทำให้ไม่ทันเวลา ดังนั้นเราจะต้องใช้คณิตศาสตร์ทำให้เวลาเหลือเพียง $O(nlogn)$ เพื่อลดเวลาในการคำนวณ โดยเราจำหา คนที่วิ่งเร็วที่สุดจากการ sort ($O(nlogn)$) หรือ การทำ sequential search ($O(n)$) แล้วให้คนที่วิ่งเร็วที่สุดวิ่งไป $k$ รอบ กล่าวคือ เมื่อ $a$ คือ เวลาที่ใช้น้อยที่สุดเวลาที่ใช้วิ่งคือ $ak$ หน่วยและการน็อครอบจะเกิดขึ้นเมื่อ เวลาที่ใช้วิ่ง $k - 1$ รอบของ $i$ ใดๆ น้อยกว่าหรือเท่ากับ $ak$ เมื่อ ความเร็วของ $i \neq a$
Full Solution in C++
#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
long long k, s;
int n, cnt = 0;
cin >> n >> k;
vector<long long> v(n);
for(auto &x: v){
cin >> x;
}
sort(v.begin(), v.end());
for(int i=1; i<n; ++i){
if(v[1] * k > v[i] * (k - 1)){
cnt++;
}
}
cout << cnt;
return 0;
}
MinMax
จากโจทย์เราได้รับตารางขนาด $n \times n$ โดยในตารางมีค่า $a_{i,j}$ โดยเราจะเลือกเลขที่ไม่เกิน $b$ มาเพื่อเพิ่มหรือลดค่าทั้งแถวได้แถวละหนึ่งครั้ง
วิธีการทำข้อนี้คือหาค่ามากที่สุดกับหาค่าที่น้อยที่สุดตั้งแต่เริ่มแล้วนำมาเป็นคำตอบแรก จากนั้นวนลูปเพื่อเลือกแถวที่จะลดค่ากับแถวที่จะเพิ่มค่า โดยใช้เวลาทั้งหมด $O(n^3)$ แต่สามารถ optimize ให้เหลือเพียง $O(n ^ 2)$ ได้
Full Solution in C++
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[33][33];
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int n;
ll b, minn = 1e9, maxx = -1e9;
cin >> n >> b;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
cin >> a[i][j];
minn = min(ninn, a[i][j]);
maxx = max(maxx, a[i][j]);
}
}
ll ans = maxx - minn;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(i == j){
continue;
}
maxx = -1e9;
minn = 1e9;
for(int k=1; k<=n; ++k){
minn = min({minn, a[i][k] + b, a[j][k] - b});
maxx = max({maxx, a[i][k] + b, a[j][k] - b});
}
ans = max(ans, maxx - minn);
}
}
cout << ans;
return 0;
}
Balance
จากโจทย์เราได้รับ Binary Tree มาและต้องทำให้ทุก Sub Tree มีผลรวม Child ซ้ายเท่ากับผลรวมของ Child ขวา
ในการทำข้อนี้สามารถทำได้ด้วยการ Depth First Search หรือทำ Dynamic Programming เราจะเฉลยในรูปแบบของ Depth First Search โดยเริ่มต้นเราจะสร้างกราฟที่เก็บ ชื่อไม้หรือน้ำหนัก
int n;
vector<pair<int, int>> adj[1010];
for(int i=1; i<=n; ++i){
cin >> opr >> x;
adj[i].emplace_back(x, opr);
cin >> opr >> x;
adj[i].emplace_back(x, opr);
}
จากตัวอย่าง $adj[u][0]$ จะเก็บ Child ทางซ้ายและ $adj[u][1]$ จะเก็บลูกขวาไว้จากนั้นเราจะเริ่ม Depth First Search จากโหนด $1$ โดย first จะเก็บว่าต้องไปโหนดไหนต่อ และ second ถ้าเป็น 1 จะเก็บว่าเป็นน้ำหนักส่วน 0 จะเป็นโหนดอื่น
int ans = 0;
int dfs(int u, int type){
if(type == 1){
return u;
}
int l = dfs(adj[u][0].first, adj[u][0].second);
int r = dfs(adj[u][1].first, adj[u][1].second);
ans += abs(l - r);
return max(l, r) * 2;
}
dfs(1, 0);
Full Solution in C++
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[1010];
int ans = 0;
int dfs(int u, int type){
if(type == 1){
return u;
}
int l = dfs(adj[u][0].first, adj[u][0].second);
int r = dfs(adj[u][1].first, adj[u][1].second);
ans += abs(l - r);
return max(l, r) * 2;
}
int main(){
cin.tie(nullptr)->ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i=1; i<=n; ++i){
cin >> opr >> x;
adj[i].emplace_back(x, opr);
cin >> opr >> x;
adj[i].emplace_back(x, opr);
}
dfs(1, 0);
cout << ans;
return 0;
}
author