読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 065

お酒を飲んだあとに参加したけど、あんまり影響はなかった。

 

以下感想。

 

C問題 白昼夢

4種類の文字列を追加していくことで文字列Sを作ることはできますかという問題。

dreamとdreamer、eraseとeraserは先頭の方の文字が一致しているので先頭から見ていくと泥沼なので、末尾から見ていく。

(stringの仕様がわからずstringのアレコレを調べながら書く。)

AC

D問題 連結

道路と鉄道の線路が街にいっぱいあるので、道路でも鉄道でも連結であるような街の数を街ごとに答える問題。

とりあえずunion-findかぁということでこの前書いたunion-findを持ってくる。

とりあえず道路のunion-findして、道路が同じ成分だったら鉄道についてもunionを取ればいいか〜。とりあえず手元のは通ったしいっけぇーサイクロンマグナム!

➔WA

道路が1⇔3、鉄道が1⇔2、2⇔3とかで普通に落ちる。酷い思い違い。

しょうがないから道路と鉄道で連結成分を全部計算。

<<道路の成分、鉄道の成分>、街の番号>というvectorをつかってソートして端から順にunion-find。

連結成分の数をそれぞれの街について出力。

➔AC

多分絶対もっと賢い方法があるんだろうなぁ。

 

EもFもわからず。(F考察しようとしたけど破滅的な方向へ進んで無事終了)

 

136位。パフォーマンス2058 新レート1852(+30)