Code Jam to I/O for Women 2019

なにそれ？

codingcompetitions.withgoogle.com

Google が毎年開催している、女性向けの online coding contest です。
スコアがTOP150位内にランクインすると Google I/O へのチケットと旅費が賞品として授与されます。

2019 は？

今年は２月に開催されたのですが、Google I/O の話題で盛り上がりつつある昨今、
ふと思い出して今更ながらまとめておこうと思います。
去年はスケジュールの都合で参加できず、今年初めて参加したのですが、 結果としては散々で、世界の壁の厚さを思い知ることに・・・
ランキングを見るとロシアや中国の方が強かったですね、日本人の方も１人ぐらい150以内に入っていた気がするけど先進国の中ではワーストなのでは...ってぐらい少なかったです。

参加方法は？

毎年、開催の１ヶ月程度前から公式サイトで事前登録が始まります。
Google アカウントがあれば誰でも登録できます。
（特に女性であることの証明みたいのはなかった）

事前準備は？

過去問を解く

とりあえず、チュートリアルだけでも絶対やっておいたほうがよいです。
Code Jam のサイトでは、自分で書いたコードがテストケースをクリアするかどうかオンライン上で即時に判定されます。
毎回問題の内容自体は異なりますが、テストケースの入力形式とテスト結果の出力形式は一緒です。
このテストケースを読み込み、テスト結果を出力する部分は予め準備しておけるわけです。

テストケースとテスト結果の input / output 形式

テストケースは標準入力（STDIN）としてテストコードに渡ってきます。

• １行目がテストケースの数（1 ≤ T ≤ 100.）
• ２行目以降が検証する要素の数と検証する要素の値

（例）

3                # テストケースの数
5                # Case1 の要素数
0 2 1 1 2        # Case1 の値
1                # Case2 の要素数
0                # Case2 の値
6                # Case3 の要素数
2 2 2 2 2 2      # Case3 の値

テスト結果は標準出力（STDOUT）としてアウトプットする必要があります。
そしてこれも出力形式が決まっています。

（例）

Case #1: 2              # Case1 のテスト結果
Case #2: 0              # Case2 のテスト結果
Case #3: 10              # Case3 のテスト結果

実際に解いてみる

2018年のハンバーガーの具材を最適化しようという課題を試しに解いてみましょう。
Burger Optimization

プログラミング言語はプルダウンから自分の好きな言語を選べます。

select programming language at Code Jam

※ 参加した時は、プルダウンに Perl がなかったのですが、今見ると対応言語が増えているようで...

Go で書いてみる

つっこみどころ満載のコードですが晒します。
ローカルで実装しながら検証するときはテストケースを外部ファイルとして作っておくと便利です。
あとは go run コマンドで実行するだけ。
（限られた時間で競うときこそコンパイルが速い go にすべきじゃない？）

$ go run main.go < input_file.txt

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "sort"
    "strconv"
)

var s = bufio.NewScanner(os.Stdin)

func main() {
    s.Split(bufio.ScanWords)
    t := nextInt() // test case 数

    for i := 1; i <= t; i++ {
        k := nextInt()       // burger の中の要素数
        ds := make([]int, k) // バンズまでの距離のslice
        bs := make([]int, k) // 最適なバンズまでの距離のslice
        for j := 0; j < k; j++ {
            ds[j] = distance(k, j) // バンズまでの距離
            bs[j] = nextInt()      // 最適なバンズまでの距離
        }

        // 最小誤差を出すために並び替える
        sort.Sort(sort.IntSlice(ds))
        sort.Sort(sort.IntSlice(bs))

        es := 0 // 誤差合計
        for j := 0; j < k; j++ {
            d := square(ds[j] - bs[j]) // 誤差
            log.Print(d)
            es += d
        }
        fmt.Printf("Case #%d: %d\n", i, es)
    }

    if err := s.Err(); err != nil {
        log.Fatal(err)
    }
}

func nextInt() int {
    s.Scan()
    i, e := strconv.Atoi(s.Text())
    if e != nil {
        panic(e)
    }
    return i
}

// 次乗
func square(x int) int {
    return x * x
}

// バンズからの距離
func distance(k, j int) int {
    d := k - 1
    if (d - j) < j {
        return d - j
    }
    return j
}

標準入力の取得は os パッケージ（当たり前だけど）、 os.Stdin から io.Reader を一行ずつ読み込むのには、bufio.NewScanner を使いました。
※ bufio.NewScanner はスキャンできる一行のサイズに上限があるので、テストケースによっては使えないことがあるかもしれませんが、
Code Jam の課題ではここを超えてくるテストケースには出会いませんでした。

あとよく使うであろう、nextInt() や square() も予め用意しておいたほうがよさげです。

Perl で書いてみる

この記事を書こうとして Perl がサポートされていることに気づき Perl版も作ってみました。
（書いて気づいたけど、Perl の方がコード量半分で済むし、そもそもコンパイル要らないよ...って）

use strict;
use warnings;
use utf8;

my $t = <STDIN>; # test case 数

for (my $i = 1; $i <= $t; $i++) {
    my $k = <STDIN>; # burger の中の要素数
    my @bs = split(/ /, <STDIN>); # 最適なバンズまでの距離の配列
    my @ds;                        # バンズまでの距離の配列
    for (my $j = 0; $j < $k; $j++) {
        push @ds, distance($k, $j); # バンズまでの距離
    }

    # 最小誤差を出すために並び替える
    @ds = sort { $a <=> $b } @ds;
    @bs = sort { $a <=> $b } @bs;

    my $es = 0; # 誤差合計
    for (my $j = 0; $j < $k; $j++) {
        my $d = ($ds[$j] - $bs[$j]) ** 2; # 誤差
        $es += $d;
    }
    printf("Case #%d: %d\n", $i, $es);
}

# バンズからの距離
sub distance {
    my ($k, $j) = @_;
    my $d = $k - 1;
    return $d - $j if ($d - $j) < $j;
    return $j;
}

当日のハプニング

2019年の競技開始は何やらトラブルがあったようで何度も遅れました・・・ 日本時間 AM0:00 開始予定だったのが直前に 30min 遅れになり、さらにまた 30min 延長、さらに... といった感じで眠気との戦いが大変でした。

感想

来年こそはチケットと旅費を手に入れるぞ！（※会社に出してもらうのではなく）