TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

05 /
15
2022
 

【ABC251-Bの反省】 300の3乗は大丈夫だった(2回目)

2022年5月14日に開催されたパナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251)(以下、ABC251) に参加しました。

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251) – AtCoder
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

結果は以下の通りでした。

良かった点

良くなかった点

今回はB問題について以下の3点について復習します。

  1. AtCoderのジャッジでは1秒あたり何回計算できるのか?
  2. 定数倍って何?
  3. 再帰は早いの?

B問題について

問題等は以下のリンクをご確認ください。

B – At Most 3 (Judge ver.)
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

問題文を読んでまず思ったのは、for文を \(3\) 重にして全パターン試すこと。

しかし、\(1 \leq N \leq 300\)だから、\(3\) 重 \(300^{3} = 27,000,000\) 回になってTLEになるからダメだな、と思い別の方法を考えました。

この判断ミスは2回目です。

結果、\(30\) 分以上使ってACしました。

1.AtCoderのジャッジでは1秒あたり(10^8)回程度の計算が可能(再確認)

AtCoderの「C++入門 AtCoder Programming Guide for beginners (APG4b)」の「EX21 – 計算量の見積もり」に計算量についての目安が書いてありました。

EX21 – 計算量の見積もり
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

AtCoderのジャッジでは1秒あたり\(10^{8} = 100,000,000\)回程度の計算が可能です。

\(300^{3} = 27,000,000\) は十分間に合います。

忘れるな。そして自信を持て、自分。

また、計算量の話になったときによく「定数倍が云々」という話や文章を見ます。文字面でなんとなく意味がわからなくもないのですが、説明はできないので少し調べた結果を書いておきます。

2.定数倍のイメージ

「定数倍は計算量のオーダーに影響しないところ」って考えたらいけそう。もっと横着に言えば、for文の中というイメージ。下のコードの「ここから」「ここまで」の処理というイメージ。

for(int k = j + 1; k < N; ++k) {
    // ここから
    v = A[i] + A[j] + A[k];
    if (v  <= W) {
        ans.insert(v);
    }
    // ここまで
}

なんか、相変わらずわかったようなわからないような感じだが、若干納得できてきました。

このイメージでうまくいかなかったらまたその時考えよう。

3.再帰の方が早い?

今回、3重for文と再帰の2パターンでACできたのですが、問題文の入力例4で何回ループしているのかを数えてみると

3重for文の場合(コードはこちら) … 35回
再帰の場合(コードはこちら) … 127回

うん。再帰の方が遅い。

どうして再帰だと間に合うって思ったんだろうな。
パニクったときの思考は怖い。

こういう基本的な知識が弱いよなぁ。