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)、有理数で持ちます。
しかし、まだ自分は有理数ライブラリを作っておらず、その場で頑張って実装しようかと思いましたが諦めてググったところ、けんちょんさんの有理数ライブラリがヒットしたので拝借したら、無事通りました!
感謝感激。
F - Keep Connect
どう見ても解けそうにないので諦め...
まとめ
いやー、Dで詰まったときはどうなるかと思いましたが、Eが通せて助かりました。有理数ライブラリは作らないとなーと思いつつ作れてなかったんですよね...