[AtCoder 参加感想] 2019/03/22:ABC 159

  A B C D E F
問題文
自分の提出
結果 AC AC AC AC AC AC

スポンサーリンク

全体感想

遅刻参加です。所要時間自体は、35分(1ペナ)でした。

問題 E、第一印象の方針で正しくて、すぐに分かったくせに 15分+ の実装時間がかかっていて、下手でした。

1ペナは問題 F なのですが、numpyのバージョン違いによるものです。何度かやらかした経験のあるものの再発ですが、言語アプデが予告されているので、克服の優先度は低めで・・。

問題A:Aのなかでは最難クラスじゃないですか? わりと意外。問題Cの方が(証明なしなら)易しいという人が多いかもしれません。

問題A – The Number of Even Pairs

問題Aのなかでは最難クラスじゃありませんか?

愚直に探索するなら、balls = [0,0,0,0,…, 1,1,1,1,…] のように並べて、2元の和を全部テストすればよいです → 提出例

$N$ 個のボールなどから $2$ 個を選ぶ方法を数え上げるという問題は、数え上げでは基本で、競技プログラミングでも頻出(毎週のように見る)ので、知らなかった人はこの機会にぜひ覚えておくと良いと思います。

全体から 「偶数 + 奇数」 を除くという解法もあります。

問題F – Knapsack for All Segments

はいはい、出番ですね。

まず、$f(L,R)$ を理解しましょう。使える数が、[2,2,4] であれば、$$[x^S](1+x^2)(1+x^2)(1+x^4)$$が求めるものです。 いろんな区間に対して、多項式の積を加算する問題だと分かります。

サンプル 1 なら、$f_1 = 1 + x^2$, $f_2 = 1 + x^2$, $f_3 = 1 + x^4$ として、$$[x^S](f_1f_2f_3 + f_1f_2 + f_2f_3 + f_1 + f_2 + f_3)$$ を計算することになります。

因数分解とかも上手くできないです。項の規則がよくわからないので、適当な場合分けを軸にまとめます。右端の添字ごとに場合分けをして、

$$F_1 = f_1,\qquad F_2 = f_1f_2 + f_2, \qquad F_3 = f_1f_2f_3 + f_2f_3 + f_3$$

とおきましょう。$[x^S](F_1 + F_2 + F_3)$ を求めればよいです。よく見ると、$F_2 = f_2(F_1 + 1), F_3 = f_3(F_2 + 1)$ といった要領で計算できることが分かります。(計算用紙上では、添字を含む式は画数が多いので、 $abc+ab+bc+a+b+c$ という式を書いて考えました)。

結局、次の計算方法が結論です。

・$F_0 = 0$ とする。
・$F_i = (F_{i-1} + 1)(1+x^{A_i})$ により順次 $F_i$ を計算していく。計算したら、$x^S$ の係数を答に加算していく。

タイトルとURLをコピーしました