A
問題概要
A-Isosceles
三角形の\(4\)辺の長さが与えられる。二等辺三角形か判定しなさい。
不正な三角形は入力として与えられない。
解法
特に何も考えず、 \(3\) 辺のうち少なくとも$2$辺の長さが等しければその三角形は二等辺三角形である。
もし不正な三角形が入力される可能性があるなら、一番長い辺がそれ以外の辺の長さの合計より短いかどうかを判定すればよい。
提出
https://atcoder.jp/contests/abc424/submissions/69509904
B
問題概要
B - Perfect
\(N\) 人が \(M\) 問からなるコンテストに参加した。人 \(A_i\) が問題 \(B_i\) に正解した情報が与えられる。全ての問題に正解した人の番号を正解したタイミングが早い順に出力しろ。
解法
入力の制約で \(i \neq j \rightarrow (A_i , B_i) \neq (A_j , B_j)\) が保証されている。
なので人ごとに正解数を管理しておいて正解数が \(M\) になった瞬間に答えを保持する配列にメモすればよい。
提出
https://atcoder.jp/contests/abc424/submissions/69510002
C
問題概要
C - New Skill Acquired
\(N\) 個のスキル \((A_i,B_i)\) が与えられる。
\((A_i,B_i) = (0,0)\) のときスキル \(i\) を習得済みであり、そうでないときはスキル \(A_i,B_i\) のどちらかを習得していればスキル \(i\) を習得できる。
すでに取得済みのスキルも含め、最大で習得できるスキルの数を求めろ。
制約
\(1 \le N \le 2 \times 10^5\)
解法
\((0,0)\) のスキルからBFSをすればよい。 このとき、\(A_i\) (もしくは \(B_i\) )) を添え字に持ち要素をスキルの添字にするような配列を持てば、あるスキルから次どのスキルを習得できるかが高速に探すことができる。合計ステップ回数が \(N\) 回比例になる。