Facebook Hacker Cup 2017 R1に挑む。敗退。

今日は一日中Facebook Hacker Cupに挑んでいました。
A問題は、毎日パイを食べたい人がいて、
その日ごとにm種類の値段のパイがある。
買いだめOKですが、買った値段+税(個数^2)の費用がかかる。
かかる費用の最小値を求めよという問題。

最初コストでソートしてうまいぐあいに取るとかやっていましたが、
未来のパイを食べたりしていてダメだと気付き、ゲーセンでDPをやるとうまくいくんじゃないかと思い施行する。

DP[N日目][M個持ち][利用個数] = 費用で解いた。

<pre>
import java.io.*;
import java.util.Arrays;

public class R1A3 {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../FacebookHackerCup2017/io/pie_progress.txt"));
pw = new PrintWriter(new FileWriter("../FacebookHackerCup2017/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] str = input.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
int[][] costs = new int[N][M];
for(int j = 0 ; j < N ; j++){
str = input.readLine().split(" ");
for(int k = 0 ; k < M ; k++){
costs[j][k] = Integer.parseInt(str[k]);
}
Arrays.sort(costs[j]);
}
int[][][] dp = new int[N + 1][N + 1][M + 1];//N日目、M個持ち、利用個数
for(int j = 0 ; j <= N ; j++){
for(int k = 0 ; k <= N ; k++){
for(int l = 0 ; l <= M; l++){
dp[j][k][l] = Integer.MAX_VALUE / 2;
}
}
}
dp[0][0][0] = 0;
for(int j = 0 ; j < N ; j++){
for(int k = j; k <= N ; k++){
for(int l = 0 ; l < M ; l++){
if(k < N){
dp[j][k + 1][l + 1] = Math.min(dp[j][k + 1][l + 1], (int)(dp[j][k][l] + costs[j][l] + (Math.pow(l + 1, 2) - Math.pow(l, 2))));
dp[j + 1][k + 1][0] = Math.min(dp[j + 1][k + 1][0], dp[j][k + 1][l + 1]);
}
dp[j + 1][k][0] = Math.min(dp[j + 1][k][0], dp[j][k][0]);
}
}
}
/*for(int j = 0 ; j <= N ; j++){
for(int k = 0 ; k <= N ; k++){
System.out.println(dp[j][k][0]+",j:"+j+",k:"+k);
}
}*/
System.out.println("cost:"+dp[N][N][0]);

pw.println("Case #"+(i+1)+": "+dp[N][N][0]);
pw.flush();
}
input.close();
pw.close();
}
}
</pre>

2問目はゾンビの座標がN個与えられ、半径Rの円と一辺がRの正方形でゾンビを囲める最大数を求める問題。
ゾンビの座標からうまくやれば行けそうだけど、条件がきつそうなのでやらなかった。

3問目は、ある区間からある区間のコストが与えられていて、スタートが1の町から。
最大2か所の荷物を同時に運搬できるが、降ろす順序は家族の先順になるようにするとき、
コストの最小値を求めよという問題。
ダイクストラで各場所の最小コストを求めつつ、DPした。ダメだった。

DP[現在処理してる数][現在位置][荷物状態0,1,2]でやっていた。

<pre>
import java.io.*;
import java.util.Arrays;

public class R1C {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../FacebookHackerCup2017/io/manic_moving.txt"));
pw = new PrintWriter(new FileWriter("../FacebookHackerCup2017/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] str = input.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
int K = Integer.parseInt(str[2]);
int[][] costs = new int[N][N];
int[] fst = new int[K];
int[] fgo = new int[K];
for(int j = 0 ; j < N ; j++){
for(int k = 0 ; k < N ; k++){
costs[j][k] = Integer.MAX_VALUE / 2;
}
}
for(int j = 0 ; j < M ; j++){
str = input.readLine().split(" ");
int st = Integer.parseInt(str[0]) - 1;
int go = Integer.parseInt(str[1]) - 1;
int cost = Integer.parseInt(str[2]);
costs[st][go] = cost;
costs[go][st] = cost;
}
for(int j = 0 ; j < K ; j++){
str = input.readLine().split(" ");
fst[j] = Integer.parseInt(str[0]) - 1;
fgo[j] = Integer.parseInt(str[1]) - 1;
}
for(int j = 0 ; j < N ; j++){
for(int k = 0 ; k < N ; k++){
costs[j][k] = (int)dijkstra(j,k,N,costs);
//System.out.print(costs[j][k]+",");
}
//System.out.println();
}
int[][][] dp = new int[K + 1][N][3];
for(int j = 0 ; j <= K ; j++){
for(int k = 0 ; k < N ; k++){
for(int l = 0 ; l < 3; l++){
dp[j][k][l] = Integer.MAX_VALUE / 2;
}
}
}
dp[0][0][0] = 0;
//now,place,familynum
for(int j = 0 ; j < K ; j++){
for(int l = 0 ; l < 3 ; l++){
for(int k = 0 ; k < N ; k++){
if(dp[j][k][l] == Integer.MAX_VALUE / 2)continue;
if(l == 0){
if(j < K && costs[k][fst[j]] != Integer.MAX_VALUE / 2)dp[j][fst[j]][l + 1] = Math.min(dp[j][fst[j]][l + 1],dp[j][k][l]+costs[k][fst[j]]);
}else if(l == 1){
if(j < K - 1 && costs[k][fst[j + 1]] != Integer.MAX_VALUE / 2)dp[j][fst[j + 1]][l + 1] = Math.min(dp[j][fst[j + 1]][l + 1],dp[j][k][l]+costs[k][fst[j + 1]]);
if(costs[k][fgo[j]] != Integer.MAX_VALUE / 2)dp[j + 1][fgo[j]][l - 1] = Math.min(dp[j + 1][fgo[j]][l - 1], dp[j][k][l] + costs[k][fgo[j]]);
}else if(l == 2){
if(costs[k][fgo[j]] != Integer.MAX_VALUE / 2)dp[j + 1][fgo[j]][l - 1] = Math.min(dp[j + 1][fgo[j]][l - 1], dp[j][k][l] + costs[k][fgo[j]]);
}
}
}
}
/*for(int j = 0 ; j <= K ; j++){
for(int k = 0 ; k < N ; k++){
for(int l = 0 ; l < 3 ; l++){
System.out.println(dp[j][k][l]+",j:"+j+",k:"+k+",l:"+l);
}
}
}*/
int cost = Integer.MAX_VALUE;
for(int j = 0 ; j < N ; j++){
cost = Math.min(cost,dp[K][j][0]);
}
if(cost == Integer.MAX_VALUE / 2){
System.out.println("cost:"+-1);
pw.println("Case #"+(i+1)+": -1");
}else{
System.out.println("cost:"+cost);
pw.println("Case #"+(i+1)+": "+cost);
}
pw.flush();
}
input.close();
pw.close();
}
public static long dijkstra(int st,int g,int n,int[][] dist){
int x;
long min;
long INF = 10000000000000000l;
boolean[] used = new boolean[n];
long[][] cost = new long[n][n];
int rindex = -1;
for(x = 0; x < n; x++){
for(int y = 0 ; y < n ; y++){
cost[y][x] = INF;
}
}
cost[g][g] = 0;
while(true){
min = INF;
for(x = 0; x < n; x++){
if(!used[x] && min > cost[g][x]){
min = cost[g][x];
rindex = x;
}
}

if(min == INF)break;
for(x = 0; x < n; x++){
if(cost[g][x] > dist[x][rindex] + cost[g][rindex]){
cost[g][x] = dist[x][rindex] + cost[g][rindex];
}
}
used[rindex] = true;
}
if(cost[g][st] == INF){
return -1;
}else{
return cost[g][st];
}
}
}
</pre>

4問目は、傘がN個、区間がM与えられ、
傘の直径がN行並んでいて、
被らないようにうまく置ける組み合わせが何通りあるか求める問題。
組み合わせってだけでもうやる気をなくした。

結局1問目しか通過できず、今年はR1敗退で終わった。お疲れ様でした。


ゲーセンはYellow Sketch(RX-Ver.S.P.L.)(A)を難
Facebook Hacker Cup 2017 R1に挑む。敗退。_f0019846_17473730.jpg
ポケモンGOはFHCを粘ったため、3時過ぎからショートカット側。1つ諦めて6占領。
Facebook Hacker Cup 2017 R1に挑む。敗退。_f0019846_17480480.jpg

  by ddrer-yossi | 2017-01-15 17:26 | Beatmania

<< 弐寺の進捗アリアリな一日。F(... 地下謎への招待状2016に挑戦 >>

SEM SKIN - DESIGN by SEM EXE