ナランハジャグリングまつり二日目+ポップン+GCJ R1B

今日は朝11時頃にナランハジャグリングまつりの会場に到着、
11時からワークショップでデビルスティックをやりました。
あああ難しいわーってやってました。ボール以外本当にほとんどできないです。

お昼も食べずに、ジャグリングセールへ。
何故か販売終了したFUSIGIボール(展示品)を500円でゲットしました。
やらなさそうなのにネタで。

その後はフリーパフォーマンス+ゲストパフォーマンスを見ました。

終わった後は、N字ボックス系の練習をしつつ、喋りつつという感じであっという間に終了時刻に。

その後はポップンをやりに、池袋ラウンドワンへ。
が、混んでいたので一旦スポルト池袋へ。
しかし、ボタンが固いと感じたので、DDRやったりビーマニやったり。
ビーマニもそれほど環境が良くなくて、結局ラウンドワンへ再移動。

ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_126486.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_127143.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_127167.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1272971.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1274523.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1275647.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_128935.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1282325.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_12835100.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1284870.jpg


ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_1291522.jpg


48でPSGブレイクコア、サイバーフラメンコ、グロッソラリア、シンフォニックメタルop2の4曲が
埋まり、55%へ。

途中プレー前に画面が落ちて、再起動がかかりました。WindowsXPはサポートが(以下略
その際に100円玉をいじっていたらなくしました。アホかー!

満足できなかったビーマニを地元ゲーセンでやろうとするも、
1クレで混んできたので退散。エナジードリンクを買って、
夕飯を食べつつ、GCJに備える。
ナランハジャグリングまつり二日目+ポップン+GCJ R1B_f0019846_12111025.jpg


A問題。
最初に正の整数値が与えられていて、他にいくつかの数列がある。
その値より小さい値を足し合わせることができる。
足しあわせられないときに以下の動作ができる。
・要素を1個消す
・任意の値を数列に加える

この動作の回数が最小となる値を求めよ。

数学的に考えていたものの、正直思い浮かばなかったので、
いいや、全探索しても間に合うだろうということで、幅探索解を提出して、smallは通る。
が、largeもそんなに大きくならないだろうと見誤ってしまった。
これはほんとうに良くない。


import java.util.*;
import java.io.*;

public class Test2 {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
for(int i = 0 ; i < num ; i++){
int A = input.nextInt();
int N = input.nextInt();
int[] sob = new int[N];
for(int j = 0 ; j < N ; j++){
sob[j] = input.nextInt();
}
pw.print("Case #"+(i+1)+": "+radius(A,N,sob));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static int radius(int A,int N,int[] sob){
Arrays.sort(sob);
int max = Integer.MAX_VALUE;
Queue q = new LinkedList();
q.add(0+","+sob.length+","+A+","+0);//st,en,pow,turn
while(!q.isEmpty()){
String[] st = q.poll().split(",");
int s = Integer.parseInt(st[0]);
int e = Integer.parseInt(st[1]);
int pow = Integer.parseInt(st[2]);
int turn = Integer.parseInt(st[3]);
if(s == e){
max = Math.min(max, turn);
}else{
if(pow > sob[s]){
q.add((s+1)+","+e+","+(pow+sob[s])+","+turn);
}else{
if(pow != 1)q.add(s+","+e+","+(pow+(pow-1))+","+(turn+1));
}
q.add(s+","+(e-1)+","+pow+","+(turn+1));
}
}
return max;
}
}


B問題はダイヤが0,0に向かって落ちてくる。
左か右かわからない場合は等確率で落ちてくる。
いくつか落ちた時のある座標に落ちている確率を求めよという問題。
これも全探索なのかなーという感じでしたが、なにせ最後に解こうとしたので、わからず。

C問題は、辞書が与えられていて、ある文字に関して、
辞書の文字列で構成されているはずだが、何箇所かに誤りがある。
その誤りは、必ず5つ以上離れている。
誤っている数の最小値を出力せよという問題。

まず工夫しないと終わりません。
自分の場合は、ある文字まで見終わった時の誤りの最小値を格納してます。
同時に誤りの位置も格納しました。が、これは本来この2つで二次元配列でやるべきだということに、
終了後に気づきます。

small、largeが通る解ですが、largeは、数時間はかかる感じなので、
本番では更に高速化することが求められます。


import java.util.*;
import java.io.*;

public class Test2 {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-large-practice.in"));
Scanner input2 = new Scanner(new FileReader("./iothings/garbled_email_dictionary.txt"));
ArrayList list = new ArrayList();
while(input2.hasNext()){
list.add(input2.next());
}
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
for(int i = 0 ; i < num ; i++){
String s = input.next();
//System.out.println(s);
pw.print("Case #"+(i+1)+": "+radius(s,list));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static int radius(String s,ArrayList list){
Queue q = new LinkedList();
int min = 4000;
int[] zanteimin = new int[s.length()];
int[] zanteisindex = new int[s.length()];
for(int i = 0 ; i < zanteimin.length ; i++){
zanteimin[i] = Integer.MAX_VALUE;
zanteisindex[i] = Integer.MAX_VALUE;
}
q.add(0+","+s.length()+","+(-5)+","+0);//st en slindex snum
while(!q.isEmpty()){
String[] st = q.poll().split(",");
int stindex = Integer.parseInt(st[0]);
int enindex = Integer.parseInt(st[1]);
int s_index = Integer.parseInt(st[2]);
int snum = Integer.parseInt(st[3]);
if(stindex == enindex){
min = Math.min(min,snum);
//System.out.println(min+"kita");
}else{
if(snum < min){
for(int i = 0 ; i < list.size(); i++){
String cmp = list.get(i);
if(stindex+cmp.length() > s.length())continue;

int scount = 0;
boolean isok = true;
int sindex = s_index;

for(int j = 0 ; j < cmp.length() ; j++){
if(s.charAt(j+stindex) != cmp.charAt(j)){
if((j+stindex)-sindex < 5){
isok = false;
break;
}else{
scount++;
sindex = j+stindex;
}
}
}
if(isok){
if((snum+scount) < zanteimin[stindex+cmp.length()-1]){
q.add((stindex+cmp.length())+","+s.length()+","+sindex+","+(snum+scount));
zanteimin[stindex+cmp.length()-1] = (snum+scount);
zanteisindex[stindex+cmp.length()-1] = sindex;
}else if((snum+scount) == zanteimin[stindex+cmp.length()-1] && sindex < zanteisindex[stindex+cmp.length()-1]){
q.add((stindex+cmp.length())+","+s.length()+","+sindex+","+(snum+scount));
zanteisindex[stindex+cmp.length()-1] = sindex;
}
//System.out.println(cmp+","+(snum+scount)+","+(stindex+cmp.length())+","+s.length());
}
}
}
}
}
return min;
}
}


結果は ox -- o- 22ptsの3238位。
残すは後1回。去年はR2進出しただけあって、今回も1Cで通過しましょう。

天鳳1-1

  by ddrer-yossi | 2013-05-04 23:02 | 日常生活

<< 新宿東南口のタイトーへ、Cod... SRM578 と ナランハジャ... >>

SEM SKIN - DESIGN by SEM EXE