TopCoder SRM 491

SRM 491(12/19 2:00~4:00)

悪夢は続く．

■FoxMakingDice(Div1 Easy)
立方体サイコロの各面に1~nまでの数字を割り振る．ある面とその対になる面の和はどの面についても等しく，かつk以上で開ければならない．
nとkが与えられた時，条件を満たすサイコロは何種類あるか．

問題を読み間違えてたので無理ゲーじゃん，と思っていました．

コンテスト後，他の人の回答を見たら，非常に明快に解けることが分かりました．

1. 和sumはk以上2n-1以下．
2. a<bで，a+b=sumとなる対a-bの数waysを数える．
3. ways個から3個を選択する選び方は，_waysC₃
4. ↑の値を全てのsumについて和を取る．
5. (a-b, c-d, e-f)という選び方をするサイコロは(同位体みたいな感じを想像すると)2通りある事が分かるので，最後に2をかける．

これを書くだけです．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. public class FoxMakingDice {  
7.  int INF=1<<28;  
8.  double EPS=1e-9;  
9.   
10.  public long theCount(int n, int k) {  
11.   long res=0;  
12.   for(int sum=k;sum<=2*n-1;sum++){  
13.    long ways=0;  
14.    for(int first=1;first<=n&&first<sum-first;first++){  
15.     if(sum-first<=n){  
16.      ways++;  
17.     }  
18.    }  
19.    res+=ways*(ways-1)*(ways-2)/6;  
20.   }  
21.   res*=2;  
22.   return res;  
23.  }  
24.   
25.  void debug(Object...os){  
26.   System.err.println(Arrays.deepToString(os));  
27.  }  
28.   
29.  void print(String s){  
30.   System.out.print(s);  
31.  }  
32.   
33.  void println(String s){  
34.   System.out.println(s);  
35.  }  
36. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class FoxMakingDice {
 int INF=1<<28;
 double EPS=1e-9;

 public long theCount(int n, int k) {
  long res=0;
  for(int sum=k;sum<=2*n-1;sum++){
   long ways=0;
   for(int first=1;first<=n&&first<sum-first;first++){
    if(sum-first<=n){
     ways++;
    }
   }
   res+=ways*(ways-1)*(ways-2)/6;
  }
  res*=2;
  return res;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}

■Result
××× 0 0
0.0p

■Rating
1348 -> 1266

今年の目標は残念ながら達成出来そうに無いです…．