ABC233 参加記録
コンテスト中AC:A〜E
C - Product
ボールの数の総積がを超えないので、各袋からボールを1つ選んだ時の全組み合わせも
を超えません。よって、得られる全ての積を配列に保存できます。
部分和DPの要領で、i番目の袋からボールを取った時に得られる全ての積の組み合わせを記録しておきます。そして、それらの全ての積に対して、i+1番目の袋のそれぞれのボールとの積を取ります。これをN番目まで繰り返します。
積の値は非常に大きいので、部分和DPのように配列のインデックスと積を一致させられません。そこで連想配列を使用します(C++のmap)。
連想配列は、ボールの積をキーに、その積の組み合わせ数を記録します。
気をつけたいのが、積がオーバーフローする場合です。
gccなら、__builtin_smulll_overflow関数でオーバーフロー検知できます。
書いてみて、mapで確保するメモリの領域が多くなってしまう場合を考慮できていなかったことに気づきました。now,nextのように2つの配列を使い回した方が安全かもしれません。
また、全組み合わせが少ないので、同値をまとめなくとも普通の配列(C++のvector)に、個別に記録しておいても良さそうです。
D - Count Interval
連続する部分列について、条件に一致するようにすべての区間を求める問題は以下に示すような典型的考え方があります。
を、
までの累積和、と定義します。便宜上
とします。
半開区間(j, i]のAの連続する部分列の和は以下のように示されます。
よって、満たすべき条件は、
です。式を変形して、
したがって、iを末尾とする連続した部分列であって、条件を満たすものの個数は、上式を満たすjの個数となります。
そこで、以下のようなアルゴリズムで計算できます。
i=1〜Nについて、
・iまでの累積和を得る
・これまでに出現した累積和のうち、と等しいものの出現数を答えに足す。
・の出現数を+1する
出現数の管理は連想配列やハッシュマップですればよいです。
また、最初に累積和0が1個必要なことに気をつけます。
それぞれは各iで計算できるので、計算量はハッシュマップならで、連想配列(C++のmap)なら、
です。
E - Σ[k=0..10^100]floor(X／10^k)
筆算をイメージすると分かりやすいです。
X = 5891を例にします。
0は無視すると、求める和sumは、
です。説明のため、以下のように変形します。
それでは、sumの1桁目と2桁目を求めてみます。
1桁目はのみによって決定され、10の指数が0以外のものの影響を受けません。よって、
となり、1桁目は3です。
2桁目は、と、1桁目で計算した時に発生した
との和によって決定されます。この時も、10の指数が1以外のものの影響を受けません。よって、
となり2桁目は4です。
以下同様にして3桁目以降も求められます。
このように、sumのi桁目は、前の桁からの桁上がりと、元々のの係数の和のみによって計算できます。また、桁の重みである10の冪乗は無視できます。すなわち、先程の2桁目を求めるとき、
の2桁目を求める問題だったのを、
の1桁目を求める問題とみなすことができます。
これは、筆算で桁毎に独立に計算することと同じ意味です。
の係数は以下のように、
で計算できます。
Xの各桁を1桁の整数とみなした時に得られる整数列とします。更に、ここから得られる
までの累積和を
とします。
すると、最初の方に示した式は、以下のように書き変えられます、
このように、元々のの係数は、Xの各桁を1桁の整数とみなしたときの累積和をとっておけば、
で求められます。
具体的なアルゴリズムとしては、
XがN桁あるとし、桁上がりを示すcarry = 0とし、i = 1〜Nまで以下を繰り返します。
1.とする。
2.とする。
3. を
のi桁目とする。
4. とする。
1番目の計算ですが、桁上がり値は、１つ上の桁より大きくなる可能性があるので、該当の桁のみ取り出しています。
気をつける点として、このアルゴリズムが終了した時点で、carry > 0なら、0となるまで上記アルゴリズムのを0にして実行する必要があります。
上はの係数を意識するため、書き直したものです。以下はコンテスト中の実装です。
carryは該当の桁のみを取り出さなくても計算できます。
1.とする。
2. を
のi桁目とする。
3. とする。
