https://codeiq.jp/ace/yuki_hiroshi/q303

pigdata.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Security.Cryptography;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static ushort getindex(ulong index)
        {
            ulong r = index % 10;
            ulong q = index / 10;
            byte[] s =  Encoding.ASCII.GetBytes(q.ToString());
            SHA1 h = new SHA1CryptoServiceProvider();
            var d = h.ComputeHash(s);
            ushort result = (ushort)(d[2 * r] << 8 | d[2 * r + 1]);
            return result;        
        }

        static ushort[] getindex_array(ulong index)
        {
            byte[] s = Encoding.ASCII.GetBytes(index.ToString());
            SHA1 h = new SHA1CryptoServiceProvider();
            var d = h.ComputeHash(s);
            ushort[] result = new ushort[10];
            for (var i = 0; i < 10; i++) { 
                result[i] =  (ushort)(d[2 * i] << 8 | d[2 * i + 1]);            
            }            
            return result;        
        }
        
        static ulong getsign(ulong count, ulong skip)
        {
            var sorted = new List<ushort>(); 
            for(var i = 0UL ; i < count; i++)
            {
                sorted.Add(getindex(i));
            }
            sorted.Sort();
            ulong total = 0UL;

            for(var i =0UL; i < count; i+=skip)
            {
                total += (ulong)(sorted[(int)(i)]);
            }
            return total;
        }

        static ulong[] get_bucket(ulong index)
        {
            var bucket = new ulong[0x10000];

            var loop_num = index/10;
            for (var i = 0UL; i < loop_num; i += 1) {
                var hash = getindex_array(i);                
                foreach(var item in hash){
                    bucket[item] += 1;
                }
            }
            return bucket;
        }

        static ulong[] get_bucket2(ulong index)
        {
            var bucket = new ulong[0x10000];
            var loop_num = index / 10;
            SHA1 h = new SHA1CryptoServiceProvider();

            for (var i = 0UL; i < loop_num; i += 1)
            {
                byte[] s = Encoding.ASCII.GetBytes(i.ToString());
                var d = h.ComputeHash(s);
                for (var j = 0; j < 10; j++)
                {
                    int bucket_index = (d[2 * j] << 8 | d[2 * j + 1]);
                    bucket[bucket_index] += 1;
                }
            }
            return bucket;
        }

        static ulong[] get_bucket3(ulong index)
        {

            var parallel_num = 16UL;
            var bucket = new ulong[parallel_num, 0x10000];

            if (index < 1000){
                return get_bucket2(index);
            }

            //Thread.CurrentThread.Priority = System.Threading.ThreadPriority.Highest; //追加
            var options = new ParallelOptions();
            //options.MaxDegreeOfParallelism = 4;
            options.MaxDegreeOfParallelism = (int)parallel_num;
            Parallel.For(0, (int)parallel_num, options, thread_id =>
            {
                ulong start = (ulong)((index / 10UL * (ulong)(thread_id)) / parallel_num);
                ulong end = (ulong)((index / 10UL * (ulong)(thread_id + 1)) / parallel_num);

                SHA1 h = new SHA1CryptoServiceProvider();
                //var h = new SHA1Managed();
                for (var i = start; i < end; i++)
                {
                    byte[] s = Encoding.ASCII.GetBytes(i.ToString());
                    var d = h.ComputeHash(s);
                    for (var j = 0; j < 10; j++)
                    {
                        int bucket_index = (d[2 * j] << 8 | d[2 * j + 1]);
                        bucket[thread_id, bucket_index]++;
                    }
                }
                Console.WriteLine("Thread" + thread_id + "finished " + start + " " + end);
            });

            var result_bucket = new ulong[0x10000];
            for(var i = 0 ;i < 0x10000; i++){
                for(var thread_id = 0; thread_id < (int)parallel_num; thread_id++){
                    result_bucket[i] += bucket[thread_id, i];           
                }
            }
            return result_bucket;
        }
        
        static ulong[] get_bucket_dummy(ulong index)
        {
            var bucket = new ulong[0x10000];
            for (var i = 0; i < 0x10000; i++)
            {
                bucket[i] = index >> 16;
            }
            return bucket;
        }


        static ulong getsign_with_bucket(ulong count, ulong skip)
        {
            if (count % 10 != 0) {
                return 0;
            }

            //var bucket = get_bucket(count);
            //var bucket = get_bucket2(count);
            var bucket = get_bucket3(count);
            //var bucket = get_bucket_dummy(count);

            var loop_num = count / skip;
            var total = 0UL;
            var i = 0;
            for(var k = 0UL; k < loop_num; k++){
                while(true){
                    if(bucket[i] > 0){
                        total += (ulong)(i);
                        break;
                    }else{
                        i+=1;
                    }
                }
                var left = skip;
                while(left > 0){
                    while(bucket[i] > 0){
                        if (bucket[i] >= left)
                        {
                            bucket[i] -= (left);
                            left = 0;
                        }
                        else{
                            left -= bucket[i];
                            bucket[i] = 0; 
                            i+=1;                        
                        }

                        if (left == 0)
                        {
                            break;
                        }
                    }

                    if (bucket[i] == 0){
                        i += 1;
                    }
                }
            }

            Console.WriteLine(total);

            return total;
        }

        static TimeSpan print_sw(Stopwatch sw) { 
            sw.Stop();
            TimeSpan ts = sw.Elapsed;
            Console.WriteLine(ts);
            sw.Reset();
            sw.Start();
            return ts;
        }


        static void Main(string[] args)
        {

            Stopwatch sw = new Stopwatch();

            var write_stream = new System.IO.StreamWriter("./result.txt");
            
            print_sw(sw);
            /*
            write_stream.WriteLine(getindex(0));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getindex(123456));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign(100, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(100, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(1000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(10000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(100000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(1000000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(10000000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(100000000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(1000000000, 10));
            write_stream.WriteLine(print_sw(sw));
            write_stream.WriteLine(getsign_with_bucket(10000000000, 10));
            write_stream.WriteLine(print_sw(sw));
            //*/
            write_stream.WriteLine(getsign_with_bucket(107374182400, 16777216));
            write_stream.WriteLine(print_sw(sw));
            write_stream.Flush();
            Console.ReadLine();
        }
    }
}