AtCoder Regular Contest 058

Chong Wang Lv6
  2016-07-30 14:02:24 2016-07-30 14:02:24 Created   2026-10-09 08:49:25 2026-10-09 08:49:25 Updated  

The codes for C, D, and E are here

This week I have been busy writing some things that the teacher asked me to write, and finally I collapsed gloriously on Saturday. I was so tired.

It was originally the competition last week. I still couldn’t pass F in a week. I asked some people on Codeforces and I finally understood the principle. However, I still haven’t learned the Z-algorithm mentioned by yosupo. This has also been added to the To_do_list. I will definitely come back. . .

C Iroha’s Obsession

The meaning of question C is to find a number x that is greater than or equal to n, and then it cannot be used if k numbers are given.

Violence is fine, just go up one by one and judge whether you meet the conditions. It is a bit troublesome to do it yourself.

D roha and a Grid

The meaning of question D is that a grid with a length of H and a width of W is given, and one has to walk from the upper left corner to the lower right corner. Then a lower left area is given, with a length of A and a width of B, which cannot be reached. The final number of methods is asked.

The problem is to consider this blue area, enumerate the number of ways for each point on the blue line to reach the point from the upper left corner, and then consider that these points all pass vertically through the horizontal line below, calculate how many ways the points below can reach the end point, and just add them up.

There are c(x-s+y-t,x-s) ways from the starting point (x, y) to the end point (s, t). Just count the number of combinations.

R058_D

E Iroha and Haiku

The meaning of question E is that given N numbers (N<=40), each number consists of 1 to 10, ask whether three adjacent sub-segments can be found in these compositions. The sum of the first segment is

This is a great question. . . .

The method is to find those that do not match. Write 1 as 1, 2 as 10, and 3 as 100. Then the last number can be written as a 01 string, and then this string contains xyz-Haiku, which is equivalent to doing an AND operation with the 01 string composed of xyz, and the result is not 0.

F Iroha Loves Strings

The meaning of question F is that N strings are given, and they are combined in order into a string of length k, which is guaranteed to be found. Then ask what is the lexicographically smallest string.

I asked yosupo and this is what he said. I roughly understand it, but not z-algorithm. . .

R058_F_1

After reading other people’s AC codes, some of them were confusing, and then I wrote them according to the ideas. WA always loses 4 data, I don’t know why. . .

Please explain this question to someone passing by. . .

WA code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//#pragma comment(linker, "/STACK:102400000,102400000") 
#pragma warning(disable:4996)
#include <fstream>
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
 
typedef long long ll;
#define eps 1e-10
#define LL_INF 0x33ffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define pper(i,n,m) for(int i = n;i >= m; i--)
#define repp(i, n, m) for (int i = n; i <= m; i++)
#define rep(i, n, m) for (int i = n; i < m; i++)
#define sa(n) scanf("%d", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
 
const int maxn = 2e3 + 10;
const ll mod = 1e9 + 7;
const double PI = acos(-1.0);
ll po(ll a, ll b) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1)res = res*a%mod; a = a*a%mod; }return res; }
 
int n, k;
string val[maxn];
int vis[maxn];
int dp[maxn][10010];
int loc[2][3005][2];
 
void solve()
{
	int i, j;
 
	set<char>ch;
	repp(i, 1, n)
	{
		cin >> val[i];
		rep(h, 0, val[i].length())
		{
			ch.insert(val[i][h]);
		}
	}
	mem(dp, 0);
	dp[n + 1][0] = 1;
 
	for (i = n; i >= 1; i--)
	{
		for (j = 0; j <= k; j++)
		{
			if (dp[i + 1][j])
			{
				dp[i][j] = 1;
			}
			if (dp[i + 1][j] && j + val[i].length() <= k )
			{
				dp[i][j + val[i].length()] = 1;
			}
		}
	}
	int now = 0, pre = 1;
	int cnt = 0;
	for (i = 1; i <= n; i++)
	{
		if (k - val[i].length()>=0 && dp[i + 1][k - val[i].length()])
		{
			cnt++;
			loc[pre][cnt][0] = i;
			loc[pre][cnt][1] = 0;
		}
	}
	string res = "";
	int remain = k;
	for (i = 1; i <= k; i++)
	{
		mem(vis, 0);
		char minx = 'z';
		for (j = 1; j <= cnt; j++)
		{
			minx = min(minx, val[loc[pre][j][0]][loc[pre][j][1]]);
		}
		int ncnt = 0;
		int mn = n;
		for (j = 1; j <= cnt; j++)
		{
			char x = val[loc[pre][j][0]][loc[pre][j][1]];
			if (x != minx)continue;
			if (loc[pre][j][1] == val[loc[pre][j][0]].length() - 1)
			{
				mn = min(mn, loc[pre][j][0]);
			}
			else
			{
				vis[loc[pre][j][0]] = 1;
				++ncnt;
				loc[now][ncnt][0] = loc[pre][j][0];
				loc[now][ncnt][1] = loc[pre][j][1] + 1;
			}
		}
		remain--;
		for (j = mn + 1; j <= n; j++)
		{
			if (vis[j])continue;
			if (remain - val[j].length() >= 0 && dp[j + 1][remain - val[j].length()])
			{
				ncnt++;
				loc[now][ncnt][0] = j;
				loc[now][ncnt][1] = 0;
			}
		}
		res = res + minx;
		cnt = ncnt;
		pre = 1 - pre;
		now = 1 - now;
	}
	cout << res << endl;
}
 
int main()
{
	while (scanf("%d%d", &n, &k) != EOF)
	{
		solve();
	}
	return 0;
}
On this page
AtCoder Regular Contest 058
  1. C Iroha’s Obsession
  2. D roha and a Grid
  3. E Iroha and Haiku
  4. F Iroha Loves Strings