AtCoder Beginner Contest 176に参加しました

ABC176に参加しました。

 A~Cまでは6分ほどで解くことができ、Eも3ペナ67分で通せたので良かったと思います。Dは、解けそうで解けないまま2週間が過ぎました。

Tasks - AtCoder Beginner Contest 176

All Submissions - AtCoder Beginner Contest 176

A-Takoyaki

余りを切り上げる必要があります。(N+X-1)/Xとすることで、簡潔に書くことができます。

B-Multiple of 9

string型でないとNを受け取れないことにまず注意します。各桁の数字を足していき、最後に9で割り切れるかどうかを確認します。

C-Step

前から順番にチェックしていきます。

一番前の人は台を使わなくてもいいです。自分の直前の人が、自分よりも背が高い場合は、差分を足し合わせていき、さらに、前の人の高さを自分の高さとして更新します。このように前からチェックしていくと、一つ前の人の高さを確認するだけで、条件をすべて満たすことができるようになります。

差分の合計が最小値になります。

E-Bomber

各行、各列ごとにいくつの爆弾があるかをそれぞれカウントし、一番多い行と列の数字を足し合わせます。この時、選んだ行と列の交点にあたるマスに爆弾がある場合は重複してカウントしていることになるので、足し合わせたものから1引く必要があります。最多の行ないし列が複数ある場合もあるのでその点にも注意が必要です。

各行と列については行番号列番号と爆弾の数をpairにしたvectorで管理しました。爆弾の位置も管理しないといけないため、初めは二次元配列で管理しようとしましたが、サイズが大きくてバグっていることに気が付きませんでした。爆弾の数は30万個以下なので、setでx、y座標を管理することで交点についてチェックできるようにしたところACとなりました。

今回は以上です。

Dも出来そうで出来ない状態なので、早めに通しておきたいです。