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