2018-07-22

C - Modulo Summation / ABC103

問題

$\max\{f(m) = \sum (m \% a_i )| m \geq 0, m \in \mathbb{Z}\}$ を求めよ。

https://beta.atcoder.jp/contests/abc103/tasks/abc103_c

解法

まず任意の $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);
    }
}

2018-07-11

Pythonで競プロを始めるという選択肢

その他

久しぶりにブログを更新します。今回は解説記事ではなく自分語り系の記事です。

twitterを見ていたら「pythonで競プロをやるってどうなの？」みたいな話が出ていたので、私も元python競プロerとして考えを述べてみたいと思います。（もともとこのブログのタイトルは「Pythonで競プロ」だった）

結論から言うと、AtCoderに限ればpythonで競プロを始めるのは普通にアリなんじゃないかなと思います。
なぜAtCoderに限定しているかというと

いざとなればpypyに投げれば何とかなる
制約が厳しい問題がそんなに多くない（大きくても $10^7$ とか）
分かってしまえば実装はシンプルなので定数倍もキツくない

という感じであまり障壁にならないからですね。前にも書きましたがCodeforcesは問題の傾向が割と多種多様で想定解が $10^8$ という問題もdiv.2-Bに出てきたりするのでpythonではまともに戦えないなと過去に思いました。（最近はめっきりこどふぉに出てないのでもしかしたら現状は変わっているかもしれないです、そうならばすみません）

pythonで競プロを始めることに対する想定される反対意見として

「pythonで競プロを始めても、そのうちpythonでは通せない問題が出てきて絶望して他の言語に乗り換えるのだからその乗換えの無駄を考えたら最初からC++とかで競プロに慣れておいたほうがいい」

というのがあって、これは一理あるかもしれません。実際私がそうで最終的にはD言語に乗換えました。こどふぉもキツいんですが、本格的にpythonでは無理だなーって思い始めたのはJOIの過去問を解いていたときですね。あれも $10^8$ とか普通に想定解になってたり、pythonだとメモリも食うのでそもそもMLEになっちゃって（JOIはメモリ制限もキツめです）どうしようもないなと思いました。

しかしこのデメリットは競プロをある程度やって初めて感じるデメリットです。最初から「競プロを一生の趣味にするぞ！」とか「レッドコーダーになるまでやり続けるぞ！」とか意志を固めて始める人はC++からのほうがよさそうですが、そうでないなら別にpythonでもよさそうです。どうせすぐ辞めちゃうかもしれないしね。

自分の場合は少し時間が出来てプログラミングを勉強しようかなと思って、まずpythonを覚えようと思って最初にpaizaで勉強してたんですね。paizaも一応コーディングテストみたいな、競プロっぽい問題を解けるのですがそのうち物足りなくなってyukicoderに出会いました。なんでAtCoderの前にyukicoderに出会ったのか、その経緯は覚えてませんが……ともかくその延長でpythonで競プロを始めたんですね。その後詳しく調べてみると「pythonで競プロは無理だぞ」というのが競プロ界の常識だったのですが、ひねくれているのでpythonでやっていってやるぞとか思っていました。最終的に折れちゃったんですけど。

だからといって「最初からpythonで競プロやらなければよかった……」と後悔しているかというと別にそうでもなくてですね。pythonで簡単な競プロ問題が解けるぐらいになっておくと良いこともあります。あれとかこれとか。

それでもし、あなたがpythonで競プロを始めて数か月か数年かしたぐらいに「pythonでは無理だー！」と思ったとします。そのときに乗換え先としてオススメしたいのはD言語ですね。

そもそもなんで私はD言語というマイナー言語を使っているんでしょうか。どこかで「pythonとD言語は似ているからpython競プロerの乗換先としてちょうどいい」みたいな言説を見たからだったと記憶してます。

実際似ているかと言われるとよく分かりませんが、しかし確かにD言語は使いやすいです。「pythonだったらこういうことできるのにな」と思ったことはD言語でもだいたい出来るしそれどころかあんなことやこんなことも出来る！っていうのが結構嬉しいし、使っていて楽しい言語だなと思います。それでいて実行速度も速い(10^8が余裕で通るのは本当に感動します)ので文句がありません（ホントは少しある）。デバッグもしやすいし、パソコン音痴でもインストール簡単なのでもう少し使われてもいいんじゃないかと思います。yosupoさんも使ってるし。

主題からズレたのでそろそろまとめると

とりあえずpythonでも何でもいいから好きな言語で競プロを始めよう
pythonに限界を感じたらD言語に乗換えよう

ということでした。ありがとうございました。

2018-03-04

A - Uncommon/みんプロ2018本戦

Atcoder 包除原理数学

問題概要

集合 $A = \{a_1, a_2, ..., a_N\}$ が与えられる。
各整数k = 1, 2, ..., Mについて、kと互いに素であるAの要素の個数を求めよ。

制約

$1 \leq N, M, a_i \leq 10^5$

解法

愚直にやると少なくともO(N*M)かかってしまうのでまとめて数え上げるなどの高速化が必要になります。

kを固定したときに、kとa_iが互いに素であるというのは、gcd(k, a_i) = 1であるというのが定義ですがこの条件はまとめて数え上げようとするときには少し使いにくいので別の同値な条件に言い換えてみます。
$k = p_1^{e_1} p_2^{e_2} ... p_t^{e_t}$
という感じにkを素因数分解したとします。(p_jは素数)
このとき、kとa_iが互いに素であることの必要十分条件は、a_iがどのp_jでも割りきれないこととなります。逆に、kとa_iが互いに素でないことは、a_iがあるp_jで割り切れることと同値です。

この事実を使ってkと互いに素でないa_iの個数を求めることにします。その個数をn(k)とします。
$A_{x}$ をxで割り切れるa_i全体の集合と定義すると、求めたいのは
$n(k) = \#(\cup_{j} A_{p_j})$
となります。和集合で表されているものは一般には数え上げには使い辛いので、包除原理を使って書き直してやると

$n(k) = \sum_{i} \#(A_{p_i}) - \sum_{i < j} \#(A_{p_i p_j}) + \sum_{i < j < k} \#(A_{p_i p_j p_k}) - ...$

と求めることが出来ます。

後は、 $\#(A_{p_i})$ とか $\#(A_{p_i p_j})$ とかをどうやって求めるのかとか、それをn(k)に足したり引いたりするのをどうするのかというところです。
まず初めに、エラトステネスの篩風の前処理をしておくと各整数kに含まれる異なる素因数の積やその個数などをO(MlogM)で求めて置くことができます。
それをやっておいてから、整数dを2,3,...と動かしていき、d = (dに含まれる異なる素因数の積)となっていれば上で書いたような $\#(A_{p_i p_j})$ みたいな感じの求めるべきものなのでそこをちゃんと数えます。つまりAに含まれるdの倍数を数えます。ただし、愚直にやるとここでO(N)かかってしまうので最初にbool配列を取っておいてそこにAの要素があるないのフラグを立てておくとdの倍数ごとにスキップしながら見るということが出来るので、全体での計算量がM + M/2 + M/3 + ... = O(MlogM)程度になってくれます。そしてこれを求めたらdに含まれる素因数の個数偶奇に応じて+か-か決めて、またdの倍数ごとにスキップしながら足し引きすべきn(k)に対してそれを足したり引いたりします。

こうやってやるとO(MlogM)程度で解くことが出来てちゃんと間に合うという感じになりました。

ソースコード

適宜省略

void main() {
    int n, m;
    scan(n, m);
    auto a = iota(n).map!(i => readln.chomp.to!int).array;

    auto b = new bool[](a.reduce!max + 1);

    foreach (ai ; a) {
        b[ai] = 1;
    }

    auto pd = new int[](m + 1);
    auto pcn = new int[](m + 1);
    pd[] = 1;

    foreach (p ; 2 .. m + 1) {
        if (pd[p] == 1) {
            for (int d = p; d < m + 1; d += p) {
                pd[d] *= p;
                pcn[d]++;
            }
        }
    }

    auto cnt = new int[](m + 1);

    foreach (i ; 2 .. m + 1) {
        if (pd[i] < i) continue;
        int res = 0;

        for (int d = i; d < b.length.to!int; d += i) {
            if (b[d]) res++;
        }

        int diff = res * (-1)^^((pcn[i] & 1) ^ 1);

        for (int d = pd[i]; d < m + 1; d += pd[i]) {
            cnt[d] += diff;
        }
    }

    writeln(n);
    foreach (i ; 2 .. m + 1) {
        writeln(n - cnt[i]);
    }
}