Blog ブログ

こんにちは。エンジニアリング事業部の秋月です。

今回は、AtCoder Beginner Contest 304の参加記になります。

問題文についてはリンク先をご参照ください。

A – First Player

A問題にしてはえらい複雑な問題で面食らいました。
最年少からはじめてmodをとれば良いです。
提出

B – Subscribers

こういった問題はstringとして受け取った方が楽です。
こっちがA問題でも良かった気がします。
提出

C – Virus

各頂点間の距離を計算して辺を張ったあとにDFSすれば良いです。
提出

D – A Piece of Cake

a, bそれぞれについて二分探索で位置を求め、pairをkeyとしたmapを作成すれば最大値がわかります。
最小値は得られたmapのkey数が(A+1)*(B+1)ならばmap内の最小値が答えになります。そうでない場合には0になります。
map生成のミスで1WA、最小値の求め方のミスで1WAの2WAでした。
提出

E – Good Graph

GをUnion-Find木で管理し、各x_i, y_iに対して根のpairを作成し、setに入れておきます。
各クエリに対して、p_i, q_iに対して根のpairを作成し、それがsetに含まれるかを出力すれば良いです。
なお、c++のpairの比較はfirst同士, second同士の比較になるため、pair生成時に小さい方をfirstにするなどの対策をしておく必要があります。
提出

感想

ジャッジが詰まっていたのがしんどかったです。コンテストがunratedになったためrateの変動はありませんでした。