CuteWisp

[C++] AtCoder Beginner Contest 213

09 Aug 2021 | PS

AtCoder Beginner Contest 213

결과

submission rating

Rating : 701 -> 740 (+39)

풀이

A

a

A - Bitwise Exclusive Or

정수 A,B 가 있을 때 A ^ C = B 가 되는 C를 구하는 문제

양변에 A를 xor 해주면 A ^ B = C 가 되므로 이를 출력하면 정답

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc213/tasks/abc213_a
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll a,b;
    cin >> a >> b;
    ll ans = a ^ b;
    cout << ans;

    return 0;
}
B

b

B - Booby Prize

N명의 플레이어 들이 A_i 만큼의 점수를 가지고 있고 낮은 점수가 높은 순위를 기록한다고 했을 때

뒤에서 2번째로 낮은 순위의 플레이어를 찾는 문제

점수와 몇번째 플레이어인지를 vector에 기록한 뒤 이를 Sorting 하여 뒤에서 두번째값의 플레이어 번호를 출력하면 정답

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc213/tasks/abc213_b
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    vector<pair<ll,ll>> v;
    rep(i,n){
        ll a;
        cin >> a;
        v.push_back({a,i+1});
    }
    sort(all(v));
    for(ll i = 0;i<n;i++){
        if(i == n-2){
            cout << v[i].second;
        }
    }

    return 0;
}
C

c

C - Reorder Cards

높이 H, 너비 W의 행렬이 있을 때 (A_i, B_i)의 위치에 정수 i가 쓰여져 있다.

아무것도 쓰여있지 않은 행과 열은 지워진다고 했을 때 마지막 행렬에서의 i가 쓰여있는 좌표를 순서대로 출력하는 문

HW 크기의 행렬을 모두 검사하여 체크하기엔 H,W 값이 10^9승 까지이기 때문에 당연히 TLE가 발생한다.

문제를 잘 살펴보면 입력받은 각각의 A_i, B_i 배열에서 오름차순으로 배열했을때 순서를 출력한다고 보면 된다.

즉 (A_i, B_i) 입력이 다음과 같이 주어졌을 때

2 4
5 6
3 4

출력은 다음과 같다

1 1
3 2
2 1

자세한 풀이는 아래 코드를 참고

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc213/tasks/abc213_c
bool sortbysec(const tl3& a, const tl3& b) { return (get<1>(a) < get<1>(b)); }
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll h, w, n;
    cin >> h >> w >> n;
    vector<tl3> a;
    vector<tl3> b;
    for (ll i = 1; i <= n; i++) {
        ll ta, tb;
        cin >> ta >> tb;
        a.push_back(make_tuple(ta, i, 0));
        b.push_back(make_tuple(tb, i, 0));
    }
    sort(all(a));
    sort(all(b));
    ll rep = 0;
    for(ll i = 0;i<n;i++) {
        if(i == 0) a[i] = make_tuple(get<0>(a[i]), get<1>(a[i]), i+1);
        else if(i != 0 && get<0>(a[i]) == get<0>(a[i-1])) {
            a[i] = make_tuple(get<0>(a[i]), get<1>(a[i]), get<2>(a[i-1]));
            rep++;
        }
        else a[i] = make_tuple(get<0>(a[i]), get<1>(a[i]), i+1-rep);  
    }
    rep = 0;
    for(ll i = 0;i<n;i++) {
        if(i == 0) b[i] = make_tuple(get<0>(b[i]), get<1>(b[i]), i+1);
        else if(i != 0 && get<0>(b[i]) == get<0>(b[i-1])) {
            b[i] = make_tuple(get<0>(b[i]), get<1>(b[i]), get<2>(b[i-1]));
            rep++;
        }
        else b[i] = make_tuple(get<0>(b[i]), get<1>(b[i]), i+1-rep);  
    }
    sort(all(a), sortbysec);
    sort(all(b), sortbysec);
    rep(i, n) { cout << get<2>(a[i]) << " " << get<2>(b[i]) << "\n"; }

    return 0;
}
D

d

D - Takahashi Tour

N개의 도시가 있으며 N-1개의 경로를 입력받는다.

타카하시가 도시 1에서부터 출발할 때 아래와 같은 규칙으로 출력이 발생한다.

  • 타카하시가 현재 위치한 도시에서 바로 접근할 수 있는 도시 중 방문하지 않은 도시가 있다면 작은 숫자의 도시부터 방문
  • 그렇지 않으면 , 타카하시가 현재 위치한 도시가 1이라면 끝
  • 1이 아니라면 이전에 있던 도시로 되돌아옴

위 조건은 평범한 DFS임을 알 수 있다. 하지만 입력받은 경로를 sorting하는 과정이 필요하다.

자세한 해답은 아래 코드 참고

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc213/tasks/abc213_d
vll path[202020];
bool isVisited[202020] = {0};
void dfs(ll start) {
    isVisited[start] = true;
    cout << start << " ";
    for (auto k : path[start]) {
        if (!isVisited[k]) {
            isVisited[k] = true;
            dfs(k);
            cout << start << " ";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    rep(i, n - 1) {
        ll a, b;
        cin >> a >> b;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    for (ll i = 0; i <= n; i++) {
        sort(all(path[i]));
    }
    dfs(1);

    return 0;
}

[C++] AtCoder Beginner Contest 198

30 May 2021 | PS

AtCoder Beginner Contest 198

풀이

A

A - Div

정수 N을 입력받았을 때

두 소년이 N개의 사탕을 분배할 수 있는 방법은 총 몇가지인지 묻는 문제

ex) 2명이 3개의 사탕을 분배하는 경우 -> (1,2) (2,1) 총 2가지 2명이 4개의 사탕을 분배하는 경우 -> (1,3) (2,2) (3,1) 총 3가지 …

N-1을 출력하면 정답

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc198/tasks/abc198_a
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    cout << n-1;

    return 0;
}
B

B - Palindrome with leading zeros

Leading Zero를 붙이거나 안붙였을때 펠린드롬이 되는지 여부를 확인하면 되는 문제

Leading Zero를 포함하는 펠린드롬이라면 원래 뒤에 0이 붙어있을 것이기 때문에 10으로 나눠질때 까지 나눠준 후 펠린드롬 여부를 확인하면 된다.

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc198/tasks/abc198_b
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    if(n == 0) {
        cout<<"Yes";
        return 0;
    }
    else {
        while(n%10 == 0)
            n/=10;
    }
    string s = to_string(n);
    string ss = s;
    reverse(all(s));
  
    if(ss == s) cout<<"Yes";
    else cout<<"No";

    return 0;
}
C

C - Compass Walking

R, X, Y를 입력받을 때 평면에서 한번에 R만큼의 거리를 갈 수 있다고 하자

(0,0)부터 시작해서 (X,Y)까지 도착하려면 총 몇번을 가야하는지 묻는 문제

도착 지점과 원점과의 거리가 R과 같다면 1 R 초과 2R 이하라면 2 이외의 경우에는 ceil(d/R)을 출력하면 정답

문제 이름대로 좌표평면에 원을 그려보면 쉽게 이해 가능

ss

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc198/tasks/abc198_c
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll r,x,y;
    cin >> r >> x >> y;
    ll len = x*x + y*y;
    ll ans = 0;
    if(len == r*r) cout << 1;
    else if(len < r*r) cout << 2;
    else{
        while(r*r*ans*ans<len){
            ans++;
        }
        cout << ans;
    }

    return 0;
}

[C++] AtCoder Beginner Contest 197

04 Apr 2021 | PS

AtCoder Beginner Contest 197

풀이

A

A - Rotate

3글자 문자열을 받아서 첫번째 문자를 맨뒤로 옮겨 출력하면 정답.

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc197/tasks/abc197_a
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;
    for(int i = 1;i<s.length();i++){
        cout << s[i];
    }
    cout << s[0];

    return 0;
}
B

B - Visibility

정해진 맵이 H,W 크기로 있다고 할 때 맵 상에서 가로와 세로 일직선으로 쭉 볼 수 있다고 하자

(X,Y) 좌표가 보이는 좌표는 총 몇 군데 인지 계산하는 문제

(X,Y)를 기준으로 상하좌우로 반복문을 돌려 장애물이 나올때 까지 세면 정답

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc197/tasks/abc197_b
ll h, w, x, y;
vector<string> s;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> h >> w >> x >> y;
    s.resize(h);
    rep(i, h) { cin >> s[i]; }
    ll ans = -3;
    x--;
    y--;
    for (ll i = x; i < h && s[i][y] != '#'; i++) ans++;
    for (ll i = x; i >= 0 && s[i][y] != '#'; i--) ans++;
    for (ll j = y; j < w && s[x][j] != '#'; j++) ans++;
    for (ll j = y; j >= 0 && s[x][j] != '#'; j--) ans++;

    cout << ans;

    return 0;
}
C

C - ORXOR

N개의 수를 입력받아 이를 두 그룹으로 나누어 한 그룹은 OR 나머지 그룹은 XOR을 한다고 할 때 최소값을 찾는 문제

N이 최대 20으로 작기 떄문에 모든 경우를 포함해도 시간내로 통과 가능

  
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc194/tasks/abc197_c
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    vll a(n);
    rep(i, n) { cin >> a[i]; }
    ll ans = INT_MAX;
    for (int i = 0; i < 1 << (n - 1); i++) {
        ll xor_ = 0;
        ll or_ = 0;
        for (int j = 0; j <= n; j++) {
            if (j < n) {
                or_ |= a[j];
            }
            if (j == n || (i >> j & 1)) {
                xor_ ^= or_ ;
                or_ = 0;
            }
        }
        ans = min(ans, xor_);
    }
    cout << ans;
    return 0;
}

[C++] AtCoder Beginner Contest 196

14 Mar 2021 | PS

AtCoder Beginner Contest 196

결과

submission rating

Rating : 616 -> 701 (+85)

풀이

A

A - Difference Max

a <= x <= b 이고 c <= y <= d 일때 x-y의 최대값을 찾아야 하므로 b - c 를 출력하면 된다.

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc196/tasks/abc196_a
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << b - c;

    return 0;
}
B

B - Round Down

소수를 입력받아 소수점 이하를 버리고 정수부분만 출력하는 문제

본인은 string으로 받아서 다시 출력하다가 소수점이 나오면 종료하는 방법으로 구현하였다.

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc196/tasks/abc196_b
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;
    for(auto k : s){
        if(k == '.') break;
        cout << k;
    }

    return 0;
}
C

C - Doubled

1부터 N까지의 수 중 짝수자리이고 앞의 절반과 뒤의 절반의 수가 동일한 수는 몇개가 있는지 찾는 문제

1부터 하나씩 증가해 가면서 해당 수를 두번 반복햇을 때 그 수가 N보다 작으면 계속 진행한다.

그렇게 N보다 커질때까지 계속 수행하면 조건에 맞는 모든 수의 갯수를 찾을 수 있다.

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc196/tasks/abc196_c
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    ll ans = 0;
    for(int i = 1;;i++){
        string str = to_string(i);
        str += str;
        ll temp = stol(str);
        if(temp <= n) ans++;
        else break;    
    }
    cout << ans;

    return 0;
}

[C++] AtCoder Beginner Contest 195 C번 Comma

14 Mar 2021 | PS

AtCoder Beginner Contest 195 C번 Comma

문제

https://atcoder.jp/contests/abc195/tasks/abc195_c abc195_c

풀이

N보다 낮은 자리수의 컴마의 갯수를 싹다 더하고

N과 같은 자리수에 컴마의 갯수를 더해주는 방법으로 구현했다.

근데 N <= 10^15 이므로 이걸 for문을 N번돌면서 하면 안된다…

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc195/tasks/abc195_c
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    ll ans = 0;
    ll temp = 0;
    for(int i = 0;temp <= n;i++){
        ll prevTemp = temp;
        temp = temp * 10 + 9;
        if(temp <= n){
            ans += (i/3) * (temp - prevTemp);
        }
        else{
            ans += (i/3) * (n - prevTemp);
        }
    }
    cout << ans;

    return 0;
}