Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 152

3完。今年初めての激冷えですね・・・。Dを捨ててEを取って失敗した結果ではあります。今回はこの選択に悔いはないです。

各問題

A - AC or WA

N == MならYes、そうでなければNoですね。

B - Comparing Strings

実際に文字列を作って、比較すればよいです。数字を文字(列)に変換して、ループして結合していけばよいです。

で、今気づきましたが、数字が小さいほうが辞書順で小さくなるので、そっちを出したらいいような・・・。例えば3 4なら3のほうが小さいので3333が答え、という要領で。(Editorialにも書いてありましたね。)

C - Low Elements

一瞬、これがCかよ!?って思いましたが、気づけば簡単なやつですね。

前から順に最小値を保存しながら見ていって、今いる項の値が保存した最小値を上回っていなければ、その項は条件を満たします。最小値を上回っていないのなら、その他のどの項も上回ることはないので。

D - Handstand 2

うわー、なんだか面倒くさそうだー、と思って先にEをやりました。

最後までこっちに戻ってこれませんでした。on_

E - Flatten

Aのすべての項の最小公倍数をとって、それをAiで割ったものがBi、なのはすぐわかったのですが、最小公倍数が爆発するため、そのままではいけません。 そこで、素因数分解して扱えばいいということに思いあたりました。

ここまでEditorialと同じです。あってます。

ところが、TLEしました。実装が何かまずかったようです・・・。

(追記)

最小公倍数 / A を(素因数分解された形で)愚直に計算すると間に合わず、Aの逆元を取って足し合わせてから最小公倍数をかければよかったようです。

Submission #9635300 - AtCoder Beginner Contest 152

maspyさんの記事を参考にさせていただきました。

maspypy.com

F - Tree and Constraints

見てません。

まとめ

Eの考察がなまじできてしまったがために立ち回りに悪い影響を与えてしまいました・・・。

まあ考察が間違っていたわけではないので、今回はベターな判断だったと思うことにしましょう。

f:id:mdstoy:20200120005139p:plain