AtCoder Beginner Contest 251

## [A - Six Characters](https://atcoder.jp/contests/abc251/tasks/abc251_a)

O(6)
文字列を6回コピーして、先頭から６文字を出力。

```C++: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;

    string ans;
    for(int i=0; i<6; i++) ans+=s;
    cout << ans.substr(0, 6) << endl;

    return 0;
} 
```

## [B - At Most 3 (Judge ver.)](https://atcoder.jp/contests/abc251/tasks/abc251_b)

O(N^3)
300^3=27000000
全探索でいけますね。

```C++: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, W;
    cin >> N >> W;
    vector<int> A(N);
    for(auto &a:A) cin >> a;

    set<int> st;
    for(int i=0; i<N; i++){
        if(A[i]<=W) st.insert(A[i]);
        for(int j=i+1; j<N; j++){
            if(A[i]+A[j]<=W) st.insert(A[i]+A[j]);
            for(int k=j+1; k<N; k++){
                if(A[i]+A[j]+A[k]<=W) st.insert(A[i]+A[j]+A[k]);
            }
        }
    }
    cout << st.size() << endl;

    return 0;
} 
```

## [C - Poem Online Judge](https://atcoder.jp/contests/abc251/tasks/abc251_c)

O(N)
データ構造を使う問題です。
setかmapでいけます。

自分はソートを使用したので、O(NlogN)かな？

```C++: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;
    map<string, int> mp;
    vector<tuple<int, string, int, int>> vec;
    for(int i=0; i<N; i++){
        string s;
        int t;
        cin >> s >> t;
        mp[s]++;
        vec.push_back(make_tuple(i+1, s, t, mp[s]));
    }

    sort(vec.begin(), vec.end(), [](const auto&x, const auto& y){
        return get<2>(x) == get<2>(y)?   get<0>(x) < get<0>(y): get<2>(x) > get<2>(y);
    });

    for(auto &v:vec){
        if(get<3>(v)>1) continue;
        cout << get<0>(v) << endl;
        return 0;
    }
    cout << 0 << endl;

    return 0;
} 

```

## [D - At Most 3 (Contestant ver.)](https://atcoder.jp/contests/abc251/tasks/abc251_d)

O(297)

```C++: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 W;
    cin >> W;
    int N=99;
    cout << N*3 << endl;
    for(int i=1; i<=N; i++){
        cout << i << ' ';
        cout << i * 100 << ' ';
        cout << i * 10000 << ' ';       
        if(i==N) cout << endl;
        else cout << ' ';
    }

    return 0;
} 
```

## [E - Takahashi and Animals](https://atcoder.jp/contests/abc251/tasks/abc251_e)

```C++: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; }
 
ll INF = 2e18;
 
ll solve1(int N, vector<ll> A){
	vector<ll> dp(N+1, INF);
	dp[1] = dp[2] =  A[1];
 
	for(int i=3; i<=N; i++){
		dp[i] = min(dp[i-1] + A[i], dp[i-2] + A[i-1]);
	}
 
	return dp[N];
}
 
ll solve2(int N, vector<ll> A){
	vector<ll> dp(N+1, INF);
	dp[0] = dp[1] = A[N];
 
	for(int i=2; i<=N; i++){
		dp[i] = min(dp[i-1] + A[i], dp[i-2] + A[i-1]);
	}
 
	return dp[N-1];
}
 
int main(){
	ll N;
	cin >> N;
	vector<ll> A(N+1);
	for(int i=1; i<=N; i++) cin >> A[i];
	A[0] = INF;
	cout << min(solve1(N, A), solve2(N, A)) << endl;
 
	return 0;
}
```