AtCoder Beginner Contest 172
ABC172に参加しました。
Cをめちゃくちゃにバグらせた結果、解けたはずのDも落としたのでかなり苦い回になりました。Bまではそれなりに早く解けたので大丈夫まだ焦るような時間じゃないと言い聞かせています。
Tasks - AtCoder Beginner Contest 172
All Submissions - AtCoder Beginner Contest 172
A-Calc
計算するだけですね…。
B-Minor Change
SとTを前から見比べて、違う文字になっていればカウントしていきます。
C-Tsundoku
Cは解けるだろうと高をくくっていたので、積読か~~あるあるwwwとか思いながら実装し始めたところ完全に終わってしまいました。
まず机Aの本を順番にK分になるまで読んでいき、その後一冊ずつ読む数を減らしていって、都度机Bから読めるだけ読んでいき、カウントを更新するという方針で実装しようとしました。結局コンテスト後にもこの方針ではAC出来ていません…。どこが間違っているのかわかりませんが、少し時間を空けてリトライしようと思います。1冊も読めない時の添え字の扱いとか多分そういうことだと思うのですが…。
せめて解説ACはしておきたいと思い、コンテスト後に解説PDFを見ながらACしました。X冊目まで読むのにかかる合計の時間を机ごとに前計算しておき、しゃくとり法のイメージで実装するとすんなりACできたので、バグらせにくい方針で解き始められるのは大切だなあと改めて実感しました(コンテスト二回ぶりN回目)。
D-Sum of Divisors
コンテスト中ほとんど考えなかったのがもったいなかったですね。
コンテスト後にエラトステネスの篩の要領で、実装しACしました。
あらかじめN+1個の配列を用意し、2<=i<=Nの範囲で、各iの倍数に1ずつ足していくことでN+1個分のそれぞれの約数の個数をカウントすることができます。C++であれば1.4秒くらいでできるようです。
頑張ればできたんじゃないかという気はしますが、まぁたどり着くこともできなかったので言っても仕方ないですね。
今回は以上です。
Eも解説見ながらならできるかもしれないので考えておきたいです。