ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）に参加しました。
結果
A,B,C問題のの3問ACでした。 C問題まではサクッと解けたけどD問題は全然分からなかった…
A - Lacked Number
問題文の通り解けば良い。
0~9まで出てきたかどうかをフラグ管理して、出てきていないものを表示させれば良い。
C++なら文字を数値に変換するのは数値を表す文字から'0'を引けば良い。
例：'9'-'0'
B - Slimes
問題文の通りに解けば良い。
ループ文でスライムの数がB以上になるまでK倍し続けて、何回K倍にしたのかを答える。
A=1、B=、K=2の場合でも答えが30程度なので愚直に解くのでも十分間に合う。
C - Dice Sum
DP[x][ ]=何通り としてDPで解けば良い。
の最大値でも2500程度なのでメモリ不足とか配列が確保できないとかにはならない。
D - Range Count Query
ACできる解き方が全く思いつかなかった…
任意の区間で条件を満たす物の数を答えると考えれば尺取り法が使えそうな気がした。
あとはクエリを処理する系の問題なので、いくつかのクエリをまとめて処理するとか、最後から処理していくとかがよくある解き方だから使えそうか考えたけど、今回は使えなさそう。
次に制約を見てわかることとしては、
数列の長さは最大ででクエリの数も最大で
なので各クエリでLからRまで線形探索をするとTLEになりそう。
なので各クエリでくらいで解きたい。あるいは事前に何らかの処理をしておいて各クエリにはO(1)で答えたい。
なので1～iまでで何が何個出てきているのかを管理しつつ各クエリにはO(1)で答えるという方針で解いてみたけど、”1～iまでで何が何個出てきているのかを管理する”の部分が遅くてTLEだったりREだったりした。
