結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー 明智重蔵
提出日時 2015-09-12 10:47:17
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 46 ms / 5,000 ms
コード長 4,546 bytes
コンパイル時間 3,629 ms
コンパイル使用メモリ 108,672 KB
実行使用メモリ 22,784 KB
最終ジャッジ日時 2024-09-16 16:29:32
合計ジャッジ時間 3,390 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input3";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1");
            WillReturn.Add("11");
            //3
            //まず[1,11] の中に含まれる素数列は 2,3,5,7,11 である
            //Frankのハッシュアルゴリズムを適用すると 2,3,5,7,2 となる
            // ここでコリジョンが起こらない(値が重ならない）
            //最大の長さの素数列を取り出すと2,3,5,7と3,5,7,11 となる。
            //数が大きい方を選択するので素数列の最初は3となる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("100");
            //31
            //[10,100] の素数列を考えると以下の長さが最高となる
            //31,37,41,43,47,53→4,1,5,7,2,8
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    //No.6 使いものにならないハッシュ
    static void Main()
    {
        List<string> InputList = GetInputList();
        int K = int.Parse(InputList[0]);
        int N = int.Parse(InputList[1]);

        Eratosthenes(N);

        //素数情報のListを作成
        List<SosuuInfoDef> SosuuInfoList = DeriveSosuuInfoList(K, N);

        //しゃくとり法を使う
        int UB = SosuuInfoList.Count - 1;
        //開始素数の最大値[長さ]なDict
        var AnswerDict = new Dictionary<int, int>();

        int L = 0;
        for (int R = 0; R <= UB; R++) {
            int CurrHashVal = SosuuInfoList[R].HashVal;

            //再登場のハッシュ値の場合
            int wkInd = SosuuInfoList.FindIndex(L, R - L, X => X.HashVal == CurrHashVal);

            if (wkInd >= 0) {
                L = wkInd + 1;

                //下限値枝切り
                int RestMaxCnt = UB - L + 1;
                if (RestMaxCnt < AnswerDict.Keys.Max()) break;
            }

            AnswerDict[R - L + 1] = SosuuInfoList[L].SosuuVal;
        }
        //foreach (var EachPair in AnswerDict) {
        //    Console.WriteLine("AnswerDict[{0}]={1}", EachPair.Key, EachPair.Value);
        //}
        var Tmp = AnswerDict.OrderByDescending(X => X.Key).ThenByDescending(X => X.Value);
        Console.WriteLine(Tmp.First().Value);
    }

    struct SosuuInfoDef
    {
        internal int SosuuVal;
        internal int HashVal;
    }

    //素数情報のListを作成
    static List<SosuuInfoDef> DeriveSosuuInfoList(int pK, int pN)
    {
        var WillReturn = new List<SosuuInfoDef>();
        foreach (int EachInt in SosuuArr) {
            if (EachInt < pK) continue;
            if (EachInt > pN) break;
            SosuuInfoDef WillAdd;
            WillAdd.SosuuVal = EachInt;
            WillAdd.HashVal = DeriveHashVal(EachInt);
            WillReturn.Add(WillAdd);
        }

        //foreach (SosuuInfoDef EachSosuuInfo in WillReturn) {
        //    Console.WriteLine("{0}のハッシュ値={1}",
        //        EachSosuuInfo.SosuuVal, EachSosuuInfo.HashVal);
        //}
        return WillReturn;
    }

    static int[] SosuuArr;

    //エラトステネスの篩
    static void Eratosthenes(int pJyougen)
    {
        var CheckArr = new System.Collections.BitArray(pJyougen + 1);
        for (int I = 2; I <= CheckArr.Count - 1; I++) {
            CheckArr[I] = true;
        }
        for (int I = 2; I <= CheckArr.Count - 1; I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (CheckArr[I]) {
                for (int J = I * 2; J <= CheckArr.Count - 1; J += I) {
                    CheckArr[J] = false;
                }
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= CheckArr.Count - 1; I++)
            if (CheckArr[I]) SosuuList.Add(I);

        SosuuArr = SosuuList.ToArray();
    }

    //ハッシュ値を求める
    static int DeriveHashVal(int pTarget)
    {
        int CurrHashVal = pTarget;
        while (CurrHashVal >= 10) {
            int CopiedVal = CurrHashVal;
            CurrHashVal = 0;
            while (CopiedVal > 0) {
                CurrHashVal += CopiedVal % 10;
                CopiedVal /= 10;
            }
        }
        return CurrHashVal;
    }
}
0