Codeforces#194とTopCoder SRM 586

CodeforcesをRegisterしておいて、昼過ぎにゲーセンへ。

みんなで宇宙戦争の張り紙がしてありました。
f0019846_3224338.jpg


f0019846_3202662.jpg

Go Beyond(A)のミスがかなり減った。

f0019846_3204927.jpg

Click Again(H)フルコン

f0019846_3212340.jpg

天庭銅◆

f0019846_3215853.jpg

トイコン(H)銅★

f0019846_323655.jpg

DEAD LOCK 86.9%

f0019846_3233420.jpg

文明開化銅★。これはかなりうまくいった。

帰宅後はCodeforcesへ。

A問題は、N^2個のバッグを買った。
バッグの中には1,2,3..N^2個のキャンディが入っている。
これを同じ数だけ分け与えるような数を出力せよという問題。
Nは偶数である。

やり方は色々あるが、単純に一番左と一番右を足しあわせたものは、
2番目左と2番目右と等しくなるというのを利用して、
n/2までを弟、それ以降を兄のようにすればよい。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 16 2 15 3 14 4 13
5 12 6 11 7 10 8 9 といった具合である。


import java.util.Scanner;



public class Main2 {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = n*n;
StringBuilder sb = new StringBuilder();
int count = 0;
for(int i = 1; i <= max/2 ; i++){
if(count == (n/2)){
System.out.println(sb.substring(0,sb.length()));
sb = new StringBuilder();
count = 0;
i--;
}else{
sb.append(i+" "+(max-(i-1))+" ");
count++;
}
}
System.out.println(sb.substring(0,sb.length()));
}
}


B問題は、x1 x1,y1 x1,y2 x1,y3 x2,y1 x2,y3 x3,y1 x3,y2 x3,y3となっているかを調べる問題。
通らなかったので書きません。

C問題は、1,3,9...27...という硬貨しかないときに、
ちょうどN支払えないときの最大枚数を求めよという問題。
たとえば15の時は、9+9が最悪ケースとなる。
これ以外で3を使ったケースや1を使ったケースを書こうとしても、うまくいかない。
9+3+3であれば丁度ですし、9+9+3であれば9+9で払えば良い。
14の時は、3+3+3+3+3が最悪ケースとなる。
nが3のべき乗で割れなくなる額の金貨でnを割って、+1すれば良い。
これに気づくのが大変ですが…。

import java.util.Scanner;



public class Main2 {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
long l = input.nextLong();
if(l % 3 != 0){
System.out.println(l/3+1);
}else{
int count = 0;
long num = l;
while(num / 3 != 0){
num /= 3;
count++;
}
boolean isstack = false;
long number = 1;
for(int i = 1 ; i <= count ; i++){
number = 1;
for(int j = 1 ; j <= i ; j++){
number *= 3;
}
if(l % number != 0){
isstack = true;
break;
}
}
if(!isstack){
System.out.println(1);
}else{
System.out.println((l/number)+1);
}
}
}
}


D問題は、n*nの碁盤で、m個のマスが使えない状態で、四隅以外の端に碁盤を置いて、
対岸に行くまで毎ターン1つずつ動かす。使えないマスに入ってしまったらダメなとき、
置ける最大個数を求めよという問題。



夜は雨が降っていて隅田川花火大会が中止になっていました。
f0019846_14314261.jpg


夜はブレインワールドカップを観ていました。
なんだかんだそれなりに解けたような。
東京大学が優勝してましたね。

その後はSRM586。

easyは、2チームのキャプテンがいて、
それぞれ強いと感じる人の番号を配列0から与えている時、
チーム分けがどうなるか出力せよという問題。

単純に配列の左から交互に調べて行って、まだ使われていない数字を配列に格納し、
最後にその配列を出力する。


public class TeamsSelection {

public String simulate(int[] preference1, int[] preference2) {
int n = preference1.length;
StringBuilder sb = new StringBuilder();
int count = 0;
int[] chosed = new int[n];
while(count != n){
if(count % 2 == 0){
for(int i = 0 ; i < n ; i++){
if(chosed[preference1[i]-1] == 0){
chosed[preference1[i]-1] = 1;
break;
}
}
}else{
for(int i = 0 ; i < n ; i++){
if(chosed[preference2[i]-1] == 0){
chosed[preference2[i]-1] = 2;
break;
}
}
}
count++;
}
for(int i = 0 ; i < n ; i++){
if(chosed[i] == 1){
sb.append("1");
}else{
sb.append("2");
}
}
return sb.toString();
}

}


mediumは、N個の頂点が1,y1 2,y2 3,y3 ... N,yNと与えられ、
それぞれを線分で繋いだ時、
y = aに対応するxがいくつあるかをそれぞれ出力する。

クエリに対してそれぞれ頂点を調べて、その範囲内であるかどうかでカウントすればよいだけ。


public int[] countSolutions(int[] Y, int[] query) {
int[] answer = new int[query.length];
for(int i = 0 ; i < query.length ; i++){
int count = 0;
boolean choten = false;
for(int j = 0 ; j < Y.length-1 ; j++){
if(Y[j] == Y[j+1] && query[i] == Y[j]){
count = Integer.MAX_VALUE;
break;
}else if((Y[j] <= query[i] && query[i] <= Y[j+1]) || Y[j+1] <= query[i] && query[i] <= Y[j]){
if(!choten){
if(Y[j+1] == query[i])choten = true;
count++;
}else{
choten = false;
}
}else{
choten = false;
}
}
if(count == Integer.MAX_VALUE){
answer[i] = -1;
}else{
answer[i] = count;
}
}
return answer;
}

}


hardは、左端のアルファベットから右端のアルファベットの距離の総和を重みとするとき、
文字の長さLが与えられた時重みが最小となる通りは何通りあるか計算せよという問題。
数が多くなるので1,000,000,009で割ってくださいというのもついている。

たとえば2文字であれば
AB...AZ...~..ZA ... ZYで26*25 = 650となる。

  by ddrer-yossi | 2013-07-27 23:17 | TopCoder | Comments(0)

<< 夕方からゲーセン、友人と合流。... 研究後ゲーセン。 >>

SEM SKIN - DESIGN by SEM EXE