ABC351を解いた際の考え方と解説を読んだアウトプット
ABC351
結果は2完(所用でrated参加出来ませんでしたが…)
A - The bottom of the ninth
考え方
Aの合計 + Bの合計 + 1で答え、やるだけ
B - Spot the Difference
考え方
string配列に1つ目のグリッドを格納
2つ目のグリッドはchar型に1つずつ受け取り、1文字ずつ比較
i、jに+1した値を出力して終了
C - Merge the balls
エラー解決してたら時間切れ、解けそうだったので悔しい
考え方
stack構造の一番上と入力を比較して、等しい場合はpopし入力に1を足す
↑この処理を一番上と入力が違う値となるまで繰り返す
最終的なstackの中身を出力
反省
stackの中身が空の時の処理を入れていなかったことから参照エラーが起きていた
解説を読んで
ボールの数を記録し、配列の参照位置を一つずつずらすことで求めていた。
stackを使わなくても求められるのはエレガントでかっこいい
D - Grid and Magnet
着手出来なかったやつ、終了後に問題見た
考え方
マス目ってことはDFS/BSFとかUnionFindかな？
動けるマス+隣接マスを求めるっぽい
隣接マスをメモにとって重複して数えないようにしたい
解説を読んで
考え方とほぼ同じ、実装方法でメモのリセットを気にしないと計算量が大きくなってしまう
座標移動する配列を用意して、移動度計算したり移動可能か判定する
Atcoder liveではBFSを採用していて、公式解説ではDFSを用いていた
黒塗り解説ではUnionFindを用いていた
愚直にDFSを実装したら再帰を考えないといけない(UFとかBFSはmainにベタ書きできるっぽい？)
ドデカメモ
C問題でのstackの使い方に注意、stackが空の状態を条件に入れなければならない
D問題で計算量の把握が出来るようになると更に良くなる(要修行)