BottomCoder SRM 361 Div2

時間があったので参加させていただきました。

結果
Easy(250) Failed System Test
Medium(500) 448.40
Hard(1000) 472.27


Easy
id:atetubouさんの解法が凄いシンプルで良いと思う。
Failed System TestしたのはInStrの第一引数が1スタートであることを考慮しなかったからでした。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Imports Weight = System.Int32
Public Class SearchBox
    Public Function find(ByVal text As String, ByVal search As String, ByVal wholeWord As String, ByVal start As Integer) As Integer
        Dim i As Integer, j As String
        If wholeWord = "N" Then
            find = InStr(start+1, text, search) - 1
        Else
            text = " " + text + " "
            j = "NOSTRINGINGIINGINGININGINGINGININGINGINGININGINGINGININGINGINGININGINGINGININGINGINGININGINGINGININGINGINGININGNGINGINING"
            if Mid(text,start+1,1)=" " Then j=""
            For i = start + 2 To Len(text)
                If (Mid(text, i, 1) = " ") Then
                    If j = search Then
                        Return i - Len(j) - 2
                    End If
                    j = ""
                Else
                    j += Mid(text, i, 1)
                End If
            Next
            find = -1
        End If
    End Function
End Class

Medium
与えられた数の最大値をrとすると、結果はrかr+1か-1になる。
貪欲に一意に定まるか確認する。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Imports Weight = System.Int32
Public Class WhiteHats
    Public Function whiteNumber(ByVal count As Integer()) As Integer
        Dim i As Integer, j As Integer
        Array.Sort(count)
        Dim Res(UBound(count)) As Integer
        Array.Reverse(count)
        If count(0) >= UBound(count) + 1 Then Return -1
        whiteNumber = -1
        For i = 0 To UBound(count)
            Res(i) = 0
            If i < count(0) Then
                Res(i) = 1
            End If
        Next
        Array.Reverse(Res)
        Dim TeRes As Integer = count(0)
        Dim Ans As Boolean = True
        For i = 0 To UBound(count)
            If TeRes - Res(i) <> count(i) Then Ans = False
        Next
        If Ans Then Return TeRes
        For i = 0 To UBound(count)
            Res(i) = 0
            If i <= count(0) Then
                Res(i) = 1
            End If
        Next
        Array.Reverse(Res)
        TeRes = count(0) + 1
        Ans = True
        For i = 0 To UBound(count)
            If TeRes - Res(i) <> count(i) Then Ans = False
        Next
        If Ans Then Return TeRes
    End Function
End Class

Hard
最下位から貪欲に定めることが出来る。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Public Structure Pair(Of T1 As IComparable(Of T1), T2 As IComparable(Of T2))
    Implements System.IComparable
    Implements System.IComparable(Of Pair(Of T1, T2))
    Public First As T1, Second As T2
    Public Function CompareTo(ByVal tar As Pair(Of T1, T2)) As Integer Implements System.IComparable(Of Pair(Of T1, T2)).CompareTo
        If First.CompareTo(tar.First) < 0 Then Return 1 Else If First.CompareTo(tar.First) > 0 Then Return -1 Else If Second.CompareTo(tar.Second) > 0 Then Return 1 Else If Second.CompareTo(tar.Second) < 0 Then Return -1 Else Return 0
    End Function
    Public Function CompareTo(ByVal tar As Object) As Integer Implements System.IComparable.CompareTo
        If tar.GetType() IsNot Me.GetType() Then Throw New ArgumentException("比較不可能な型です", "tar")
        Return Me.CompareTo(DirectCast(tar, Pair(Of T1, T2)))
    End Function
End Structure
Public Class Election
    Public Function votesNeeded(ByVal votes As Integer(), ByVal wishList As Integer()) As Integer
        Dim i As Integer, j As Integer, n As Integer = UBound(votes), k As Integer
        Dim Vote(n) As Pair(Of Integer, Integer)
        For i = 0 To n
            Vote(i).Second = i
            Vote(i).First = votes(i)
        Next
        Array.Sort(Vote)
        Dim Usingdata(n) As Integer
        For i = 0 To n
            Usingdata(i) = 0
        Next

        For i = 0 To n
            If wishList(i) <> -1 Then Usingdata(wishList(i)) = 1
        Next
        For i = 0 To n
            If Usingdata(i) Then Continue For
            For j = 0 To n
                If wishList(Vote(j).Second) = -1 Then
                    wishList(Vote(j).Second) = i
                    Usingdata(i) = 1
                    Exit For
                End If
            Next
        Next
        votesNeeded = 0
        Dim Used(n) As Integer
        For i = 0 To n
            Used(i) = 0
        Next
        For i = n To 0 Step -1
            For j = 0 To n
                If wishList(j) = i Then
                    Dim Minval As Integer = votes(j)
                    For k = 0 To n
                        If k = j + 1 Then Minval += 1
                        If (Used(k) = 0) Then
                            If votes(k) < Minval Then
                                votesNeeded += Minval - votes(k)
                                votes(k) = Minval
                            End If
                        End If
                    Next
                    Used(j) = 1
                End If
            Next
        Next
    End Function
End Class