#84095 (C#(csc)) No.14 最小公倍数ソート

• 問題: No.14 最小公倍数ソート
• ユーザー: 14番
• 提出日時: 2016-03-31 11:41:02
• 言語: C#(csc) (csc 3.9.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,657 bytes
• コンパイル時間: 1,012 ms
• コンパイル使用メモリ: 115,960 KB
• 実行使用メモリ: 43,364 KB
• 最終ジャッジ日時: 2024-10-02 08:23:14
• 合計ジャッジ時間: 8,236 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
other	AC * 4 TLE * 1 -- * 15

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public void Proc() {
        Reader.IsDebug = false;
        this.SetPrimeNumberList();
        int numCount = int.Parse(Reader.ReadLine());
        int[] intArr = Reader.GetInt();
        List<ItemNumber> numList = new List<ItemNumber>();
        foreach (int num in intArr)
        {
            numList.Add(new ItemNumber(num));
        }

        List<ItemNumber> ansList = new List<ItemNumber>();
        ansList.Add(numList[0]);
        numList.RemoveAt(0);
        ItemNumber target = ansList[0];
        for(int i=1; i<numCount; i++) {
            int minKoubai = int.MaxValue;
            int minIdx = 0;
            int minBaseNum = int.MaxValue;
            for(int j=0; j<numList.Count; j++) {
                int tmp = target.GetKoubaisu(numList[j]);
                if(minKoubai > tmp || (minKoubai == tmp && numList[j].Value < minBaseNum)) {
                    minIdx = j;
                    minKoubai = tmp;
                    minBaseNum = numList[j].Value;
                }
            }
            ansList.Add(numList[minIdx]);
            numList.RemoveAt(minIdx);
            target = ansList[ansList.Count - 1];
        }
        StringBuilder ans = new StringBuilder();
        foreach (ItemNumber item in ansList)
        {
            if(ans.Length > 0) {
                ans.Append(" ");
            }
            ans.Append(item.Value);
        }
        Console.WriteLine(ans.ToString());
    }
    
    private void SetPrimeNumberList() {
        int maxNum = 10000;
        bool[] flag = new bool[maxNum + 1];
        ItemNumber.PrimeNumberList = new List<int>();
        for(int i=2; i<=maxNum; i++) {
            if(!flag[i]) {
                ItemNumber.PrimeNumberList.Add(i);
                int maxIdx = maxNum / i;
                for(int j=1; j<maxIdx; j++) {
                    flag[j*i] = true;
                }
            }
        }
    }
    
    public class ItemNumber {
        public static List<int> PrimeNumberList;
        public int Value = 0;
        public Dictionary<int, int> Soinsu = new Dictionary<int, int>();
        
        public ItemNumber(int num) {
            this.Value = num;
            int tmp = num;
            while (tmp > 1)
            {
                for(int i=0; i<PrimeNumberList.Count; i++) {
                    if(tmp % PrimeNumberList[i] == 0) {
                        if(Soinsu.ContainsKey(PrimeNumberList[i])) {
                            this.Soinsu[PrimeNumberList[i]]++;
                        } else
                        {
                            Soinsu.Add(PrimeNumberList[i], 1);
                        }
                        tmp = tmp / PrimeNumberList[i];
                        break;
                    }
                }
            }
        }
        public int GetKoubaisu(ItemNumber target) {
            Dictionary<int, int> tmp = new Dictionary<int, int>();
            Dictionary<int, int>[] dicList = new Dictionary<int, int>[] {this.Soinsu, target.Soinsu};
            foreach (Dictionary<int, int> dic in dicList)
            {
                foreach (int key in dic.Keys)
                {
                    if(tmp.ContainsKey(key)) {
                        tmp[key] = Math.Max(dic[key], tmp[key]);
                    } else {
                        tmp.Add(key, dic[key]);
                    }
                }
            }
            int ans = 1;
            foreach (int key in tmp.Keys)
            {
                for(int i=1; i<= tmp[key]; i++) {
                    ans *= key;
                }
            }
            return ans;
        }
    }

    public class Reader {
        private static String InitText = @"

5
1 2 3 4 5


        ";
        
        private static System.IO.StringReader sr = null;
        
        public static bool IsDebug = true;
        
        public static string ReadLine() {
            if(IsDebug) {
                if(sr == null) {
                    sr = new System.IO.StringReader(InitText.Trim());
                }
                return sr.ReadLine();
            } else {
                return Console.ReadLine();
            }
        }
        public static int[] GetInt(char delimiter = ' ') {
            string[] inpt = ReadLine().Split(delimiter);
            int[] ret = new int[inpt.Length];
            for(int i=0; i<inpt.Length; i++) {
                ret[i] = int.Parse(inpt[i]);
            }
            return ret;
        }
    }
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}