今日はサークルの日でした
本日選んだ問題は、問題番号１０４５番、「Split Up!」というもの
相方 乃。がいなかったため今日は先輩とタッグを組んでの挑戦
***************************************************
問題の概要は…
ｎ個の整数を入力し、それらを２つのグループ（Ａ・Ｂ）に分け、
Ａに属する数の合計とＢに属する合計の差の最小値を出力する
入力データは…
ｎ（入力される整数の個数。これが０のとき終了。２０以下で与えられる）
ａ１ ａ２ … ａｎ（整数。空白区切り。１００万を超えることはない。）
***************************************************
なんかね…この問題を見たときとんでもないやつを取ってしまったなと思ったんですよ
まあ一番簡単な方法は全通り確かめること。
でもそれって最悪２＾１９（＝524288）通り求める
（最悪の２０個の場合でもその中の最大をＡ・Ｂの片方に入れとけばＯＫ）ってことじゃないですか！
そんな計算してたらタイムリミットで弾かれるだろっ！！って思ったんです
だけど…
Accepted
目を疑いました。どんな値を与えても必ず全通りをやってくれるのはずなのですが
先輩がそのあとC++で試したところライブラリの使用を控えたらそっちも通りました
このくらいの計算だったらパソコンも大丈夫なんだろうか
それともサンプルデータが甘々なのか
まあ通って何よりですが、もっと効率のいい方法はないものでしょうか
もしなにかありましたらコメントで
（とはいえ俺もレベルまだまだなんで力説されても理解できないことがある可能性ありますが）
これが本日の成果といえるか分からない成果物↓
超オーソドックスなやり方。本当にこれでいいのか？悩む限り
**********************************************
import java.util.Scanner;
public class Split_Up {
static int dmin,n;
static void func(int[] data,int a,int b,int count){
if(count==n){
if(Math.abs(a-b)<dmin)
dmin=Math.abs(a-b);
return;
}
func(data,a+data[count],b,count+1);
func(data,a,b+data[count],count+1);
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
while(true){
n=scan.nextInt();
dmin=Integer.MAX_VALUE;
if(n==0) break;
else{
int[] data=new int[n];
for(int i=0;i<n;i++)
data[i]=scan.nextInt();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
func(data,data[0],0,1);
System.out.println(dmin);
}
}
}
}
**********************************************
次回予告：
会津オンラインジャッジの過去問リストを見ていると奇妙な問題を発見
「Accelerated Railgun」、「SAT-EN-3」…
これってどう考えてもアレですよね。
問題文を読んだらなおよく分かります。ええ、最近観たばっかりですから
ナンバリングの後半あたりからネタが炸裂している問題がちらほらあります（これ以外にも）
まだそのナンバーまでそこそこ問題がありますが、
もっと勉強して腕を上げたら頑張ろう！
ということで今日はさらば！
＋α
高校行く行くって何回も書いときながら本日まで１日も行けませんでした
特に情報部の皆さん、来るんじゃないか来るんじゃないかと警戒しながら活動しているようであったなら
本当にすみませんでした<(_ _)>
行けるとしたら明日ですね。今度こそ嘘っぱちにならなければいいんですけど