AtCoder Beginner Contest 350（Promotion of AtCoderJobs）に参加しました。
結果
A,B,C,Dの4問正解でした。
個人的にはC問題が面白いなと思った。自分でソートを実装してどことどこを入れ替えるかを答えるというのは、 ソートの種類ごとの計算量とかを把握していないと実装はできてもTLEしたり交換はN-1回以内とかの制約に引っかかると思う。バブルソートなんて実装したらとてもじゃないけど通せない。
A - Past ABCs
ABCXXXのようにABC＋数字3桁の6文字が与えられるので、それはこれまでに開催されたコンテストの略称かどうかを答える問題。 開催されたコンテストはABC001からABC349の範囲でABC316だけは誤答になるのでそこだけは例外的に処理が必要。
単純に処理するなら文字列の大小比較するだけで解けると思う。 ABC001以上かつABC349以下であり、ABC316ではない時はYesと出力して違うときはNoと出力するだけの問題。
プログミング言語的に文字列の大小比較がただの演算子でできるなら特に困らない問題だと思う。
最初の3文字はABCで固定なので後ろの三文字を取り出してどうにかして数値に変換して・・・と処理しても良いけど面倒くさい。
B - Dentist Aoki
最初はN本の歯があってQ回治療を行う。番目の歯があるなら歯を抜いて、歯がないなら歯を生やす(生やす!?）。
最終的に生えている歯の本数を答える問題。
が出てきた回数が奇数か偶数かで、その歯は最後抜かれたのか生やされたのかが判断できる。
配列でどの歯を何回治療したのか管理して、最後に治療回数が偶数回の歯の本数を数えて出力すればよい。
C - Sort
数列が与えられるのでN-1回以内のスワップでソートする問題。 どの位置の数字とどの位置の数字を入れ替えるかを順番に出力して答える。
ソートのやり方はいろいろなアルゴリズムがあるのでまずはその中からどれを実装するか決めて、スワップするときにどことどこを入れ替えたのかを記録していけば解けると思う。
ソートアルゴリズムの計算量を把握して置かないととかのアルゴリズムで実装するとTLEになるので注意が必要。
はじめはクイックソートを実装しようとしたけどテストケースのいくつかがWAになった。サンプルは問題ないから微妙なパターンでバグがあったのかなあ。 クイックソートがダメだったので選択ソートをベースにしつつ連想配列でどの値がどの位置にあるのかを管理して、未ソートの中の最小値がどこにいるのかをすぐに分かるようにして実装した。
D - New Friends
N人の人がいて、友達の友達は友達と言う考えで友達を増やしていった場合、ユーザー全体では今の状態から最大何人友達を増やせるかを答える問題。
サンプルを手計算しながら考えてみると、以下のことに気づいた。
- 人のつながりの状況によってはいくつかグループができる。
- グループ内だと全員と友達になれる。（友達の友達は友達になれて、その新しい友だちの友達とも友達になれるので、結局グループ内の全員と友達となれる。トポロジー的にはフルメッシュになる。）
なので解く方法としては、人と人とのつながりを元にグループ分けする。 グループ内では未設定の友達関係が何組あるのかを数える。
グループ分けする方法は深さ優先探索や幅優先探索、Union-Find木を使うなどいろいろやり方がある。
グループ内で新規に友達となれる組がどれくらいあるのかはグループ内に誰がいるのかと現状何組の友達がいるのかを元に数えていく必要がある。けど、グループごとに配列を用意してまとめて、二重ループでこの組は今友達なのかどうかを確認して、数えてとやってみたらTLEとかWAとかMLEとかになった...
よくよく考えると知りたいのは新規に友達となれる組数だけで、誰と誰が友達になれるのかはあまり重要じゃない。
グループごとの人数と、グループ内の友達の組数だけわかれば、最大何組の友達関係が構築できる中で、今この組数しか構築できていない。よって新規に何組が友達になれるかが計算できる。
なのでこの組み合わせは友達かどうか確認するのをやめて計算して友だちになれる組数を全グループ分求めて答えることにした。
