Javaの練習にABC#002を解いてみました
どうも、6日ぶりの更新になります。
最近は英語の方に注力してしまっていて、なかなかプログラミングができませんでした。
しかし、3月1日にAtcoderのレギュラーコンテストが開催されるようなので、それに向けて励んでいこうと思います。
今日はABC002を解いてみました。ABCはビギナーコンテストというだけあって、問題の幅が広く、私のような初心者の練習には丁度いい！
開催側で解説も用意されているので、非常に助かっております。
競技プログラミング初心者の方にはおすすめです。
まずは問題のリンク
Tasks - AtCoder Beginner Contest #002 | AtCoder
今回も1～2番はかなり簡単な問題、3番は少し考えさせる問題、そして4番はなかなか解き応えのある問題というような構成でした。
ということで今回は4番の問題だけ取り扱おうと思います。
D: 派閥 - AtCoder Beginner Contest #002 | AtCoder
これは全探索を使って解きました。(解説を見るまでは、意味の分からないアルゴリズムで撃沈していたのは秘密)
Nが最大12なので、全ての派閥の組み合わせを探索したとしても最大でも2^12＝4096通りです。この程度の数なら全探索で余裕です。(解説の受け売りです)
AtCoder Beginner Contest 002 解説
全探索のパターンの調べ方としては、上の解説の14ページの方法を使いました。
それに伴い、探索方法はビット演算を用いたものになっています。
ビット演算をプログラムで行ったのは初めてだったのでなかなか苦戦しました。
今回知らなかったことをメモとしておいておきます。
シフト演算記号
1 >> N ←1をNビットだけ右シフト
1 << N ←1をNビットだけ左シフト
& ← AND演算子
ではソースを置いておきます。
import java.util.Scanner;
public class Main4 {
public static void main(String args){
Scanner stdin = new Scanner(System.in);
int N = stdin.nextInt();
int M = stdin.nextInt();
boolean[] lis = new boolean[N][N];
for(int i=0; i<M; i++){
int a = stdin.nextInt()-1;
int b = stdin.nextInt()-1;
lis[a][b]=true;
}
int size = 1 << N;
int max=1;
int bitnum=1;
if(M==0){
System.out.println(max);
}else{
LOOP:
for(int bit=1; bit<size; bit++){
bitnum=0;
for(int a=0; a<N-1; a++){
if((bit & 1 << a) == 0){
continue;
}
for(int b=a+1; b<N; b++){
if((bit & 1 << b)== 0){
continue;
}else if(!lis[a][b]){
continue LOOP;
}
}
}
for(int i=0; i<N; i++){
if((bit & 1 << i)!=0){bitnum++;}
}
if(max<bitnum)max=bitnum;
}
System.out.println(max);
}
stdin.close();
}
}
最初は全く分からない問題でも、解説を見たり、他の参加者の方のソースを拝見させて頂いたりすることで、アルゴリズムや考え方が身についてくると思います。
プログラミングの世界は、上には上がいる(いすぎる)のでやる気が削がれてしまうことは有るかもしれませんが地道に頑張っていこうと思います。
では今日はこれくらいで。
