2020-10-24

Online Judge Template Generator で std::endl を使わないようにする

ツール

このツール使ってる人なら既にやってるひと多そうだけど一応

概要

Online Judge Template Generator で普通にテンプレートを出力させると std::endl を利用したものが出力されるが、こどふぉ等で出力 TLE になる可能性があるのでできれば使用を避けたい。

printf を使用するようなオプションもあるが _get_base_type_format_specifier の実装を見ると、string 型に対応していないことが分かる。真面目にテンプレを書けば対処はできるがちょっとめんどくさい。

以上を踏まえてちょっと妥協した感じの対処法を書きます。

TL; DR

std::endl ではなく const char newl = '\n'; を使う
出力方法を自分で定義したテンプレートを使うようにする

ちなみに newl という命名は beet さんのテンプレをリスペクトしています。

テンプレ

テンプレの冒頭にこれを書くと std::endl ではなく newl が出るようになる。(私は using namespace std; する人なので、それ用の設定も混じっていますが、適宜変えてください)

<%!
    import onlinejudge_template.generator.cplusplus as cplusplus
    import onlinejudge_template.generator.about as about
    from typing import List
    def newl_output(exprs: List[str], *, newline: bool) -> List[str]:
        items = ["cout"]
        for i, (expr, _) in enumerate(exprs):
            if i: items.append("' '")
            items.append(expr)
        if newline:
            items.append("newl")
        return [" << ".join(items) + ";"]
%>\
<%
    data['config']['printer'] = newl_output
    data['config']['using_namespace_std'] = True
%>\

get_base_type_format_specifier に準ずるものを自分で書けば、scanf, printf に対応させることも可能だと思います。やりたい人はやるとよいです。

2020-09-20

大学合宿の作問を卒業した & HUPC2020 Day1 の講評とか

勉強会参加記 AOJ

9/14〜9/16 に HUPC2020 が開催され、9/14 は北大セットでした。元々は RUPC2020 の北大セットとして出す予定だったので自分もまだ作問に携わっていて、今回で大学合宿の作問は卒業ということになりました。思い返してみれば、RUPC2017 からセット提供するごとに毎回作問しているのでなんだかんだ 3 年半くらい関わったことになります (しかも HUPC 主催で作問機会を自ら増やしているという・・・)。そう考えるとなんとなく結構やったのかもという気持ちになりますね。

今回もセットを作るにあたって相当いろいろやったので、振り返ってみます (なんかこういうのやりたくなっちゃうんですよね、半分ポエムだけど許してください)

2020-07-08

2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) B: Coprime Integers

ICPC 数学

この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます

問題概要

原文 (PDF): https://codeforces.com/gym/101982/attachments/download/7897/20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf

整数 $A, B, C, D$ が与えられる。 $A \leq x \leq B, C \leq y \leq D$ を満たす整数の組 $(x, y)$ であって $x, y$ が互いに素であるものの個数を求めよ。

$1 \leq A \leq B \leq 10^{7}$
$1 \leq C \leq D \leq 10^{7}$
TL 1 sec

解法

※ 計算量を書くために、 $N = \max(B, D)$ としています。

お察しの通り $O(N \log N)$ を書いても落ちると思います。それよりも時間計算量が良いものを書く必要があります。

$f(p, q)$ を、「 $1 \leq x \leq p, 1 \leq y \leq q$ を満たす組 $(x, y)$ であって $x, y$ が互いに素であるものの個数」とします。元の問題で要求されていることとは微妙に異なりますが、この関数を組み合わせることで元の問題を表現することができます。具体的には $f(B, D) - f(A-1, D) - f(B, C-1) + f(A-1, C-1)$ を考えれば良いです (二次元累積和を実装したことがあるならば、それがイメージの助けになるかと思います)

では、この関数 $f$ はどのようにすれば高速に計算できるでしょうか？整数の組 $(x, y)$ の $1$ 以外で最小の公約数が $d$ であるとして、包除原理のように考えると以下のようになります。

$d$ に含まれる素数が奇数個ならば、引かなければならないので引く
$d$ に含まれる素数が偶数個ならば、引きすぎたぶんを足す
ただし、 $d$ が平方数で割り切れる (つまりある素数 $p$ があって $d$ が $p^{2}$ で割り切れる) 場合は他の結果に包含されるので考慮しない

ここで「引く」「足す」「考慮しない」など、それぞれの場合の数に対して $-1, +1, 0$ といった係数がかかることになりますが、この係数はまさにメビウス関数 (Mobius function) そのものです。この関数について詳しく知りたい方はメビウスの反転公式の証明と応用 | 高校数学の美しい物語を見てください。メビウス関数はエラトステネスのふるいを動かす際に一緒に計算できるので、元の問題は $O(N \log \log N)$ で解けます。

ソースコード

const int MAXN = 10000010;
int mu[MAXN + 5];
bool is_prime[MAXN + 5];

int main() {
    fill(is_prime + 2, is_prime + MAXN + 1, true);
    fill(mu, mu + MAXN + 1, 1);
    for(int i=2; i<=MAXN; i++) {
        if(!is_prime[i]) continue;
        mu[i] = -1;
        for(int k=i<<1; k<=MAXN; k+=i) {
            is_prime[k] = false;
            if((k/i) % i == 0) mu[k] = 0;
            else mu[k] = -mu[k/i];
        }
    }

    int A, B, C, D; scanf("%d%d%d%d", &A, &B, &C, &D);

    auto calc = [&](int x, int y) {
        ll res = 0;
        for(int i=1; i<=min(x, y); i++) {
            res += 1LL * (x/i) * (y/i) * mu[i];
        }
        return res;
    };

    ll ans = calc(B, D) - calc(A-1, D) - calc(B, C-1) + calc(A-1, C-1);
    printf("%lld\n", ans);
    return 0;
}

hogecoder

tsutaj 競技プログラミングの記録