RCC 2014 Warmup (Div. 2) C問題：Football

CodeforcesのRCC2014の予選？に参加した。

結果は2/5問正解。レートは下がって1428

相変わらず問題を解くのが遅い。

問題文が英語ということもあり、問題の意図を汲み取るのにかなりの時間がかかっているのが敗因の一つのように思われる。

では今回は時間内に解けなかったC問題を取り上げる。

Problem - C - Codeforces

・問題

1～NのN個のフットサルチームがある。
それぞれのチームは同盟を結んでいて、N個の全てのチームがそれぞれk回勝利すると決まっている。
一度当たった相手とは二度と当たらない。

「試合数」と「全ての試合の結果(勝ちチームと負けチーム)」を時系列順に出力する。

もし条件に合う試合の組み合わせが無かった場合、-1を出力する。

試合は、数値の順番で行われる。

・方針

まず、どんなときに-1を出力することになるのかを考える。
N個全てのチームがk回ずつ勝利することが出来ないときにというのは例えば

n=5, k=3

等が挙げられる。

これの試合を上から列挙すると

1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5

と、この段階でチーム3は戦える相手チームがいないので、全てのチームが3回勝つという条件に満たさない。

また、逆に

n=5, k=2

のときは

1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2

のように条件を満たす。

これを踏まえて、条件を満たせるときというのは、
チームN(最後のチーム)が重複無しでk回勝利できるとき→"チーム数n - 1 > 2k"を満たすとき
である。

説明しにくいのでこの辺にしておく。

出力は、試合を順番に出力するだけ。

・ソース

import java.io.PrintWriter;
import java.util.Scanner;

public class Main3 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int k = sc.nextInt();
		sc.close();
		if(2*k+1>n){
			out.println("-1");
		}else{
		out.println(k*n);
		for(int i=1; i<=n; i++){
			for(int j=0; j<k; j++){
				int count = (i+j)%n+1;
				out.println(i+" "+count);
			}
		}
		}
		out.close();
	}
}

初めは、出力にSystem.out.printlnを使用していたが、

それだと処理に時間がかかるらしく無念のTLE

他の人のソースを参考にして、PrintWriterを使ってみたら、余裕のACだった

そのせいで、こんな問題にかなりの時間を使ってしまったが
オーダー以外にも大切なことは多いということを学べたので、良しとする。