Hatena::Grouptopcoder

minus9dの記録

2016-04-11

Google Code Jam 2016 Qualを多言語で解く

| 22:24 | Google Code Jam 2016 Qualを多言語で解く - minus9dの記録 を含むブックマーク はてなブックマーク - Google Code Jam 2016 Qualを多言語で解く - minus9dの記録

今年も去年に引き続き、GCJの予選問題を多言語で解いてみました。昨年はD-Largeを落として7言語でしたが、今年は全問正解でリベンジ達成です。新しい言語を使う良いきっかけ、というのは方便で、ただの自己顕示欲の発露です。

去年とかぶらない言語、しかもなるべく自分が使ったことがなく、使用者が少ないレアな言語で--と思い、なでしこElixir, D言語, PHPと実装を頑張ったのですが、あまりに疲弊したため徐々に制限を緩和し、残りはJulia, Octave, Ruby, Javaで埋めました。今年も去年と同等以上に疲れました。

ランキングは (Multiple submission languages (2016) — Code Jam Statistics) です。なでしこが認識されず7言語になってしまっています。

戦略

まず6時間かけてPythonでプロト実装を行い、Largeまで解けそうなことを確認しました。各問題の方針は以下の通りです。

A. Counting Sheep

0 <= N <= 10^6の範囲のNすべてでシミューレションを行うだけです。INSOMNIAとなるのはN=0のときだけであることが確認できます。

数字から文字列に変換できる言語であればほぼ何でもOKです。

B. Revenge of the Pancakes

入力文字列の連続する+や-を圧縮して一つにした後、末尾の+を除くと、以下のいずれかになります。

(i)空文字列

(ii)+-, +-+-, +-+-+-, ...

(iii)-, -+-, -+-+-, ...

それぞれ必要な操作回数は

(i)0

(ii)2, 4, 6, ...

(iii)1, 3, 5, ...

となります。

文字列操作ができる言語であればOKです。

C. Coin Jam

頭と末尾が1である文字列1xxxx1を次々と作り、2進数から10進数のいずれで解釈しても合成数であることを愚直に確かめるだけです。合成数であることの確認は、「2, 3, 5, 7, 11のいずれかで割り切れる数」とすれば十分です。(最初は「素数でない数」を合成数と判定しようとしましたが、これだと素数の数え上げが大変です)

Pythonでは、int("10001001", 3)などとすると文字列"10001001"を3進数で解釈した値を簡単に得られます。これと同様の関数を持つ言語だと実装が簡単です。また、Largeだと多倍長整数が欲しいです。

D. Fractiles

小さなKとCで実験をして規則性を導きました。例えばK=3のとき、"GLL", LGL", LLG"の3つのパターンが、Cが増えるに従いどう増殖するかを観察します。すると、複雑度がCのとき、GがC個出現するポジションがある法則で出現しそうなことが分かります。

Dも多倍長整数が使える言語を選定しました。


問題詳細


A. Counting Sheep

Elixirのコードは以下です。関数型言語の経験が皆無のため非常に怪しいです。whileで無限ループするのに相当する書き方がわからず、関数再帰させています。

defmodule Main do
  def main do
    tt = IO.gets("")
    {tt, _} = Integer.parse(tt)
    for t <- 1..tt do
      n = IO.gets("")
      {n, _} = Integer.parse(n)
      IO.puts "Case ##{t}: #{solve(n)}"
    end
  end

  def solve(n) do
    if n == 0 do
      :INSOMNIA
    else
      seen = MapSet.new([])
      ans = func(n, 1, seen)
    end
  end

  def func(n, cnt, seen) do
    if MapSet.size(seen) == 10 do
      (cnt-1)*n
    else
      tmp = Integer.digits(n*cnt)
      tmp = MapSet.new(tmp)
      seen = MapSet.union(seen,tmp)
      func(n, cnt+1, seen)
    end
  end
end

Main.main

Javaは以下です。

import java.util.Scanner;
import java.util.HashSet;
import java.util.ArrayList;

public class A {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int T = sc.nextInt();
        for(int t = 1; t <= T; ++t) {
            System.out.printf("Case #" + t + ": ");
            Long n = sc.nextLong();
            solve(n);
        }
    }

    private static void solve(Long n) {
        if (n == 0) {
            System.out.println("INSOMNIA");
            return;
        }

        HashSet<Character> seen = new HashSet<Character>();
        Long cnt = 1L;
        while(true) {
            Long val = n * cnt;
            String val_s = String.valueOf(val);
            for(char ch : val_s.toCharArray()) {
                seen.add(ch);
            }

            if (seen.size() == 10) {
                System.out.println(val_s);
                break;
            }
            cnt++;
        }
    }
}

B. Revenge of the Pancakes

今回圧倒的に苦労した、なでしこのコードです。3時間ほどかかってます。Webを検索しても例がほとんどヒットしないのが苦労の最大の理由です。64bit整数がなかったり、文字列をイテレートする方法が(おそらく)なかったりするなど、競技プログラミングとの相性は高くないと思われます。ここでは文字列をイテレートする代わりに、文字列から部分文字列を抜き出す命令「文字抜き出す」を使っています。

#   convert LF to CRLF of input_file
#   cnako.exe b.nako input_fie


!変数宣言は必要

ファイル名とは文字列。
ファイル名は、コマンドライン[2]。

入力ファイルとは文字列。
入力ファイルはファイル名を「読ん」でファイルストリーム開く

問題数とは整数。
問題数は入力ファイルのファイルストリーム一行読む

問題とは整数。
問題を1から問題数まで繰り返す
  パンケーキとは文字列。
  パンケーキは入力ファイルのファイルストリーム一行読む。
  
  直前文字とは文字列。
  直前文字は「z」。
  
  長さとは整数。
  長さはパンケーキの文字数

  カウントとは整数。
  カウントは0。
  
  idxとは整数。
  idxは1。
  
  
#  「=======」を表示
#  「パンケーキ:{パンケーキ} 長さ:{長さ}」を表示
  
  idxで1から(長さ)まで繰り返す
    文字とは文字列。
    文字はパンケーキのidxから1文字抜き出す。
#    「文字:{文字}」を表示
    もし、文字!=直前文字ならば
      カウントに1を直接足す。
    直前文字は文字

  もし、直前文字=「+」ならば
    カウントから1を直接引く。

  「Case #{問題}: {カウント}」を表示。

実は初めてphpを書きました。perlと似てるのですね。

<?php
function solve($s) {
    $prev = 'z';
    $cnt = 0;

    // echo "input: $s";

    $len = strlen($s);
    for ($i = 0; $i < $len; $i++) {
        if ($prev != $s[$i]) {
           $cnt += 1;
        }
        $prev = $s[$i];
    }

    if (substr($s, -1) == '+') {
       $cnt -= 1;
    }

    return $cnt;
}
$T = (int)fgets(STDIN);
for ($t = 1; $t <= $T; $t++) {
    $s = trim(fgets(STDIN));
    $res = solve($s);
    echo "Case #$t: $res\n";
}
?>
C. Coin Jam

経験がないわけではないが苦手なOctaveです。どんくさいコードである可能性が高いです。多倍長整数を使っていないのでSmall限定のコードです。文字の連結にわざわざ関数strcat()を使わないといけないなど文字列操作にはストレスが溜まる言語です。

% octave

line = fgetl(stdin);
testnum = sscanf(line,'%d');

for i = 1:testnum
    printf("Case #%d:\n", i)

    line = fgetl(stdin);
    [NJ,count] = sscanf(line,'%d %d');
    N = NJ(1);
    J = NJ(2);

    numstr = "1";
    for j = 1:N-1
        numstr = strcat(numstr, "0");
    endfor

    found = 0;
    num = int64(bin2dec(numstr));
    while (true)
        num += 1;
        binstr = dec2bin(num);

        if substr(binstr, -1) == '0'
            continue
        endif

        ok = true;
        divisors = {};
        for base = 2:10
            val = base2dec(binstr, base);
            cands = [2 3 5 7 11];

             for c = cands
                if mod(val,c) == 0
%                   printf("%d is dividable by %d\n", val, c);
                   divisors = [divisors, c];
                   break
                endif
            endfor
        endfor

%        printf("mod size:%d\n", size(mod))


        if length(divisors) == 9
           found += 1;
           printf("%s", binstr)
           for d = divisors
               printf(" %d", d{1})
           endfor
           printf("\n")

        endif

        if found == J
           break
        endif

    endwhile
end

rubyは、ほぼPythonのプロト実装を逐語訳して実装できました。

#!/usr/bin/env ruby

def solve()
  n,j = gets.split.map {|s| s.to_i}

  numstr = "1" + "0" * (n-1)
  num = numstr.to_i(base=2)

  found = 0
  loop do
    num += 1

    binstr = num.to_s(2)
    if binstr[-1] == '0' then
        next
    end

    ok = true
    divisors = []
    (2..10).each{|base|
      val = binstr.to_i(base)
      cands = [2,3,5,7,11]
      cands.each{|c|
        if val % c == 0 then
          divisors.push(c)
          break
        end
      }
    }

    if divisors.size == 9 then
      print(([binstr]+divisors).join(" "), "\n")
      found += 1
      if found == j then
        break
      end
    end
  end
end


def main()
    testnum = gets.to_i
    testnum.times do |t|
        puts "Case ##{t+1}:"
        solve()
    end
end

main()

D. Fractiles

D言語でD問題を解くのをやってみたかったのです。Python 2.x系と3.x系どころではない変更がD言語の1.x系と2.x系にあったらしく、ネット上で取得したサンプルが手元でビルドできないことが多く苦労しました。

#!/usr/bin/rdmd

// $ dmd d.d
// $ ./d < input_file

import std.stdio;
import std.array;
import std.string;
import std.conv;
import std.file;
import std.bigint;

BigInt power(BigInt base, BigInt n) {
    BigInt ret = 1;
    while(n > 0) {
        ret *= base;
        n--;
    }
    return ret;
}

void solve(int tc) {
    auto items = readln.split;
    BigInt K = BigInt(items[0].to!int);
    BigInt C = BigInt(items[1].to!int);
    BigInt S = BigInt(items[2].to!int);

    BigInt minimum = (K + C - 1) / C;
    if (S < minimum) {
        writeln(" IMPOSSIBLE");
        return;
    }

    BigInt[] ans;
    BigInt nxt = 0;
    for (int m = 0; m < minimum; ++m) {
        BigInt idx = 0;
        for(BigInt c = C-1; c >= 0; --c) {
            idx += (power(K,c) * nxt);
            nxt++;
            if (nxt == K) {
                nxt -= 1;
            }
        }
        ans ~= [idx];
    }

    foreach (BigInt a; ans) {
        write(" ", a+1);
    }
    writeln("");
}


void main() {
        int n = readln.chomp.to!int;
        for (int i = 1; i <= n; i++) {
        write("Case #", i, ":");
        solve(i);
    }
}

去年始めて書いてみたJuliaです。良さそうな感じはあるのですが、Python生態系が強力すぎるおかげで本格的に勉強するモチベーションは湧きません。

# $ julia d.jl < input_file

function solve()
    K,C,S = map(x -> parse(BigInt,x), (readline() |> split))

    minimum = div(K+C-1, C)
    if S < minimum
        println("IMPOSSIBLE")
        return
    end

    ans = []
    nxt = BigInt(0)
    for m = 0:minimum-1
        idx = BigInt(0)
        for c = C-1:-1:0
            # K ^ c = c-th power of K
            idx += (K ^ c) * nxt
            nxt += 1
            if (nxt == K)
                nxt -= 1
            end
        end
        push!(ans, idx+1)
    end
    println(join(ans, " "))
end

function main()
    T = parse(Int,readline())
    for t = 1:T
        print("Case #$t: ")
        solve()
    end
end

main()

おまけ

実は最初はCOBOLで書いてみようとも思ったのですが、あまりに世界が違いすぎて手も足も出ませんでした。来年以降の宿題です。