Questo post è pensato come un’introduzione alla programmazione competitiva per gli sviluppatori .Net. Uno degli obiettivi di questo post è anche convincere i lettori dei vantaggi che il linguaggio Visual Basic porta nella programmazione competitiva.
Per iniziare a programmare in VB .Net vi è bisogno di un ambiente di sviluppo adeguato. Per questo abbiamo deciso di utilizzare una macchina con sistema operativo Windows XP e come IDE Microsoft Visual Studio™ 2008 Professional Edition.
Come problema di esempio abbiamo scelto il seguente: C - Rotation
Il problema si può risolvere con un semplice intero, tuttavia per dimostrare le piene potenzialità di VB .Net, abbiamo deciso di impiegare un MucchiAlbero.
Dopo allegheremo anche il codice, ma per ora elenchiamo alcuni dei vantaggi che la programmazione in VB .Net porta con se:
-
Operatori di comparazione molto più chiari: l’operatore di uguaglianza è il semplice
=, invece del==o addirittura===di alcuni altri linguaggi di programmazione inferiori. Quello di disuguaglianza è invece<>, al contrario di altri linguaggi di programmazione inferiori, si capisce subito che non è un’uguaglianza, proprio per la mancanza del simbolo=. -
Operatori logici not short-circuiting: gli operatori
AndeOrdi default valutano entrambi gli operandi, come qualunque persona logica si aspetterebbe. Per non valutare il secondo membro quando non necessario si possono utilizzare gli operatoriAndAlsoeOrElse. L’utilizzo di nomi così oscuri per questi operatori fa subito comprendere la loro inutilità. -
Presenza degli operatori
IsTrueeIsFalse, per controllare in modo molto più intuitivo se un valore booleano è vero o è falso, e fanno esattamente quello che ti aspetteresti. -
Sintassi separata per funzioni che hanno un valore di ritorno o no. Questo permette molto agevolmente, leggendo il codice, di capire se, usando una certa funzione, ci si deve aspettare un valore di ritorno o meno.
-
Sintassi esplicita per passare valori per reference o per valore. Grazie a
ByRefeByValnon ci sarà più bisogno di indovinare se qualcosa è stato passato per copia o per riferimento. -
Tutto è un puntatore, ma non lo sai. Questo è molto intuitivo per programmatori novizi. Di fatto, per agevolare i novizi, non vi è supporto per i puntatori come li conosciamo noi.
-
Tutto è in UpperCamelCase. In questo modo, attraverso il nome, viene sancita l’uguaglianza tra i diversi tipi di oggetti.
-
Di default, tutte le operazioni aritmetiche sono controllate per overflow. Questo è molto comodo per i novizi, essendo che non potrebbero essere a conoscenza delle limitate dimensioni degli interi. Altri linguaggi inferiori hanno interi infiniti (Python) oppure overflowano silenziosamente. Non Visual Basic che lancia un’eccezione. Per disabilitare questo controllo, per ottenere uno speedup di almeno 5x nel codice serve la versione pro (che noi abbiamo a disposizione).
-
I for hanno range incluso-incluso [a, b] . Questo è più intuitivo dei range incluso-escluso [a, b) .
-
Le stringhe sono immutabili. Per costruire una stringa bisogna usare la classe molto intuitivamente chiamata
System.Text.StringBuilder. -
Tutte le altre funzionalità dell’architettura .Net, come le funzioni
Microsoft.VisualBasic.ChrW(),Microsoft.VisualBasic.AscW()eSystem.Random()
Questo è il codice risolutivo (comprendente MucchiAlbero), del problema:
Module Mucchialbero
Class Mucchialbero
Private Generator As System.Random = New System.Random()
Private LastNode As Integer = 0
Private Nodes(499999, 4) As Integer
Private Treap As Integer = -1
Private Function NewNode(ByVal C As Char)
Nodes(LastNode, 0) = 1
Nodes(LastNode, 1) = Generator.Next(0, 33554432)
Nodes(LastNode, 2) = Microsoft.VisualBasic.AscW(C)
Nodes(LastNode, 3) = -1
Nodes(LastNode, 4) = -1
LastNode += 1
Return LastNode - 1
End Function
Private Sub Split(ByVal T As Integer, ByRef Left As Integer, ByRef Right As Integer, ByVal Key As Integer, ByVal Add As Integer)
If T = -1 Then
' Fake node
Left = -1
Right = -1
Return
End If
' Real node
Dim CurrentKey As Integer = If(Nodes(T, 3) = -1, 0, Nodes(Nodes(T, 3), 0)) + Add
If CurrentKey < Key Then
' left subtree
Split(Nodes(T, 4), Nodes(T, 4), Right, Key, CurrentKey + 1)
Left = T
Else
' right subtree
Split(Nodes(T, 3), Left, Nodes(T, 3), Key, Add)
Right = T
End If
Nodes(T, 0) = 1 + If(Nodes(T, 3) = -1, 0, Nodes(Nodes(T, 3), 0)) + If(Nodes(T, 4) = -1, 0, Nodes(Nodes(T, 4), 0))
End Sub
Private Sub Merge(ByRef T As Integer, ByVal Left As Integer, ByVal Right As Integer)
If Left = -1 Then
T = Right
Return
End If
If Right = -1 Then
T = Left
Return
End If
If Nodes(Left, 1) < Nodes(Right, 1) Then
Merge(Nodes(Left, 4), Nodes(Left, 4), Right)
T = Left
Else
Merge(Nodes(Right, 3), Left, Nodes(Right, 3))
T = Right
End If
Nodes(T, 0) = 1 + If(Nodes(T, 3) = -1, 0, Nodes(Nodes(T, 3), 0)) + If(Nodes(T, 4) = -1, 0, Nodes(Nodes(T, 4), 0))
End Sub
Private Function Search(ByVal T As Integer, ByVal Pos As Integer, ByVal Add As Integer) As Char
Dim CurrentKey As Integer = Add + If(Nodes(T, 3) = -1, 0, Nodes(Nodes(T, 3), 0))
If CurrentKey = Pos Then
Return ChrW(Nodes(T, 2))
ElseIf CurrentKey < Pos Then
Return Search(Nodes(T, 4), Pos, CurrentKey + 1)
Else
Return Search(Nodes(T, 3), Pos, Add)
End If
End Function
Private Function Build(ByRef S As String, ByVal L As Integer, ByVal Length As Integer) As Integer
If Length = 0 Then
Return -1
End If
Dim Mid As Integer = Length >> 1
Dim T As Integer = NewNode(S(L + Mid))
Nodes(T, 3) = Build(S, L, Mid)
Nodes(T, 4) = Build(S, L + Mid + 1, Length - Mid - 1)
Nodes(T, 0) = 1 + If(Nodes(T, 3) = -1, 0, Nodes(Nodes(T, 3), 0)) + If(Nodes(T, 4) = -1, 0, Nodes(Nodes(T, 4), 0))
Return T
End Function
Private Sub Heapify(ByVal T As Integer)
If T = -1 Then
Return
End If
Dim Max As Integer = T
If Nodes(T, 3) <> -1 AndAlso Nodes(Nodes(T, 3), 1) < Nodes(Max, 1) Then
Max = Nodes(T, 3)
End If
If Nodes(T, 4) <> -1 AndAlso Nodes(Nodes(T, 4), 1) < Nodes(Max, 1) Then
Max = Nodes(T, 4)
End If
If Max = T Then
Return
End If
Dim Temp As Integer
Temp = Nodes(Max, 1)
Nodes(Max, 1) = Nodes(T, 1)
Nodes(T, 1) = Temp
Heapify(Max)
End Sub
Public Sub Query(ByVal X As Integer)
Dim N As Integer = Nodes(Treap, 0)
Dim L As Integer = -1
Dim R As Integer = -1
Split(Treap, L, R, N - X, 0)
Merge(Treap, R, L)
End Sub
Public Function Search(ByVal Pos As Integer)
Return Search(Treap, Pos, 0)
End Function
Public Sub New(ByVal S As String)
Treap = Build(S, 0, S.Length())
Heapify(Treap)
End Sub
End Class
Sub Main()
Dim N As Integer = 0
Dim Q As Integer = 0
Dim Temp As String = System.Console.ReadLine()
Dim LastRead As Integer = 0
For I As Integer = 0 To Temp.Length() - 1
If Temp(I) = " " Then
LastRead = I + 1
Exit For
End If
N = N * 10 + Microsoft.VisualBasic.AscW(Temp(I)) - 48
Next I
For I As Integer = LastRead To Temp.Length() - 1
Q = Q * 10 + Microsoft.VisualBasic.AscW(Temp(I)) - 48
Next I
Dim S As String
S = System.Console.ReadLine()
Dim Treap As Mucchialbero = New Mucchialbero(S)
Dim Sb As New System.Text.StringBuilder()
For I As Integer = 0 To Q - 1
Dim T As Integer = 0
Dim X As Integer = 0
Temp = System.Console.ReadLine()
For J As Integer = 0 To Temp.Length() - 1
If Temp(J) = " " Then
LastRead = J + 1
Exit For
End If
T = T * 10 + Microsoft.VisualBasic.AscW(Temp(J)) - 48
Next J
For J As Integer = LastRead To Temp.Length() - 1
X = X * 10 + Microsoft.VisualBasic.AscW(Temp(J)) - 48
Next J
If T = 2 Then
Sb.AppendLine(Treap.Search(X - 1))
Continue For
End If
Treap.Query(X)
Next I
System.Console.WriteLine(Sb.ToString())
End Sub
End Module
