AtCoder Beginner Contest 363

A - Piling Up

O(1)
表示される ^ の数を現在より増やすために必要なのは、1と10の位の２桁に加算して100の位の数を変更できる数を求める事です。

A = 100 - (R % 100)

Aを加算すると100の位の数が変わります。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int R;
    cin >> R;
    R = R % 100;
    cout << 100 - R << endl;
    return 0;
} 

B - Japanese Cursed Doll

O(N)
シミュレートしましょう。
L_iの長さは1以上です。
L_iをループ文で0からTの長さまで加算して判定します。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, T, P;
    cin >> N >> T >> P;
    vector<int> L(N);
    rep(i, N) cin >> L[i];

    for(int i=0; i<T; i++){
        int cnt = 0;
        for(int j=0; j<N; j++){
            if(L[j] + i >= T){
                cnt++;
            }
        }
        if(cnt>=P){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
} 

C - Avoid K Palindrome 2

O(N! * K)

Sの文字を並び替えて得られる文字列（S自身を含む）であって、

から、順列全探索であることがわかります。
また順列全探索した文字列を、

長さNの文字列Tが「長さKの回文を部分文字列として含む」とは、
ある(N−K)以下の非負整数iが存在して、1以上K以下の任意の整数jについて
Ti+j=Ti+K+1−j
​が成り立つ

にて回文が含まれているか判定します。
これは問題文通りに実装できるかの実装問題です。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, K;
    cin >> N >> K;
    string s;
    cin >> s;
    sort(s.begin(), s.end());

    int ans = 0;
    do {
        int ok = 1;
        for(int i=0; i<=N-K; i++){
            string a, b;
            for(int j=0; j<K; j++){
                a += s[i+j];
                b += s[i+K-j-1];
            }
            if(a==b) ok=0;
        }
        if(ok) ans++;
        
    } while (next_permutation(s.begin(), s.end()));
    cout << ans << endl;

    return 0;
} 

D - Palindromic Number

回文数の規則性を見つけましょう。
1番目の回文数は0です。
0は特別なパターンとして、最初に処理をしましょう。

if(N == 1){
    cout << 0 << endl;
    return 0;
}
N--;

Nを1引いて、1番目の回文数を1として考察していきます。

桁数	1	2	3	4	5
回文数の最小値	1	11	101	1001	10001
回文数の最大値	9	99	999	9999	99999
回文数の数	9	9	90	90	900

表からN桁の回文数の数は、

9 * 10 ^ {(桁数 - 1) / 2}

と表すことができます。
各桁毎の回文数をNから引いていくと、答えはketa桁目のn番目の回文数になることが分かります。

for(ll keta=1; ; keta++){
    ll l = (keta - 1) / 2;
    ll num = 9;
    rep(i, l) num *= 10;
    if(N > num){
        N -= num;
        continue;
    }
}

では5桁の133番目の回文数を求めてみましょう。
回文数はK桁の上位(K+1)/2の桁の数が分かると残りも求めることができます。
上位(K+1)/2の桁の数は、

(5+1)/2 = 3

23232の場合、上位3桁の232を求める事ができれば、残りの32も求める事ができます。
5桁の上位3桁について、最初の数は100になります。
133番目の回文数なので、100に133を加算します。
101の開始ではなく、100の開始なので1を減算します。

// 5桁の上位3桁について、最初の数を求めます。
// numを9で除算をすると求める事ができます
// 900 / 9 = 100
num = num / 9
// 133番目の回文数なので、100に133を加算します。
// 101の開始ではなく、100の開始なので1を減算します。
N = num + N - 1

コードをまとめます。

N += num / 9 - 1

5桁の133番目の回文数について、上位3桁は232だということが分かりました。
回文数の半分を求めることができたので232をコピーして繋ぎ合わせます。
232232だと6桁になるので、前半部分の最後か、後半部分の最初の数を削除しましょう。

"23232" = "23" + "232"

文字列として扱うと、数のリバースと繋ぎが簡単にできます。
考察ができたのでコーディングしましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N;
    cin >> N;

    if(N==1){
        cout << 0 << endl;
        return 0;
    }
    N--;

    for(ll keta=1; ; keta++){
        ll l = (keta - 1) / 2;
        ll num = 9;
        rep(i, l) num *= 10;
        if(N > num){
            N -= num;
            continue;
        }

        N += num / 9 - 1;
        string s = to_string(N);
        string rs = s;
        reverse(rs.begin(), rs.end());
        if(keta&1) s.pop_back();
        cout << s << rs << endl;
        break;
    }

    return 0;
}