上野ゲーセン、コーディング三昧。(TopCoder SRM570、Codeforces Round #167)
スカイツリーの実物を見たのは初めて。
お昼は海鮮丼。
解散後は、アメ横にあるアドアーズに向かいました。
メンテは微妙でしたが、☆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