AtCoder Beginner Contest 389

A - 9x9

O(1)

aはS[0] = '0'。
bはS[2] = '0'。
で求めることができます。

C++

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 a = (s[0] - '0');
    int b = (s[2] - '0');
    cout << a * b << endl;
    return 0;
} 

B - tcaF

O(N)
入力であるXは、N!であることが保証されています。
Xを1から順番に、インクリメントした変数で除算をしていきます。
Xが1になった時、答えが求まります。

C++

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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

    ll ans = 1;
    while(X / ans > 1){
        X /= ans;
        ans++;
    }
    cout << ans << endl;

    return 0;
} 

C - Snake Queue

O(N)
1の時、最後尾に要素を追加。
2の時、先頭の要素を削除。
3の時、先頭からK個目の要素を求める。

3の時にO(1)で処理できるかを考察する必要があります。
下記は、dequeのコンテナに直接のアクセスをしてk個目の要素を求めています。

C++

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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

    deque<pair<ll, ll>> que;
    ll m = 0;
    rep(i, Q){
        int q;
        cin >> q;

        if(q==1){
            int l;
            cin >> l;
            if(que.size() == 0){
                que.push_back({0, l});
            }else{
                que.push_back({que.back().first + que.back().second, l});
            }
        }

        if(q==2){
            m += que.front().second;
            que.pop_front();
        }

        if(q==3){
            int k;
            cin >> k;
            k--;
            cout << que[k].first - m << endl;          
        }
    }

    return 0;
} 

dequeのコンテナにアクセスするのは、言語のアップデート次第で出来なくなる可能性を含めています。
dequeは正攻法の解法ではありません。
vectorを使用してコーディングしましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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

    vector<pair<ll, ll>> A;
    ll idx = 0;
    ll d = 0;
    rep(i, Q){
        int q;
        cin >> q;

        if(q==1){
            int l;
            cin >> l;
            A.push_back({d, l});
            d += l;
        }

        if(q==2){
            idx++;
        }

        if(q==3){
            int k;
            cin >> k;
            k--;
            cout << A[idx + k].first - A[idx].first << endl;          
        }
    }

    return 0;
} 

正攻法の解法になりましたね。

D - Squares in Circle

O(N)
尺取法の問題です。
円の第1象限を考察します。

1. y=Rからy=0までループします
2. xを1からインクリメントします

下記の画像がイメージです。
赤の部分を考察しています。

判定式は、

(x+0.5)^2+(y+0.5)^2<=R^2

整数で判定したいので両辺に4をかけます。

(2x+1)^2+(2y+1)^2<=R^2*4

円の第1象限でカウントしたマスの数をansとして、
円の全てのマスの数は、ansを4倍して(0, 0)のマスを１つ追加した数が答えになります。
式は、

ans * 4 + 1

となります
考察ができたので実装します。

C++

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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; }

void solve(ll r){
    
    auto f = [&](ll x, ll y) -> bool {
        x = x*2+1;
        y = y*2+1;
        return x*x+y*y <= r*r*4;
    };

    ll x = 0;
    ll ans = 0;
    for(ll y=r; y>=0; y--){
        while(f(x+1, y)) x++;
        ans += x;
    }

    cout << ans * 4 + 1 << endl;
}

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

    solve(R);
    
    return 0;
}