AtCoder Beginner Contest 192

흑흑...
A, B, C로 3솔 하고서
D번이 parametric search임을 알고있음에도 불구하고 오버플로우 지점을 찾지 못해 틀리고 말았다...

중간에 chrome 번역기 버튼이 사라져서 찾는 법을 알아보다가 10분을 날렸다.
그거 잘만 아꼈어도 D를 풀 수 있었을지 모르는데 말이다...
아마 D 제출 횟수가 너무 많아서 레이팅 내려갈 것 같다...

매크로 참고

using ll = long long;
#define EB emplace_back
#define REPh(i,a,b) for (int i = a; i < b; ++i)
#define REPc(i,a,b) for (int i = a; i <= b; ++i)
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)v.size()

A. Star

void solve() {
    int n; cin >> n;
    int m = (n/100+1)*100;
    cout << m-n;
}

처음에는 floor 넣었다가 WA 먹고서 아, ceil이군! 하고 내려다가 멈칫하고 +1로 써서 냈습니다.

B. uNrEaDaBIEsTrInG

제목 읽기 거지같다는 것이 문제를 나타냅니다.

읽기 거지같은 문자열인가?

가 문제의 쿼리입니다.

void solve() {
    bool chk = true; string s; cin >> s;
    for (int i = 0; i < sz(s); ++i) {
        if (~i&1) {
            if (isupper(s[i])) chk = false;
        } else {
            if (islower(s[i])) chk = false;
        }
    }
    cout << (chk ? "Yes" : "No");
}

i가 0부터 시작인데 착각해서 급히 '~'를 붙였습니다.
<cctype>의 isupper와 islower을 사용하면 간단하게 구현할 수 있습니다.
STL 공부의 보람을 느끼는 순간이였습니다.

C. Kaprekar Number

단순한 구현 문제였습니다.
앳코더에 항상 자릿수 관련 문제가 자주 출제되는데, 아직 미숙해서 구현이 느리네요ㅠ
함수명도 살짝 거지같은 면이 없지 않습니다...

int g1(int x) {
    int l = ceil(log10(x)), res = 0;
    vector<int> ans;
    int tenkth = 1;
    REPc(k,1,l) {
        ans.EB((x/tenkth)%10);
        tenkth *= 10;
    }
    sort(all(ans));
    tenkth = 1;
    REPh(k,0,l) {
        res += ans[k]*tenkth;
        tenkth *= 10;
    }
    return res;
}

int g2(int x) {
    int l = ceil(log10(x)), res = 0;
    vector<int> ans;
    int tenkth = 1;
    REPc(k,1,l) {
        ans.EB((x/tenkth)%10);
        tenkth *= 10;
    }
    sort(rall(ans));
    tenkth = 1;
    REPh(k,0,l) {
        res += ans[k]*tenkth;
        tenkth *= 10;
    }
    return res;
}

void solve() {
    int n, k; cin >> n >> k; //x는 음아정
    int a = n;
    while (k--) {
        a = g1(a)-g2(a);
    }
    cout << a;
}

하지만 C번에 대해 AtCoder의 코드가 훨씬 깔끔해서 함께 첨부해봅니다.
물론 시간은 제 코드가 더 빨라요! (어쩌라고)

#include<stdio.h>
int f(int n){
	int c[20]={};
	while(n){
		c[n%10]++;
		n/=10;
	}
	int g1=0,g2=0;
	for(int i=9;i>=0;i--)for(int j=0;j<c[i];j++)g1=g1*10+i;
	for(int i=0;i<=9;i++)for(int j=0;j<c[i];j++)g2=g2*10+i;
	return g1-g2;
}

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<k;i++)n=f(n);
	printf("%d\n",n);
}

D. Base n

이 문제는 전형적인 parametric search임에도 불구하고, 안 틀리기 어렵습니다.

그 이유는 크게 2가지입니다.
1. 수의 크기가 미친듯이 크다
2. 서로 달라야 한다

일단, 수의 크기는 너무 커서 long long 말고 __int128_t를 사용하는 편이 현명합니다. 저도 2월달에 풀었을 때는 clang이라서 못 써서 많이 아쉬웠습니다.

서로 달라야 한다는거는 $X_{(n)}$

몇 개월만에 풀었고, 너무 속시원하네요..!

#include <bits/stdc++.h>
using namespace std; using lint = __int128_t;
const lint M = 1000000000000000000;
string s; lint m, d;

bool ok(lint x) {
    lint sum = 0;
    for (char c : s) {
        sum += c-'0';
        if (sum > m) return false;
        sum *= x;
    }
    return true;
}

int main() {
    long long tmp; cin >> s >> tmp; m = tmp;
    for (char c : s) d = max(d,lint(c-'0'));
    lint x = d;
    if (size(s) == 1) {cout << (s[0]-'0' <= m); return 0;}
    for (lint b = M; b >= 1; b >>= 1)
        while (x+b <= M && ok(x+b)) x += b;
    cout << (long long)(x-d);
}

E. Train

공사 할 수 있을까..?

F. Potion

이건 공사 못 하겠지..?