12345678910

私の初投稿となります。
writer: くしらっちょ(@kusirakusira)
tester: Fplusさん(@FplusFplusF____)

【writer解法(627ms)】
書いてある数について順番に番号を付けます。 k番目の数を書いているときの「数字が何であるか」、「その数字の何桁目なのか」を求めることでO(loglogK)で答えを求めることが出来ます。
数字の桁数によって一つ数を大きくしたときの番号の大きくなり方が異なるので、n桁の数字が書き終わった後を記録しておきます。 計算量はO(TloglogK)です。

例) k=15の場合
「12の2桁目」 => 2

import bisect
t = int(input())
A = [0]
for i in range(1,20):
    A.append(A[i-1]+i*(9*pow(10,i-1)))

for a in range(t):
    n = int(input())
    idx = bisect.bisect_right(A,n) - 1
    
    q,r = divmod(n-A[idx], idx+1)
    if(r==0):
        q -= 1
    print(str(pow(10,idx)+q)[r-1])

【tester解法(580ms)】 1からxまでの整数の桁数の和をf(x)として、二分探索をして答えを求めます。 計算量はO(TlogN)です。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
const ll INF=(1ll<<60);
#define rep(i,n) for (ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
template<class T> void chmin(T &a,T b){
    if(a>b){
        a=b;
    }
}
template<class T> void chmax(T &a,T b){
    if(a<b){
        a=b;
    }
}
vector<ll> v(18),r(18);
ll f(ll x){
    ll s=to_string(x).size();
    return v[s-1]+(x-r[s]+1)*s;
}
void solve(){
    ll k;
    cin >> k;
    ll ok=0,ng=1e17;
    while(1<abs(ok-ng)){
        ll mid=(ok+ng)/2;
        if(f(mid)<k) ok=mid;
        else ng=mid;
    }
    string s=to_string(ng);
    cout << s[k-f(ok)-1] << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    r[1]=1;
    for(ll i=1;i<17;i++) r[i+1]=r[i]*10;
    for(ll i=1;i<=17;i++){
        v[i]=i*9*r[i];
    }
    rep(i,17) v[i+1]+=v[i];
    ll t;
    cin >> t;
    while(t--){
        solve();
    }
}