Codeforces Global Round 9 感想
問題
Dashboard - Codeforces Global Round 9 - Codeforces
感想
4完。 ギャクが多かった。
[追記]
うぉ~~~!!ついに紫になったぞ~~~~うれし~~~~
維持できるようにがんばる。
A - Sign Flipping
正負正負...... or 負正負正......にすればいい。ギャグ。
問題を理解するのに時間かかった。
提出コード
void solve() {
int Q;
cin >> Q;
Vl A, B;
while (Q--) {
ll N;
cin >> N;
A.resize(N);
for (ll i = 0; i < N; i++) {
cin >> A[i];
}
B.resize(N);
for (ll i = 0; i < N; i++) {
if (i & 1) {
B[i] = abs(A[i]);
}
else {
B[i] = -abs(A[i]);
}
}
for (ll i = 0; i < N; i++) {
cout << B[i] << " ";
}
cout << "\n";
}
}
B - Neighbor Grid
例えば、 なら
みたいにすればいい。できなければNO。ギャグ。
提出コード
void solve() {
int Q;
cin >> Q;
while (Q--) {
ll N, M;
cin >> N >> M;
bool ok = true;
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < M; j++) {
int a;
cin >> a;
if ((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M - 1)) {
if (a > 2) {
ok = false;
}
}
else if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
if (a > 3) {
ok = false;
}
}
else {
if (a > 4) {
ok = false;
}
}
}
}
if (ok) {
cout << "YES\n";
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < M; j++) {
int a;
if ((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M - 1)) {
a = 2;
}
else if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
a = 3;
}
else {
a = 4;
}
cout << a << " ";
}
cout << "\n";
}
}
else {
cout << "NO\n";
}
}
}
C - Element Extermination
結論はギャグで、 < ならYES、そうでなければNO。
[必要性の証明]
どんな操作をしても先頭は より小さくできないし、末尾は より大きくできない。 だから、もし なら (先頭) > (末尾) の関係はずっと保存されてしまうので、要素数を1にすることはできない。
[十分性の証明]
< を仮定したときに、数列の要素数を1にできる操作列が必ず存在することを示す。
操作によって、先頭と末尾の間の要素たち(先頭と末尾は含まない)を単調減少にすることができる。 単調増加な連続部分列に対して、一番大きな要素以外を消すように操作を行っていくことでこれは実現できる。
この操作の結果、数列が に変化したとする。
そして、可能な限り、先頭2つに対して を残すように操作を繰り返す。
その結果、数列が に変化したとする。このとき、 が成り立つ。
また、同様に、可能な限り、末尾2つに対して を残すように操作を繰り返す。
< ならば、 なので、 この操作によって 以外はすべて消えて数列の要素数は必ず1になる。(証明終わり)
この証明をコンテスト中に思いつけたのはよかった。
提出コード
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];
}
if (A[0] < A[N - 1]) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
D - Replace by MEX
適当を投げるとなんか通った、笑。
どうせ数列を 0, 1, ... , n-1 にするんだろな~~と思って、mex != n なら を mex に変化させて、 mex == n なら を満たす最小の i を s、 を満たす i を tとして、 t -> s の順番に操作をするというコードを投げたら通った。やったぜ。
一応、色々テストケースを作って大丈夫なことを確かめてから提出した。
提出コード
void solve() {
int Q;
cin >> Q;
Vi A;
vector<set<int>> pos;
Vi ans;
while (Q--) {
ll N;
cin >> N;
A.resize(N);
pos.assign(N + 1, set<int>());
for (ll i = 0; i < N; i++) {
int a;
cin >> a;
A[i] = a;
pos[a].emplace(i);
}
ans.clear();
while (true) {
bool ok = true;
int cur;
for (ll i = 0; i < N; i++) {
if (A[i] != i) {
ok = false;
cur = i;
break;
}
}
if (ok) {
break;
}
int mex = 0;
while (mex <= N && !pos[mex].empty()) {
++mex;
}
if (mex == N) {
auto itr = pos[cur].begin();
ans.emplace_back(*itr);
pos[mex].emplace(*itr);
A[*itr] = mex;
pos[cur].erase(itr);
mex = cur;
}
while (mex < N) {
ans.emplace_back(mex);
pos[A[mex]].erase(mex);
pos[mex].emplace(mex);
A[mex] = mex;
mex = 0;
while (mex <= N && !pos[mex].empty()) {
++mex;
}
}
}
cout << ans.size() << "\n";
for (const auto& ai : ans) {
cout << ai + 1 << " ";
}
cout << "\n";
}
}
E以降
問題を見てないので割愛。