台湾旅行3日目 ~台湾からCodeforces #195~
パスタとリゾットが美味しいお店でした。
皆で取り皿で分けて食べる方式でいきました。お腹いっぱいです。
137 Cafeというお店です。
その後は近くのアイスを販売しているお店でアイスを皆で食べる。
マンゴーと紫芋が半分ずつ と パイナップル味。
その後は新築したというその友人宅へ。そこの娘さんがチーズケーキを作ってました。
美味しくいただきましたー。
そして夕方には杏仁豆腐シャーベットを食べる。いつものやつー。
夜は鉄板焼きに行きました。大衆的なやつです。
辛めの注文だったのですが、辛すぎでした。ははは…。
その後はハイネケン飲んだり、抹茶ミルクティ飲んだりしつつ、研究して、Codeforces待機。
A問題は、長方形の一点x,y座標が与えられ、そこから垂直、平行に線を引いて長方形を作った時、
その頂点とx,y軸にぶつかる線を引いた時の、二点の座標を求めよという問題。
傾きは-1か1になるので、後は場合分けして座標を求めるだけです。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
if((x > 0 && y > 0) || ( x < 0 && y < 0)){
int b = y+x;
if(x < 0 && y < 0){
System.out.println(b+" "+"0"+" "+0+" "+b);
}else{
System.out.println("0"+" "+b+" "+b+" "+"0");
}
}else{
int b = y-x;
if(x > 0){
System.out.println(0+" "+b+" "+-b+" "+"0");
}else{
System.out.println(-b+" "+"0"+" "+0+" "+b);
}
}
}
}
B問題は、なんかやばそうだったのでパスしました。
C問題は、2^vで割り切れるvをなるべく大きくしたときに、含まれる要素をすべて出力するという問題。
2進数変換して文字数合わせ(0-insert)→ビットを見て、必要な配列の要素数だけ確保→上位ビットから見て、グループ分け→そのグループの数値を全部&演算→そのビット値で割れるかどうかで判断、割れなければ下位ビットに行く。→全部で割れなければ要素全出力-1で解くことができる。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n];
String[] grouping = new String[n];
int maxnum = -1;
for(int i = 0 ; i < n ; i++){
num[i] = sc.nextInt();
maxnum = Math.max(maxnum, num[i]);
grouping[i] = Integer.toBinaryString(num[i]);
}
int maxg = 0;
while(maxnum != 0){
maxnum /= 2;
maxg++;
}
for(int i = 0 ; i < n ; i++){
if(grouping[i].length() != maxg){
StringBuilder sb = new StringBuilder();
for(int j = 0 ; j < maxg-grouping[i].length(); j++){
sb.append("0");
}
grouping[i] = sb.toString()+grouping[i];
}
}
int[] gc = new int[maxg];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < maxg ; j++){
if(grouping[i].charAt(j) =='1')gc[j]++;
}
}
boolean isok = false;
for(int i = 0 ; i < maxg ; i++){
if(gc[i] == 0)continue;
int[] grouper = new int[gc[i]];
int index = 0;
for(int j = 0 ; j < n ; j++){
if(grouping[j].charAt(i) == '1'){
grouper[index] = num[j];
//System.out.println(maxg+","+grouper[index]);
index++;
}
}
Arrays.sort(grouper);
int st = grouper[grouper.length-1];
for(int j = grouper.length-2 ; j >= 0 ; j--){
st &= grouper[j];
}
if(st % Math.pow(2, maxg-1-i) == 0){
isok = true;
System.out.println(grouper.length);
for(int j = 0; j < grouper.length ; j++){
if(j != grouper.length-1){
System.out.print(grouper[j]+" ");
}else{
System.out.println(grouper[j]);
}
}
break;
}
}
if(!isok){
System.out.println(n);
for(int j = 0; j < num.length ; j++){
if(j != num.length-1){
System.out.print(num[j]+" ");
}else{
System.out.println(num[j]);
}
}
}
}
}
C問題は時間ないAcceptできなかったので散々な結果に終わりました。
by ddrer-yossi | 2013-08-09 23:03 | 台湾へ赴く