81. AtCoder参加記録（AtCoder Beginner Contest 243）

前回は私用で出られなかったので2週間ぶりのABCです。

現状です。9回参加でレート 908 です。14回参加してないので若干低めのレートになっているようです（補正期間長い…）。

今回はパフォーマンス 1317 で、過去最高でした（水色パフォ）。

ABCDを通して、EはWA、FGExは未解答です。悲しいミスにより、Cで1ペナです。

各問題の感想です。

A

素直に書くだけです。

初め、「毎晩」という条件を見逃していて「条件を満たさない場合の出力はどうするんだろう？」と思っていたのですが、入力例2で理解しました。

B

各数列に含まれる要素が全て異なるという制約があるので、簡単になっています（制約がないとややしんどい）。

まず Hit だけ数え上げて、各列に含まれていた数字を HashSet で保持しておき、これを用いてあらためて Blow をカウントします。

C

動くのはX軸方向のみなので、とりあえずY座標ごとに分類します。

分類したものをそれぞれX座標昇順に並べ替えます。これで、「Rが出た後に」Lが出るパターンがあれば衝突します。

ホントにどうしようもなくしょーもないミスで1回WA出しました。変数まで用意してたのに条件式に入れ忘れていたという…。

D

制約がバカでかいので文字列で扱います。二分木なので2進数で考えるのが筋が良さそうです。

ここで、親・左の子・右の子を2進数で表すとどのような関係になるのか考えました。すると、

• 親→左の子: 末尾に 0 を足す
• 親→右の子: 末尾に 1 を足す
• 子→親: 末尾を削除する

となることが分かりました。これを文字列として処理して、あらためて10進数に組み立て直せば良いです。

ライブラリ整備などで二分木をよく扱っていたためか、割とすぐ解けました。

E

とりあえずクラスカル法で最小全域木を出して、その後ダイクストラ法で各頂点間の最短距離を計算し、採用されていない辺を加えたときに、その2点間の距離がより短くなるなら採用する…としたのですが、WAが取れませんでした。なんでだろう。

F, G, Ex

Fはちらっと見て、なんとなく手が出そうな雰囲気を感じましたが時間的に諦めました。G,Exは見てないです。

Cのケアレスミスは、事故と言えば事故ですが悲しいですね。あと、どうもグラフ問題に苦手意識がありそうな気がしてきました。グラフは扱う道具が割と限られている印象なので、数をこなして得意分野にすれば武器になりそうだなぁ…と思っています。

とりあえず、あんまり学習を進められていなかったので、これからぼちぼちとペースを取り戻していきたいです。