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をかける．

これを書くだけです．

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

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