AtCoder Beginner Contest 292に参加しました。
結果
A,B,C,Dの4問正解でした。
途中よくわからないバグでエラーが起きたり、コードは間違っていないはずなのにテストケースの答えが一致しなかったり、かと思えば大してコードを変更していないはずなのに今度はちゃんとテストケースと答えが一致して無駄に時間をロスしたりと、珍しい現象でちょっと時間を無駄にしたコンテストだった。
A - CAPS LOCK
英小文字の文字列を英大文字の文字列へ変換し出力する問題。
C++ならtransformと_toupperを組み合わせると1度の処理で文字列全体を変換できるのであんまり困らない。
もしくは1文字ずつ大文字に変換して出力する。a~zとA~Zはそれぞれchar的には連番なので各文字の値にaとAの差（aとAの距離）を足せばtoupperとか使わなくても大文字に変換できそう。
B - Yellow and Red Card
イエローカードかレッドカードが提示されるイベント（クエリ）がいくつか与えられるので、選手別に退場しているかどうかを管理して、指定された選手が退場しているかどうかを答える問題。
クエリを処理しながら指定された要素の状態を答える問題であり、クエリの数はそれほど多くないのでクエリを順次処理しながら答えていくのでも十分間に合いそう。
答える時には何かしらの値を参照するだけで判断したいので、選手別に状態を管理できるようにしておく。
選手の人数はそれほど多くないので、選手の人数分の配列で状態を管理すれば良い。
イエローカードは2回で退場、レッドカードは1回で退場なので、レッドカードはイエローカード2回分とみなして
各選手がイエローカード何回提示されているのかをカウントしておく。
退場処分を受けたか質問されると、その選手がイエローカードを2回以上提示されているかどうかでYes/Noを判断して答える。
C - Four Variables
AB+CD=NとなるA,B,C,Dの組み合わせ数を答える問題（A,B,C,D>0）。
考えたこととしては
- 愚直に得ならA,B,C,Dをそれぞれ1~Nまで全通り試して解く。けど
になってTLEするのが目に見えるので論外。
なので
くらいの解じゃないとTLEになりそう。
- A,B,C,D>0なのでAB,CDの最小値は1で最大値はN-1までを考えておけば良い。
- ABを1から1ずつ増加させると、CDはN-1から1ずつ減少していく。
- AB=XとするとCDはN-Xであり、C=1、D=（N-X)で条件は満たせるのでAB,CDはそれぞれ1~N-1までの全ての値の可能性があり得る。
- 1~N-1までのA,Bの組み合わせ数をどうにかして計算しておけばその結果はC*Dの組み合わせ数としても利用できる。
だから、次に1~N-1それぞれのA,Bの組み合わせ数を計算しようとした。 これはA*B=XとなるA,Bの組み合わせの数になる。そしてこれはXの約数の個数と一致する。
よって問題を解く手順としては以下になると考えた。
- 1~N-1それぞれの値の約数の数を求める
- A*B=Xとした時、1~N-1まで順番に、Xの約数の数
(N-X)の約数の数 を計算し合計する。
- 合計した値を出力する。
D - Unicyclic Components
無向グラフが与えられるので連結成分ごとに頂点の数と辺の数が一致するかどうかを計算し、一致しないものが1つでもあればNoをそうでないならYesを答える問題。
連結成分ごとに処理するので、Union-Findを使ってどの頂点が連結成分になっているのか判断するのが楽そうだと思った。
どのへんがどの連結成分に含まれるのか分かれば、連結成分ごとの頂点の数を数えるのは簡単にできる。 また、頂点がわかればその連結成分に何本の辺が含まれているのかが計算できる。
そこで以下の手順で解いてみた。
- Union-Findで各頂点はどの頂点をRootとする連結成分に含まれるのかを計算する。
- 各頂点で 頂点→Rootの値からどの連結成分に含まれるか判断し、Root別に自分をRootとする頂点の数、その頂点が持つ辺の数を数える。
- 各Rootで 自分をRootとする頂点の数 と その頂点が持つ辺の数の合計 が一致するかを確認する。
- 1つでも一致しない場合があればNoを出力して処理を終了する。
最後まで処理が終われば全ての連結成分で条件を満たすことになるのでYesを出力する。
