はじめに
今回は初の5完でしたので、Eまで載せようと思います。
では、見ていきましょう。
A - Anyway Takahashi
問題文はこちら
問題文そのままですね。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//各値の受け取り
int a = System.in.nextInt();
int b = System.in.nextInt();
int c = System.in.nextInt();
int d = System.in.nextInt();
//計算結果の出力
System.out.println((a+b)*(c-d));
//Takahashiの出力
System.out.println("Takahashi");
System.out.close();
}
}
高橋君･･･。
B - Rectangle Detection
問題文はこちら
Cの場所を全探索してから芋づる的にD、A、Bの場所を探しました。
二重for文で#の始まりを探し、Cを決定したらDを探し、Dが決定したらforを一つだけ抜けてA、Bを探しました。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Sの受け取り
char[][] S = System.in.nextCharArray(10);
//各変数の初期化
int A=0,B=0,C=0,D=0;
//Cの場所の探索
for(int i=0;i<10;i++){
int temp = -1;
for(int j=0;j<10;j++){
//Cの場所を見つけた？
if(S[i][j]=='#'){
temp = j;
C = D = j+1;
//Dを探す
while(D<10&&S[i][D]=='#')D++;
break;
}
}
//Cが見つかった？
if(temp!=-1){
A = B = i+1;
//Bを探す
while(B<10&&S[B][temp]=='#')B++;
break;
}
}
//答えの出力
System.out.println(A+" "+B);
System.out.println(C+" "+D);
System.out.close();
}
}
最初バグらせてちょっと余計なことしちゃったなぁ･･･って感じでした。ペナルティが重い･･･。
C - Submask
問題文はこちら
bit全探索みたいに解きました。
まず、1の箇所を下から順に探してArrayListに加えていきます。後はbit全探索の要領で解けば良いです。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
long N = System.in.nextLong();
//1の箇所を記録するリスト
ArrayList<Integer> list = new ArrayList<Integer>();
//各位を調べる
int temp = 0;
while(temp<60){
if((N&(1L<<temp))!=0)
list.add(temp);
temp++;
}
//bit全探索
for(int i=0;i<(1<<list.size());i++){
long tmp = 0;
int num = 1,index = 0;
//iを元に値を構成
while(num<1<<list.size()){
if((i&num)!=0)
tmp += 1L<<list.get(index);
num <<= 1;
index++;
}
//出力
System.out.println(tmp);
}
System.out.close();
}
}
公式解説の解法2に近い解答ですが、解法1の方がとてもわかりやすいんじゃないかなぁと個人的には思います。
D - Do use hexagon grid
問題文はこちら
再帰DFSで解きました。
boolean型配列ですでに調べたかどうかを管理しておき、まだ調べていないマスがあれば答えに1加算してDFSで隣接しているマスを全てtrueにすることで、隣接しているマスを除くことができます。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、黒く塗られた箇所の受け取り
int N = System.in.nextInt();
int[][] list = System.in.nextInt(N,2);
//確認済みか管理する配列
boolean[] checked = new boolean[N];
//答えを数える変数
int answer = 0;
for(int i=0;i<N;i++){
//すでにDFSで探索済みならスキップ
if(checked[i])
continue;
//dfsで連結している箇所を全てtrueに
checked[i] = true;
dfs(i,list,checked);
//新しい連結成分として加算
answer++;
}
//答えの出力
System.out.println(answer);
System.out.close();
}
//DFS
public static void dfs(int now,int[][] list,boolean[] checked){
//今の座標を記録
int x = list[now][0];
int y = list[now][1];
//全探索
for(int i=0;i<list.length;i++){
//すでに調べたならスキップ
if(checked[i])
continue;
//差を求める
int subx = list[i][0]-x;
int suby = list[i][1]-y;
//隣接条件に合うならtrueにしてdfs
if(subx==-1&&(suby==-1||suby==0)){
checked[i] = true;
dfs(i,list,checked);
}else if(subx==0&&(suby==-1||suby==1)){
checked[i] = true;
dfs(i,list,checked);
}else if(subx==1&&(suby==0||suby==1)){
checked[i] = true;
dfs(i,list,checked);
}
}
}
}
比較的易しいかなと感じました。
E - Last Rook
問題文はこちら
二分探索で解きました。
a=1、b=N、c=(a+b)/2として、? 1 N a cを出力し、返ってきた値ansがc-a+1未満だったらa=c+1、違うならb=c-1と更新しながらルークが置ける場所を探しました(? a c 1 Nの時も同様です)。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = System.in.nextInt();
//各変数初期化
int aX = 1;
int bX = N;
int aY = 1;
int bY = N;
int X = 1,Y = 1;
//x座標の二分探索
while(aX-bX<=0){
int c = (aX+bX)/2;
System.out.println("? "+X+" "+c+" "+1+" "+N);
System.out.flush();
int ans = System.in.nextInt();
//上記の通りに値更新
if(ans<c-X+1)
bX = c-1;
else
aX = X = c+1;
}
//yも同様に
while(aY-bY<=0){
int c = (aY+bY)/2;
System.out.println("? "+1+" "+N+" "+Y+" "+c);
System.out.flush();
int ans = System.in.nextInt();
if(ans<c-Y+1)
bY = c-1;
else
aY = Y = c+1;
}
//答えの出力
System.out.println("! "+X+" "+Y);
System.out.close();
}
}
最初!を出力し忘れてペナルティを頂いてしまいました･･･悔しい･･･。
感想
A:易しい(Takahashiの意味は･･･？)
B:ちょっとバグらせてしまった･･･。
C:ちょっと身構えてしまったが、そこまで難しくはなかった。いろいろ解法があるそう。
D:そんな難しくはなかったが、実装に時間をかけすぎてしまった。
E:制約と「質問を20回まで行うことができます」から二分探索では？って思えた。良かった･･･。
って感じでした。
実装バグらせたり解法がなかなか思いつかなかったりで、そんなにパフォーマンスは大きくなかったです。悔しい･･･。