답안 #466081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466081 2021-08-17T21:28:53 Z ChrisGe123 Calvinball championship (CEOI15_teams) C++14
100 / 100
125 ms 536 KB
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>,
//     rb_tree_tag, tree_order_statistics_node_update>;

const int maxn = 10001;
#define mp make_pair
#define pb push_back
#define f first
#define s second

const int mod = 1000007;

typedef pair<int, int> pii;
int n;
int seq[maxn];
ll dp[2][maxn]; // we're going to sliding window on the first dimension

/*
We're looking at sequences of the integers 1..k, where the first occurrence of 1..k are in precisely that order
- interesting note: this means that all sequences should start with 1
Want to find how many of these sequences appear lexicographically before our current sequence

number of seuqences of each length
1: 1
2: 2
3: 5
4: 15

1 2 2
- Everything with 1 1 is before: there are 2 options (that's easy to count)
- Everything with 1 2 1 is before: only 1 option
- this should be 4

Observation: the first n numbers in a length n+1 sequence also form a valid sequence (maybe we'll just call them sequences from now on)
- from a length n sequence where the numbers 1..k are used, you have k+1 options for the next thing to append to it

1 2 3 2
- everything that starts with a sequence that is before 1 2 3 is before it
- this is still problematic though because of the fact that the number of ways to make a sequence of length 4 depends on the numbers used 

What if we have a function S(n, k) that tells us the number of sequences of size n that use 1..k
S(n+1, k) = S(n, k-1) + kS(n, k)
This is stirling numbers of the second kind
So the number of sequences is the Bell numbers

Size n = number of ways to partition a set of size n, the largest element we use should somehow correlate to the number of subsets
There should be one subset per each number
Wait this bijection is literally what the question is asking

So I guess back to the examples: 1 2 3 2
The problem is that we don't just need the number of 3-sequences below 1 2 3, we need for each sequence the highest k value that it uses, which seems a lot harder to get

Is it easy to count everything that starts with 1 1? 
- yes because there should just be 5 (the number of length 3 sequences)
What about 1 2 1: this is fine for now because there's only one more option, but what about when we need something of like length 5
- Ok this fowards strategy seems quite bad

This still feels like a dp problem
Let T(m, k) be the number of sequences of size m using 1..k that are strictly lower in lexicographic order than the first m elements of our sequence
Answer would be sum of the T(n, 1..n)
There are n^2 states = 10^8 which might run in time

The transition
T(i+1, j) = (number of sequences that perfectly match first i and have lower i+1th position) + T(i, j-1) + jT(i, j)
This seems O(1) enough
Figuring out the first part is just a matter of preprocessing which numbers are used at each point in our given sequence

Sliding window so that we have enough memory
*/

void setupIO(string s)
{
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}


int main()
{
	//setupIO("calvinball");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; i++)
	{
		cin >> seq[i];
	}
	int largestnum = 1;
	for (int i=1; i<n; i++)
	{
		for (int j=1; j<=i+1; j++)
		{
			dp[i%2][j] = (dp[(i-1)%2][j-1] + j*dp[(i-1)%2][j])%mod;
			if (largestnum == j)
			{
				dp[i%2][j] = (dp[i%2][j]+seq[i]-1)%mod;
				//because seq[i] is at most largestnum+1, so the largest number used in any sequence that's the first i-1 terms + something lower than seq[i] is largestnum
			}
		}
		largestnum = max(largestnum, seq[i]);
	}
	ll ans = 1;
	for (int i=1; i<=n; i++)
	{
		ans = (ans + dp[(n-1)%2][i])%mod;
	}
	cout << ans << endl;
}

Compilation message

teams.cpp: In function 'void setupIO(std::string)':
teams.cpp:78:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:79:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 460 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 412 KB Output is correct
2 Correct 31 ms 332 KB Output is correct
3 Correct 31 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 536 KB Output is correct
2 Correct 125 ms 472 KB Output is correct
3 Correct 121 ms 520 KB Output is correct