Hatena::Grouptopcoder

minus9dの記録

2015-04-12

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

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

go-heroという、GCJの提出結果をまとめたサイトに、使用した言語数のランキングがあります (Multiple submission languages (2015) — Code Jam Statistics) 。

普段はC++Pythonしか使わないのですが、今回はこのランキングに乗ることを狙いました。

戦略

C++PythonはRound 1用に温存しておきたかったので、他の言語から8つを捻出します。Perlは昔の杵柄。Ruby, C#は昔入門書を読んだので何とかなりそう。JavaとGoは今後のために勉強しつつ書く。有名すぎる言語だけだと面白みが薄いので、組み込みに使われることがあるというLuaと、科学技術計算用言語のJuliaに挑戦――という感じでした。

関数型言語にも挑戦したかったのですが、数時間では入出力部分さえ動かなそうだったので諦めました。

どの言語でどの問題を解くかはなかなか迷いました。Aはやるだけなので、まったく未知の言語であるJuliaとLuaを割り当て。Bは優先度付きキューを使う問題だと当初勘違いしていたので、標準ライブラリでそれを提供するGoとJavaを採用。Cはクオータニオンをクラスで表現しようと思ったので、少しは知識があるC#Rubyを割り当て。Dはその残り、という決め方です。

結果

D-largeを間違えて7つ通りました。冒頭に貼ったリンクを見ると、幸運なことに同率で暫定1位(計6人)になりました! しかしもう1つか2つ増えるだけで打ち止めでしょう。

問題詳細

A. Standing Ovation

JuliaとLuaで解きました。問題自体は単純なシミュレーションなので簡単ですが、まったく初めての言語だと入出力すら覚束ず。特にLuaは、正規表現を使ったSplitが独特で、入力部だけで1時間以上かかりました。どちらの言語も、去年GCJを解いた人のコードが参考になりました。

以下はJulia。シンタックス・ハイライトできない…。

function solve(smax, shys)
    people = 0
    ret = 0
    for s = 0:smax
        shy_n = int(shys[s+1] - '0')
        #println("s = ", s, ". shy_n = ", shy_n)
        if people < s && shy_n > 0
            ret += (s - people)
            people += (s - people) + shy_n
        else
            people += shy_n
        end
        #println("ret, people = ", ret, ", ", people)
    end
    return ret
end

function readinput()
    smax, shys = readline() |> split
    smax = int(smax)
    return smax, shys
end

function main()
    T = readline() |> int
    for t = 1:T
        println("Case #$t: ", solve(readinput()...))
    end
end

main()

以下はLua。ハイフンによるコメント、gmatchを多用する流儀、変数にlocalを付けないとglobalになってしまう仕様、1-originの配列などなど、独特の要素が多数。今回一番苦労しました。

function solve()
    local line = io.read()

    -- split into two string
    local words = {}
    for s in string.gmatch(line, '%S+') do
        table.insert(words, s)
    end

    local smax = tonumber(words[1])
    local shys = words[2]

    local people = 0
    local ret = 0
    for s = 0, smax do
        local shy_n = tonumber( shys:sub(s+1,s+1) )
        if (people < s and shy_n > 0) then
            ret = ret + (s - people)
            people = people + (s - people) + shy_n
        else
            people = people + shy_n
        end
    end
    return ret
end

function main()
    local ntest = tonumber(io.read())
    for i = 1, ntest do
        print("Case #" .. i .. ": " .. solve())
    end
end

main()

B. Infinite House of Pancakes

皿に乗ったパンケーキを二つに分割する処理と、すべての皿のパンケーキを一つ減らす処理のどちらか一つを選ぶ。パンケーキが0枚となる最小の処理回数を答える問題。

パンケーキを分割する処理を最初にまとめて行い、最後にすべての皿のパンケーキを一つ減らす処理を行うのがよさそうです。最初の方針では、パンケーキの分割方法として「もっとも多くのパンケーキが乗った皿を二等分」すればよいかと思いましたが、これだと初期皿が[40, 120]のときうまくいきません。

「すべての皿がn以下になるまでパンケーキの分割を行う」と考えるとうまくいきます。nを1からmaxまで変えて、処理回数が最小になるnの場合を探します。

以下はGo言語。未使用の変数などがあればエラーが出る仕様は、時間に追われるコンテストだと有難迷惑という感じです。

package main

import (
       "fmt"
       "sort"
)
func solve() int {
     var D int
     fmt.Scan(&D)

     dishes := make([]int, D, D)

     for d := 0; d < D; d++ {
         fmt.Scan(&dishes[d])
     }
     sort.Sort(sort.Reverse(sort.IntSlice(dishes)))

     ret := dishes[0]
     for mx := 1; mx <= dishes[0]; mx++ {
         minutes := mx
         for _, dish := range dishes {
             minutes += (dish - 1) / mx
         }
         if minutes < ret {
             ret = minutes
         }
     }

     return ret
}

func main() {
     var T int
     fmt.Scan(&T)
     for t := 0; t < T; t++ {
          fmt.Printf("Case #%v: %v\n", t+1, solve())
     }
}

Javaは恥ずかしながらmainの書き方が分かりませんでした…。文法はC++と似ているので他は簡単でした。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.io.*;
import java.util.*;

public class B
{
    Scanner sc = new Scanner(System.in);

    int solve() {
        int D = sc.nextInt();
        ArrayList<Integer> dishes = new ArrayList<Integer>();

        for (int d = 0; d < D; ++d) {
            dishes.add(sc.nextInt());
        }

        int max_dish = Collections.max(dishes);
        int ret = max_dish;
        for (int mx = 1; mx <= max_dish; ++mx) {
            int minutes = mx;
            for (int dish: dishes) {
                minutes += (dish - 1) / mx;
            }
            if (minutes < ret) ret = minutes;
        }

        return ret;
    }

    void run() {
        int T = sc.nextInt();
        for (int t = 1; t <= T; ++t) {
            System.out.printf("Case #%d: %d\n", t, solve());
            System.out.flush();
        }
    }

    public static void main(String[] args) {
        new B().run();
    }
}


C. Dijkstra

クオータニオン1, i, j, kからなる、長さLの文字列を、X倍した文字列が与えられる。文字列を適当に3分割すると、分割した部分の計算結果がi, j, kになるかどうかを判定する問題。

もし3分割してi, j, kとなるなら、文字列全体の評価結果は i * j * k = -1となるはず。これが必要条件。もしこの必要条件が満たされる場合、「文字列の先頭部からiとなる部分文字列が取れ、かつ、文字列の末尾部からkとなる文字列が取れる」ならば、残りの真ん中の部分は必ずjとなる、と分かる。

問題は、文字列の先頭部と末尾部を何文字分見ればいいかということ。クオータニオンは16個の状態しか持たないので、なんとなくL*16個分見れば十分な気がしたけど、正当化できていません。

ハマったのが、文字列の末尾部を順番に見ていく部分。交換則が成り立たないことを忘れていました。

以下はruby。引数の異なるinitializerを二つ持てないらしく、対策に難儀しました。

#!/usr/bin/env ruby

class Quaternion

  attr_accessor :state, :sign
  
  def initialize()
    @state = '1'
    @sign = 1
  end

  # another initializer
  def self.new2(state, sign)
    ret = self.new
    ret.state = state
    ret.sign = sign
    return ret
  end

  def mulTable(ch1, ch2)
    if (ch1 == '1') then 
      return [ch2, 1]
    elsif (ch1 == 'i') then
      table = {
        '1' => ['i', 1],
        'i' => ['1', -1],
        'j' => ['k', 1],
        'k' => ['j', -1]
      }
      return table[ch2]
    elsif (ch1 == 'j') then
      table = {
        '1' => ['j', 1],
        'i' => ['k', -1],
        'j' => ['1', -1],
        'k' => ['i', 1]
      }
      return table[ch2]
    else
      table = {
        '1' => ['k', 1],
        'i' => ['j', 1],
        'j' => ['i', -1],
        'k' => ['1', -1]
      }
      return table[ch2]
    end
  end
  private :mulTable

  # self * ch
  def mul(ch)
    res = mulTable(@state, ch)
    @state = res[0]
    @sign *= res[1]
  end

  # ch * self
  def mul_rev(ch)
    res = mulTable(ch, @state)
    @state = res[0]
    @sign *= res[1]
  end

  def pow(n)
    newsign = (@sign == 1) ? 1 : ((n % 2 == 1) ? -1 : 1)
    if @state == '1' then
      return Quaternion.new2('1', newsign)
    end

    case n % 4
    when 0
      return Quaternion.new2('1', newsign)
    when 1
      return Quaternion.new2(@state, newsign)
    when 2
      return Quaternion.new2('1', -1 * newsign)
    else
      return Quaternion.new2(@state, -1 * newsign)
    end

    return ret
  end

  def same(q)
    return @state == q.state && @sign == q.sign
  end

  def debug_print()
    print (@sign == 1 ? "" : "-"), @state, "\n"
  end

end

def solve()
  l,x = gets.split.map {|s| s.to_i}
  str = gets.chomp

  q = Quaternion.new
  str.each_char do |ch|
    q.mul(ch)
    # print "ch: ", ch, ".\n"
    # q.debug_print()
  end

  all = q.pow(x)
  shouldbe = Quaternion.new2('1', -1)
  return "NO" if (!all.same(shouldbe))

  willGoI = Quaternion.new
  i = Quaternion.new2('i', 1)
  lenI = 0
  found = false

  [16,x].min.times do |rep|
    break if found
    str.each_char do |ch|
      willGoI.mul(ch)
      lenI += 1
      if willGoI.same(i) then
        found = true
        break
      end
    end
  end
  return "NO" if (!found)

  willGoK = Quaternion.new
  k = Quaternion.new2('k', 1)
  lenK = 0
  found = false
  str.reverse!
  [16,x].min.times do |rep|
    break if found
    str.each_char do |ch|
      willGoK.mul_rev(ch)
      lenK += 1
      if willGoK.same(k) then
        found = true
        break
      end
    end
  end
  
  return "NO" if (!found)
  return "YES" if lenI + lenK < l * x
  return "NO"
  
end

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

main()

以下はC#。Largeファイルダウンロード後に、int型では足りないことに気付いて、提出はぎりぎりでした。コードが長い…。

te == 

D. Ominous Omino

X個のブロックからなるX-ominoの集合がある。Gabrielは、指定盤面R*Cを、任意のX-ominoで敷き詰められば勝ち。敷き詰めなければRichardの勝ち。ただしGabrielは、Richardが選んだX-ominoを必ず使わなければならない。

丁寧に場合分け…だと思う。Largeを落としたので後で復習。

常套手段として、常にR<=CとなるようにRとCをswapしておくと便利。

以下はCで書いたSmallを通過するコード。

#include <stdio.h>

/// @retval 0: can't fill (Richard)
/// @retval 1: can fill (Gabriel)
int solve(int X, int S, int B) {
    // always S <= B
    if (B < S) {
        int tmp = S;
        S = B;
        B = tmp;
    }

    if (X == 1) {
        return 1;
    }
    else if (X == 2) {
        if (B == 1) return 0;
        if ((B * S) % 2 == 0) return 1;
        return 0;
    }
    else if (X == 3) {
        if (B <= 2) return 0;
        if (S == 1) return 0;
        if ((B * S) % 3 == 0) return 1;
        else return 0;
    }
    else if (X == 4) {
        if (B <= 3) return 0;
        if (S <= 2) return 0;
        if ((B * S) % 4 == 0) return 1;
        else return 0;
    }
}

int main(void)
{
    /* int x, s, b; */
    /* for(x = 1; x <= 4; ++x) { */
    /*     for(s = 1; s <= 4; ++s) { */
    /*         for(b = s; b <= 4; ++b) { */
    /*             printf("x, s, b, result = %d, %d, %d, %d\n", x, s, b, solve(x, s, b)); */
    /*         } */
    /*     } */
    /* } */

    int T;
    scanf("%d", &T);
    int t = 0;
    for(t = 0; t < T; ++t) {
        int X, S, B;
        scanf("%d %d %d", &X, &S, &B);
        printf("Case #%d: %s\n", (t+1), (solve(X, S, B) ?  "GABRIEL" : "RICHARD"));
    }
    return 0;
}


(追記)Largeのバグを修正したPerlのコードです。X=5, 短辺=3のときにバグがありました。このときは長辺が8以上のときに盤を埋めるチャンスがあります。

#!/usr/bin/env perl
use strict;
use utf8;

&main();

# @retval 0: can't fill (Richard)
# @retval 1: can fill (Gabriel)
sub solve
{
    my ($X, $S, $B) = @_;

    # always S <= B
    ($B, $S) = ($S, $B) if ($B < $S);

    if ($X == 1) {
        return 1;
    }
    elsif ($X == 2) {
        return 0 if ($B == 1);
        return 1 if (($B * $S) % 2 == 0);
        return 0;
    }
    elsif ($X == 3) {
        return 0 if ($B <= 2);
        return 0 if ($S == 1);
        return 1 if (($B * $S) % 3 == 0);
        return 0;
    }
    elsif ($X == 4) {
        return 0 if ($B <= 3);
        return 0 if ($S <= 2);
        return 1 if (($B * $S) % 4 == 0);
        return 0;
    }
    elsif ($X == 5) {
        return 0 if ($B <= 4);
        return 0 if ($S <= 2);

        # S = 3のとき、B >= 8ならチャンスがある。 B <= 7ならどうやっても無理
        # もっとも難しいブロックは以下
        # □□□□■■□□
        # □□□■■□□□
        # □□□■□□□□
        return 0 if ($S == 3 && $B <= 7);

        return 1 if (($B * $S) % 5 == 0);
        return 0;
    }
    elsif ($X == 6) {
        return 0 if ($B <= 5);
        return 0 if ($S <= 3);
        return 1 if (($B * $S) % 6 == 0);
        return 0;
    }
    else {
        return 0;
    }
}

sub main
{
    # for my $x (1..8) {
    #     for my $s (1..8) {
    #         for my $b ($s..8) {
    #             printf("x, s, b, result = %d, %d, %d, %d\n", $x, $s, $b, solve($x, $s, $b))
    #         }
    #     }
    # }

    my $T = <STDIN>;
    for my $t (0..$T-1)
    {
        my ($X, $S, $B);
        my $line = <STDIN>;
        chomp($line);
        ($X, $S, $B) = split(' ', $line);
        printf("Case #%d: %s\n", ($t+1), (solve($X, $S, $B) ?  "GABRIEL" : "RICHARD"));
    }
}