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型では足りないことに気付いて、提出はぎりぎりでした。コードが長い…。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace a
{
    class Quaternion
    {
        long sign;  // 1 or -1
        char state;

        public Quaternion()
        {
            this.state = '1';
            this.sign = 1;
        }
        public Quaternion(char ch, long s)
        {
            this.state = ch;
            this.sign = s;
        }

        private Tuple<char, long> MulTable(char ch1, char ch2)
        {
            if (ch1 == '1') return Tuple.Create(ch2, 1L);
            else if (ch1 == 'i')
            {
                var table = new Dictionary<char, Tuple<char, long>>
                {
                    {'1', Tuple.Create('i', 1L)},
                    {'i', Tuple.Create('1', -1L)},
                    {'j', Tuple.Create('k', 1L)},
                    {'k', Tuple.Create('j', -1L)}
                };
                return table[ch2];
            }
            else if (ch1 == 'j')
            {
                var table = new Dictionary<char, Tuple<char, long>>
                {
                    {'1', Tuple.Create('j', 1L)},
                    {'i', Tuple.Create('k', -1L)},
                    {'j', Tuple.Create('1', -1L)},
                    {'k', Tuple.Create('i', 1L)}
                };
                return table[ch2];
            }
            else
            {
                var table = new Dictionary<char, Tuple<char, long>>
                {
                    {'1', Tuple.Create('k', 1L)},
                    {'i', Tuple.Create('j', 1L)},
                    {'j', Tuple.Create('i', -1L)},
                    {'k', Tuple.Create('1', -1L)}
                };
                return table[ch2];
            }
        }

        public void mul(char ch)
        {
            var res = MulTable(this.state, ch);
            this.state = res.Item1;
            this.sign *= res.Item2;
        }

        public void mul_rev(char ch)
        {
            var res = MulTable(ch, this.state);
            this.state = res.Item1;
            this.sign *= res.Item2;
        }

        public Quaternion pow(long n)
        {
            long newsign;
            if (this.sign == 1) newsign = 1;
            else newsign = (n % 2 == 1) ? -1 : 1;

            if (this.state == '1')
            {
                return new Quaternion('1', newsign);
            }

            switch (n % 4)
	        {
                case 0:
                    return new Quaternion('1', newsign);
                case 1:
                    return new Quaternion(this.state, newsign);
                case 2:
                    return new Quaternion('1', -1 * newsign);
                default:
                    return new Quaternion(this.state, -1 * newsign);
	        }
        }

        public bool Same(Quaternion q)
        {
            return this.state == q.state && this.sign == q.sign;
        }

        public void print()
        {
            Console.WriteLine("{0}{1}", (this.sign == 1 ? "" : "-"), this.state);
        }
    }


    class Program
    {
        public static string Reverse(string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }

        static void Main(string[] args)
        {
            new Program().Run();
        }

        void Run()
        {
            long T = long.Parse(Console.ReadLine());
            for (long t = 0; t < T; ++t)
            {
                Console.WriteLine("Case #{0}: {1}", t + 1, Solve());
            }
        }

        string Solve()
        {
            string[] stringArr = Console.ReadLine().Split(' ');
            long L = long.Parse(stringArr[0]);
            long X = long.Parse(stringArr[1]);

            string str = Console.ReadLine();

            // get value of string L*X
            Quaternion q = new Quaternion();
            foreach (var ch in str)
            {
                q.mul(ch);
                //q.print();
            }
            Quaternion all = q.pow(X);
            Quaternion shouldbe = new Quaternion('1', -1);
            if (!all.Same(shouldbe)) return "NO";

            // check if 'i' appears within first 16 repeat of string L
            Quaternion willGoI = new Quaternion();
            long lenI = 0;
            bool found = false;
            for (long rep = 0; rep < System.Math.Min(16,X) && !found; ++rep)
            {
                foreach (var ch in str)
                {
                    willGoI.mul(ch);
                    ++lenI;
                    if (willGoI.Same(new Quaternion('i', 1)))
                    {
                        found = true;
                        break;
                    }
                }
            }
            if (!found) return "NO";

            // check if 'k' appears within last 16 repeat of string L
            found = false;
            var revStr = str.Reverse();
            Quaternion willGoK = new Quaternion();
            long lenK = 0;
            found = false;
            for (long rep = 0; rep < System.Math.Min(16, X) && !found; ++rep)
            {
                foreach (var ch in revStr)
                {
                    willGoK.mul_rev(ch);
                    ++lenK;
                    if (willGoK.Same(new Quaternion('k', 1)))
                    {
                        found = true;
                        break;
                    }
                }
            }
            if (!found) return "NO";

            if (lenI + lenK < L * X) return "YES";
            else return "NO";
        }
    }
}


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"));
    }
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/minus9d/20150412