Submission #64191286

---

Source Code Expand

using System;
using System.Diagnostics;

namespace cp;

internal static class Codeforces
{
    private static int _d;
    private static int[] _c;
    private static int[,] _s;
    
    private static readonly Random _random = new Random();
    
    public static void Main()
    {
        _d = Convert.ToInt32(Console.ReadLine());
        _c = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
        Debug.Assert(_c.Length == 26);
        
        _s = new int[_d, 26];
        for (int i = 0; i < _d; i++)
        {
            IEnumerable<int> r = Console.ReadLine()!.Split(' ').Select(int.Parse);
            IEnumerator<int> e = r.GetEnumerator();
            for (int j = 0; j < 26; j++)
            {
                e.MoveNext();
                _s[i, j] = e.Current;
            }
            Debug.Assert(!e.MoveNext());
        }


        // int[] bestSchedule = RunHillClimbing();
        int[] bestSchedule = RunSA();
        
        for (int i = 0; i < _d; i++)
        {
            Console.WriteLine(bestSchedule[i]);
        }
    }

    private static int[] RunHillClimbing()
    {
        int bestScoreHc = int.MinValue;
        
        // Initialize a random probably shitty schedule
        int[] schedule = new int[_d];
        for (int i = 0; i < _d; i++)
        {
            schedule[i] = _random.Next(1, 27);
        }
        
        Stopwatch stopwatch = Stopwatch.StartNew();
        while (stopwatch.ElapsedMilliseconds < 1950)
        {
            int randomIdx = _random.Next(_d);
            int oldScheduledContest = schedule[randomIdx];
            int randomContest = _random.Next(1, 27);
            schedule[randomIdx] = randomContest;
            int newScore = EvaluateSchedule(schedule);
            if (newScore > bestScoreHc)
            {
                bestScoreHc = newScore;
            }
            else
            {
                schedule[randomIdx] = oldScheduledContest;
            }
        }
        
        return schedule;
    }
    
    private static int[] RunSA()
    {
        int bestScoreSa = int.MinValue;
        int[] bestScheduleSa = new int[_d];
        const float initialTemperature = 2000;
        const float finalTemperature = 600;
        
        // Initialize a random probably shitty schedule
        int[] schedule = new int[_d];
        for (int i = 0; i < _d; i++)
        {
            schedule[i] = _random.Next(1, 27);
        }
        
        Stopwatch stopwatch = Stopwatch.StartNew();
        while (stopwatch.ElapsedMilliseconds < 1950)
        {
            // t_initial * pow(t_final / t_initial, elapsed() / time_limit)
            float temperature = initialTemperature * (float)Math.Pow(
                finalTemperature/initialTemperature, 
                stopwatch.ElapsedMilliseconds/1950f
            );
            int randomIdx = _random.Next(_d);
            int oldScheduledContest = schedule[randomIdx];
            int randomContest = _random.Next(1, 27);
            while (randomContest == oldScheduledContest)
            {
                randomContest = _random.Next(1, 27);
            }
            schedule[randomIdx] = randomContest;
            int newScore = EvaluateSchedule(schedule);
            if (newScore > bestScoreSa)
            {
                bestScoreSa = newScore;
                bestScheduleSa = (int[])schedule.Clone();
            }
            else
            {
                if (_random.NextDouble() < Math.Exp((newScore - bestScoreSa) / temperature))
                {
                    bestScoreSa = newScore;
                    bestScheduleSa = (int[])schedule.Clone();
                }
                else
                {
                    schedule[randomIdx] = oldScheduledContest;
                }
            }
        }
        
        return bestScheduleSa;
    }

    private static int EvaluateSchedule(int[] schedule)
    {
        Debug.Assert(schedule.Length == _d);
        
        int[] last = new int[26];
        int totSatisfaction = 0;
        for (int i = 0; i < _d; i++)
        {
            int contest = schedule[i] - 1;
            totSatisfaction += _s[i, contest];
            last[contest] = i + 1;
            for (int j = 0; j < 26; j++)
            {
                totSatisfaction -= _c[j] * (i + 1 - last[j]);
            }
        }
        
        return totSatisfaction;
    }
}

Submission Info

Judge Result