コンテストラッシュ

Contest FHC C++ Java Codeforces SRM

最近プログラミングコンテストがやけに集中して開催されていたので、いくつか出てみました。

Facebook Hacker Cup 2013 Qualification Round

就活のためにと思って登録したFacebookでしたけど、コンテストなんてやっているとは。

1.Beautiful strings

https://www.facebook.com/hackercup/problems.php?pid=475986555798659&round=185564241586420

各アルファベットに1〜26の点数を割り当てたとき、与えられた文字列の点数を最大化する問題。

単純にアルファベットの数を数え、出現回数が多い順に高い点数を当てはめていけば良い。

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> data;

int doIt(){
	int m = 0;
	int ary[26];
	string input;
	data ans[26];
	cin >> m;
	cin.ignore();

	for(int i = 0; i < m; i++){
		getline(cin, input);
		fill(ary, ary + 26, 0);
		for(int j = 0; j < input.size(); j++){
			char c = input[j];
			if('a' <= c && c <= 'z') ary[c - 'a']++;
			else if('A' <= c && c <= 'Z') ary[c - 'A']++;
		}
		for(int j = 0; j < 26; j++) ans[j] = data(ary[j], j);
		sort(ans, ans + 26);
		int val = 1;
		for(int j = 0; j < 26; j++) ary[ans[j].second] = val++;
		int res = 0;
		for(int j = 0; j < input.size(); j++){
			char c = input[j];
			if('a' <= c && c <= 'z') res += ary[c - 'a'];
			else if('A' <= c && c <= 'Z') res += ary[c - 'A'];
		}

		cout << "Case #" << (i + 1) << ": " << res << endl;;
	}

}


int main(){
	doIt();
}
2.Balanced Smileys

https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420

丸括弧と顔文字（「:)」、「:(」）のある文法でかっこのバランスが正しいかどうかを判定する問題。

始めは研究で使っているPackrat Parsingで解こうと思ったが、よく考えると上手くいかない。
文字列長が高々100なので、ネストのレベルは高々100となる。そこで、文字列を解析してあり得るネストのレベルを並列に覚えておくことにした。
1.「:(」が来たらネストのレベルを0、1増やす。
2.「:)」が来たらネストのレベルを0、1減らす。
3.「(」が来たらネストのレベルを1増やす。
2.「)」が来たらネストのレベルを1減らす。
これで最後にネストレベル0があり得たら"YES"、あり得なかったら"NO"とすればよい。

と、これで出来たのですが、始めに書いたコードにバグがあり、それを修正したコードを書いたのに間違えて始めに書いたコードを提出してWAというorz


正解コード

import java.util.Scanner;

public class Q2012_2 {

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		sc.nextLine();
		for(int i = 0; i < t; i++){
			char[] input = sc.nextLine().toCharArray();
			boolean[] nest = new boolean[101];
			boolean bColon = false;
			nest[0] = true;
			for(int j = 0; j < input.length; j++){
				char c = input[j];
				if(c == ':'){
					bColon = true;
					continue;
				}

				if(c == '('){
					if(bColon){
						for(int k = 99; 0 <= k; k--) if(nest[k]) nest[k + 1] = true;
					}
					else{
						for(int k = 99; 0 <= k; k--) 
							if(nest[k]){
								nest[k] = false;
								nest[k + 1] = true;
							}
					}
				}
				else if(c == ')'){
					if(bColon){
						for(int k = 1; k < 100; k++) 
							if(nest[k]) nest[k - 1] = true;
					}
					else{
						if(nest[0]) nest[0] = false;
						for(int k = 1; k < 100; k++) 
							if(nest[k]){
								nest[k - 1] = true;
								nest[k] = false;
							}
					}
				}
				else{
					if('a' <= c && c <= 'z' || c == ' ' || c == ':'){
					}
					else{nest[0] = false;break;}
				}
				bColon = false;
			}
			System.out.println("Case #" + (i + 1) + ": " + (nest[0]? "YES" : "NO"));
		}
	}

}

3問目は全く分かりませんでした。


結局1問正解で7319 / 11392位でした。2問目を落としたのが本当に悔やまれる。
一応次のラウンドに進めました。

Codeforces Round #164 (Div. 2)

http://codeforces.com/contest/268

今度こそはCを解こう！と意気込んで参加。

A.Games

始めはスポーツスケジューリング問題かと思ったけど違った。シミュレーション。

import java.util.Scanner;

public class A {

	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] uni = new int[n][2];
		for(int i = 0; i < n; i++){
			uni[i][0] = sc.nextInt();
			uni[i][1] = sc.nextInt();
		}
		int count = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(uni[i][0] == uni[j][1]) count++;
			}
		}
		System.out.println(count);
	}
}
B.Buttons

正解のボタンを押し続けると錠が解ける金庫を最悪ケース何回押さないといけないかを求める問題。
ボタンの個数がn個とすると、1個目のボタンは最悪でn回押さないといけない。2個目のボタンはn-1*(2)回、k個目のボタンは(n - (k - 1))*(k)回押さないと行けない。

import java.util.Scanner;

public class B {

	public static void main(String[] args) {
		doIt();
	}

	static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int inc = 1;
		int sum = 0;
		for(int i = n; 0 < i; i--){
			sum += (i-1)*inc;
			inc++;
		}
		System.out.println(sum + n);

	}
}
C. Beautiful Sets of Points

n * mの二次元座標が与えられたとき、各点間の距離が整数にならないように点を配置したとき、その最大数と各点の座標を求める。ただし(0, 0)には置けない。


上手く解けませんでした。
始めに、(i, j)に点を置くとそれ以降にi行目とj列目には点が置けなくなるので、おそらく点の数はmin(n, m) + 1になるというのは分かった。
小さいところから貪欲に置いていけばいいのかと思ったのですが、(0, 1)、(4, 4)の距離が5になるなど問題が発生してしまう。
結局時間切れで駄目でした。後日、人に訊いてみたら「右斜め下の端から左斜め上に向けて置いていけば絶対大丈夫なんじゃない？」と言われ、その通りに実装したら通りました。言われてみれば簡単なんだけどなー。コロンブスの卵。

あとこれはあまり関係ないけど、この問題のように正しい要素とその総数を出力する問題の場合、コードの実行順に出力すると要素→総数となってしまいます。
PrintWriterを使うと、flushを呼ぶまで出力を遅延出来るので（初めて知った）、PrintWriterに要素の出力を溜めておき、総数をSystem.out.printlnで出力し、その後にPrintWriterをflushすると総数→要素の順に出せます。

正解コード

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

public class C {
	
	public static void main(String[] args) {
		doIt();
	}
	
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int m = sc.nextInt();
		//boolean[] usedX = new boolean[n + 1];
		boolean[] usedY = new boolean[m + 1];
		int count = 0;
		for(int i = n; 0 <= i; i--){
			for(int j = 0; j <= m; j++){
				if(0 < i+j && usedY[j] == false){
					count++;
					out.println(i + " " + j);
					usedY[j] = true;
					break;
				}
			}
		}
		System.out.println(count);
		out.flush();
	}
}

D,Eは見ていません。

結局2問正解で1126 / 3001位でした。今回は全然駄目だったなー。

Rating : 1435(Rank 956) → 1406(Rank 854)

SRM568 (Div. 1)

初Div.1！過去のDiv.1 Easyを見ても全く解けなかったので緊張しながら参加。

Easy. BallsSeparating

http://community.topcoder.com/stat?c=problem_statement&pm=12398

n個の箱に赤、緑、青のボールがいくつかずつ入っている。全ての箱のボールを1色にするようにボールを移動させるとき、その最小個数はいくつか。

単純にやりました。
各箱について、一番個数が多い色以外の色のボールを移動すれば良い。
でも、ある一つの色がどの箱でも最大個数で無い場合に、その色の行き先の箱がなくなってしまう。その場合は各箱を見て、その色の個数と最大個数の差が最小になる箱を見つけて、その差分を結果に足せば良い。
一番難しいのは全ての箱で一つの色が最大個数になっているとき。この場合は残りの二色とその色の差分を昇順にソートして、それぞれ一番少ない差分を足せば良い。インデックスが同じ場合は一番と二番を比較すればよい。

と思ったんですが、Systm Testで落とされてました。なんか駄目みたいです。なんで？？

medium以降は全く分からなかったので、1問目の撃墜しようとコーナーケースを作ってました。
でも、Challenging Phaseで何も出来ずorz

結局1問も解けず、Div2に降格。Div1は僕にはまだ早いですね・・・。

Rating : 1287 → 1172



追記(2013/01/30)
初その日のうちに追記！
TopCoderもCodeforcesみたいにテストケースが見れることをさっき知りました。僕の解答は以下のやつです。
http://community.topcoder.com/stat?c=problem_solution&rm=315694&rd=15488&pm=12398&cr=23103815

分析してみると、駄目な原因が分かりました。1つの色がどの箱でも最大個数でない場合に、コンテスト中に提出したコードではその色と最大個数との差分が一番小さいものを無条件に使っていたのですが、その最大個数の色がその箱しか無い場合にその色を入れる箱が無くなってしまうために上手くいかないんですね。思いつきませんでした。

import java.util.Arrays;

//import java.util.*;
public class BallsSeparating {
	public int minOperations(int[] red, int[] green, int[] blue) {
		int ret = 0;
		int n = red.length;
		pair[][] diff = new pair[3][n];
		int[] max = new int[n];
		int[] bFlag = new int[3];

		if(n < 3) return -1;
		for(int i = 0; i < n; i++){
			int r = red[i];
			int g = green[i];
			int b = blue[i];
			if(r <= g && b <= g){max[i] = 1;diff[0][i] = new pair(g - r, i);diff[1][i] = new pair(0, i); diff[2][i] = new pair(g - b, i);bFlag[1] += 1;ret += r + b;}
			else if(r <= b && g <= b){max[i] = 2;diff[0][i] = new pair(b - r, i);diff[1][i] = new pair(b - g, i); diff[2][i] = new pair(0, i);bFlag[2] += 1;ret += r + g;}
			else{max[i] = 0;diff[0][i] = new pair(0, i);diff[1][i] = new pair(r - g, i); diff[2][i] = new pair(r - b, i);bFlag[0] += 1;ret += g + b;}
		}
		int count = 0;
		for(int i = 0; i < 3; i++){if(bFlag[i] == 0) count++;}
		if(count == 0) ;
		else if(count == 1){
			int tar = 0;
			for(int i = 0; i < 3; i++){if(bFlag[i] == 0) tar = i;}
			Arrays.sort(diff[tar]);
			for(int i = 0; i < n; i++){if(bFlag[max[diff[tar][i].index]] > 1){ret += diff[tar][i].diff; break;}};
		}
		else{
			int[] tar = new int[2];
			int index = 0;
			for(int i = 0; i < 3; i++){if(bFlag[i] == 0){tar[index] = i;index++;}}
			Arrays.sort(diff[tar[0]]);
			Arrays.sort(diff[tar[1]]);
			if(diff[tar[0]][0].index == diff[tar[1]][0].index){ret += Math.min(diff[tar[0]][0].diff + diff[tar[1]][1].diff, diff[tar[0]][1].diff + diff[tar[1]][0].diff);}
			else ret += diff[tar[0]][0].diff + diff[tar[1]][0].diff;
		}
		return ret;

	}
	// BEGIN CUT HERE
	public static void main(String[] args) {
		int[] red = {852057, 889141, 662939, 340220};//{10, 5, 8};
		int[] green = {600081, 390298, 376707, 372199};//{8,2,2};
		int[] blue = {435097, 40266, 145590, 505103};//{9,2,2};
		
		BallsSeparating temp = new BallsSeparating();
		System.out.println(temp.minOperations(red, green, blue));
	}
	// END CUT HERE
}

class pair implements Comparable<pair>{
	int diff = 0;
	int index = 0;
	pair(int d, int i){
		diff = d;
		index =  i;
	}
	public int compareTo(pair o) {
		return diff - o.diff;
	}
}

しかしJavaもC++の

typedef pair<int, int> data;

みたいにsort可能なお手軽な2つ組のクラスがあるといいんですが。他のコンテストならC++使えば良いんですが、TopCoderはエディタの設定が大変なのできついです。pairクラスのテンプレートを作っておくしかないのかなあ。



追記2：2013/02/24

Facebook Hacker Cup Qualification Roundの3問目Find the Min(https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420)を解説(http://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621)を見ながら解きました。

・bとかcはlongにしとかないと危険。
・解説にある通りmapを使う。始めHashMapを使おうと思ったんだけど、HashMapには最小のキーを取る関数が無かったのでTreeMapを使用。pollFirstEntryで最小のキーを取得しながらmapから取り除くことが可能。超便利。
・コード下部のposを合わせるのがちょっと大変だった・・・。

import java.util.TreeMap;
import java.util.Scanner;

public class Q2013_QR_3 {

	public static void main(String[] args) {
		doIt();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		sc.nextLine();
		for(int i = 0; i < t; i++){
			int n = sc.nextInt();
			int k = sc.nextInt();
			int a = sc.nextInt();
			long b = sc.nextInt();
			long c = sc.nextInt();
			long r = sc.nextInt();
			int[] ans = new int[k + 1];
			boolean[] nums = new boolean[k + 1];
			int[] m = new int[k];
			int[] time = new int[k + 1];
			m[0] = a;
			if(0 <= a && a <= k){nums[a] = true; time[a] = 0;}
			TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
			for (int j = 1; j < k; j++) {
				long e = (b * m[j - 1] + c) % r;
				m[j] = (int)e;
				if(0 <= e && e <= k && m[j] < k + 1){nums[m[j]] = true; time[m[j]] = j;}
			}
			for (int j = 0; j <= k; j++) {
				if(!nums[j]) map.put(j, 0);
			}
			boolean[] nums2 = new boolean[k + 1];
			for (int j = 0; j < k; j++) {
				int e = map.pollFirstEntry().getKey();
				ans[j] = e;
				if(m[j] <= k && !nums2[j] && time[m[j]] <= j){
					map.put(m[j], 0);
					nums2[j] = true;
				}
			}
			ans[k] = map.pollFirstEntry().getKey();
			int pos = (n - k - 1) % (k + 1);
			System.out.println("Case #" + (i + 1) + ": " + ans[pos]);
		}
	}
}