https://codeforces.com/contest/1650
Dashboard - Codeforces Round #776 (Div. 3) - Codeforces
codeforces.com
윽
Div. 3을 만만하게 본 나의 잘못.
아직 hack이 안 끝났다.
A.
해당 문자 c가 문자열에서 홀수 번째에 등장하는 경우가 있는지 확인하면 된다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
string s; cin >> s;
char c; cin >> c;
bool ans = false;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == c && i % 2 == 0) {
ans = true; break;
}
}
cout << (ans ? "YES" : "NO") << kEndl;
}
}
B.
나머지가 큰 경우가 무조건 이득이라는 결론에는 쉽게 도달했다.
그런데 틀렸다.
내가 내린 결론이 틀린 줄 알고 일단 넘어가서 C를 풀고 돌아왔다.
한참 고민하다가 3중 for문으로 l, r, a에 모두 1부터 100까지 대입해서 확인해봤는데, r % a == a - 1인 경우에 문제가 생겼다.
r 이하의 수 중 a로 나눈 나머지가 a - 1인 가장 큰 수를 구할 때 x = (r / a) * a - 1 라고 한 게 문제였다...
아........
이렇게 로직은 맞는 거 같은데 틀릴 때 앞으로는 일단 테스트를 돌려봐야겠다.
ㅠㅠ
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
ll l, r, a; cin >> l >> r >> a;
if (a == 1) {
cout << r << kEndl;
continue;
}
ll x = ((r + 1) / a) * a - 1;
if (x < l) {
x = r;
}
cout << x / a + x % a << kEndl;
}
}
C.
설명은 거창했지만 문제는 정말 간단했다.
결국 전체 합이 최소가 되길 바라는 것이기 때문에 weight가 작은 순서대로 2n개의 좌표를 고르고,
그것들을 다시 좌표를 기준으로 오름차순 정렬한 뒤 차례대로 좌표가 가장 작은 것과 가장 큰 것을 묶어주면 된다.
struct Data {
int cordinate;
int index;
ll weight;
};
bool SortByCordinate(Data a, Data b) {
return a.cordinate < b.cordinate;
}
bool SortByWeight(Data a, Data b) {
return a.weight < b.weight;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n, m; cin >> n >> m;
vector<Data> arr(m);
for (int i = 0; i < m; ++i) {
cin >> arr[i].cordinate >> arr[i].weight;
arr[i].index = i + 1;
}
sort(arr.begin(), arr.end(), SortByWeight);
vector<Data> ans(2 * n);
ll sum = 0;
for (int i = 0; i < 2 * n; ++i) {
ans[i] = arr[i];
sum += ans[i].weight;
}
sort(ans.begin(), ans.end(), SortByCordinate);
cout << sum << kEndl;
for (int i = 0; i < n; ++i) {
cout << ans[i].index << ' ' << ans[2 * n - 1 - i].index << kEndl;
}
cout << kEndl;
}
}
D.
C를 풀고 난 후 B를 고민하면서 이 문제도 같이 봤다.
처음에는 i가 증가하는 방향으로 고민했다.
i = 2일 때 어떤 상황이 생길 수 있는지, 그리고 그에 따라 i = 3일 때는 어떤 경우가 생길 수 있는지, 이런 식으로.
그러다가 갑자기 깨달아버렸다.
i = n일 때의 operation 결과를 보면 몇 번의 shift가 있었는지 바로 알 수 있다.
그리고 나면 i = n - 1일 때의 operation 결과를 얻을 수 있고, 이를 통해서 또 몇 번의 shift가 있었는지 알 수 있고...
이렇게 역으로 살펴보면 되는걸.
하......
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
deque<int> cur;
for (int i = 0; i < n; ++i) {
int input; cin >> input;
cur.push_back(input);
}
vector<int> ans(n + 1);
for (int i = n; i >= 2; --i) {
for (int idx = 1; idx <= i; ++idx) {
if (cur.front() == i) {
ans[i] = idx % i;
cur.pop_front();
break;
}
cur.push_back(cur.front());
cur.pop_front();
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
cout << kEndl;
}
}
E.
모든 케이스에 대해서 구현하면 되는 것 같다. 시간이 없어서 코드를 완성하진 못했다.
으-악.
문제를 푸는데 갑자기 너무 피곤했다.
다음 코포때는 몸 관리 잘하고 해야지...