AtCoder Beginner Contest 162

AtCoder Beginner Contest 160 - AtCoder

結果:4AC(1WA)
3240 位。みなさん解くの早すぎません?

問題 A, B

特にいうことなし。

問題 C

いざ書いてみたら計算量 200 \times 200 + 200 \times 200なのに、ずっと頭の中で 200 \times 200 \times 200だと勘違いし続けて、時間を消費。

問題D

第一条件を満たすパターンから、第二条件を満たさないかつ第一条件を満たすパターンを引いた。後者のパターンは愚直に数え上げたが、なぜこれが計算量間に合っているのか検討がつかない。

問題E

問題Cと同じアルゴリズムを使うと、 O(k^{2} \times n)。そんなぁ。
解答見ました。計算量が10^{6}程度行ってそうに見えるんですが...?

問題F

思いついた解答の計算量 10^{6}程度行っちゃいそうだったので、時間もなかったのので撤退。
解答みました。どちゃくそ頭のよい dp で計算量 O(n)で答え出せるっぽいです。テーブル2つ作るのか...。

感想

うーん。
これはひどい

どうも、「計算量は 10^{6}まで行くと解けない場合がある」と思っていたのですが、W - 2.06.計算量曰く、

AtCoderの問題では実行時間制約が2秒くらいであることが多いです。 コンテストに参加する人は、1秒あたり 10^{8}回くらいの計算ができることを覚えておきましょう。

とのこと。どっかで覚え違いをしていたかもしらん。*1

反省。

*1:とはいえ、上のページは C++ 前提で書かれているようなので、Python では事情が違うことはあるかもしれませんが