競プロでやりがちなミス集

自分がよくやりがちなミスをまとめてみました。
このようにまとめておくことで、

  • よくやるミスをやらかさないよう注意深くなる
  • 解法は合っているはずなのに何故かWAする、といった場合に疑うべき場所が明確になる

という効果を期待しています。D言語特有の仕様とかも結構あるので、一般にはあまり役に立たなさそうです。

  • longにすべきところをintにしてオーバーフローさせてしまう
  • 10^^12と書いてオーバーフローさせてしまう(正しくは 10L^^12)
  • 1<<60と書いてオーバーフローさせてしまう(正しくは 1L<<60)
  • while (a.front < x) のように書いてしまいRE(正しくはwhile (!a.empty && a.front < x), 空配列でないことを逐一チェックする必要がある)
  • BinaryHeapをminが出てくると勘違いしてしまう(BinaryHeap!(Array!T, "a < b")()みたいに書くので)
  • 尺取り法が上手く実装できない
  • 境界条件があやふや
  • 中央値を求めるときにソートし忘れる
  • infを十分大きな値にしていない
  • BFSするときに頂点を見たときに距離を書かなきゃいけないのに、頂点を訪れたときに距離を書いてしまう
  • 空チェックをせずに、a.lowerBound(x).frontと書いてRE
  • bitwise orをxorと勘違いしてしまう


なにかまた思いついたら更新します。

No.752 mod数列

No.752 mod数列 - yukicoder

問題

数列
 a_i = P \% i (i = 1, 2, 3, \dots)
が与えられる。

Q個のクエリ (L_j, R_j)に対して
 \sum_{i = L_j}^{R_j} a_iを求めよ。

制約

  •  1 \leq P \leq 10^9
  •  1 \leq Q \leq 10^5
  •  1 \leq L_j \leq R_j \leq 10^9

解法

まずおなじみの累積和テクニックの考え方から

 \sum_{i = L_j}^{R_j} a_i = \sum_{i = 1}^{R_j} a_i - \sum_{i=1}^{L_j - 1} a_i

が成り立つので、任意のRに対して

 \sum_{i = 1}^{R} a_i

を求めるにはどうすればよいか?を考えることにします。

ここで R \leq 10^5程度までであれば単純に累積和でやればいいんですが、今回は R \leq 10^9ですので一筋縄ではいかなさそうです。まずいきなり和を考えるのではなくて、数列a_iがどのようになっているかを考えてみることにします。自明ではあるが重要なこととして、 i > P \Rightarrow a_i = Pとなっていることが分かります。よって i \leq Pだけで考えてみることにします。

こういうのは小さな具体例から考えてみるとよいので、 P = 24としてa_iがどのようになるかを見てみます。

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
a_i 0 0 0 0 4 0 3 0 6 4 2 0 11 10 9 8 7 6 5 4 3 2 1 0

すると一つ分かりやすい法則が見えます。i = 13, 14, 15, \dotsとなるにしたがって a_iは一つずつ減っていくことが分かります。このことを式で表すと P > i > P / 2 \Rightarrow a_i = P - iとなるということが分かります。さらに i = 9, 10, 11にも着目するとここでも規則性が見えて、a_iが2ずつ減っていくことが見て取れます。これも式で表すと P/2 > i > P / 3 \Rightarrow a_i = P - 2iとなることが分かります。

ここまで分かると一般化することが出来て、最初の自明な事実 i > P \Rightarrow a_i = Pも合わせると、

任意の k = 0, 1, 2, \dotsに対して P / k > i > P / (k + 1) \Rightarrow a_i = P - ki

と表せることが分かります。ここでk = 0のときP / 0 = \inftyと考えることにするとつじつまが合います。

そしてこれが分かると、kを固定したときの区間 (P/(k+1), P/K)に含まれるiに関するa_iの総和というのは簡単に分かります。Pは単に区間の長さ倍すればよくkiの部分はおなじみの \sum_{i = 1}^{N} i = N(N-1)/2という公式を使えばよいからです。

さて、この事実が分かると何がよいのでしょうか?
任意の k = 0, 1, 2, \dotsに対して P / k > i > P / (k + 1) \Rightarrow a_i = P - kiで、この区間に対してa_iの和はO(1)で求められます。なので k = 0, 1, 2, \dots, Pと回せばいいわけですが、 P \leq 10^9までなのでこれでは計算量の削減になっていません。
しかし、 k = 1, 2, \dots, 9999までやるとしてみましょう。すると i > P / 10^4の部分に対してはこれで求められて、残りの i \leq P / 10^4の部分は累積和で求めてやることにすると計算量が良い感じに収まることが分かります。
後は和の上限が指定したRを超えないように適宜区切ったりなんやかんやする必要がありますが、大筋のアイデアはこんな感じで計算量は今回は適当に10^4とかにしましたが一般には\sqrt{P}くらいにするのがいいのでO(Q + \sqrt{P})に出来ます。

感想

計算量にルートが出てくる問題ってあまり無い気がして面白かったので久々に書きました。

C - Modulo Summation / ABC103

解法

まず任意のiについて、 0 \leq (m \% a_i) \leq a_i - 1であることから、f(m)の上限は \sum a_i - Nであることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとればf(m)をこの上限に一致させることが出来るのではないかと予想が立てられます。

実際この予想は正しくて、 m = a_1 a_2 \dots a_N - 1とすると、任意のiに対して m \equiv -1 \equiv a_i - 1 (\mod a_i)となることが分かり、このときf(m) = \sum a_i - Nとなり上限に一致させることが出来ます。

感想

予想を立てるところまではすぐにいったのですが、それを証明するのに意外と時間がかかってしまいました。分かってしまえば簡単なのですが、a_iが互いに素でないときは成り立たなかったりするのではないかと考えたり、最近知った中国剰余定理かなとか考えてしまいました。modの世界では-1が最大になるというのは面白いですね。

実装

今回はJavaです。最近Javaの練習をしています。競プロにはやや使いづらいような印象ですが、uwiさんなどは普通に使いこなしているので凄いなと思いました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            ans += a - 1;
        }

        System.out.println(ans);
    }
}