学内プロコン(15/03/11)

procon.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;
using System.Net;

namespace Procon
{
    class Program
    {
        // ref: https://gist.github.com/hanoia/b9784a3cdfe546b1cad2
        // ref: http://paralleltree.hatenablog.com/entry/2015/03/11/204145
        static void Main(string[] args)
        {
            string targeturl = @"http://localhost/procon/hard/{0}.txt";
            int count = 100;
            var wc = new WebClient() { Encoding = Encoding.UTF8 };
            var arr = new string[count];
            for (int i = 0; i < count; i++)
            {
                Console.WriteLine("Receiving... {0} of {1}", i, count);
                arr[i] = wc.DownloadString(string.Format(targeturl, i + 1)).Trim();
            }

            Console.Write("Calc... ");
            string ans = CalcSum(arr);
            Console.WriteLine("done! -> {0}", ans);

            Console.Write("Sending...");
            var values = new System.Collections.Specialized.NameValueCollection();
            values.Add("token", "unique_token");
            values.Add("num", ans);
            wc.UploadValues(@"http://localhost/procon/post.php", values);
            Console.WriteLine("done!");

            Console.ReadLine();
        }

        static string CalcSum(string[] input)
        {
            // 200桁まで
            var digits = new int[200];
            for (int i = 0; i < input.Length; i++)
            {
                int len = input[i].Length;
                for (int j = 0; j < len; j++)
                {
                    digits[len - j - 1] += int.Parse(input[i].Substring(j, 1));
                }
            }

            // 1の位から解答生成
            var sb = new StringBuilder(200);
            for (int i = 0; i < digits.Length; i++)
            {
                // 現在の桁における総和
                string now = digits[i].ToString();
                sb.Insert(0, now.Substring(now.Length - 1, 1));

                if (now.Length > 1)
                {
                    // 繰り上がりを1桁ずつ足す
                    for (int j = now.Length - 2; j >= 0; j--)
                    {
                        digits[i + (now.Length - j - 1)] += int.Parse(now.Substring(j, 1));
                    }
                }
            }

            // 文字列として有効な範囲を取り出す
            string ans = string.Concat(sb.ToString().SkipWhile(p => p == '0'));
            return ans.Length == 0 ? "0" : ans;
        }

        // 雑テスト
        static bool Test()
        {
            CalcSum(new string[] { "0" }); // -> "0"

            var rnd = new Random();
            var cases = Enumerable.Range(0, 30)
                .Select(p =>
                    Enumerable.Range(0, 600)
                        .Select(q => rnd.Next(0, 100000).ToString())
                        .ToArray());

            foreach (var test in cases)
            {
                string expected = test.Sum(p => int.Parse(p)).ToString();
                string result = CalcSum(test);
                Console.WriteLine("expected: {0}, result: {1}", expected, result);
                if (expected != result)
                {
                    return false;
                }
            }

            return true;
        }
    }
}