[AtCoder] ABC 179 D – Leaping Tak
動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...
[yukicoder] No. 1233 割り切れない気持ち
\ であることを利用して、
\
となります。ここで、
\
について考えます。自然数 \( k \) を用いて、\( A_i \) が
\
を満たすとき、
[yukicoder] No. 1220 yukipoker
全ての手札の組み合わせは \( {}_{NM} \mathrm{ C }_{K} \) 通りありますが、確率を比較するうえでは必要ありません。フラッシュの総数は、同一のソートから \( {}_{N} \mathrm{ C }_ ...
[AtCoder] ABC 177 C – Sum of product of pairs
与えられた式は、
\
となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、
\
となります。よって、あらかじめ累積和を計算してから求め ...
[AtCoder] ABC 174 D – Alter Altar
条件を満たす石の並びは、先頭から \( i (0 \leq i \leq N)\) 個目までが赤石で、以降は白石です。\( i = 0 \) のときは全てが赤石で、\( i = N \) のときは全てが白石です。し ...
[AtCoder] ABC 166 E – This Message Will Self-Destruct in 5s
配列の添え字を \( i, j (i < j) \) とすると、
\begin{eqnarray}
j – i &=& A_i + A_j \\
i + A_i & ...
[AtCoder] ABC 158 E – Divisible Substring
大まかな方針は、下の問題と同じです。
\( P = 2 \) または \( P = 5 \) のとき\( S = s_N s_{N-1} \cdots s_1 \) とします。
このとき、\( s_i ...
[AtCoder] ABC 164 D – Multiple of 2019
\( 12114 \) は \( 12114 = 2019 \times 6 \) なので \( 2019 \) の倍数です。次に、\( 1211472\) という文字列を考えると、\( 12114 \) という文字列があるの ...
[AtCoder] ABC 172 C – Tsundoku
机 \( A \) の本を \( i \) 冊読んだとき、机 \( B \) の本を最大でいくつ読むことができるかを考えます。机 \( A \) の本を \( i \) 冊読むのにかかる時間は、累積和で求めるこ ...
[AtCoder] ABC 162 D – RGB Triplets
まず初めに、\( S_i \neq S_j \wedge S_i \neq S_k \wedge S_j \neq S_j \) を満たす組の数を求めます。これは、\( i, j \) について、\( S_i \neq S_j ...