LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 397

Posted at

A - Thermometer

O(1)
問題文通りに条件分岐を記載しましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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() {
    double x;
    cin >> x;

    if(x >= 38.0){
        cout << 1 << endl;
    }else if(x >= 37.5){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }

    return 0;
}

B - Ticket Gate Log

O(N)
Sの文字列を２文字毎に判定して、奇数のインデックスはio、偶数のインデックスはoiになっているか探索します。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 n = s.size();
    string t;
    int ans = 0;
    rep(i, n){
        if(t.size()%2==0 && s[i] == 'o'){
            t += 'i';
            t += 'o';
        }else if(t.size()%2==1 && s[i] == 'i'){
            t += 'o';
            t += 'i';
        }else{
            t += s[i];
        }
    }
    if(t.back() == 'i') t += 'o';
    cout << t.size() - s.size() << endl;
    return 0;
}

すぬけさんのコーディングです。
このコードのが綺麗ですね。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 n = s.size();
    int ans = 0;
    char target = 'i';
    rep(i, n){
        if(target != s[i]) ans++;
        else target = target == 'i'?'o':'i';
    }
    if(s.back() == 'i') ans++;
    cout << ans << endl;
    return 0;
}

C - Variety Split Easy

単純に全探索を行うとO(N^2)となってTLEになります。

O(NlogN)
全ての要素の値をキーにして個数を値として保持をするmapを用意します。
先頭からループして、種類数を保持するsetを用意します。
ループ中にsetへ値を追加、mapから個数を減算していき0になったらキーを削除します。

ans = max(ans, setのサイズ+mapのサイズ)

が答えになります。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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; }

void solve(int N, vector<int>& A){
    map<int, int> mp;
    rep(i, N) mp[A[i]]++;

    int ans = 0;
    set<int> st;
    rep(i, N-1){
        st.insert(A[i]);
        if(mp.find(A[i]) != mp.end()){
            mp[A[i]]--;
            if(mp[A[i]] <= 0){
                mp.erase(A[i]);
            }
        }
        int m = st.size() + mp.size();
        ans = max(ans, m);
    }
    cout << ans << endl;
}

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

    solve(N, A);

    return 0;
}

もっといいコーディングはないか調べました。
双方向の配列を用意するのが良いですね。
公式の解説動画のコードです。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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; }

void solve(int N, vector<int>& A){
    vector<int> numl(N+1), numr(N+1);
    {
        set<int> st;
        rep(i, N){
            st.insert(A[i]);
            numl[i+1] = st.size();
        }
    }
    {
        set<int> st;
        for(int i=N-1; i>=0; i--){
            st.insert(A[i]);
            numr[i] = st.size();
        }
    }

    int ans = 0;
    for(int i=1; i<N; i++){
        ans = max(ans, numl[i] + numr[i]);
    }
    cout << ans << endl;
}

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

    solve(N, A);

    return 0;
}

D - Cubes

数学の問題です。
x^3 - y^3を因数分解します。

(x-y) * (x^2 + xy + y^2)

x > yであり、xとyの差分は0以上だと分かります。
xを、

x = y + d

として、x^3 - y^3の式を考察します。

x^3 - y^3 = (y+d)^3 - y^3

(y+d)^3 - y^3 = y^3 + 3y^2d + 3yd^2 + d^3 - y^3 = d^3 + 3y^2d + 3yd^2

d^3 + 3y^2d + 3yd^2 = d^3 + 3yd * (y+d)

よって、

N = d^3 + 3yd * (y+d)

\frac{(N - d^3)}{3d} = y * (y+d)

\frac{(N - d^3)}{3d} = c

として、

y^2 + dy - c = 0

yは、解の公式から

y = \frac{-d * \sqrt{d^2 + 4 * 1 * c}}{ 2 * 1 }

この式をもとに全探索を行います。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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;

    for(ll d = 1; d * d * d < N; d++){
        ll c = N - d * d * d;
        if(c % (3 * d)) continue;
        c /= 3 * d;
        ll y = (sqrt(d * d + 4 * c) - d) / 2;
        if(y * y + d * y - c == 0){
            cout << y+d << ' ' << y << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}

忘れないように１週間に１回、あと５回ぐらい解こうと思います。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?