HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)に参加しました。
結果
A,B,C,Dの4問正解でした。
D問題がちょっと詰まったけど、少し考え込んでちゃんとACできたのが嬉しかった。
E問題はちょっと考えたけど解き方がちょっと思いつかなかった。
A - Generalized ABC
問題文の通り処理する。
C++なら'A'へ1ずつ加算しながら出力すれば良い。 あるいはA~Zまで連結した文字列を用意して先頭からK文字を表示させるのでも良さそう。
B - Let's Get a Perfect Score
N人の中から条件を満たすペア数を出力する問題。
制約を見ると人数は十分小さいし、条件の判定に用いる文字列も十分短い。 だから、全通りのペアを順番に条件を満たすか確認していけば良い。
C - String Delimiter
"で括られた文字列か、そうじゃないかを判断しながら、を.に置き換える問題。
文字列の長さはそこそこ長いのでくらいで解けるアルゴリズムじゃないとTLEになりそう。
簡単そうなのは、”で括られている最中なのか”で括られていない部分なのかをフラグで管理しながら 線形探索で文字列を見ていく。途中で,が見つかったときに”で括られている最中ではない場合は,を.に置き換える。
最後に編集後の文字列を出力する。
D - Make Bipartite 2
二部グラフかどうかを判定して、二部グラフだったら条件を満たすノードのペア数を答える問題。
二部グラフの判定は、グラフに対して幅優先探索とか深さ優先探索しながらノードを色分けしていき、 今注目しているノードの色と隣接しているノードの色が被らないなら二部グラフと判断できる。
二部グラフであることを確認して色分けした後は、辺を追加しても二部グラフのままになるノードペアの数を数えて出力する。 ただ、二重ループなどで全ペアを確認していればTLEになるので全通りの数え上げ意外の方法でペア数の計算が必要。
ここで少し躓いたから少し考えた。最終的に欲しいのは、2色に色分けした後で色が異なるノード同士の組み合わせから最初にある辺を除いた数だから、
1色目と2色目のノードの数をそれぞれ数えれば計算して求められることに気づいた。
ノードのペア数はN(N-1)/2で、1色目のノード数がｘ個、2色目のノード数がy個なら
両端が異なる色となるペアの数は N(N-1)/2 - ｛（x(x-1)）｝/2 - ｛y（y-1）｝/2 になる。
ここから最初にある辺の内両端の色が異なる辺が何本あるか数えて上記の計算結果から引けば良い。
これならO(1)で算出できるのでTLEしなくなる。
後は、ノードが全部で1つの木（連結成分）になるとは限らないのですべての連結成分に対して上記の処理を行っていく。
全部の連結成分を処理する部分のうまい実装方法が思いつかなかったので、グラフを2色に色分けしているときにやっている探索でチェック済みかどうかを判断するフラグを流用した。
具体的には、フラグを確認しながらまだチェックしていないノードを探し、見つかったらそのノードを根として二部グラフの判定から処理を行っていく。
一連の処理が終われば次の未チェックノードの探索を再開して、全部のノードがチェック済みになるまで繰り返していく。
全部のノードがチェック済になったら計算した結果を集計して答えを出力する。
