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で書いてみようとも思ったのですが、あまりに世界が違いすぎて手も足も出ませんでした。来年以降の宿題です。

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

2014-11-01

Code Runner 2014 予選Aに参加

| 23:58 | Code Runner 2014 予選Aに参加 - minus9dの記録 を含むブックマーク はてなブックマーク - Code Runner 2014 予選Aに参加 - minus9dの記録

チームラボとキャリフルが主催するCODE RUNNER 2014 予選Aに参加しました。自分は47位で、なんとか予選突破圏内でした(社会人なので資格がありませんが)。自分が経験する初めてのタイプのコンテストで新鮮だったので、簡単にメモしておきます。

問題

AからDからなる50文字の文字列を作って高得点を目指す

戦略
  • ランダムな長さ50の文字列をたくさん作って投げる
  • 点数の高かった上位n件について、長さ8の部分文字列を抽出して点数を調べる
  • 長さ8の文字列のうち点数の高い上位m件から、ランダムに6つ選び、ランダムな2文字をランダムに挿入して50文字の文字列を生成。たくさん試す
使ったツールなど
  • Pythonを使用
  • itertoolsが便利
  • 文字列と点数の組を辞書として持ち、適宜pickleで保存。cacheとして使った
感想と反省
  • 点数の高い長さ8の文字列を結合するときに、先頭と末尾が一致する文字列を結合できるようにしたかったが間に合わず
  • 点数の高い長さ8の文字列の弾が足りなかった
  • スクリプトでHTTP 400の対策を組み込むべきだった
    • 2並列以上でスクリプトを動かすと例外で死ぬ)
    • 乱数を投げ続けるスクリプトを動かしつつ、手元で改善したスクリプトを動かせる環境があるとよかった

2014-04-29

Google Code Jam 2014 Round1A

| 18:18 | Google Code Jam 2014 Round1A - minus9dの記録 を含むブックマーク はてなブックマーク - Google Code Jam 2014 Round1A - minus9dの記録

Round1AはA-smallしか解けず2471位で敗退。

本番ではSmallを優先して解く戦略を取った。とりあえずA-smallをブルートフォースで解き、B-smallに集中するも、手も足も出ずそのまま時間切れ。AとBを両方解いても解答時間によっては敗退してしまうような難易度では勝ち目はまったくなかったと言える。

LayCurseさんのとても教育的な解説を読んで復習した。以下のコードは、Aを除いて、LayCurseさんのコードをほぼ丸々下敷きにしている。

A. Charging Chaos

コンセントと電化製品とのマッチングについて、ビットで制限を加えつつ総当り的なことをしないといけないと勘違いをしていた。しかし実際は、ある一つの組み合わせさえ決めればよいのであった。これは本番中に気づかなければいけない問題だった。

// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_a

#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

const int INF = 10000;

void flip(char &ch){
    if (ch == '0') ch = '1';
    else ch = '0';
}

int main(void)
{
    int TEST_NUM;
    cin >> TEST_NUM;

    for(int test = 0; test < TEST_NUM; ++test){
        int N, L;
        cin >> N >> L;
        vector<string> init(N);
        vector<string> need(N);
        REP(i, N){
            cin >> init[i];
        }
        REP(i, N){
            cin >> need[i];
        }

        sort(ALL(need));

        // 最初のデバイスを、i番目のコンセントにつなぐとしたときに、何度スイッチを押す必要があるかを調べる
        int ret = INF;
        REP(i, N){
            vector<string> init_copy = init;
            int flip_cnt = 0;
            REP(l, L){
                if (init[0][l] != need[i][l]) {
                    REP(j, N){
                        flip(init_copy[j][l]);
                    }
                    ++flip_cnt;
                }
            }
            sort(ALL(init_copy));
            if (init_copy == need) {
                ret = min(ret, flip_cnt);
            }
        }

        cout << "Case #" << (test+1) << ": ";
        if (ret == INF) {
            cout << "NOT POSSIBLE";
        }
        else{
            cout << ret;
        }
        cout << endl;
    }

    return 0;
}

B. Full Binary Tree

ループしていることも考慮すると大変だぞ、と思いあれこれ考えるが、よく問題文を読むと、エッジの数はノードの数-1なのでループはありえないのであった。グラフに関する問題だというだけで必要以上に身構えてしまう悪い傾向がある。

LayCurseさんの解説コードではdpの要素は使っていなかったようなので、以下のコードではdpテーブルは省いてある。再帰関数にて親側のノードを誤って数えないようにする工夫が勉強になった。


// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_b

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

int N;
int edge[1200][1200]; ///< エッジのリスト
int es[1200]; ///< 頂点が持つエッジの数

// now番目のノード以下、残せるノードの最大数を求める
// befは、i番目のノードの親。間違って親側に逆流することを防ぐ
int solve(int now, int bef){
    int i, j, k;

    // now番目のノードの子ノードのそれぞれが、何個のノードを残せるか
    vector<int> num;

    // now番目のノードが持つエッジでループ
    rep(k,es[now]){
        i = edge[now][k];
        if(i==bef) continue;
        num.push_back( solve(i, now) );
    }

    // now番目のノードの子の数が0個または1個の場合は、まったく子は残せないので1
    int ret = 1;

    // now番目のノードの子の数が2個以上の場合は、残せる子の数が多いもの上位2個を選ぶ
    if(num.size() >= 2){
        sort(num.rbegin(), num.rend());
        ret += num[0] + num[1];
    }

    return ret;
}

int main(){
    int i, j, k;
    int res, tmp;
    int T, cnt = 0;

    scanf("%d",&T);
    while(T--){
        fprintf(stderr,"rest %d\n",T);
        printf("Case #%d: ", ++cnt);

        scanf("%d",&N);
        rep(i,N) es[i] = 0;
        rep(i,N-1){
            scanf("%d%d",&j,&k);
            // 0 originに直す
            j--; k--;
            edge[j][es[j]++] = k;
            edge[k][es[k]++] = j;
        }

        // debug print
        // printf("\n");
        // rep(i, N){
        //     printf("es[%d] = %d\n", i, es[i]);
        //     rep(j, es[i]){
        //         printf("  edge ->%d\n", edge[i][j]);
        //     }
        // }

        res = INF;
        // 何番目を頂点にするかのループ
        // 一番良い結果を選ぶ
        rep(i,N){
            tmp = solve(i, -1);
            res = min(res, N-tmp);
        }

        printf("%d\n", res);
    }

    return 0;
}

C. Proper Shuffle

BAD法で生成したランダム配列はGOOD法で生成したランダム配列に比べて悪い癖があるはずで、それをシミュレーションによって明らかにすればよかった。

// 参考:http://rsujskf.s602.xrea.com/?googlecodejam_2014_1a_c

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

// Gper[i][j]: BAD法により、a[i] = jとなる確率のN倍
double Gper[1200][1200];

// サイズnのアレーをBAD法で生成するのをt回シミュレート 確率をGper[i][j]に記録
void test3(int n, int t){
    int i, j, k, loop;
    vector<int> p(n);

    // per[i][j]: BAD法のシミュレート後、アレーのi番目の数字がjである回数をカウント
    static int per[1200][1200] = {};

    // BAD法をt回シミュレート
    rep(loop,t){
        rep(i,n) p[i] = i;
        rep(i,n){
            k = rand() % n; // bad
            swap(p[i], p[k]);
        }

        rep(i,n) per[i][p[i]]++;
    }

    rep(i,n) rep(j,n) Gper[i][j] = (double)per[i][j] / t * n;
  // rep(i,n){ rep(j,n) printf("%f ",(double)per[i][j]/t*n); puts(""); }
}

int main(){
    int i,j,k;
    int T, cnt = 0;
    int N, p[2000], sum;
    double res;
 
    test3(1000, 1000000);
  
    scanf("%d",&T);
    while(T--){
        fprintf(stderr,"rest %d\n",T);
        printf("Case #%d: ", ++cnt);

        scanf("%d",&N);
        rep(i,N) scanf("%d",p+i);
        res = 1;
        rep(i,N) res *= Gper[i][p[i]];
        if(res <= 1) puts("GOOD"); else puts("BAD");
    }

    return 0;
}

2014-01-12

2013年のまとめと2014年の目標

| 14:52 | 2013年のまとめと2014年の目標 - minus9dの記録 を含むブックマーク はてなブックマーク - 2013年のまとめと2014年の目標 - minus9dの記録

2013年のまとめ

2013年の年初に立てたTopCoderの目標はまずまず達成できた。

  • 2回に1回くらいは復習する
    • →未達成
  • Div1にいる時間の方がDiv2にいる時間よりも長くなるように
    • →達成。9割以上の時間Div1に留まれた
  • あわよくば黄色に
    • 一瞬だけだが達成。Max1567

2012年末のレート1189から、2013年末には1496まで上昇。Div1 Easyを、速度はともかく高確率で正解できたことが大きかった。

GCJはRound1で敗退。復習もしていない…

CodeforcesはDiv1とDiv2を行ったり来たりでDiv1に定着できず。


2014年の目標

  • TopCoderの平均レート1500
  • TopCoderのMAXレート1800
  • GCJ Round2進出