UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)に参加しました。
結果
A,B,D問題の3問正解でパフォーマンスが833でした。
C問題がACできなかったのが悔しい。思いついたコーナーケースは潰したけどWAが1つだけ残ってわからなかった…
A - Distinct Strings
何種類の文字があるかで作れる文字のパターン数が決まるので、setに1文字づつ入れてそのサイズを取得すれば良い。 もしくはnext_permutationで全通り文字列を作ってそれが何通りなのかを数える。
B - Star or Not
木がスターかどうかを確かめる問題。
各頂点の次数を数えて、1つだけ次数がN-1、他はすべて次数が1となっていればスター。そうじゃなかったらスターじゃない。
D - Play Train
問題を読んでいるとUnionFindTreeを使えば楽そうと思いつつ、出力するデータは連結の前から後ろまで順番にってあるのでUnionFindTreeよりは双方子に参照できる連結リストのほうが良さそうって思った。各電車の前後には1台ずつしか電車はつながらないので各電車の前と後ろだけを管理して処理をした。
出力時の処理は制約的に1重ループでも間に合いそうなので愚直に実装して処理した。
