Codeforces Round #656 (Div. 3) 感想
問題
Dashboard - Codeforces Round #656 (Div. 3) - Codeforces
感想
5完。可もなく不可もなくで特に何も言葉が出てこない。
A - Three Pairwise Maximums
a, b, c を出力する順番は何でもいいらしいので、x, y, z を入れ替えて となるようにしてもOK。
すると、
だから、 でないといけないことが分かる。
のとき、
とすれば上式を満たすからこれを出力すればいい。
よく考えると、a, b, c のとる値は x, y, z に限っても良くて、何も考えずに全探索でもいける。
リンク： http://codeforces.com/contest/1385/submission/87105915提出コード
void solve() {
int Q;
cin >> Q;
ll v[3];
while (Q--) {
cin >> v[0] >> v[1] >> v[2];
sort(v, v + 3);
if (v[1] != v[2]) {
cout << "NO\n";
continue;
}
cout << "YES\n";
cout << 1 << " " << v[0] << " " << v[1] << "\n";
}
}
B - Restore the Permutation by Merger
前から見ていって、まだ登場してなければ答えの vector に push_back して、すでに登場していれば無視する。
Aより簡単じゃね？
リンク：http://codeforces.com/contest/1385/submission/87110903提出コード
void solve() {
int Q;
cin >> Q;
Vl A;
vector<bool> used;
while (Q--) {
ll N;
cin >> N;
A.resize(N * 2);
used.assign(N + 1, false);
for (ll i = 0; i < N * 2; i++) {
cin >> A[i];
}
for (ll i = 0; i < N * 2; i++) {
if (!used[A[i]]) {
cout << A[i] << " ";
used[A[i]] = true;
}
}
cout << "\n";
}
}
C - Make It Good
要素の増減が ／＼ ← こんな感じになっていることが good であるための必要十分条件。 ／ や ＼ でもOK。
数列 a を後ろから見ていって、この条件がいつまで満たされるかを調べればいい。
リンク：http://codeforces.com/contest/1385/submission/87118183提出コード
void solve() {
int Q;
cin >> Q;
Vl A;
while (Q--) {
ll N;
cin >> N;
A.resize(N);
for (ll i = 0; i < N; i++) {
cin >> A[i];
}
reverse(A.begin(), A.end());
ll ans = 0;
bool fg = false;
for (ll i = 1; i < N; i++) {
if (!fg) {
if (A[i - 1] > A[i]) {
fg = true;
}
}
else {
if (A[i - 1] < A[i]) {
ans = N - i;
break;
}
}
}
cout << ans << "\n";
}
}
D - a-Good String
good であるための条件が再帰的なので、再帰かな～という気持ちになる。
文字列の長さが 2 以上の場合に c-good であるための条件は
(i) cccc<(c+1)-good>
(ii) <(c+1)-good>cccc
の2通りがあって、これを a-good, b-good, c-good, ... について dfs で全探索する。 探索数は と同じくらいだから計算量は大丈夫。
書き換えなければいけない文字数を高速で計算するために、累積和を作って「区間における各アルファベットの登場回数」を求められるようにしておく。
dfs の実装ではセグ木を再帰で書いたときの経験が活きた。
リンク：http://codeforces.com/contest/1385/submission/87133819提出コード
ll N;
string S;
ll ans;
vector<Vl> nums;
ll dfs(ll l, ll r, ll x) {
if (r - l == 1) {
int si = S[l] - 'a';
return si != x;
}
ll mid = (l + r + 1) >> 1;
ll t1 = dfs(mid, r, x + 1);
ll t2 = dfs(l, mid, x + 1);
ll k1 = (mid - l) - (nums[x][mid] - nums[x][l]);
ll k2 = (r - mid) - (nums[x][r] - nums[x][mid]);
return min(t1 + k1, t2 + k2);
}
void solve() {
int Q;
cin >> Q;
while (Q--) {
cin >> N;
cin >> S;
nums.assign(26, Vl(N + 1));
for (ll i = 0; i < 26; i++) {
for (ll j = 0; j < N; j++) {
int si = S[j] - 'a';
nums[i][j + 1] = nums[i][j] + (si == i);
}
}
ll ans = dfs(0, N, 0);
cout << ans << "\n";
}
}
E - Directing Edges
サンプルを見るとトポロジカルソートかな～という気持ちになる。
ます、有向辺のみでグラフを構成しトポロジカルソートを試みる。閉路があって失敗したときは NO。
トポロジカルソートに成功すれば YES で、 無向辺をトポロジカル順序の上位から下位へ向きづければ閉路はできない。
リンク：http://codeforces.com/contest/1385/submission/87145244提出コード
void solve() {
int Q;
cin >> Q;
using Graph = vector<Vi>;
Graph gd, gud;
set<Pii> used;
Vi indeg;
Vi topo;
vector<Pii> udes;
while (Q--) {
ll N, M;
cin >> N >> M;
ll ne = 0;
gd.assign(N, Vi());
gud.assign(N, Vi());
indeg.assign(N, 0);
for (ll i = 0; i < M; i++) {
int t, u, v;
cin >> t >> u >> v;
--u, --v;
if (t == 0) {
gud[u].emplace_back(v);
gud[v].emplace_back(u);
}
else {
gd[u].emplace_back(v);
++indeg[v];
++ne;
}
}
stack<int> st;
topo.clear();
for (ll i = 0; i < N; i++) {
if (indeg[i] == 0) {
st.emplace(i);
topo.emplace_back(i);
}
}
while (!st.empty()) {
int u = st.top();
st.pop();
for (auto v : gd[u]) {
--indeg[v];
--ne;
if (indeg[v] == 0) {
st.emplace(v);
topo.emplace_back(v);
}
}
}
if (ne > 0) {
cout << "NO\n";
continue;
}
used.clear();
udes.clear();
for (ll i = 0; i < N; i++) {
int u = topo[i];
for (auto v : gud[u]) {
int x, y;
x = u, y = v;
if (x > y) swap(x, y);
if (used.find({x, y}) == used.end()) {
udes.emplace_back(u, v);
used.emplace(x, y);
}
}
}
cout << "YES\n";
for (ll i = 0; i < N; i++) {
for (auto v : gd[i]) {
cout << i + 1 << " " << v + 1 << "\n";
}
}
for (auto [u, v] : udes) {
cout << u + 1 << " " << v + 1 << "\n";
}
}
}
F - Removing Leaves
解けなかった。全方位木DPの雰囲気があるけどどうなんだろ......。後で時間があるときに解こうと思う。
G - Columns Swaps
見てない。
