LoginSignup
0
0
@RubyLrving(ruby lrving)

AtCoder Beginner Contest 369

Posted at

A - 369

O(N)
全探索
-100から199までを全探索しましょう。

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 A, B;
    cin >> A >> B;

    int ans = 0;
    for(int i=-100; i<200; i++){
        vector<int> v({A, B, i});
        sort(v.begin(), v.end());
        if(v[1] - v[0] == v[2] - v[1]) ans++;
    }
    cout << ans << endl;

    return 0;
}

O(1)
パターン分けをしましょう。

  • a == bの時
1 1 の時、1
2 2 の時、2
3 3 の時、3

xは1通りです。

  • (a + b) / 2 % == 0 の時
3 5 の時、1 4 7
1 3 の時、-1 2 5

xは3通りです。

  • (a + b) / 2 % == 1 の時
3 4 の時、2 5
1 4 の時、-2 7

xは2通りです。

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 A, B;
    cin >> A >> B;

    if(A == B){
        cout << 1 << endl;
    }else if((A+B) % 2 == 0){
        cout << 3 << endl;
    }else{
        cout << 2 << endl;
    }

    return 0;
}

B - Piano 3

O(N)
全探索です。

LとRでパターン分けをして実装しましょう。

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> L, R;
    rep(i, N){
        int a;
        char s;
        cin >> a >> s;
        if(s == 'L') L.push_back(a);
        if(s == 'R') R.push_back(a);
    }

    int ans = 0;
    for(int i=1; i<L.size(); i++){
        ans += abs(L[i] - L[i-1]);
    }
    for(int i=1; i<R.size(); i++){
        ans += abs(R[i] - R[i-1]);
    }
    cout << ans << endl;

    return 0;
}

C - Count Arithmetic Subarrays

O(N)
尺取り法です。
「条件」を満たす区間 (連続する部分列) を数え上げよ。
という時に使用できます。
今回の条件は等差数列です。

配列Aが等差数列の条件は、

（right < N）の時、
    （right > left + 1）の時、
        A[right] - A[right-1] == A[right-1] - A[right-2]

rightを加算しましょう。
leftをfor文で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() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll right = 0;
    ll ans = 0;
    for(ll left = 0; left < N; left++){
        while(right < N){
            if(right > left + 1 && A[right] - A[right-1] != A[right-1] - A[right-2]) break;

            right++;
        }
        ans += right - left;
    }
    cout << ans << endl;

    return 0;
}

D - Bonus EXP

O(N)
動的計画法です。
状態の変化である漸化式は、

  • 0 ~ Nまでのモンスター
  • 0, 1のモンスターを倒した時は奇数か偶数
    の２点を管理します。
（モンスターを倒した時に偶数になる）
    モンスターを倒さない場合は、一つ前の偶数の値を取得。
    モンスターを倒す場合は、一つ前の奇数の値にA[i]*2を加算した値を取得。
    dp[i+1][0] = max(dp[i][0], dp[i][1] + A[i] * 2)
（モンスターを倒した時に奇数になる）
    モンスターを倒さない場合は、一つ前の奇数の値を取得。
    モンスターを倒す場合は、一つ前の偶数の値にA[i]を加算した値を取得。
    dp[i+1][1] = max(dp[i][1], dp[i][0] + A[i])

N匹から高橋君が得た経験値の合計としてあり得る最大の値の取り出し方は、

max(dp[N][0], dp[N][1])
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;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<vector<ll>> dp(N+1, vector<ll>(2, 0));
    dp[0][1] = -1 * 2e18;

    for(int i=0; i<N; i++){
        dp[i+1][0] = max(dp[i][0], dp[i][1] + A[i] * 2);
        dp[i+1][1] = max(dp[i][1], dp[i][0] + A[i]);
    }

    cout << max(dp[N][0], dp[N][1]) << endl;

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