コンテスト中の考察(AC)
- 何も思いつかないのでとりあえずDFSを書いてみる。ほとんどTLEでWAがちょっと出た。
- よくわからないので色々実験してみる。
- 実験した結果、数列に0が含まれる場合は全てプラスにすることができることに気づく（証明はできんけど）
- それ以外の場合は、数列に対しループを回し、i番目にマイナスの値が出てきたらA[i]とA[i+1]に-1をかける操作をする。その結果が、マイナスの値が1つ以上の場合とそれ以外の場合に分けることができそう（証明できんけど）。マイナスの値が1つ以上の場合、数列中に含まれるマイナスの値はひとつでその他はプラスの値となる。これは、実験した結果なんとなくそう思った。操作後の数列にマイナスが含まれない場合は、全てをプラスにすることができる。たぶんね。
- そんな感じで考察して提出したらACしてしまった。実験してそれっぽい解法投げただけなので全然理解してない。
反省
詰まった部分
- 要素5に対して操作→要素1に対して操作→要素3に対して操作→...みたいなことができるので、頭が壊れた。何が最適かわからなくなっていた。
思いつき方1(パターン列挙から入る)
- 操作する対象のパターンを列挙する。
- この問題では連続する2つの要素に対して操作を行う。ぱっと見ぐちゃぐちゃに見える。でも、２要素に対する操作ののパターンを抜き出すと
++、--、+-、-+の4パターンへの操作しかない。 -
--はすべて++にしても問題ない。 -
-+は+-にしていくことで、マイナスを右端に集めることができる。そして、集めたやつを--から++にすることができる。 - この操作をすると、マイナスの個数が0個か1個になる。
+-と-+への操作はマイナスの個数の偶奇は変わらない。そして、--への操作でもマイナスの個数の偶奇は変わらない。なので、与えられた配列のマイナスの個数によって残るマイナスの個数が異なる。 - マイナスの個数が偶数個ならすべてのマイナスを消せる。マイナスの個数が奇数個なら偶数個しか減らすことしかできないためマイナスは1つ残る。
思いつき方2(どうなれば嬉しいか考える)
- フリップ操作では連続する2つの要素の偶奇をフリップする。
- これより、任意の2つの要素をフリップできたら嬉しいなぁって思う。これができればいいことがあるので、試してみる。
- 赤い2つの要素のプラマイを反転させる。図のようにすれば赤い部分は1回で反転、その間の要素は2回反転で元に戻る。なので、実質赤い２つの要素のプラマイを反転させることができる。
- これより、マイナスの要素を2つずつ消していくことができる。マイナスの個数が偶数この場合はすべての要素をプラスにすることができる。だが、マイナスの個数が奇数個の時はマイナスの要素が1つだけ残る。
解法
- 与えられた配列のマイナスの個数をカウントする。
- マイナスの個数が偶数個ならば要素の絶対値の和が答え。
- マイナスの個数が奇数個ならば要素の絶対値が一番小さいものをマイナスにし、その他の要素をプラスにして足し合わせたものが答え。
コード
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N;
int A[111111];
signed main() {
cin >> N;
int minus = 0; // マイナスの個数
for (int i = 0; i < N; i++) {
cin >> A[i];
if (A[i] < 0) {
minus++;
}
}
if (minus % 2 == 0) {
int ans = 0;
for (int i = 0; i < N; i++) {
ans += abs(A[i]);
}
cout << ans << endl;
} else {
for (int i = 0; i < N; i++) {
A[i] = abs(A[i]);
}
sort(A, A+N);
int ans = -A[0]; // 一番小さいやつをマイナスにする
for (int i = 1; i < N; i++) {
ans += A[i];
}
cout << ans << endl;
}
return 0;
}
要点
- どうなれば嬉しいか考えると良さげ
- パターン列挙するのも良さげ。
- なんかぐちゃぐちゃだった盤面をシンプルに考えられたので。
メモ
- けんちょんさんの記事
- 類題出て思いつける気がしねえ
- DPでも解けるみたい