Toy と帽子と ADP BE

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

ユニークビジョンプログラミングコンテスト2022(AtCoder Beginner Contest 248)

5完3WA2TLE。

けんちょんさん (@drken1215) の有理数ライブラリのおかげで命拾いしたー。

各問題

A - Lacked Number

0から9までのバケツ(要するに要素数10の配列)を作って、与えられた数字を一つずつ確認してバケツに入れて(つまりa[数字]を+1して)いき、最後に空っぽのバケツが一つあるはずなので、それが答える数です。

後から気づいたのですが、9文字の中に0があるか確認、1があるか確認、... と9まで全探索すればよいだけでした。(たいして実装内容に差はありませんが)

ところで、バケツの中身を確認する処理で、9を確認するのを忘れており1WA出しました。(あほ

B - Slimes

AをBを超えるまでK倍していきます。何回K倍したかが答えです。K倍した結果がintに収まらない可能性があるので注意です。

C - Dice Sum

複雑そうな問題文ですが、要はN×KのDPをするだけです。最終的な答えはΣdp[N-1][i]です。

D - Range Count Query

A_iの値ごとに、出現したインデックスを配列で持ちます。クエリ毎にLとRの間に含まれているインデックスが該当するインデックスなので、それを数えるためにLとRで二分探索します。

WAやTLEを出してしまったので、配列が空のとき二分探索しないようにしたら通りました。まじか...。

E - K-colinear Line

まず、K=1のときは必ずInfinityです。それ以外でInfinityはないので以下K=2の時を考えます。

2点間の傾きとy切片のペアを全探索して、同じペアを持つi, j をsetで管理します。要するにmap<pair<傾き, 切片>, set<int>>を作って管理です。(ただしx=a型の直線の場合は傾きが求められないため例外として、傾きと切片ではなくx座標だけで別に管理します)

setの中身がK以上の直線がほしい直線なので、その数が答えとなります。

ところで、傾きや切片をdoubleなどで持って実際に計算してしまうと誤差で死んでしまうので(これで1WA)、有理数で持ちます。

しかし、まだ自分は有理数ライブラリを作っておらず、その場で頑張って実装しようかと思いましたが諦めてググったところ、けんちょんさんの有理数ライブラリがヒットしたので拝借したら、無事通りました!

drken1215.hatenablog.com

感謝感激。

F - Keep Connect

どう見ても解けそうにないので諦め...

まとめ

いやー、Dで詰まったときはどうなるかと思いましたが、Eが通せて助かりました。有理数ライブラリは作らないとなーと思いつつ作れてなかったんですよね...

f:id:mdstoy:20220416230714p:plain