Toy と帽子と ADP BE

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

AtCoder Beginner Contest 224

ABCFの4完。

F問題まじで神。

各問題

A - Tires

最後の一文字が'r'か't'かで判定すればよいです。

B - Mongeness

4重ループの全探索を書けばよいです。

C - Triangle?

3点の座標から面積を導出する公式(の一部)を使って面積を実際に計算し、0かどうかを判定すればよいです。

(が、しかし、それに気づくまでに20分以上かけてしまいました・・・)

D - 8 Puzzle on Graph

しばらくこれを考えていましたが、可能性の判定も確たる方法はわからず、移動回数の判定に至ってはまったくわからず・・・。

E - Integers on Grid

全然見当もつかず・・・。グラフに落とす系?とか思ってましたが、解説をチラ見したらDPとか書いてあって全く見当はずれでした。

F - Problem where +s Separate Digits

例えば1234の場合、1は1000の位で1回、100の位で1回、10の位で2回、1の位で4回登場します。 2は100の位で2回、10の位で2回、1の位で4回登場します。 3は10の位で4回、1の位で4回登場します。 4は1の位で8回登場します。

これには規則性があることはわかりますが、上から順に処理してもO(n2)かかるのでだめです。(たぶん)

そこで、位毎に見ていくと、1の位では1234が4+4+4+8回、10の位では123が2+2+4回、100の位では12が1+2回、1000の位では1が1回登場します。これにも規則性があることがわかります。

各桁の数の累積和をあらかじめ取っておくことで、各桁ごとにO(1)で計算することができ、合計でO(|S|)で計算することが可能となります。

まとめ

解けそうな問題をきっちり見極めて解き切れたのは久しぶりかも。

f:id:mdstoy:20211023231255p:plain