上野ゲーセン、コーディング三昧。(TopCoder SRM570、Codeforces Round #167)

今日は某社への用事があり、上野付近に向かいました。

f0019846_21312313.jpg

スカイツリーの実物を見たのは初めて。

お昼は海鮮丼。

f0019846_21315711.jpg


解散後は、アメ横にあるアドアーズに向かいました。
メンテは微妙でしたが、☆10難埋めを13時から17時くらいまでやってました。
大体15クレぐらいでしょうか、人が混みはじめたのでそこでやめました。

地元に戻った後もハード粘着。
Make me your ownが相当酷かった。クリア時のゲージも2%。二度とやらないことを決意した。

帰宅後はTopCoderとCodeforcesに備えて準備。

TopCoderはmedium解きが遅すぎてratingが1195->1124と急降下。

easyは、橋の長さが複数与えられていて、ペアがいくつできるかを解く問題。
ソートして前の情報とかを保持して、一致するならカウントといった具合で解ける。


import java.util.Arrays;

public class Chopsticks {

public int getmax(int[] length) {
Arrays.sort(length);
int count = 0;
int num = -1;
for(int i = 0 ; i < length.length ; i++){
if(num == -1){
num = length[i];
}else if(num == length[i]){
count++;
num = -1;
}else{
num = length[i];
}
}
return count;
}

}


mediumは単純シミュレートで間に合ったのに、何を間違ってしまったのか、
オーダ的に間に合わないと判定して、シミュレートせずにできるプログラムを書いてしまった。
故にこれはlongにすればdiv1 easyでも通ってしまいます。

public class RobotHerbDiv2 {

public int getdist(int T, int[] a) {
int x = 0;
int y = 0;
int arg = 0;
for(int i = 0 ; i < a.length ; i++){
if(arg == 0){
x += a[i];
}else if(arg == 1){
y += a[i];
}else if(arg == 2){
x -= a[i];
}else if(arg == 3){
y -= a[i];
}
arg += a[i];
arg %= 4;
}
if(arg == 0){
return Math.abs(x*T)+Math.abs(y*T);
}else if(arg == 1){
if(T % 4 == 0){
return 0;
}else if(T % 4 == 1){
return Math.abs(x)+Math.abs(y);
}else if(T % 4 == 2){
return Math.abs(x+y)+Math.abs(y-x);
}else if(T % 4 == 3){
return Math.abs(y)+Math.abs(x);
}
}else if(arg == 2){
if(T % 2 == 0){
return 0;
}else{
return Math.abs(x)+Math.abs(y);
}
}else if(arg == 3){
if(T % 4 == 0){
return 0;
}else if(T % 4 == 1){
return Math.abs(x)+Math.abs(y);
}else if(T % 4 == 2){
return Math.abs(x-y)+Math.abs(x+y);
}else if(T % 4 == 3){
return Math.abs(-y)+Math.abs(x);
}
}

return -1;//can't reach here
}

}

ものの見事、これを考えすぎたせいで提出速度に影響してしまい、敗北です。
気を取り直してcodeforcesへ。

Aは出されてる指の合計が、友人の数+自分で割った余りが1にならないような
自分の手がいくつあるかを考える。


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(count(n,a));
}

public static int count(int n,int[] a){
int sum = 0;
for(int i = 0 ; i < n ; i++){
sum += a[i];
}
int count = 0;
for(int i = 1 ; i <= 5 ; i++){
if((sum+i) % (n+1) != 1)count++;
}
return count;
}

}


Bは関数をよく見ると、立っているビットの数で判定が可能。ソートして、
同じ数だけビットが立っている数値をペアとして計算する。

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(count(n,a));
}

public static long count(int n,int[] a){
long count = 0;
int[] bit = new int[n];
for(int i = 0 ; i < a.length ; i++){
bit[i] = Integer.bitCount(a[i]);
}
long same = 1;
Arrays.sort(bit);
int number = bit[0];
for(int i = 1 ; i < a.length ; i++){
if(bit[i] == number){
same++;
}else{
count+=(same*(same-1))/2;
same = 1;
number = bit[i];
}
}
count+=(same*(same-1))/2;
return count;
}

}

Cは階段があって、そこに荷物を積み上げていくという問題。
大事なのは荷物の左端と右端の高さを比較して、
高い方を左端にあらたに加えるだけでよいということ。
それ以上の処理を書くとTLEします。
これは、時間内に解けず、方針を教わりました。

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();
long[] str = new long[n];
for(int i = 0 ; i < n ; i++){
str[i] = input.nextInt();
}
int b = input.nextInt();
int[] w = new int[b];
int[] h = new int[b];
for(int i = 0 ; i < b ; i++){
w[i] = input.nextInt();
h[i] = input.nextInt();
}
count(n,str,b,w,h);
}

public static void count(int n,long[] str,int b,int[] w,int[] h){
for(int i = 0 ; i < b ; i++){
long hei = Math.max(str[0], str[w[i]-1]);
System.out.println(hei);
hei += h[i];
str[0] = hei;
/*for(int j = 0 ; j < w[i] ; j++){
str[j] = hei;
}*/
}
}

}

  by ddrer-yossi | 2013-02-13 23:28 | TopCoder | Comments(0)

<< ☆10上位埋めとか。池袋ラウン... DJT DP八段取得、☆12追加2曲 >>

SEM SKIN - DESIGN by SEM EXE