Codeforces Round #653 (Div. 3) A ~ E1 풀이
A. Required Remainder (800)
x, y ,n이 주어지고 k mod x = y가 되는 n이하의 최댓값 k를 찾는 문제.
어차피 n의 제한이 10^9이니 완전탐색은 택도 없을거라고 생각했다.
테스트케이스를 보고 12345를 일단 7로 나눠봤다.
1763이 나왔다. 이것을 7로 곱해보았다.
12341이 나왔다.
여기에는 5를더했을 때 12346이 나오므로 n인 12345보다 커지므로 답이 될 수 없다.
그래서 1762를 곱해보았다.
여기에 5를 더하면 12339로 답이 나오게된다.
이것을 토대로 생각했다. n을 x로 나눈 몫과 그걸 -1한값과 +1한값 3개 중에 답이 있겠구나하고.
따라서 (n / x - 1) * x + y과 (n / x) * x + y과 (n / x +1) * x + y 이 세 개의 수중 n보다 작은값에 한해서 최댓값을
구해 출력했다.
4분 AC
아래는 소스코드이다.
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> T;
while(T--) {
ll x, y, n;
cin >> x >> y >> n;
ll f = (n / x - 1) * x + y;
ll s = (n / x) * x + y;
ll t = (n / x + 1) * x + y;
if(t <= n) {
cout << t << endl;
cont;
}
else if(s <= n) {
cout << s << endl;
cont;
}
else {
cout << f << endl;
cont;
}
}
}
B. Multiply by 2, divide by 6 (900)
수를 1로 만들어야 한다.
할 수 있는 연산은 곱하기2 또는 나누기6이다.나누기 6이 의미하는 것은 무엇일까? 2로나누고 3으로 나눌 수 있다는 것이다. 따라서 소인수분해 했을 때 2의 지수와 3의 지수를 한개씩 감소시킬 수 있다.
곱하기 2는 소인수분해 했을 때 2의 지수를 1 증가 시킬 수 있다는 것이다.
주어진 수를 2와 3으로만 소인수분해하자.2와 3으로 소인수분해를 했을때 수가 1이 아니라면 주어진 연산으로는 절대 1을 만들 수 없다.2의 지수가 3의 지수보다크다면 절대 1을 만들 수 없다. 2는 추가할 수 있지만 3은 추가할 수 없기 떄문이다.
따라서 2의 지수, 3의 지수를 구하고 2의 지수를 3의 지수와 똑같이 만들어야 하기 때문에 (3의 지수 - 2의 지수) 만큼 연산 해준 뒤, 2의 지수와 3의 지수를 동시에 한개씩 감소시킬 수 있으므로 3의 지수만큼 더해주면 되겠다.
15분 AC
아래는 소스코드이다.
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> T;
while(T--) {
ll n;
cin >> n;
string s;
cin >> s;
ll open = 0;
ll close = 0;
ll diff = 0;
for(int i = 0 ; i < s.size() ; i++) {
if(s[i] == '(') open++;
if(s[i] == ')') {
if(open == 0) {
diff++;
}
else {
open--;
}
}
}
diff += open;
cout << diff / 2 << endl;
}
}
C. Move Brackets (1000)
소괄호로 이루어진 문자열이 주어졌을 때 특정 인덱스를 문장의 처음이나 끝으로 보낼 수 있을 때 짝이 맞는 괄호로 만들기 위한 연산의 최솟값을 찾는 문제.
간단하게 생각해보았다. 우선 맞지않는 괄호 갯수를 세었다. 이는 스택을 이용해도되고 변수를 이용해도 된다.
나는 변수를 이용했으며 '('가 없을 때 ')'가 들어온 갯수와 끝까지 가고나서 남은 '(' 의 갯수가 맞지 않는 괄호의 갯수가 될 것이다. '(' 를 처음으로 보내던지 ')'를 끝으로 보내던지 하면 되므로 (맞지않는 괄호 수 / 2)를 출력했다.
21분 AC
아래는 소스코드이다.
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> T;
while(T--) {
ll n;
cin >> n;
string s;
cin >> s;
ll open = 0;
ll close = 0;
ll diff = 0;
for(int i = 0 ; i < s.size() ; i++) {
if(s[i] == '(') open++;
if(s[i] == ')') {
if(open == 0) {
diff++;
}
else {
open--;
}
}
}
diff += open;
cout << diff / 2 << endl;
}
}
D. Zero Remainder Array (1400)
처음에 x = 0을 가지고 시작한다.
할 수 있는 연산은 두가지.
1. 배열의 원소 하나에 x를 더하고 x를 1 증가시킨다.
2. 그냥 x만 1 증가시킨다.
k가 주어졌을 때 모든 배열의 값을 k의 배수로 만들기 위해서는 연산을 몇번해야하는가?
우선 각 원소마다 몇번의 연산이 필요한지를 구했다.
예를들면 k = 3이고 원소가 1일 경우 두번의 연산이 필요하다. 따라서 k - (k % 3) 만큼의 연산이 필요한 것이다.
k의 제한이 10^9 이기떄문에 x를 0부터 하나하나 증가시켜가며 확인하는 것은 TLE를 발생시킨다.
k의 제한을 깜빡해 한번 TLE를 받았다.
어차피 x는 1만큼 증가되므로 해야하는 연산 수는 가장 많은 연산을 필요로 하는 원소의 필요 연산 수가 될거라는 것을 알았다. 그럼 이는 어떤 원소일까?
첫번째로 k - (k % 3) 가 많이 등장 했을수록. 한번 등장할 때마다 k번 다시 x를 더해줘야하기 때문이다.
두번째로 k - (k % 3) 가 높을수록이다.
따라서 map을 이용해 이를 찾고
1 + (k * (등장수 - 1)) + 필요 연산 수를 출력했다.
58분 AC
아래는 소스코드이다.
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> T;
while(T--) {
ll n, k;
cin >> n >> k;
vector<ll> arr;
map<ll, ll> m;
bool flag = false;
for(int i = 0 ; i < n ; i++) {
ll x;
cin >> x;
if(x % k != 0) {
flag = true;
m[k - x % k]++;
}
}
ll maxcnt = 0;
ll maxcur = 0;
if(!flag) {
cout << "0" << endl;
cont;
}
for(auto x : m) {
if(x.second >= maxcnt) {
maxcnt = x.second;
maxcur = x.first;
}
}
cout << 1 + (k * (maxcnt- 1)) + maxcur << endl;
}
}
E1. Reading Books (easy version) (1600)
책을 읽는 시간이 주어지고 이 책을 앨리스가 좋아하는지, 밥이 좋아하는지, 둘 다 좋아하거나 싫어하는지가 입력되고
k가 주어지며 앨리스가 k권 이상을 좋아하고 밥이 k권 이상을 좋아하게끔 책을 뽑았을 때 책을 읽는 시간의 합이 최소가 되는 값을 찾는문제.
불가능한 조건은 명확하다.
둘 다 좋아하는 책의 갯수 + 앨리스만 좋아하는책 < k OR 둘 다 좋아하는 책의 갯수 + 밥만 좋아하는책 < k 이면 어떻게 뽑아도 둘다 k권 이상을 좋아하게끔 만들 수 없으므로 -1을 출력하면 된다.
나머지는 구현으로 밀어붙였다.
쓰리 포인터를 이용해 둘 다 좋아하는 책을 우선적으로 뽑게끔한뒤 (단 그것이 이득인지 확인해야한다.)
한명만 좋아하는 책을 뽑도록 구현했다.
워낙 식정리가 안되어서 무작정 구현한 감이 있다.
1시간 52분 AC
아래는 소스코드이다.
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
vector<ll> a;
vector<ll> b;
vector<ll> t;
vector<ll> no;
ll ali = 0;
ll bo = 0;
ll ans = 0;
ll ap = 0;
ll bp = 0;
ll tp = 0;
ll np = 0;
ll n, k;
bool chk() {
if(ali >= k && bo >= k) {
return true;
}
return false;
}
void foo() {
while(ali < k && bo < k) {
if(a[ap] + b[bp] > t[tp]) {
if(tp == t.size() - 1) return;
ans += t[tp];
ali++;
bo++;
tp++;
if(ali >= k && bo >= k) return;
}
else return;
}
}
void giveali() {
if(ali < k) {
if(a[ap] >= t[tp]) {
if(tp == t.size() - 1) return;
ali++;
bo++;
ans += t[tp];
tp++;
}
else {
if(ap == a.size() - 1) return;
ali++;
ans += a[ap];
ap++;
}
}
}
void givebo() {
if(bo < k) {
if(b[bp] >= t[tp]) {
if(tp == t.size() - 1) return;
ali++;
bo++;
ans += t[tp];
tp++;
}
else {
if(bp == b.size() - 1) return;
bo++;
ans += b[bp];
bp++;
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> k;
for(int i = 0 ; i < n ; i++) {
ll cost, alice, bob;
cin >> cost >> alice >> bob;
if(alice == 1 && bob == 0) {
a.pb(cost);
}
else if(alice == 0 && bob == 1) {
b.pb(cost);
}
else if(alice == 1 && bob == 1) {
t.pb(cost);
}
else {
no.pb(cost);
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
sort(t.begin(), t.end());
sort(no.begin(), no.end());
if(a.size() + t.size() < k || b.size() + t.size() < k) {
cout << "-1" << endl;
return 0;
}
t.pb(1e15);
a.pb(1e15);
b.pb(1e15);
while(1) {
foo();
if(chk()) {
cout << ans << endl;
return 0;
}
if(ali > bo && bo < k) {
givebo();
}
else if(bo > ali && ali < k) {
giveali();
}
else {
if(chk()) {
cout << ans << endl;
return 0;
}
if(a[ap] > b[bp]) {
givebo();
}
else {
giveali();
}
}
foo();
if(chk()) {
cout << ans << endl;
return 0;
}
}
}