コンテストラッシュ2

Contest FHC Java Project Euler Haskell CodeChef C++ COJ

ここ（http://wikiwiki.jp/kyopro/?FrontPage）を見て面白そうなOnline Judgeがあったのでいくつか登録してみました。あとFacebook Hacker Cupの結果を。

Facebook Hacker Cup 2013 Round 1

https://www.facebook.com/hackercup/problems.php?round=189890111155691

1問目だけ挑戦。時間が午前3時開始という鬼畜時間。

1.Card Game

数字が書かれているN種類のカードからK枚選ぶ。手札の強さを手札の中の最大値とするとき、全ての手札の強さの総和（ % 1 000 000 007）を求める問題。

手札を数字順にソートして、残りの枚数からk枚取る組み合わせを計算していけば良い。

組み合わせの計算が難しい。割り算が入ってくるので、公式通りに真面目にやると誤差が出てしまいそうである。
しかし、総和の% 1 000 000 007を求めれば良く、これは素数である。そこでフェルマーの小定理（http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html）を使うと、
a / b (mod 1 000 000 007) = a * b^(1 000 000 007 - 2) (mod 1 000 000 007)
と出来るのでこれを利用する。
前にARC（http://arc009.contest.atcoder.jp/tasks/arc009_3）で解いたことがあるので出来ました（参考 : http://d.hatena.ne.jp/ty70/20121028/1351418377）。
あと、BigIntegerのmodInverse関数で逆元が計算出来るみたいなので、これを使っても良さそう（http://www.tutorialspoint.com/java/math/biginteger_modinverse.htm）。

ただ、念のためにと思って入れておいた条件が邪魔して、k = 1のときに上手くいかなくてWA。これからは上限だけじゃなくて下限もチェックするように心がけます・・・。

正解コード

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

public class Q2013_R1_1 {
	static final int MOD = 1000000007;

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int t = sc.nextInt();
		for(int i = 0; i < t; i++){
			int n = sc.nextInt();
			int k = sc.nextInt();
			if(n == 1){
				out.println("Case #" + (i + 1) + ": " + sc.nextInt());
				continue;
			}
			PriorityQueue<Long> queue = new PriorityQueue<Long>(n, Collections.reverseOrder());
			for(int j = 0; j < n; j++) queue.add(sc.nextLong());
			long ans = 0;
			n--;k--;
			while(k <= queue.size() && k <= n){
				long b = queue.poll();
				ans += (b * combi(n--,k)) % MOD;
				ans %= MOD;
			}
			out.println("Case #" + (i + 1) + ": " + ans);
		}
		out.flush();
	}
	static long pow(long n, long p){
		long ans = 1;
		while(p != 0){
			if((p&1) == 1) ans = (ans*n) % MOD;
			n = (n*n) % MOD;
			p = p>>1;
		}
		return ans;
	}
	static long combi(long n, long k){
		long a = 0;
		if(n - k < k) a = n - k;
		else a = k;
		long m = 1;
		long c = 1;
		for(int i = 0; i < a; i++){
			m = (m * (n - i)) % MOD;
			c = (c * (a - i)) % MOD;
		}
		return (m * pow(c, MOD - 2)) % MOD;
	}
}


結局0問正解で全然だめでした。解説はこちら（https://www.facebook.com/notes/facebook-hacker-cup/2013-round-1-solutions/606859202663318）。2問目はいつか余裕があったら解きたいなー。

Project Euler

http://projecteuler.net/

コンテストじゃないけど、数学より（？）のオンラインジャッジ。ソースコードじゃなく、答えを提出する形式。

特訓のためにHaskellで挑戦しています。Project EulerはHaskellと相性がいいです（びっくりなことにWikiに乗ってる : http://www.haskell.org/haskellwiki/Euler_problems/）。久しぶりに1問解いてみました。

13. Large Sum(http://projecteuler.net/problem=13)

50桁の数字100個が与えられる。総和の始めの10桁を求める問題。
Haskellのプログラムに文字列として直接書き込むと改行があるためにコンパイルが通らない。そこで入力はファイルに書いておいてreadFileで読み込む。

main = do
	str <- readFile "input.txt"
	print $ (take 10) $ show $ sum $ map read (words $ str)

このプログラムの短さは本当に関数型言語の簡潔さに感動します。C++とかJavaじゃ絶対に無理な短さ。

CodeChef

http://www.codechef.com/

ランキングがインド人、インド人以外で分けられてるOnline Judge。
今February 2013 Challengeという長期間のコンテストに挑戦中なので、終わったら記事にします（多分）。

Caribbean Online Judge

http://coj.uci.cu/

The COJ Progressive Contest #5 （http://coj.uci.cu/contest/cproblems.xhtml?cid=1229）という長期間のコンテストがあったので出てみました。解けたやつだけ解説。

1. Wordstorm

ゲームのシミュレーション。書くだけ。

import java.util.Scanner;

public class Main {


	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			char[] input = sc.next().toCharArray();
			char cent = input[4];
			int[] alpha = new int[26];
			for(char c : input) alpha[c - 'A']++;
			int n = sc.nextInt();
			for(int ii = 0; ii < n; ii++){
				String word = sc.next();
				int[] alpha2 = new int[26];
				for(int i = 0; i < 26; i++) alpha2[i] = alpha[i];
				boolean bOK = true;
				boolean bCent = false;
				if(4 <= word.length()){
					for(int i = 0; i < word.length(); i++){
						if(alpha2[word.charAt(i) - 'A']-- < 1){bOK = false;break;}
						else if(word.charAt(i) == cent) bCent = true;
					}
				}
				if(bOK && bCent) System.out.println(word + " is valid");
				else System.out.println(word + " is invalid");
			}
		}

	}
}

3. Sandwich

A1, A2, .. , AMの配列が与えられた時に、A1[j1] <= A2[j2] <= ··· <= AM[jM] となるようなインデックスの集合の中で、AM[jM]-A1[j1]が最小のものを見つける問題。

配列Aiの各要素を見て、自分より小さい中で一番大きい配列A(i -1)の要素を見つけてそこに最終的に到達するAMの値を伝播していけばよい。floorEntryのように、「n以下で一番大きいkeyを見つける」機能があるTreeMapを使うと簡単。
始め、TreeMapの配列の作り方が分からなかった（参考 : http://www.javaroad.jp/bbs/answer.jsp?q_id=20101125114042213）。

import java.io.PrintWriter;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	static final int INI = (int)2.0e9;

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int t = sc.nextInt();
		for(int ii = 0; ii < t; ii++){
			int m = sc.nextInt();
			TreeMap<Integer, Integer>[] map = new TreeMap[m];
			for(int i = 0; i < m - 1; i++){
				map[i] = new TreeMap<Integer,Integer>();
				int n = sc.nextInt();
				for(int j = 0; j < n; j++) map[i].put(sc.nextInt(), INI);
			}
			map[m-1] = new TreeMap<Integer,Integer>();
			int n = sc.nextInt();
			for(int j = 0; j < n; j++){
				int k = sc.nextInt();
				map[m-1].put(k, k);
			}
			for(int i = m - 1; 1 <= i; i--){
				for(Entry<Integer, Integer> e : map[i].entrySet()){
					int v = e.getValue();
					if(v != INI){
						Entry<Integer, Integer> tar = map[i - 1].floorEntry(e.getKey());
						if(tar != null) map[i-1].put(tar.getKey(), Math.min(v, tar.getValue()));
					}		
				}
			}
			int min = INI;
			for(Entry<Integer, Integer> e : map[0].entrySet()) {
	            int key = e.getKey();
	            int val = e.getValue();
	            if(val != INI && val - key < min) min = val - key;
	        }
	        out.println(min == INI? -1 : min);
		}
		out.flush();
	}
}

4. Benevolent Dictator

Name a bの記述がいくつか与えられる。これをコストaでb得られるとすると、全てを実行出来るかという問題。

順番は任意なので、始めに0 <= b - aの処理を行い、その後にb - a < 0の処理を全部やって、総和が非負であればよい。
（C++で挑戦。始め入出力をcin,coutでやっててTLEになった）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
typedef pair<ull, ull> P;

void doIt(){
	ull n, m;
	while(true){
	  	//cin >> n >> m;
	 	scanf("%llu %llu", &n, &m);
		if(n + m == 0) break;
		vector<P> plus;
		vector<P> minus;
		for(int i = 0; i < n; i++){
			while(true){
				string s;
				char cc[1024];
				//cin >> s;
				scanf("%s", cc);
				s = cc;
				if(s.find(":") != string::npos) break;
			};
			ull c, r;
			//cin >> c >> r;
			scanf("%llu %llu", &c, &r);
			if(c <= r) plus.push_back(P(c, r));
			else minus.push_back(P(c, r));
		}
		sort(plus.begin(), plus.end());
		bool bOK = true;
		for(int i = 0; i < plus.size(); i++){
			if(plus[i].first <= m) m += plus[i].second - plus[i].first;
			else{bOK = false; break;}
		}
		for(int i = 0; i < minus.size(); i++){
			if(minus[i].first <= m) m += minus[i].second - minus[i].first;
			else{bOK = false; break;}
		}
		if(bOK && 0 <= m) printf("BENEVOLENT DICTATORSHIP\n");//cout << "BENEVOLENT DICTATORSHIP" << endl;
		else printf("SOCIETY RESISTS CHANGE\n");//cout << "SOCIETY RESISTS CHANGE" << endl;
	}
}

int main(){
	doIt();
	return 0;
}

7. Quite a Problem

文章が与えられた時に"problem"の文字列が含まれているかを判定する問題。
バカ正直にやってもいけるのかもしれないが、念のためメモ化で実装。後ろから見ていく。
改行だけの行に注意が必要。

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

public class Main {

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		while(sc.hasNext()){
			char[] line = sc.nextLine().toCharArray();
			int n = line.length;
			if(n == 0){out.println("no"); continue;}
			int[] dp = new int[n];
			if(line[n - 1] == 'm' || line[n - 1] == 'M') dp[n - 1] = 1;
			boolean bContain = false;
			for(int i = n - 2; 0 <= i; i--){
				switch(line[i]){
				case 'p':
				case 'P':
					if(dp[i + 1] == 6) bContain = true;
					break;
				case 'r':
				case 'R':
					if(dp[i + 1] == 5) dp[i] = 6;
					break;
				case 'o':
				case 'O':
					if(dp[i + 1] == 4) dp[i] = 5;
					break;
				case 'b':
				case 'B':
					if(dp[i + 1] == 3) dp[i] = 4;
					break;
				case 'l':
				case 'L':
					if(dp[i + 1] == 2) dp[i] = 3;
					break;
				case 'e':
				case 'E':
					if(dp[i + 1] == 1) dp[i] = 2;
					break;
				case 'm':
				case 'M':
					dp[i] = 1;
					break;
				default:
					break;
				}
			}
			if(bContain) out.println("yes");
			else out.println("no");
		}
		out.flush();
	}
}

18. Hitting the Targets

いくつかの図形と点が与えられたとき、各点がいくつの図形に含まれているかを判定する問題。
図形が円と四角形だけなので、簡単に判定出来る。

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

public class Main {

	static final int RECT = 1;
	static final int CIRC = 2;
	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int m = sc.nextInt();
		Shape[] ary = new Shape[m];
		for(int i = 0; i < m; i++){
			String s = sc.next();
			if(s.equals("rectangle")) ary[i] = new Shape(RECT, sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt());
			else ary[i] = new Shape(CIRC, sc.nextInt(),sc.nextInt(),sc.nextInt());
		}
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){
			int x = sc.nextInt();
			int y = sc.nextInt();
			int c = 0;
			for(int j = 0; j < m; j++){
				if(ary[j].contain(x, y)) c++;
			}
			pw.println(c);
		}
		pw.flush();
	}
}

class Shape{
	int type, x1, y1, x2, y2, r;
	Shape(int t, int x1, int y1, int x2, int y2){
		type = t;
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}
	Shape(int t, int x1, int y1, int r){
		type = t;
		this.x1 = x1;
		this.y1 = y1;
		this.r = r;
	}
	boolean contain(int x, int y){
		boolean ret = false;
		if(type == 1){
			if(x1 <= x && x <= x2 && y1 <= y && y <= y2) ret = true;
		}
		else{
			if(Math.sqrt(Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2)) <= r) ret = true;
		}
		return ret;
	}
}

22. Ragged Right

最終問題なのに実装するだけ。サービス問題？

import java.util.Scanner;
import java.util.Vector;

public class Main {

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		Vector<Integer> v = new Vector<Integer>();
		int max = 0;
		while(sc.hasNext()){
			String s = sc.nextLine();
			int m = s.length();
			v.add(m);
			max = Math.max(m, max);
		}
		int sum = 0;
		for(int i = 0; i < v.size() - 1; i++){
			sum += Math.pow(max - v.get(i), 2);
		}
		System.out.println(sum);
	}

}

6/22問でAC率35.29％、450点で11/116位でした。母数が少ないとはいえ、この順位は嬉しい。
COJの難易度は結構自分に合っていると思うので、解けなかった問題も解いてみようと思います。