TopCoder SRM566
帰宅前のゲーセン。
lower worldノマゲ。これは結構難しい。
FEEL ITも。
スクスカついたー。
その後は2011年のクソゲーオブザイヤーなどを見て楽しんだりしていたが、
夕方から本を買うために本屋へ。
その後は再度ゲーセンに寄る。
自分が引いたすぐ後にWii U当てられてたけど気にしちゃいけない。
ブルーミンフルコン。なかなかめんどくさいコンテンツ。
帰宅後は、CodeforcesのJavaのテストラウンドに出た。Java7?
A問題は、単純にa,bの数が与えられていて、大きい方から小さい方を引くという動作を
何回できるかという問題。シミュレーションでok。
import java.util.ArrayList;
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();
for(int i = 0 ; i < n ; i++){
int a = input.nextInt();
int b = input.nextInt();
System.out.println(str(a,b));
}
}
static int str(int a,int b){
int count = 0;
while(true){
if(a == b)return count+1;
if(a > b){
int num = ((a-b)/b)+1;
count += num;
a -= num*b;
}else{
int num = ((b-a)/a)+1;
count += num;
b -= num*a;
}
if(a == 0 || b == 0)return count;
if(a < 0 || b < 0)return count-1;
}
}
}
B問題は意味がわからずやめる。
後はTopCoder SRM566に参戦。
div2 easyは、右下が空いている状態にするパズルがあり、
列、行単位で動かせる。何回動かす必要があるかという問題。
空いている列が、右下と同じ列、もしくは行が右下と同じ行なら1回で可能。
それ以外なら2回かかるというのを書けばいいだけ。
public class PenguinTiles {
public int minMoves(String[] tiles) {
int wid = tiles[0].length()-1;
int hei = tiles.length-1;
int x = 0;
int y = 0;
for(int i = 0 ; i < tiles.length ; i++){
for(int j = 0 ; j < tiles[i].length(); j++){
if(tiles[i].charAt(j) == '.'){
x = j;
y = i;
}
}
}
int count = 0;
if(wid != x)count++;
if(hei != y)count++;
return count;
}
}
medは、青ペンギンと赤ペンギンが環状に並んでいて、
線が交差しないように繋げられる線の最大値を求めるという問題。
hardは、オリの点の数、半径が与えられていて、ペンギンを囲う面積の最小値を答える問題。
方針としてはおそらく、
まず正多角形の頂点のそれぞれの座標を求める(これを求めるのに25分かかるという失敗)→ある座標からスタート(for文全部の座標をなめる)して、時計回りして直線上より上回る位置にペンギンがいればその前の頂点に戻り、面積を求める。
面積が三角形にならない場合は成立しないので次のある座標からスタートをやる。成立した場合は合計した面積を求めて、最小となる面積となる場合の値を返す。
ちなみに時間内にできた人は1人もいませんでした。
by ddrer-yossi | 2013-01-12 23:40 | TopCoder