Google Developers Day 2011 DevQuiz

二ヶ月の前のことなんですね…

ウォームアップクイズ

Google App EngineやAndroid開発に触れたことが無いわたしにとっては鬼門だった。
Google先生にお世話になりつつ6度目の挑戦でようやく満点（40点）に辿りついた。

分野別クイズ

Web Game,Go!,Android,Google Apps Script,一人ゲームの5つから2つ選択する形式だった。
GoとAndoroid及びGoogle Appsの経験が無いわたしは迷わず一人ゲームとWeb Gameを選択した。

一人ゲーム

整数計画問題に直してlp_solveに解いてもらった。
実際にはDFSでいけたらしいが計算量を上手く見積もれなかった。

Imports System
Imports System.IO
Imports System.Text
Imports Microsoft.VisualBasic
Imports System.Collections
Imports System.Collections.Generic
Imports System.Math
'このコードの実行にはlp_solve.exeが同じフォルダにある必要があります．

Class Input
    Public Shared Property Delimiter As String = " ," + vbCr + vbLf + vbTab
    Public Const EOF As Integer = -1
    Public Shared Function Read() As String
        Read = ""
        Do
            Dim t As Integer = Console.Read()
            If Read = "" And t = EOF Then
                Return ""
            End If
            If t = EOF Then
                Return Read
            End If
            Dim Deli As Boolean = False
            For i As Integer = 0 To Delimiter.Length - 1
                If Delimiter(i) = ChrW(t) Then
                    Deli = True
                    If Read <> "" Then
                        Return Read
                    End If
                End If
            Next
            If Deli = False Then
                Read = Read + ChrW(t)
            End If
        Loop
    End Function

    Public Shared Function ReadInteger() As Integer
        Return Integer.Parse(Read())
    End Function

    Public Shared Function ReadDecimal() As Decimal
        Return Decimal.Parse(Read())
    End Function

    Public Shared Function ReadDouble() As Double
        Return Double.Parse(Read())
    End Function

    Public Shared Function ReadLong() As Long
        Return Long.Parse(Read())
    End Function

End Class

Module Module1
    Function ReadInt(ByVal s As String) As Integer
        Dim t As String() = s.Split(" ")
        For Each k In t
            Dim t2 As String() = k.Split(vbCrLf)
            For Each k2 In t2
                If k2.Length > 0 AndAlso IsNumeric(k2(0)) Then
                    Return Double.Parse(k2)
                End If
            Next
        Next
    End Function
    Sub Main()
        Dim T As Integer = Input.ReadInteger
        For TestCase As Integer = 1 To T
            Dim N As Integer = Input.ReadInteger
            Dim Solver(N - 1, 20) As Integer
            Dim OR_V(N - 1) As Integer

            For i = 0 To N - 1
                Solver(i, 0) = Input.ReadInteger
                OR_V(i) = 0
            Next
            For i = 1 To 20
                For j = 0 To N - 1
                    Solver(j, i) = Solver(j, i - 1) \ 2
                Next
            Next
            For j = 0 To N - 1
                For i = 0 To 20
                    If Solver(j, i) Mod 5 = 0 Then
                        Solver(j, i) = 1
                    Else
                        Solver(j, i) = 0
                    End If
                Next
            Next
            For i = 0 To 20
                For j = 0 To N - 1
                    'Console.Write("{0} ", Solver(j, i))
                Next
                'Console.WriteLine()
            Next
            Dim Ans As Integer = 99999999
            For j = 0 To 20
                For i = 0 To N - 1
                    OR_V(i) = OR_V(i) Or Solver(i, j)
                Next
                Dim OK As Boolean = True
                For i = 0 To N - 1
                    If (OR_V(i) = 0) Then
                        OK = False
                    End If
                Next
                If OK = False Then Continue For
                Dim sw As New System.IO.StreamWriter("test.txt", False)
                sw.Write("min:")
                For i = 0 To j
                    If i > 0 Then sw.Write(" +")
                    sw.Write(" x{0}", i)
                Next
                sw.WriteLine(";")
                For i = 0 To j
                    sw.WriteLine("D{0}: x{0} >= 0;", i)
                    sw.WriteLine("E{0}: x{0} <= 1;", i)
                Next
                For i = 0 To N - 1
                    sw.WriteLine("C{0}: ", i)
                    Dim s As Boolean = True
                    For k = 0 To j
                        If Solver(i, k) = 1 Then
                            If s = True Then
                                s = False
                            Else
                                sw.Write(" +")
                            End If
                            sw.Write(" x{0}", k)
                        End If
                    Next
                    sw.WriteLine(">=1;")
                Next
                sw.Write("int ")
                For i = 0 To j
                    If i > 0 Then sw.Write(" ,")
                    sw.Write(" x{0}", i)
                Next
                sw.WriteLine(";")
                sw.Close()
                Dim hPsInfo As New System.Diagnostics.ProcessStartInfo()
                hPsInfo.Arguments = "test.txt"
                hPsInfo.FileName = "lp_solve.exe"
                hPsInfo.UseShellExecute = False
                hPsInfo.RedirectStandardOutput = True
                Dim p As System.Diagnostics.Process = System.Diagnostics.Process.Start(hPsInfo)
                Dim st As String = p.StandardOutput.ReadToEnd
                'Console.WriteLine()
                p.WaitForExit()

                Ans = Min(Ans, ReadInt(st) + j)

            Next

            Console.WriteLine(Ans)
        Next


        'Console.ReadKey()
    End Sub

End Module

Web Game

神経衰弱ゲーム
VBでWebBrowserオブジェクトを操作する形で解いた。
最初は全ての組合せを試していたが、速度が足りなくなったので、ソースに埋めこまれている答を参照する形に変更した。

スライドパズル

最良優先探索で解いたが13点にしかならなかった。
両側最良優先に気づけなかったのも不味い。
ソースは汚ないので省略。

結果

113点でなんとかボーダーは越えていて嬉しかった。