プロコン部とは

プロコンってご存知ですか？

ここでいうプロコンは、ゲーム機用のProコントローラーでも、良い点（Pros）・悪い点（Cons）を列挙するのでもありません。「競技プログラミングコンテスト」の略です。

プログラミングコンテストとは、プログラミングの技術を競い合うイベントです。参加者にお題が出題されるので、そのお題を解くプログラムを制限時間内に提出します。

プロコン部では、プログラミングコンテストで出題された過去問を各自が解いて持ち寄り、その解法を披露しあうことで、楽しくプログラミング力を高めあっています。

この記事の最後に、部活で書いている実際のコードをご紹介します。JavaScriptで多倍長整数を扱う神コードも飛び出します。どうぞお楽しみください。

ゆるくて多様なプロコン部

プロコン部の最大の特徴は「ゆるさ」と「多様性」にあります。

プログラミングコンテストに挑戦して良い成績を目指すよりは、幅広いアルゴリズムに触れて楽しく実装することが目的のゆるい部活です。

部活は週1回1時間、業務時間内に開催しています。国内最大の競技プログラミングサイトAtCoderで公開されている過去問を1つ取り上げて、各人が業務の合間に自分のペースで挑戦してきます。本番のプログラミングコンテストでは「問題を早く解くスキル」も求められますが、部活ではそのプレッシャーがないのも、ゆるさにつながっています。

約10名のメンバーが使うプログラミング言語は本当に様々です。C++、Python、JavaScript、Java、Scala、Swift、Ruby、Haskell、Rust、Clojure、F#。

みんなが同じ問題を解いてくるのですが、人によってアプローチの仕方が違うことに加え、言語による得意・不得意が分かるのがとても面白いです。問題によって「Haskellだと短く書ける」「Pythonだとシンプル」「C++のライブラリ便利」といった違いがハッキリ分かります。

名著と名高い「達人プログラマー」では「毎年少なくともひとつの言語を学習する」というプラクティスを紹介していますが、この部活が新しいプログラミング言語を学ぶ最適な場になっています。私もC++で問題が解けるようになりました。

みんながいるから続けられる

メンバーにプロコン部の魅力を聞いたところ、 「一人だとなかなか続かないけど毎週集まることでモチベーションが維持できる」 「他の人と一緒にやることで、やる気が刺激される」 「解いてくる人がいるので辞めるに辞められない環境」 といった声が集まりました。

また、 「自分の解答も人に説明するので思考やコードが整理される」 という声もありました。

仲間がいるのは心強いものです。ゆるく取り組んでいるとはいえ幅広く様々なアルゴリズムを学ぶので「苦手なアルゴリズムに取り組むのはとてもしんどい」という正直な声もありました。それでも続けられるのはすごいことです。

その結果「ちゃんと力量アップした実感がある」というメンバーもいます。コンピューターのメモリー量や計算量が、利用するデータ構造やアルゴリズムによって大きく異なることを、業務だけで学ぶことはなかなかできません。「コンピュータや処理系の気持ちになれる」との声もありました。

BIGLOBEが大切にする価値観・信念（ビッグローブマインド）の一つに「継続的に成長する」があります。みんながいるから続けられる、続けられるから成長できる。私たちプロコン部の活動は「とてもBIGLOBEらしい活動だなぁ」と改めて思います。

みんなのコードをチラ見せ

振り返ってみると、週1回・週1問のゆるいペースとはいえ、とてもたくさんの問題を解いてきました。その中から3つほど、問題と解答コードをご紹介します。

コードゴルフ感ただようPython v.s. Rust

問題文

駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。

切符には 4 つの 0 以上 9 以下の整数A,B,C,D が整理番号としてこの順に書かれています。

A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。

（出典：AtCoder Beginner Contest 079 C - Train Ticket）

例えば (A, B, C, D) = (3, 2, 4, 2) が与えられた時、3+2+4-2=7 と出力するプログラムが求められています。Pythonで直積を求めるライブラリー itertools.product を活用して、コンパクトに書かれたコードがこちらです。

import sys, itertools

[a, b, c, d] = sys.stdin.readline().rstrip()

ops = ['+', '-']

for exp in ['%s%s%s%s%s%s%s' % (a, op1, b, op2, c, op3, d) for op1, op2, op3 in list(itertools.product(ops, ops, ops))]:
    if eval(exp) == 7:
        print '%s=7' % exp
        break

コードの短さを競い合う「コードゴルフ」の雰囲気が漂います。

そういえば、プロコン部で苦手なアルゴリズムに挑戦することが続いたため、その気晴らしにコードゴルフ大会が開催されたという噂があります（笑）。

style.biglobe.co.jp

ちなみに、Rust を書いてきたメンバーのコードはこれでした。コンパイルの通ったRustのコードって簡単に見えるから不思議です！

use proconio::input;
use itertools::*;
 
fn apply(op: char, x: i32, y: i32) -> i32 {
    match op {
        '+' => x + y,
        '-' => x - y,
        _ => unreachable!(),
    }
}
 
fn evaluate(a: &Vec<i32>, ops: &Vec<char>) -> i32 {
    ops.iter().zip(a.iter().skip(1))
        .fold(a[0], |s, (&op, &x)| apply(op, s, x))
}
 
fn make_expression(a: &Vec<char>, ops: &Vec<char>) -> String {
    a.iter().cloned().interleave(ops.iter().cloned()).chain("=7".chars()).collect()
}
 
fn operators(n: usize) -> impl Iterator<Item = Vec<char>> {
    (0..n)
        .map(|_| "+-".chars())
        .multi_cartesian_product()
}
 
fn solve(a: String) -> String {
    let s = a.chars().collect::<Vec<_>>();
    let a = s.iter().map(|c| c.to_digit(10).unwrap() as i32).collect::<Vec<_>>();
    operators(3)
        .filter(|ops| evaluate(&a, &ops) == 7)
        .map(|ops| make_expression(&s, &ops))
        .nth(0)
        .unwrap()
}
 
fn main() {
    input! {
        a: String,
    }
    let r = solve(a);
    println!("{}", r);
}

ワンライナー F#

問題文

ファーストフードチェーン「ピザアット」のメニューは「A ピザ」「B ピザ」「AB ピザ」の 3 種類です。A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ 1 枚あたりの値段はそれぞれ A 円、B 円、C 円です。

中橋くんは、今夜のパーティーのために A ピザ X 枚と B ピザ Y 枚を用意する必要があります。これらのピザを入手する方法は、A ピザや B ピザを直接買うか、AB ピザ 2 枚を買って A ピザ 1 枚と B ピザ 1 枚に組み替える以外にはありません。このためには最小で何円が必要でしょうか？なお、ピザの組み替えにより、必要な量を超えたピザが発生しても構いません。

（出典：AtCoder Beginner Contest 095 C - Half and Half）

例えば (A, B, C, x, y) = (1500, 2000, 1600, 3, 2) が与えられた時、つまりAピザ 1500円、Bピザ 2000円、ABピザ 1600円で、Aピザが3枚、Bピザが2枚必要な場合、AB ピザを 4 枚買って A ピザと B ピザ 2 枚ずつに組み替え、A ピザを 1 枚買い足すのが最適です。7900円と出力することが求められます。

毎回必ずF#を使って、1行のプログラム（ワンライナー）で提出するメンバーのコードを紹介します。関数型とオブジェクト指向のマルチパラダイムの言語、とのことですが、私は不勉強で理解できないため、いつも雰囲気だけ楽しんでます😇

ループを使った解法では、ABピザ2枚をi枚買って、AピザとBピザに分けつつ、足りないAピザ・Bピザを補充する戦略を取ります。ABピザを買う枚数を変化させながら、最小の金額を総当たりで調べます。

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1], x.[2], x.[3], x.[4])
|> fun (a, b, c, x, y) ->
  [1..(max x y)]
  |> List.fold (
    fun ret i ->
      a * (max (x - i) 0) +
      b * (max (y - i) 0) +
      c * i * 2
      |> min ret
  ) (a * x + b * y)
|> printfn "%d"

場合分けによる解法では、AピザとBピザを別々に買うのと、ABピザを買って分けるのとで、どちらが安くなるかを調べます。

stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1], x.[2], x.[3], x.[4])
|> fun (a, b, c, x, y) ->
  [
    a * x + b * y;
    (
      if x > y
      then a * (x - y) + c * 2 * y
      else b * (y - x) + c * 2 * x
    );
    c * 2 * (max x y)
  ]
  |> Seq.min
|> printfn "%d"

JavaScriptで多倍長整数を扱う、だと！？

問題文

非負の整数 a, b (a ≤ b) と、正の整数 x が与えられます。 a 以上 b 以下の整数のうち、x で割り切れるものの個数を求めてください。

制約 0 ≤ a ≤ b ≤ 10¹⁸ 1 ≤ x ≤ 10¹⁸

（出典：AtCoder Beginner Contest 048 B - Between a and b ...）

例えば (a, b, x) = (4, 8, 2) が与えられた時、つまり 4 以上 8 以下の整数のうち 2 で割り切れるのは、4, 6, 8 の3つなので、3 と出力するプログラムが求められています。

「0 以上 b 以下の整数のうち x で割り切れるもの」から「0 以上 (a - 1) 以下の整数のうち x で割り切れるもの」を引いた値を計算すればOKです（a が 0 の時を考慮する必要があります）。

ただ、この問題の「制約」が10の18乗で大変大きくなっているのがポイントです。C++であれば、64ビット以上の整数を表す long long を使って次のように簡単に解けます。

#include <iostream>
using namespace std;
typedef long long ll;

ll f(ll n, ll x) {
  if (n == -1) return 0;
  return n / x + 1;
}

int main() {
  ll a, b, x;
  cin >> a >> b >> x;
  cout << f(b, x) - f(a - 1, x) << endl;
  return 0;
}

私は当時 JavaScript で取り組んでいたのですが、JavaScriptで多倍長整数を扱うことができず撃沈していました。そんな時、メンバーの一人が次のコードを提出してきたのです。神か！

長いので折りたたんで表示します。

▶クリックで展開

const D = 24;
const L = 3;

function new64(n) {
    return [n % (1<<D), (n / (1<<D)) | 0, 0];
}

function mul64s(a, b) {
    var r = [];
    var x = 0;
    for (var i = 0; i < L; i++) {
        x = a[i] * b + x;
        r[i] = x % (1<<D);
        x = Math.floor(x / (1<<D));
    }
    return r;
}

function add64s(a, b) {
    var r = [];
    var x = b;
    for (var i = 0; i < L; i++) {
        x = a[i] + x;
        r[i] = x % (1<<D);
        x = Math.floor(x / (1<<D));
    }
    return r;
}

function cmp64(a, b) {
    for (var i = L-1; i >= 0; i--) {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
    }
    return 0;
}

function add64(a, b) {
    var r = [];
    var x = 0;
    for (var i = 0; i < L; i++) {
        x = a[i] + b[i] + x;
        r[i] = x % (1<<D);
        x = Math.floor(x / (1<<D));
    }
    return r;
}

function sub64(a, b) {
    var r = [];
    var x = 0;
    for (var i = 0; i < L; i++) {
        x = a[i] - b[i] - x;
        var borrow = 0;
        while (x < 0) {
            x += (1<<D);
            borrow++;
        }
        r[i] = x % (1<<D);
        x = borrow;
    }
    return r;
}

function div64s(a, b) {
    var x = 0;
    for (var i = L-1; i >= 0; i--) {
        x = a[i] + x * (1<<D);
        a[i] = (x / b) | 0;
        x = x % b;
    }
    return x;
}

function copy64(a, b) {
    for (var i = 0; i < L; i++) {
        a[i] = b[i];
    }
}

function shiftL64(a) {
    const msb = [0, 0, (1<<(D-1))];
    var d = a;
    var r = 0;
    if (cmp64(a, msb) >= 0) {
        r = 1;
        d = sub64(a, msb);
    }
    var c = add64(d, d);
    copy64(a, c);
    return r;
}

function div64(a, b) {
    var d = new64(0);
    var x = a.slice();
    var r = new64(0);
    for (var i = 0; i < L*D; i++) {
        var bit = shiftL64(x);
        shiftL64(d);
        d = add64s(d, bit);
        var y = 0;
        if (cmp64(d, b) >= 0) {
            d = sub64(d, b);
            y = 1;
        }
        shiftL64(r);
        r = add64s(r, y);
    }
    return r;
}

function parse64(s) {
    const l = s.length;
    var a = new64(0);
    for (var i = 0; i < l; i++) {
        a = mul64s(a, 10);
        a = add64s(a, parseInt(s.substr(i, 1), 10));
    }
    return a;
}

function print64(a) {
    var s = "";
    var x = a.slice();
    while (cmp64(x, new64(0)) !== 0) {
        s += div64s(x, 10);
    }
    if (s === "") {
        s = "0";
    }
    console.log(s.split('').reverse().join(''));
}

function divisors(a, x) {
    return add64s(div64(a, x), 1);
}

function solve(a, b, x) {
    return sub64(divisors(b, x), (cmp64(a, new64(1)) >= 0 ? divisors(sub64(a, new64(1)), x) : new64(0)));
}

function main(input) {
    const args = input.trim().split(' ');
    const a = parse64(args[0]);
    const b = parse64(args[1]);
    const x = parse64(args[2]);
    const c = solve(a, b, x);
    print64(c);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));