AtCoder Beginner Contest 271

## [A - 484558](https://atcoder.jp/contests/abc271/tasks/abc271_a)

O(1)
16進数に直して0パディング。

```C++:C++
#include <bits/stdc++.h>
using namespace std;
int main() {
    
	int N;
	cin>>N;
	
	int a,b;
	a = N/16, b = N%16;
	
	if(a<=9)cout<<a;
	else cout<<(char)('A'+a-10);
	
	if(b<=9)cout<<b;
	else cout<<(char)('A'+b-10);
	
	return 0;
}
```

## [B - Maintain Multiple Sequences](https://atcoder.jp/contests/abc271/tasks/abc271_b)

O(N)
グラフを作成して出力。

```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, Q;
    cin >> N >> Q;
    vector<vector<int>> A(N, vector<int>());
    for(int i=0; i<N; i++){
        int L;
        cin >> L;
        for(int j=0; j<L; j++){
            int a;
            cin >> a;
            A[i].push_back(a);
        }
    } 

    for(int i=0; i<Q; i++){
        int s, t;
        cin >> s >> t;
        s--;
        t--;
        cout << A[s][t] << endl;
    }

    return 0;
} 
```

## [C - Manga](https://atcoder.jp/contests/abc271/tasks/abc271_c)

O(N)
sort、uniqueしてdequeにpush_back。
frontから冊数Noをチェックして、存在しないなら最後から２つ消して冊数Noをpush_front。

```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;
    deque<int> dque;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    unique(A.begin(), A.end());
    for(int i=0; i<N; i++) dque.push_back(A[i]);    

    int index=1;
    while(dque.size()){
        int p = dque.front();
        if(index == p){
            dque.pop_front();
            index++;
        }else{
            int cnt=2;
            while(cnt>0){
                if(dque.size()>0) dque.pop_back(), cnt--;
                else break;
            }
            if(cnt==0) dque.push_front(index);
            else break;
        }
    }
    cout << index-1 << endl;

    return 0;
} 
```

## [D - Flip and Adjust](https://atcoder.jp/contests/abc271/tasks/abc271_d)

O(NS)
動的計画法！
 if(j+a<=S) dp[i+1][j+a] = dp[i][j] + "H";
 if(j+b<=S) dp[i+1][j+b] = dp[i][j] + "T";
aとbが同じ値を示した時に重複しないようにする工夫が必要。

```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, S;
    cin >> N >> S;
    vector<vector<string>> dp(N+1, vector<string>(S+1, ""));
    dp[0][0] = "S";
    for(int i=0; i<N; i++){
        int a, b;
        cin >> a >> b;
        for(int j=0; j<=S; j++){
            if(dp[i][j] == "") continue;
            if(j+a<=S && dp[i][j+a].size() <= i+1) dp[i+1][j+a] = dp[i][j] + "H";
            if(j+b<=S && dp[i][j+b].size() <= i+1) dp[i+1][j+b] = dp[i][j] + "T";
        }
    }
    if(dp[N][S].size()-1 == N) cout << "Yes" << endl << dp[N][S].substr(1, N) << endl;
    else cout << "No" << endl;
 
    return 0;
} 
```