ABC 006

abc006.contest.atcoder.jp

A問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    cout << (N%3 == 0 ? "YES" : "NO") << endl;
}

Submission #1025003 - AtCoder Beginner Contest 006 | AtCoder

B問題

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int a[1000010];
int main(void) {
    int n;
    cin >> n;
    a[1] = a[2] = 0;
    a[3] = 1;
    FOR(i, 4, n+1) {
        a[i] = (a[i-1] + a[i-2] + a[i-3]) % 10007;
    }
    cout << a[n] << endl;
}

Submission #1025009 - AtCoder Beginner Contest 006 | AtCoder

C問題

全てのbに対して解が存在するか調べる。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, M;
    cin >> N >> M;
    int a, b, c;
    REP(b, N+1) {
        int t = M - 3*b;
        if(t % 2 != 0) continue;
        c = t/2 - (N-b);
        a = (N-b) - c;
        if(a >= 0 && c >= 0) {
            printf("%d %d %d\n", a, b, c);
            return 0;
        }
    }
    a = b = c = -1;
    printf("%d %d %d\n", a, b, c);
}

D問題

最長増加部分列問題 (Longest Increasing Subsequence) という典型問題らしい。

  • k枚抜いたらソート済みになる最小のkが求まれば、k枚を適切な位置に挿入することで全てソート済みの列が作れるからkが答えになる。
  • 「今まで見たカードまでで作れる長さiのソート済み部分列の最後の数字の最小値」を格納するdp[i]を用意しておいてカードを前から見て埋めていく。
  • カードcを見ているとき、「dp[i-1] < c < dp[i+1]を満たす最小のi」に埋めるので二分探索で行う
  • 埋まっている数の最大値が最小数のカードを抜いた後の残り枚数なので、Nから最大値を引くと答えになる
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<int>c(N);
    REP(i, N) cin >> c[i];
    vector<int> dp(N+1, 1e9);
    dp[0] = -1e9;
    REP(i, N) {
        int k = c[i];
        int l = 0, r = N+1;
        while(l < r) {
            int m = (l + r) / 2;
            if(k < dp[m]) r = m;
            else l = m+1;
        }
        dp[l] = k;
    }
    int ans = 0;
    REP(i, N+1) {
        if(dp[i] != 1e9) ans = i;
    }
    cout << N-ans << endl;
}

Submission #1025896 - AtCoder Beginner Contest 006 | AtCoder

http://abc006.contest.atcoder.jp/submissions/1025896