ゲーセンに蔓延りし・・・。 Codeforces Round #179
なんか終始向こうのペースでした・・・。
お昼は時間があるので、少々ゲーセンへ。
ことみちゃん難ついた。
皿で切れてたけどようやく。
メンメルついた!!
その後は一旦某所へ向かい、GW。
これもやっていて楽しくなかったです。
終了後は再度ゲーセンへ。はびこっている。
maimaiとビーマニが中心でした。
帰宅後はcodeforces #179に参戦。
A問題は、隣接する配列が同じ値にならないようにできるかどうかという問題。
全体が偶数の場合は一番多い値が半数より多いとできない、
奇数の場合は半数+1より多いとできない。
import java.util.Arrays;
import java.util.Scanner;
public class Main2 {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] a = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = input.nextInt();
}
System.out.println(array(n,a));
}
public static String array(int n,int[] a){
int[] arrays = new int[1000];
for(int i = 0 ; i < n ; i++){
arrays[a[i]-1]++;
}
Arrays.sort(arrays);
int max = arrays[999];
if(n % 2 == 0){
if(n/2 < max){
return "NO";
}else{
return "YES";
}
}else{
if((n+1)/2 < max){
return "NO";
}else{
return "YES";
}
}
}
}
B問題は、見るからに面倒そうな組み合わせの計算だったのでパス。
C問題は、AからBまでの要素にC足すという命令がM個与えられていて、
DからEまでの合計を加えるという命令がN個与えられていて、合計値を求めよという問題。
いもす法と呼ばれる累乗和を取る方法を何度も駆使すれば解ける。
import java.util.Scanner;
public class Main2 {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int k = input.nextInt();
long[] a = new long[n];
for(int i = 0 ; i < n ; i++){
a[i] = input.nextLong();
}
int[] st = new int[m];
int[] en = new int[m];
int[] add = new int[m];
for(int i = 0 ; i < m ; i++){
st[i] = input.nextInt();
en[i] = input.nextInt();
add[i] = input.nextInt();
}
int[] sumop = new int[m+1];
for(int i = 0 ; i < k ; i++){
int kst = input.nextInt();
int ken = input.nextInt();
sumop[kst-1]++;
sumop[ken]--;
}
long sum = 0;
long[] a2 = new long[n+1];
for(int i = 0 ; i < sumop.length-1 ; i++){
sum += sumop[i];
a2[st[i]-1] += add[i]*sum;
a2[en[i]] -= add[i]*sum;
}
long sum2 = 0;
for(int i = 0 ; i < a.length ; i++){
sum2 += a2[i];
if(i != a.length-1){
System.out.print(sum2+a[i]+" ");
}else{
System.out.println(sum2+a[i]);
}
}
}
}
by ddrer-yossi | 2013-04-11 23:54 | codeforces