期待値、そろそろ逃げずに履修しようね
A - Past ABCs
全部書けばよいです(？)
B - Dentist Aoki
この手の問題で高橋くんが歯医者じゃないの珍しい気がする。
操作に忠実にやれば答えがわかります。歯が生えてるかの判定はtrue/falseでやれば良さそうだけど、焦っててu64で処理してた。
C - Sort
適当に実装してたら1ペナ食らった。以前なんかのツイートで見たことあるやつだ！ってなった。
前から順に見ていって、i番目に今iという数字がおいてある位置jを選んでスワップすればよく、これに則って操作を行えばn-1回目の操作で[1, n-1]の値が正しく配置されるため、残るn番目の値も正しく配置される。なので、n-1回の操作でsortが達成可能なので、これを実装すれば良い。
D - New Friends
ユーザを頂点、FF関係を辺としてみたときに、ある頂点と直接接続されていないが連結であるような場合、操作によって新たに友達になることが可能である(これは操作が再帰的に行うことができるため)。ここで、連結な頂点集合において、E頂点あるなら合計で(E-1 + E-2 + ... + 2 + 1)辺を作ることができ、操作を行える回数は現状存在する辺の数を Vとして(V - (E-1 + E-2 + ... + 2 + 1))回である。これを達成するには、BFSなりDFSで連結な成分に存在する辺の数や頂点数を数えていけば良い。
E - Toward 0
期待値わからん... ><