little star's memory

競プロの参加記など

AtCoder Beginner Contest 187

だめだったね。

atcoder.jp

以下は感想。

A - Large Digits

桁和を求めればおわり。

B - Gentle Pairs

傾きは$\frac{y_i-y_j}{x_i-x_j}$

C - 1-SAT

!がつかない文字列からなるsetと、!がつく文字列からなるsetを用意して、共通部分があるかを調べる。

D - Choose Me

(高橋票)-(青木票)が正になるようにする。ある町で演説をすると、2a+bがこの値に加算される。よって2a+bの大きい順にソートすればよい。

提出した瞬間にオーバーフローすることに気づいた。注意1秒ペナ5分。

E - Through Path

Dまで解いたときに、EよりFの方が解かれてたからしばらくFのほうを考えてた。わからなくてもう1回順位表を見たらEの方が解かれてたし、普通にEの方が簡単だった。

簡単だったとはいえ実装で無限にバグらせた。これが一番の反省ポイント。

こういうのは根付き木にするのが定番。辺u,vに操作を行うとして、uの方が上にあるとする。この問題のテクニックを使う。vから出発してuを通らないようにして到達できる頂点に加算するときは、シンプルにvに加算する。逆のときは、根に加算して、vから減算する。

最初再帰で書いてたけど、REが出た。前にもやらかしてたな。ACしたコードも1917 msだから相当遅い。どこが遅いんだろ。

F - Close Group

クリーク求めればよさそうと思って、いろいろ調べてたけど何一つ合わなかった。そしてこの解法も冷静になると間違ってる。

ABC174Fも、ABC179Fも、ABC186Fもそうだったけど、検索して出てきたアルゴリズムを写経 or C++コードを流用してACできないのが一番楽しくない。C++という難解言語の解読をしていて楽しいか?そういうものを求めて競技プログラミングしてるんじゃないんだよね。どうしてC++が覇権なんだろう。

最近競プロで楽しい思いしてない気がするなあ。一旦離れた方がいいのかな。かなり限界を感じている。