2938 Economic Phone Calls
2938 -- Economic Phone Calls
今日も練習会だったわけですが、もっと努力が必要だと痛感しました。
とりあえず、2938の電話記録を通しておきました。
Javaで一人目。
書き直したところ、O(n^2)でも普通に通ってしまいました。
一つ一つの記録を残さなかったときに年の問題がでるかどうかをチェックし、
問題なければその記録を残さないようにしています。
import java.util.*; class Main { public static void main(String[] argv) { Scanner sc = new Scanner(System.in); while(true){ int T = sc.nextInt(); if(T==0)break; int prev = 0; int year = 0; int[]dates = new int[T]; // 通話日時 int[]years = new int[T]; // 記録ごとの年を保持 boolean[]keeps = new boolean[T]; // '+'かどうか boolean[]needs = new boolean[T]; // 保持する必要があるかどうか // データの読み込み for(int t=0; t<T;t++) { String str = sc.next(); String[] tmp = str.split(":"); int value = new Integer(tmp[0])*1000000+new Integer(tmp[1])*10000+new Integer(tmp[2])*100+new Integer(tmp[3]); str = sc.next(); str = sc.next(); if(prev>=value) year++; years[t] = year; dates[t] = value; keeps[t] = str.charAt(0)=='+'; needs[t] = true; prev = value; } // 各データがなくても問題ないかどうか調べる for(int t=0; t<T; t++) { if(keeps[t])continue; // 記憶する必要があればスルー needs[t] = false; boolean check = true; int p = 0; int y = 0; for(int i=0; i<T; i++) { if(!needs[i])continue; if(p>=dates[i]) y++; if(years[i]!=y) { check = false; break; } p=dates[i]; } if(!check||y!=years[T-1]) { needs[t] = true; } } int c = 0; int first = -1; // 先頭から連続する記録する必要のない記録はないものとする for(int i=0; i<T; i++) { if(first<0) { if(keeps[i]) { first = i; c = 1; } } else if(needs[i]){ c++; } } System.out.println(c); } } }