AtCoder Beginner Contest 235

A - Rotate

O(1)
A問題にしては難しいなと思いました。
数字を文字列として受け取って、文字を順番を変更します。

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() {
    string s;
    cin >> s;

    int abc = (s[0] - '0') * 100 + (s[1] - '0') * 10 + (s[2] - '0');
    int bca = (s[1] - '0') * 100 + (s[2] - '0') * 10 + (s[0] - '0');
    int cab = (s[2] - '0') * 100 + (s[0] - '0') * 10 + (s[1] - '0');

    cout << abc + bca + cab << endl;

    return 0;
}

B - Climbing Takahashi

O(N)
配列を０番目からループさせます。
次の要素が、現在の要素より大きいなら最大値を更新して次の要素を比較します。
小さいならループを終了します。

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;
    cin >> N;

    vector<int> H(N);
    rep(i, N) cin >> H[i];

    int ans=H[0];
    repx(i, 1, N){
        if(ans < H[i]) ans = max(ans, H[i]);
        else break;
    }
    cout << ans << endl;

    return 0;
}

C - The Kth Time Query

O(NlogN)
O(NQ)はTLEします。
こういう問題はデータ構造を使用します。
aの制約は10^9です。
10^9の配列は用意できないので、連想配列を使うと導けます。
今回はmapを使用します、map<int, vector<int>>型を考察できます。

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, Q;
    cin >> N >> Q;
    vector<int> a(N);
    rep(i, N) cin >> a[i];

    map<int, vector<int>> mp;
    rep(i, N){
        int index = a[i];
        mp[index].push_back(i+1);
    }

    vector<int> x(Q), k(Q);
    rep(i, Q) cin >> x[i] >> k[i];
    rep(i, Q){
        if(mp[x[i]].size()>k[i]-1) cout << mp[x[i]][k[i]-1] << endl;
        else cout << -1 << endl;
    }

    return 0;
}

D - Multiply and Rotate

O(NlogN)
この問題のポイントは、Nの制約が１０＾６であること。
６桁の数字なら配列を使用し、一度処理を通過したか判定できること。
10^6*10^6=10^12の為、オーバーフローを考慮する。

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 a, N;
    cin >> a >> N;
    ll M=1;
    while(M<N) M*=10;

    vector<ll> dp(M+1, -1);
    queue<ll> que;
    que.push(1);
    dp[1] = 0;
    while(que.size()){
        ll p = que.front();
        que.pop();

        ll d = p*a;
        if(d<=M && dp[d]==-1){
            dp[d] = dp[p] + 1;
            que.push(d);
        }
        if(p%10 != 0 && p>=10){
            string s = to_string(p);
            s = s[s.size()-1] + s.substr(0,s.size()-1);
            ll pp = stoi(s);
            if(pp<=M && dp[pp]==-1){
                dp[pp] = dp[p] + 1;
                que.push(pp);
            }
        }
    }
    cout << dp[N] << endl;

    return 0;
}