AtCoder Beginner Contest 256

A - 2^N

O(1)
2^Nの問題です。
powlはlong doubleなのでWAになります。

C++

#include <bits/stdc++.h> 
using namespace std;

int main() {
    long long N;
    cin >> N;
    cout << (1<<N) << endl;
    return 0;
} 

B - Batters

O(4N)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(auto &a:A) cin >> a;
    vector<bool> graph(4, false);
    int P = 0;
    for(auto a:A){
        graph[0] = true;
        for(int i=3; i>=0; i--){
            if(i+a>3 && graph[i]){
                P++;
            }else if(graph[i]){
                graph[i+a] = graph[i];
            }
            graph[i] = false;
        }
    }
    cout << P << endl;
    return 0;
} 

C - Filling 3x3 array

O(N^9)に枝刈りしたもの
30^9ではTLEになります、枝刈りしました。
N^4で解答できるそうです。

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 h[3], w[3];
    rep(i, 3) cin >> h[i];
    rep(i, 3) cin >> w[i];

    ll ans=0;
    repx(m1, 1, 29){
        repx(m2, 1, 29){
            repx(m3, 1, 29){
                if(m1 + m2 + m3 != w[0]) continue;
                repx(m4, 1, 29){
                    repx(m5, 1, 29){
                        repx(m6, 1, 29){
                        if(m4 + m5 + m6 != w[1]) continue;
                            repx(m7, 1, 29){
                                if(m1 + m4 + m7 != h[0]) continue;
                                repx(m8, 1, 29){
                                    if(m2 + m5 + m8 != h[1]) continue;
                                    repx(m9, 1, 29){
                                        if(m7 + m8 + m9 != w[2]) continue;
                                        if(m3 + m6 + m9 != h[2]) continue;
                                        ans++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
} 

D - Union of Interval

ソートがO(NlogN)
他がO(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() {
    int N;
    cin >> N;
    vector<P> LR(N);
    for(auto &lr:LR) cin >> lr.first >> lr.second;

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

    vector<P> DP;
    for(auto lr:LR){
        if(DP.size() == 0){
            DP.push_back(lr);
        }else{
            int ok=1;
            for(int i=0; i<DP.size(); i++){
                if(DP[i].first < lr.second && DP[i].second >= lr.first){
                    if(DP[i].first > lr.first){
                        DP[i].first = lr.first;
                    }
                    if(DP[i].second < lr.second){
                        DP[i].second = lr.second;
                    }  
                    ok = 0;                  
                }
            }
            if(ok){
                DP.push_back(lr);
            }
        }
    }
    for(auto lr:DP){
        cout << lr.first << ' ' << lr.second << endl;
    }
    return 0;
}