Link
C – 一次元リバーシ / 1D Reversi
/*
* AC 6 ms 512 KB
*/
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
//freopen("c.in", "r", stdin);
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] != s[i+1]) ans++;
}
printf("%d\n", ans);
return 0;
}
D – 高橋君と見えざる手 / An Invisible Hand
I didn’t notice that there is a restriction that each \(A_i\) is different. So it took time for implementation.
/*
* AC 15 ms 640 KB
*/
#include <cstdio>
#include <iostream>
using namespace std;
#define INF 1e9;
int a[100005];
int N, T;
int maxDiff = 0;
int main(){
//freopen("d3.in", "r", stdin);
scanf("%d %d", &N, &T);
int tmpmin = INF;
for (int i = 0; i < N; ++i) {
scanf("%d", &a[i]);
if (tmpmin > a[i]) tmpmin = a[i];
int diff = a[i] - tmpmin;
if (diff > maxDiff) maxDiff = diff;
}
int minCount = 0, maxCount = 0;
tmpmin = INF;
int ans = 0;
for (int i = 0; i < N; ++i) {
if (tmpmin + maxDiff == a[i]) maxCount++;
if (tmpmin == a[i]) {
minCount++;
} else if (tmpmin > a[i]) {
// update
tmpmin = a[i];
ans += min(minCount, maxCount);
// re-init
minCount = 1;
maxCount = 0;
}
}
ans += min(minCount, maxCount);
printf("%d\n", ans);
return 0;
}
E – 木と整数 / Integers on a Tree
Follow editorial.
/*
* AC 78 ms 14208 KB
*/
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define INF 1e9
int N, K;
vector<int> edge[100005]; // edge[i] connect from i to edge[i][j].
int v[100005]; // v[i] is written in vertex i
int par[100005]; // vertex i's parent is par[i]
int lb[100005], ub[100005]; // Range [lb[i], ub[i]] is allowed at vertex i, v[i] must be in [lb[i], ub[i]]
int root;
void dfs(int vertex) {
for (int i = 0; i < edge[vertex].size(); ++i) {
int nextVertex = edge[vertex][i];
if (nextVertex != par[vertex]) {
par[nextVertex] = vertex;
dfs(nextVertex);
} else {
// skip this
}
}
for (int i = 0; i < edge[vertex].size(); ++i) {
int nextVertex = edge[vertex][i];
lb[vertex] = max(lb[vertex], lb[nextVertex] - 1);
ub[vertex] = min(ub[vertex], ub[nextVertex] + 1);
}
}
// Decide the example of v[i]
void dfs2(int vertex) {
for (int i = 0; i < edge[vertex].size(); ++i) {
int nextVertex = edge[vertex][i];
if (nextVertex != par[vertex]) {
par[nextVertex] = vertex;
int tmp;
tmp = v[vertex] + 1;
if (lb[nextVertex] <= tmp && tmp <= ub[nextVertex]) {
v[nextVertex] = tmp;
} else {
tmp = v[vertex] - 1;
if (lb[nextVertex] <= tmp && tmp <= ub[nextVertex]) {
v[nextVertex] = tmp;
} else {
// Error, impossible
lb[root] = INF;
ub[root] = -INF;
return;
}
}
dfs2(nextVertex);
} else {
// skip this
}
}
}
int main(){
//freopen("e3.in", "r", stdin);
scanf("%d", &N);
int a, b;
for (int i = 0; i < N-1; ++i) {
scanf("%d %d", &a, &b);
edge[a].push_back(b);
edge[b].push_back(a);
}
// init
for (int i = 1; i <= N; ++i) {
v[i] = INF;
lb[i] = -INF;
ub[i] = INF;
}
scanf("%d", &K);
for (int i = 0; i < K; ++i) {
int vertex, p;
scanf("%d %d", &vertex, &p);
v[vertex] = p;
lb[vertex] = ub[vertex] = p;
root = vertex;
}
par[root] = root;
dfs(root);
dfs2(root);
if (lb[root] == v[root] && ub[root] == v[root]) {
// possible
printf("Yes\n");
for (int i = 1; i <=N; ++i) {
printf("%d\n", v[i]);
}
} else {
printf("No\n");
}
return 0;
}