結果

問題 No.33 アメーバがたくさん
ユーザー 14番14番
提出日時 2016-05-29 16:57:47
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 3,905 bytes
コンパイル時間 974 ms
コンパイル使用メモリ 112,984 KB
実行使用メモリ 25,420 KB
最終ジャッジ日時 2023-10-24 20:18:12
合計ジャッジ時間 1,724 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
25,404 KB
testcase_01 AC 30 ms
25,404 KB
testcase_02 AC 30 ms
25,404 KB
testcase_03 AC 30 ms
25,404 KB
testcase_04 AC 29 ms
25,412 KB
testcase_05 AC 29 ms
25,412 KB
testcase_06 AC 30 ms
25,416 KB
testcase_07 AC 30 ms
25,416 KB
testcase_08 AC 30 ms
25,416 KB
testcase_09 AC 30 ms
25,420 KB
testcase_10 AC 26 ms
25,300 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        long[] inpt = Reader.ReadLine().Split(' ').Select(a=>long.Parse(a)).ToArray();
        int amebaCount = (int)inpt[0];
        Ameba.Diff =  inpt[1];
        long jikan = inpt[2];
        inpt = Reader.ReadLine().Split(' ').Select(a=>long.Parse(a)).ToArray();
        List<Ameba> list = new List<Ameba>();
        for(int i=0; i<amebaCount; i++) {
            Ameba amb = new Ameba(inpt[i]);
            amb.JikanKeika(jikan);
            list.Add(amb);
        }
        
        list.Sort((a,b)=>{
           if(a.First < b.First) {
               return -1;
           } else if(a.First> b.First) {
               return 1;
           }
           return 0;
        });
        
        while (list.Count > 1)
        {
            bool marged = false;
            int last = list.Count;
            for(int i=0; i<last; i++) {
                Ameba[] target = list.Where(a=>list[i].CanMarge(a)).ToArray();
                if(target.Length > 1) {
                    Ameba mg = new Ameba(list[i].First, list[i].Last);
                    Ameba src = list[i];
                    target.ToList().ForEach(a=>mg = mg.Marget(a));
                    list.RemoveAll(a=>src.CanMarge(a));
                    list.Insert(i, mg);
                    marged = true;
                    break;
                }
            }
            if(!marged) {
                break;
            }
        }
        long ans = 0;
        list.ForEach(a=>ans+=a.Count());
        Console.WriteLine(ans);
    }

    public class Ameba {
        public long First;
        public long Last;
        
        public static long Diff;
        
        public Ameba(long pos) {
            this.First = pos;
            this.Last = pos;
        }
        
        public Ameba(long first, long last) {
            this.First = first;
            this.Last = last;
        }
        
        public Ameba Marget(Ameba target) {
            Ameba mg = new Ameba(Math.Min(this.First,target.First), Math.Max(this.Last, target.Last));
            return mg;
        }
        
        public long Count() {
            return (this.Last - this.First) / Diff + 1;
        }
        
        public void JikanKeika(long num) {
            this.First = this.First - (num * Diff);
            this.Last = this.Last + (num * Diff);
        }
        
        public bool CanMarge(Ameba target) {
            Ameba saki;
            Ameba ato;
            if(this.First < target.First) {
                saki = this;
                ato = target;
            } else if(this.First > target.First)
            {
                saki = target;
                ato = this;
            } else
            {
                return true;
            }
            
            if((ato.First - saki.First) % Diff > 0) {
                return false;
            }
            
            if(ato.First <= saki.Last) {
                return true;
            }
            if(ato.First - saki.Last == Diff) {
                return true;
            }
            return false;
        }
    }

    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"



4 2 3
0 10 12 24



";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0