開発集中三日目、TopCoder SRM645

今日はひと通りのUIが実装できたので、
それをアニメーション化して画像として保存する部分までの実装を行いました。
ImageMagickとかいうのとjsgifというのがあって、
jsgifのほうが手軽そうなので、こちらを選択しました。
なんとか生成するも、重いので、最適そうな値にしつつ、
処理中に操作されると困るので、BlockUIを取り入れました。
$Defferedの扱いに苦戦しましたが、なんとかじゅんじゅんに画像として取り込むことに成功しました。
これ、並列に処理しちゃうと、見事に同じ画像が重なってしまうという、面倒なもので…。
.thenでつないで中身に関数を書くのを繰り返すといった感じでした。

Facebook Hacker Cup 2015ですが、まさかの3問中2問目しか解けていませんでした。

1問目のCooking the Booksは、
数字を1回だけスワップして、最小値と最大値を出力する問題。
数字が9桁制約なので、総当りしちゃっても良かったのですが、
下手に凝り過ぎました。おいおい…。

2問目のNew Year's Resolutionは、一見DPで頑張らないといけなさそうに見えますが、
制約をよく見ないといけません。
Gp,Gc,Gfを丁度満たすようなPCFの組み合わせが存在するかどうか求めるのですが、
個数が最大20なので、最大ケースでも2^20総当りやるだけです。
要するにそれぞれの食品に関して選ぶか選ばないか、
全部やっても1048576回の処理にしかなりません。
時間的に余裕なので総当りしました。1問目もそうしろと…。


import java.io.*;

public class Main {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../FHC/new_years_resolution.txt"));
pw = new PrintWriter(new FileWriter("../FHC/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] str = input.readLine().split(" ");
int gp = Integer.parseInt(str[0]);
int gc = Integer.parseInt(str[1]);
int gf = Integer.parseInt(str[2]);
int N = Integer.parseInt(input.readLine());
int[] numsp = new int[N];
int[] numsc = new int[N];
int[] numsf = new int[N];
for(int j = 0 ; j < N ; j++){
str = input.readLine().split(" ");
numsp[j] = Integer.parseInt(str[0]);
numsc[j] = Integer.parseInt(str[1]);
numsf[j] = Integer.parseInt(str[2]);
}
int pattern = (int)Math.pow(2,N);
boolean isok = false;
for(int j = 0 ; j < pattern ; j++){
String s = Integer.toBinaryString(j);
String ends = "";
int np = 0;
int nc = 0;
int nf = 0;
for(int k = 0 ; k < N - s.length(); k++){
ends += "0";
}
s = ends + s;
for(int k = 0 ; k < N ; k++){
if(s.charAt(k) == '1'){
np += numsp[k];
nc += numsc[k];
nf += numsf[k];
}
}
if(np == gp && nc == gc && nf == gf){
isok = true;
break;
}
}
if(isok){
pw.println("Case #"+(i+1)+": yes");
}else{
pw.println("Case #"+(i+1)+": no");
}
pw.flush();
}
input.close();
pw.close();
}
}


3問目のLaser Mazeは、迷路があるが、
時計回りに回転してレーザーを発射する物体が設置されていて、当たらないようにゴールに着く
最短の歩数を求める問題。ゴールする時にもあたってはいけない。
ということで、ターン数的にマスごとに4で割れる値は4つしかないので、
x,y,4の3次元配列でBFSで解いたのですが、結果的にダメでした。
どこがダメだったのかはまだ究明していません。

開発が一段落してゲーセンへ。
弐寺は進捗なし。
リフレクは走れメロンパンを粘着している人を見て、自分もやりたくなったのでやる。
あっさり99.4%。これ、エクセ(笑)いけるんじゃないと思ったけど、やめました。
開発集中三日目、TopCoder SRM645_f0019846_2402434.jpg


サンボルは魔騎士を頑張りましたが、3曲目であっさり死ぬ。難化しすぎだよねこれ…。
その後はNon-Fiction Story! 98.7%(GREAT出しすぎたなーと思えるようになった)
開発集中三日目、TopCoder SRM645_f0019846_2412362.jpg


Zirkfied 86.2%
開発集中三日目、TopCoder SRM645_f0019846_2414239.jpg


など、微更新で終わりました。

その後は1時のTopCoder SRM645に参加。明日仕事なんだけどなぁと思いつつ。
easyですが、宿泊客がある日にきて、ある日に帰ります。
ある日に祝典を渡すと、その客は満足します。また、祝典を渡されている客を見た客も、
同様に満足します。全員を満足させるのに、最低いくつの祝典が必要か出力せよという問題。
到着時刻からみればいいという話でしたが、よくわかりませんでした。
貪欲でも難しい系統なのか、問題を解かなくても200位切りました。

たとえば
[8,11,24,30,56,58,60]
[12,30,30,100,57,59,61]ですと、
2番目の客に合わせるために、11日目か12日目に祝典を与え、
30日目に4番目の客に祝典を与える、2が正解なのですが、
考えたアルゴリズムでは4が出力されてしまいます。
見た と 得たを別物として考えるのもナンセンスだし…。

1211 -> 1238

  by ddrer-yossi | 2015-01-12 23:27 | TopCoder

<< ガッツリ食べるも太るのを避けた 集中開発二日目 >>

SEM SKIN - DESIGN by SEM EXE