AtCoder abc396 振り返り
AtCoder Beginner Contest 396 の振り返りです。
だいぶ空いてしまいましたが、ABC396の振り返りです。 今週もコンスタントに3問解けた感じでした。
最近、ABCが易化傾向にあるような気がしているが、それでもD問題が解けないのはやはり悔しい。
A Triple Four: Solved
与えられた数列に３つ連続して同じ数字が出現するかどうかを判定する問題。
a[i] == a[i - 1] && a[i - 1] == a[i - 2]で前から順番に判定する感じ。
B Card Pile: Solved
カードを上に重ねるか、一番上を見て捨てるのいずれかの操作をQ回行う問題。
いかにもstackで解いてくださいという問題だったので、素直にstackを使って解いた。C++のStackを使うのが久しぶり(もしかしたら競プロでは初めてかも)だったので、stackの使い方を調べながら解いたので少し時間がかかった。
あとになってから気づいたが、popとpushがあればいいといいう意味では普通にvectorで解けばよかったような気がする。
C Buy Balls: Solved
白と黒のボールがそれぞれ与えられるが、ボール一つ一つで得点が異なり、しかも黒のボールは白のボールの数以上選ばなければならない時の選択した全てのボールの最大合計得点という、少々複雑な問題。
そもそも、問題がややこしくて理解するのに時間をかけてしまった。要するに白と黒のボールをそれぞれ大きい順にソートした後に、負の数になるか空になるまで両方の色をひとつずつ取り出していき、その後は白が余ってる場合には黒との差が正になり続ける限り両方ひとつずつ取り出し、黒が余る場合には黒が負になるか空になるまで黒のみを取り出していくという流れ。
ソートしたボールを順に取り出す処理ということで再びpopを駆使して解いたが、今回はvectorを使って解いた。それにしても、もうちょっと条件式スマートにしたかった。
int main() {
int n,m;
long long p = 0;
cin >> n >> m;
vi b(n),w(m);
for(i=0;i < n; i++){
cin >> b[i];
}
for(i=0;i < m; i++){
cin >> w[i];
}
sort(b.rbegin(),b.rend());
sort(w.rbegin(),w.rend());
for(;;){
if(!b.empty() && !w.empty() && b.back() >= 0 && w.back() >= 0){
p += b.back() + w.back();
b.pop_back();
w.pop_back();
} else if((!b.empty() && b.back() > 0) && (w.empty() || w.back() < 0)){
p += b.back();
b.pop_back();
} else if(b.back() < 0 && w.back() >= 0 && w.back()+b.back() > 0){
p += b.back() + w.back();
b.pop_back();
w.pop_back();
} else {
break;
}
}
cout << p << endl;
}
所感
C問題に少々手こずったものの、C問題まで割とスムーズに解けた。一方で、前回に引き続きD問題はグラフの問題で手も足も出なかった。
競プロ始めてからしばらく経ったけれど、やはりグラフの問題は苦手意識が強い。今まで、本番で解けた試しがない。
このところ、C問題まで解けてもレーティングが下がることが続いており、やはりD問題を解かないとレーティングが上がらないのだろう。 そういう意味では、レーティングが自分の能力に見合っているということなのかもしれないが、そうであれば尚のこと苦手を克服してレーティングを上げていきたい。
まずはコンスタントに振り返りしよう。