흑흑...
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()
void solve() {
int n; cin >> n;
int m = (n/100+1)*100;
cout << m-n;
}
처음에는 floor 넣었다가 WA 먹고서 아, ceil이군! 하고 내려다가 멈칫하고 +1로 써서 냈습니다.
제목 읽기 거지같다는 것이 문제를 나타냅니다.
읽기 거지같은 문자열인가?
가 문제의 쿼리입니다.
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 공부의 보람을 느끼는 순간이였습니다.
단순한 구현 문제였습니다.
앳코더에 항상 자릿수 관련 문제가 자주 출제되는데, 아직 미숙해서 구현이 느리네요ㅠ
함수명도 살짝 거지같은 면이 없지 않습니다...
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);
}
이 문제는 전형적인 parametric search임에도 불구하고, 안 틀리기 어렵습니다.
그 이유는 크게 2가지입니다.
1. 수의 크기가 미친듯이 크다
2. 서로 달라야 한다
일단, 수의 크기는 너무 커서 long long
말고 __int128_t
를 사용하는 편이 현명합니다. 저도 2월달에 풀었을 때는 clang이라서 못 써서 많이 아쉬웠습니다.
서로 달라야 한다는거는 의 가짓수를 세야 한다는 문제의 본분을 망각했을 때,
인 케이스에서 가능한 의 개수가 무수히 많다고 판단하면 안 된다는 점입니다.
몇 개월만에 풀었고, 너무 속시원하네요..!
#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);
}
공사 할 수 있을까..?
이건 공사 못 하겠지..?