Project Euler Problem 61

問題概要

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2061
を参照

解法

入に下2桁，出に上2桁を指定したグラフを作ってDFSする．
DPにする必要は無かった．

実装(Visual Basic.NET)

自分の環境だと0.008秒で終了．

Imports System
Imports System.IO
Imports System.Text
Imports System.Collections
Imports System.Collections.Generic
Imports System.Math
Imports System.Diagnostics

Public Structure Pair(Of T1 As IComparable(Of T1), T2 As IComparable(Of T2))
    Public First As T1, Second As T2
    Public Sub New(ByVal V1 As T1, ByVal V2 As T2)
        First = V1 : Second = V2
    End Sub
End Structure
Module Module1
    Public Answer As Integer
    Public Function P3(ByVal n As Integer) As Integer
        Return n * (n + 1) / 2
    End Function

    Public Function P4(ByVal n As Integer) As Integer
        Return n * n
    End Function

    Public Function P5(ByVal n As Integer) As Integer
        Return n * (3 * n - 1) / 2
    End Function

    Public Function P6(ByVal n As Integer) As Integer
        Return n * (2 * n - 1)
    End Function

    Public Function P7(ByVal n As Integer) As Integer
        Return n * (5 * n - 3) / 2
    End Function

    Public Function P8(ByVal n As Integer) As Integer
        Return n * (3 * n - 2)
    End Function

    Public Graph(5, 99) As List(Of Pair(Of Integer, Integer))
    Public Sub Make_Graph()
        Dim i As Integer, j As Integer
        For i = 0 To 5
            For j = 0 To 99
                Graph(i, j) = New List(Of Pair(Of Integer, Integer))
            Next
        Next
        Dim V As Integer = 0
        V = 0
        For i = 0 To 9999
            Dim t As Integer = P3(i)
            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next

        V = 1
        For i = 0 To 9999
            Dim t As Integer = P4(i)
            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next

        V = 2
        For i = 0 To 9999
            Dim t As Integer = P5(i)
            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next

        V = 3
        For i = 0 To 9999
            Dim t As Integer = P6(i)
            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next

        V = 4
        For i = 0 To 9999
            Dim t As Integer = P7(i)

            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next


        V = 5
        For i = 0 To 9999
            Dim t As Integer = P8(i)
            If t < 1000 Then Continue For
            If t > 9999 Then Exit For
            For j = 0 To 5
                If V = j Then Continue For
                Graph(V, t \ 100).Add(New Pair(Of Integer, Integer)(j, t Mod 100))
            Next
        Next
    End Sub
    Public T(10) As Integer
    Public S As Integer
    Public Sub Solve(ByVal used As Integer, ByVal now1 As Integer, ByVal now2 As Integer, Optional ByVal V As Integer = 0)
        If used + 1 = 1 << 6 And now1 = 0 And now2 = S Then
            Console.WriteLine("{0}{1}{2}{3}{4}{5}", T(0), T(1), T(2), T(3), T(4), T(5))
            Answer = T(0) + T(1) + T(2) + T(3) + T(4) + T(5)
            Answer *= 101
            Return
        End If
        T(V) = now2
        For j As Integer = 0 To Graph(now1, now2).Count - 1
            If (used >> Graph(now1, now2)(j).First) And 1 Then Continue For
            Solve(used Or (1 << Graph(now1, now2)(j).First), Graph(now1, now2)(j).First, Graph(now1, now2)(j).Second, V + 1)
        Next
    End Sub
    Sub Main()
        Dim TimeCounter As New Stopwatch
        TimeCounter.Start()
        Answer = 0

        Make_Graph()
        For i As Integer = 0 To 99
            S = i
            Solve(0, 0, i)
        Next

        TimeCounter.Stop()


        Console.WriteLine("----")
        Console.WriteLine("Answer:{0}", Answer)
        Debug.WriteLine("Answer:{0}", Answer)
        Console.WriteLine("Calculate Time:{0}sec", TimeCounter.ElapsedMilliseconds / 1000)

        '-----
        Console.WriteLine()
        Console.WriteLine("Press Any Key.")
3:      Console.ReadKey()
    End Sub
End Module