AtCoder Beginner Contest 177に参加しました

ABC177に参加しました。

A~Eの5完でかなり満足しました。自分にも解けるということは、現状ほかの人も解けるということなので、順位はそこまでよくはなかったですが…。

All Submissions - AtCoder Beginner Contest 177

A-Don't be late

小学校の算数みたいですね。

B-Substring

Tの大きさをLとして、1文字目からL文字目までがTと一致するように書き換えた文字数を数えます。同様に始点を2文字目にして、そこからL文字の間をTと一致するように書き換えた文字数を数えます。以下同じように始点をずらしていくと、書き換える必要のある最小文字数が分かります。Sの大きさはたかだか1000文字なので、この方法で間に合います。

C-Sum of product of pairs

愚直に計算していては時間制限に間に合わないので、工夫しました。i<jとなる組の積の和を求めるので、iを固定して考えると、i=1の時にjは2~Nまで、i=2の時にjは3~Nまで、以下iが増えるごとにjの取る範囲が減っていきます。固定したiごとに考えると、A1*(A2+A3+.......+AN)、A2*(A3+A4+.......+AN)というようにまとめることができます。あらかじめN個のAの値を足しておくことで、そこからAiの値を引いてからAiとの積を取ることで高速に計算できます。

D-Friends

友達の友達はみんな友達理論です。N人の集合の中に友達関係でつながった友達集団がいくつかできているということになります。これを、同じグループに友達が一人もいない状況に全員がなるようにグループ分けし、グループ数の最小値を求めるという問題です。これは、友達集団の構成人数が一番多いところを全員バラバラのグループに入れることで達成できるので、最大の友達集団の構成人数が答えになります。

Union-Findでできるやつや！と思いましたが、実装したことがないですし、構成人数が分かればいいので、DFSで友達関係を辿っていくことでそれぞれの集団の規模を調べることにしました。一度確認した人を複数回確認する必要はないので、確認の有無を入れておく配列を用意し、再帰関数で実装しました。

再帰関数でDFSを書く練習になってよかったと思います。

E-Coprime

方針が出来れば解けるタイプの問題なのかなと思いました。

pairwiseとsetwiseを独立で考えるか、両方をまとめて判定するかでまず大きな方針が決まるように思います。私ははじめ、1つの判定方法でまとめて一気に求めようとしていましたが、どうにも考えがまとまらなかったので独立で考えることにしました。pairwiseではない時のみsetwiseになる可能性があるので、まずはpairwiseであるかどうかを考えます。各Ai,Ajの組み合わせについてそれぞれ確認していては時間が足りないので工夫します。すべてのGCDが1ということは、N個のAのなかで、1以外の約数を共有していないということになります。そこで、エラトステネスの篩の要領で配列を用意し、まずAiの約数を列挙し、それぞれの約数について、倍数をチェックしていきます。この時、初めに小さい順にsortをかけておくことで、各Aiについて最初にAiがすでにチェックされているかを確認し、その後は約数とその倍数をチェックしていくだけでいいようになります。もし、約数が重複していた場合はpairwiseではないのでそこで確認を打ち切ります。計算量が多くなるかなとも思ったのですが、100万以下の素数の数は10万個もないですし、約数が重複しないように制限の中で数を用意した場合は1つ1つの値が小さくなり、また制限時間を超えるほどの数を用意できないと思ったのでこの方針で出しました。

次にsetwiseについて考えます。これはGCDを順に考えていくだけで済みます。最初にsortしているので、小さいものから順にGCDを取っていくことができます。GCD=A1としてスタートして、A1からANまで順にGCD(GCD, Ai)としていくことで拘束に求められます。GCD=1となった時点で打ち切ります。

今回は以上です。

コンテスト中に自力で解いた方法を記録していると、ほかの方のきれいな解法や実装と比べた粗がはっきりするので勉強になる、と言い聞かせてやってきました。これまではなかなか実感としてはそのようには思えませんでしたが、ABC170ごろからははD,Eまで解けることも増えてきて、比較的難しい問題を何とか通す、という状態によくなるので価値を感じ始めています。