Recruit Programming Contest っておもしろそう
今月の8日に開かれたようです。様子はこちらにあります。学生オンリー（既卒 3 年以内の未就業者も可）なので，参加はできないのですが，おもしろそうだなぁ～という印象です。
コンテストで出された問題は分からないのですが，模擬練習会の問題が公開されています。
試しにババ抜きの問題をJavaで作ってみました。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;
/**
* リクルートプログラミングコンテストのサンプル
* http://www.gizmodo.jp/2013/12/recruit_programming_contest.html
*/
public class OldMaid {
static private ArrayList repetitionList = null; // 終了しない場合
public static void main(String[] args) {
ArrayList countList = new ArrayList();// 回数保存
// テストケースの読み込み
String s = readTestCase();
if (s == null || s.length() == 0) {
System.out.println("エラーです。\nファイルを指定してください。");
return;
}
// テストケースを切り出して各テストケースに分割
ArrayList> testcases = makeTestCase(s);
// ばば抜きの実施
for (int i = 0; i < testcases.size(); i++) {
ArrayList testcase = testcases.get(i); // テストケースを取り出して
countList.add(game(testcase)); // ばば抜きの実施
}
System.out.println(countList);
}
/**
* テストケースを標準入力から読み込む
* @return テストケース
*/
static private String readTestCase() {
StringBuilder sb = new StringBuilder();
String inputLine = null;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while ((inputLine = br.readLine()) != null) {
sb.append(inputLine);
sb.append("\n");
}
} catch (IOException ex) {
ex.printStackTrace();
}
return sb.toString();
}
/**
* 与えられた文字列を各テストケースに分割
* @param s 読み込んだ文字列
* @return
*/
static private ArrayList> makeTestCase(String s) {
ArrayList> testcases = new ArrayList<>();
StringTokenizer st = new StringTokenizer(s, "\n");
int numberOfTestCase = Integer.parseInt(st.nextToken());
for (int i = 0; i < numberOfTestCase; i++) {
int num = Integer.parseInt(st.nextToken());
ArrayList testcase = new ArrayList<>();
for (int j = 0; j < num; j++) {
testcase.add(st.nextToken());
}
testcases.add(testcase);
}
return testcases;
}
/**
* ばば抜きの実施
* @param testcase
* @return
*/
static private int game(ArrayList testcase) {
int count = 0; // カードを取った回数
repetitionList = new ArrayList(); // カードパターン保存用
ArrayList players = new ArrayList<>(); // プレーヤー用
// プレーヤー作成
for (int i = 0; i < testcase.size(); i++) {
players.add(new Player(testcase.get(i)));
}
boolean repetition = false; // 終わらなくなってる？
while ((repetition = isRepetition(players)) == false) {
// 一人になったら抜ける
if (players.size() == 1 && players.get(0).hasJoker()) {
break;
}
// 次の人からカードを受け取る
for (int i = 0; i < players.size(); i++) {
if (players.get(i).isEmpty()) { // カードがなくなっていたら次の人へ
continue; // 前の人にカードを抜かれてなくなる場合がある
}
// カードを抜く人を決める
int next = (i == players.size() - 1) ? 0 : i + 1; // 基本は次の人
// 1枚引いて
players.get(i).appendCard(players.get(next).removeCard());
count++; // 回数をカウント
// 同じカードがあれば捨てる
players.get(i).dropCards();
// 二人だけが残っている状態で一人が上がったら終了
if (players.size() == 2 && players.get(i).isEmpty()) {
break;
}
}
// 手札が0になったプレーヤーを削除
Iterator it = players.iterator();
while (it.hasNext()) {
Player player = it.next();
if (player.isEmpty()) {
it.remove();
}
}
}
// 終わらなくなって抜けてきたら回数は-1
if (repetition) {
count = -1;
}
return count;
}
/**
* 終わらないかどうかの判定
* 終わらないのは3人で延々と繰り返す場合。
* 各プレーヤーのカードを文字列として連結し，それを記憶させておく。
* 同じパターンが出てきたら繰り返しが発生していると判定
* @param list
* @return
*/
static private boolean isRepetition(ArrayList list) {
boolean repetition = false;
if (list.size() != 3) {
return repetition;
}
/*
System.out.println("------------------------");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i).getCards());
}
*/
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
if (sb.length() !=0) {
sb.append(' ');
}
sb.append(list.get(i).getCards());
}
if (repetitionList.contains(sb.toString())) {
repetition = true;
} else {
repetitionList.add(sb.toString());
}
return repetition;
}
}
/**
* ゲームに参加するプレーヤ
* @author maruuo
*/
public class Player {
private StringBuilder cards;
public Player() {
this("");
}
public Player(String cards) {
this.cards = new StringBuilder(cards);
}
/**
* Jokerを持っているかどうか
* @return
*/
public boolean hasJoker() {
return (cards.indexOf("J") != -1);
}
/**
* 手札に同じカードを持っているかどうか
* @return
*/
public boolean hasSameCards() {
boolean has = false;
for (int i = 0; i < cards.length() - 1; i++) {
String s = cards.substring(i, i+1);
if (cards.indexOf(s, i+1) != -1) {
has = true;
break;
}
}
return has;
}
/**
* 手札がない？
* @return
*/
public boolean isEmpty() {
return (cards.length() == 0);
}
/**
* 手札の枚数
* @return
*/
public int length() {
return cards.length();
}
/**
* 同じ手札があれば捨てる
* @return
*/
public boolean dropCards() {
if (isEmpty() || !hasSameCards()) {
return false;
}
int pos1 = 0;
int pos2 = 0;
for (int i = 0; i < cards.length() - 1; i++) {
pos1 = i;
pos2 = cards.indexOf(cards.substring(i, i+1), i+1);
if (pos2 != -1) {
break;
}
}
cards.deleteCharAt(pos2);
cards.deleteCharAt(pos1);
return true;
}
public String getCards() {
return cards.toString();
}
public void setCards(String cards) {
this.cards = new StringBuilder(cards);
}
public void appendCard(String card) {
if (card == null) {
return;
}
cards.append(card);
}
public void appendCard(char c) {
cards.append(c);
}
public String removeCard() {
String s = cards.substring(0, 1);
cards.deleteCharAt(0);
return s;
}
static public int[] countCards(String cards) {
int[] count = {0,0,0,0,0,0,0,0,0};
for (int i = 0; i < cards.length(); i++) {
String s = cards.substring(i, i+1);
if (s.equalsIgnoreCase("J")) {
continue;
}
try {
count[Integer.parseInt(s)]++;
} catch (NumberFormatException e) {
e.printStackTrace();
}
}
return count;
}
}
コンテストでは制限時間3時間で，問題が10問出されたようです。ということは1問18分で解くということですな。ん～，できる学生さんにはかないません…
| 固定リンク | コメント (0) | トラックバック (0)
最近のコメント