ABC 006
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