yukicoder No.491 10^9+1と回文
問題概要
1以上N以下の整数で、109 + 1 の倍数かつ回文の数の個数を求めな
解法
109+1の倍数かつ回文になるには, 109+1に回文をかければ良い. よって,
Nを109+1で割った数以下の整数で, 回文の個数を数えれば良い.
よって, dfsを用いて, その整数の桁数以下の桁数で作れる回文を作成し, その整数以下であるかをしらべてカウントした. 回文なので, 右半分は左半分と一致しているので, 左半分を作ったら, ひっくり返して右側にくっつければよい. 奇数桁の時は真ん中に注意.
もっと単純にできる. N <= 1018よりN/(109+1)は109以下の整数になり, 回文の条件より, 左半分の5桁までを全探索すれば, すべての回文数を列挙できる.
ミス
もっと単純に全探索すればよかった.
int main(void){ ll n; cin >> n; ll cnt = 0; ll m = n / (1000000001); set<ll> se; for (int i = 1; i <= 100000; ++i){ string left = to_string(i); string right = left; reverse(all(right)); string even = left + right; string odd = left + right.substr(1); se.insert(stoll(odd)); se.insert(stoll(even)); } for(auto u : se) if(u <= m) cnt++; printf("%lld\n", cnt); return 0; }
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; set<string> tmp; void dfs(string s, int cnt, int size){ if(cnt == size){ tmp.insert(s); return; } if(cnt < size / 2){ rep(i, 10){ string d = to_string(i); dfs(s + d, cnt + 1, size); } } if(cnt >= size / 2){ auto left = s; auto right = s; reverse(all(right)); if(size % 2 == 1){ rep(i, 10){ string d = to_string(i); tmp.insert(left + d + right); } }else{ tmp.insert(left + right); } } return; } ll solve(ll n){ ll ret = 0; string s = to_string(n); reps(cnt, 1, s.size() + 1){ reps(i, 1, 10){ auto d = to_string(i); dfs(d, 1, cnt); } } for(auto u : tmp){ ll d = stoll(u); if(d <= n) ret++; } return ret; } int main(void){ ll n; cin >> n; n /= (INF + 1); printf("%lld\n", solve(n)); return 0; }