コンテスト

麻雀の待ち判定問題 リベンジ

投稿日: 更新日:


あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
[西尾泰三,ITmedia] 2010年04月03日 00時00分 更新前回の記事「麻雀の待ち判定問題」の続きです。バグがあったということで、リベンジしました。今度こそ完成!

今回は、「単騎待ち」や値が重複するのを踏まえて設計をし直しました。
以前のバージョンから、さらに1時間半は使いました。
なお、前回と同じくチートイツとフリテンは考えていません。

大体の時間配分
0:00-0:30 アルゴリズム※1を考えた
0:30-1:50 コーディング&デバッグ
1:50-2:20
単騎の事を考えおらず、アルゴリズム※2練り直し
2:20-3:00  コーディング&デバッグ
3:00-3:30  提示された4種のサンプルは通ったが、「1112223334445」のように被る場合のことを考えておらずアルゴリズム※3を見直す
3:30-4:30  コーディング&デバッグ

※1 効率化を考え、「ソート後に並んだ2つ(待ち碑と仮定)を取り出してから、チェックしていけばいいんじゃないか」といったもの
※2 頭が出来ていない場合などを考えていなかった。2つ取り出す手法の破錠したので、その場の考えで修正案を。
※3 左端から出来ているのを調べる方法では、被る場合に対処できない。結局、正直に3つの塊を作れるかという考えていくことにした。

反省点
コードを書きながら、アルゴリズムを考えるのではなく、
アルゴリズムを考えてからコードを書いてく手法はよかったが、
考えたアルゴリズムが穴だらけだった。
工夫点は、関数や変数名をわかりやすい名前にしたとか。やっていることが見てわかるような感じにした。

追記・isNormal関数を縮めた。

追記:2011年7月10日
satoshii様のご指摘でソースコードの貼付けにミスがあるのに気が付きました。ありがとうございます!!
オリジナルのソースコードは、「ダウンロード」から
改めて見ると、単騎待ちのチェックの取ってつけた感がすごい。
でも時間制限があるし、しょうがないようね!うん!


import java.awt.Graphics;
import java.awt.Toolkit;
import java.awt.image.BufferedImage;
import java.awt.image.IndexColorModel;
import java.awt.image.MemoryImageSource;
import java.awt.image.Raster;
import java.util.ArrayList;
import java.util.Arrays;

public class Mahjong2 {

	static BufferedImage repairBufferedImage(BufferedImage image) {
	    Raster raster = image.getData();
	    int height = raster.getHeight();
	    int width = raster.getWidth();
	    int datasize = width * height;
	    final int GRAYSIZE = 256;
	    int[] color = new int[4];
	    byte[] pallet_grayscale = new byte[GRAYSIZE];
	    for(int i=0;i<GRAYSIZE;i++) {
	        pallet_grayscale[i] = (byte)i;
	    }
	    IndexColorModel icm = new IndexColorModel(8,GRAYSIZE,pallet_grayscale,pallet_grayscale,pallet_grayscale);
	    byte[] indexout = new byte[datasize];
	    int i = 0;
	    for(int y=0;y<height;y++) {
	        for(int x=0;x<width;x++) {
	            raster.getPixel(x,y,color);
	            indexout[i] = (byte)color[0];
	            i++;
	        }
	    }
	    BufferedImage out = new BufferedImage(width,height,BufferedImage.TYPE_BYTE_INDEXED,icm);
	    Graphics g = out.createGraphics();
	    g.drawImage(Toolkit.getDefaultToolkit().createImage(new MemoryImageSource(width,height,icm,indexout,0,width)),0,0,null);
	    g.dispose();
	    g = null;
	    return(out);
	}

	public static void main(String[] args) {
		String tiles = "1112345678999";
		String[] readyhands = Mahjong2.getReadyHands(tiles);
		for (int i = 0; i < readyhands.length; i++) {
			System.out.println(readyhands[i]);
		}
	}

	/**
	 * 麻雀の手牌が入力として与えられたとき「待ち」を出力する
	 *
	 * @param tiles
	 *            入力の麻雀の手牌
	 * @return
	 */
	static public String[] getReadyHands(String tiles) {
		if (!isNormal(tiles)) {
			return (new String[0]);
		}
		char[] data = getSortingCharacters(tiles).toCharArray();
		ArrayList out = new ArrayList();
		// 隣あった2つが待ちの状態と考えて抜く
		char[] machi = new char[2];
		char[] buffer = new char[data.length - 2];
		for (int i = 0; i < data.length - 1; i++) {
			machi[0] = data[i];
			machi[1] = data[i + 1];
			if (!isMachi(machi)) {
				continue;
			}
			for (int j = 0, k = 0; j < buffer.length; k++) {
				if ((i == k) || (i + 1 == k)) {
					continue;
				}
				buffer[j] = data[k];
				j++;
			}
			String[] memo = new String[4];
			checkMati(buffer, machi, memo, out, 0);
		}
		String[] dst = new String[out.size()];
		for (int i = 0; i < out.size(); i++) {
			dst[i] = out.get(i);
		}
		return (getSortStrings(dst));
	}

	/**
	 * 待ち状態を調べる
	 *
	 * @param tiles
	 * @param machi
	 *            (これがかぶったときは動作しなくてもいいと思う(。・ω・。))
	 * @param memo
	 * @param out
	 *            存在する待ちをここに代入する
	 */
	static private void checkMati(char[] tiles, char[] machi, String[] memo,
			ArrayList out, int depth) {
		char[] tripleset = new char[3];
		char[] nokori;
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				nokori = getRemoveSheungFast(tiles, tripleset, 0);
			} else {
				nokori = getRemovePongFast(tiles, tripleset);
			}
			if (nokori != null) {
				memo[depth] = getString(tripleset);
				if (nokori.length == 2) {
					if (isAtama(nokori)) {
						memo[depth + 1] = getString(nokori);
						String text = getOutput(memo, getString(machi));
						if (!out.contains(text)) {
							out.add(text);
						}
					}
					// 単騎(4枚で調べ直す)
					else {
						String force = getSortingCharacters(getString(nokori)
								+ getString(machi));
						char[] data = force.toCharArray();
						for (int k = 0; k < 3; k++) {
							if (k == 0) {
								nokori = getRemoveSheungFast(data, tripleset, 0);
							} else if (k == 1) {
								nokori = getRemoveSheungFast(data, tripleset, 1);
							} else {
								nokori = getRemovePongFast(data, tripleset);
							}
							if (nokori != null) {
								memo[depth + 1] = getString(tripleset);
								String text = getOutput(memo, getString(nokori));
								if (!out.contains(text)) {
									out.add(text);
								}
							}
						}
					}
				} else {
					checkMati(nokori, machi, memo, out, depth + 1);
				}
			}
		}
	}

	/**
	 * 表示用
	 *
	 * @param in1
	 *            順子・刻子・アタマ
	 * @param in2
	 *            待ち
	 * @return
	 */
	static private String getOutput(String[] in1, String in2) {
		String[] sort = getSortStrings(in1);
		String text = "";
		int j;
		for (j = 0; j < sort.length; j++) {
			text = text.concat("(" + sort[j] + ")");
		}
		text = text.concat("[" + in2 + "]");
		return (text);
	}

	/**
	 * ソートして返す
	 *
	 * @param in
	 * @return
	 */
	static private String[] getSortStrings(String[] in) {
		String[] out = new String[in.length];
		System.arraycopy(in, 0, out, 0, in.length);
		Arrays.sort(out);
		return (out);
	}

	/**
	 * 「待ち」に成りえるかどうか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isMachi(char[] tiles) {
		if (tiles.length == 2) {
			if (Math.abs(tiles[1] - tiles[0]) <= 2) {
				return (true);
			}
		}
		return (false);
	}

	/**
	 * 「頭」に成りえるかどうか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isAtama(char[] tiles) {
		if (tiles.length == 2) {
			if (tiles[0] == tiles[1]) {
				return (true);
			}
		}
		return (false);
	}

	/**
	 * 「順子」があるか調べる。あったら消す。
	 *
	 * @param tiles
	 * @param shuntsu
	 *            消した順子
	 * @param x
	 *            見つかっても無視する回数
	 * @return 順子をぬいたもの
	 */
	static private char[] getRemoveSheungFast(char[] tiles, char[] shuntsu,
			int x) {
		int[] tiletable = new int[9];
		for (int i = 0; i < tiles.length; i++) {
			tiletable[tiles[i] - '1']++;
		}
		boolean isshuntsu = false;
		for (int i = 0, j = 0; i = 1) && (tiletable[i + 1] >= 1)
					&& (tiletable[i + 2] >= 1)) {
				if (j < x) {
					j++;
					continue;
				}
				shuntsu[0] = (char) (i + '1');
				shuntsu[1] = (char) (i + '2');
				shuntsu[2] = (char) (i + '3');
				tiletable[i + 0]--;
				tiletable[i + 1]--;
				tiletable[i + 2]--;
				isshuntsu = true;
				break;
			}
		}
		if (!isshuntsu) {
			return (null);
		}
		return (getCharacters(tiletable));
	}

	/**
	 * 「刻子」があるか調べる。あったら消す。
	 *
	 * @param tiles
	 * @param kotsu
	 *            消した刻子
	 * @return 刻子をぬいたもの
	 */
	static private char[] getRemovePongFast(char[] tiles, char[] kotsu) {
		int[] tiletable = new int[9];
		for (int i = 0; i < tiles.length; i++) {
			tiletable[tiles[i] - '1']++;
		}
		int ispong = -1;
		for (int i = 0; i = 3) {
				ispong = i;
				tiletable[i] -= 3;
				break;
			}
		}
		if (ispong == -1) {
			return (null);
		}
		for (int i = 0; i < 3; i++) {
			kotsu[i] = (char) (ispong + '1');
		}
		return (getCharacters(tiletable));
	}

	/**
	 * テーブル(9種の碑がそれぞれいくつあるか)から文字配列に変換します。
	 *
	 * @param characters
	 * @return
	 */
	static private char[] getCharacters(int[] tiletable) {
		int sum = 0;
		for (int i = 0; i < tiletable.length; i++) {
			sum += tiletable[i];
		}
		char[] out = new char[sum];
		for (int i = 0, k = 0; i < tiletable.length; i++) {
			for (int j = 0; j < tiletable[i]; j++) {
				out[k] = (char) (i + '1');
				k++;
			}
		}
		return (out);
	}

	/**
	 * 文字配列を文字列に変換します。
	 *
	 * @param characters
	 * @return
	 */
	static private String getString(char[] characters) {
		String out = "";
		for (int i = 0; i < characters.length; i++) {
			out = out.concat(String.valueOf(characters[i]));
		}
		return (out);
	}

	/**
	 * 与えられた麻雀の手牌をソートする
	 *
	 * @param tiles
	 * @return
	 */
	static private String getSortingCharacters(String tiles) {
		char[] data = tiles.toCharArray();
		Arrays.sort(data);
		return (getString(data));
	}

	/**
	 * 与えられた麻雀の手牌が条件にそっているか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isNormal(String tiles) {
		return ((tiles.matches("[1-9]{13}")));
	}
}

麻雀の待ち判定問題

投稿日: 更新日:



昨晩は、話題の「あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定」をやってました。
意外に時間がかかって大変でした。
こんな時期にやるんじゃなかった。眠たい。(p_-)

正直3時間ちょっとかかってしまいました。
テンパイ(1113335558888)とチートイツ判定なしです。

以下は、作った後の感想です。

3時間が短いと感じました。
麻雀単語に弱いので調べ物してたのですが、Wikipediaの「麻雀」に「順子」や「刻子」の説明がないのは驚きでした。
ほとんど完成仕掛けの時に、単騎があることに気づき機能を後付けする形になってしまいました。
後付けが汚くなってしまいましたが、重さは考えずに見やすさ(関数化やJavadoc)を考えて作りました。
「順子」や「碑」や「待ち」といった英単語を調べるのが苦労して最終的にローマ字にしました。
みんなの回答を見て、短くまとめている人や、短時間で生成している人など、すごいと思いました。(゜o゜)
「順子」と「刻子」のテーブルを使って一気に計算っていう手など、アイデアもすごい。

さて、コードですが、恥ずかしいので貼りませ……でも、貼っちゃいます。

「1112223334445」と
「2233445566778」がミスるようです。
(123)(234)(234)(11)[45]
(111)(222)(444)(33)[35]
(123)(234)(345)(11)[24]
とかかぶりあ
いすること考えてなかった。

というわけで誤解答例。 続き→「麻雀の待ち判定問題 リベンジ

時間配分については、「麻雀の待ち判定問題 リベンジ」を御覧下さい。


import java.util.ArrayList;
import java.util.Arrays;

public class Mahjong {

	public static void main(String[] args) {
		String tiles = "1112345678999";
		String[] readyhands = Mahjong.getReadyHands(tiles);
		for (int i = 0; i < readyhands.length; i++) {
			System.out.println(readyhands[i]);
		}
	}

	/**
	 * 麻雀の手牌が入力として与えられたとき「待ち」を出力する
	 *
	 * @param tiles
	 *            入力の麻雀の手牌
	 * @return
	 */
	static public String[] getReadyHands(String tiles) {
		if (!isNormal(tiles)) {
			return (new String[0]);
		}
		char[] data = getSortingCharacters(tiles).toCharArray();
		ArrayList out = new ArrayList();
		// 隣あった2つが待ちの状態と考えて抜く
		char[] machi = new char[2];
		char[] buffer = new char[data.length - 2];
		for (int i = 0; i < data.length - 1; i++) {
			machi[0] = data[i];
			machi[1] = data[i + 1];
			if (!isMachi(machi)) {
				continue;
			}
			for (int j = 0, k = 0; j < buffer.length; k++) {
				if ((i == k) || (i + 1 == k)) {
					continue;
				}
				buffer[j] = data[k];
				j++;
			}
			String[] memo = new String[4];
			checkMati(buffer, machi, memo, out, 0);
		}
		String[] dst = new String[out.size()];
		for (int i = 0; i < out.size(); i++) {
			dst[i] = out.get(i);
		}
		return (getSortStrings(dst));
	}

	/**
	 * 待ち状態を調べる
	 *
	 * @param tiles
	 * @param machi
	 *            (これがかぶったときは動作しなくてもいいと思う(。・ω・。))
	 * @param memo
	 * @param out
	 *            存在する待ちをここに代入する
	 */
	static private void checkMati(char[] tiles, char[] machi, String[] memo,
			ArrayList out, int depth) {
		char[] tripleset = new char[3];
		char[] nokori;
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				nokori = getRemoveSheungFast(tiles, tripleset, 0);
			} else {
				nokori = getRemovePongFast(tiles, tripleset);
			}
			if (nokori != null) {
				memo[depth] = getString(tripleset);
				if (nokori.length == 2) {
					if (isAtama(nokori)) {
						memo[depth + 1] = getString(nokori);
						String text = getOutput(memo, getString(machi));
						if (!out.contains(text)) {
							out.add(text);
						}
					}
					// 単騎(4枚で調べ直す)
					else {
						String force = getSortingCharacters(getString(nokori)
								+ getString(machi));
						char[] data = force.toCharArray();
						for (int k = 0; k < 3; k++) {
							if (k == 0) {
								nokori = getRemoveSheungFast(data, tripleset, 0);
							} else if (k == 1) {
								nokori = getRemoveSheungFast(data, tripleset, 1);
							} else {
								nokori = getRemovePongFast(data, tripleset);
							}
							if (nokori != null) {
								memo[depth + 1] = getString(tripleset);
								String text = getOutput(memo, getString(nokori));
								if (!out.contains(text)) {
									out.add(text);
								}
							}
						}
					}
				} else {
					checkMati(nokori, machi, memo, out, depth + 1);
				}
			}
		}
	}

	/**
	 * 表示用
	 *
	 * @param in1
	 *            順子・刻子・アタマ
	 * @param in2
	 *            待ち
	 * @return
	 */
	static private String getOutput(String[] in1, String in2) {
		String[] sort = getSortStrings(in1);
		String text = "";
		int j;
		for (j = 0; j < sort.length; j++) {
			text = text.concat("(" + sort[j] + ")");
		}
		text = text.concat("[" + in2 + "]");
		return (text);
	}

	/**
	 * ソートして返す
	 *
	 * @param in
	 * @return
	 */
	static private String[] getSortStrings(String[] in) {
		String[] out = new String[in.length];
		System.arraycopy(in, 0, out, 0, in.length);
		Arrays.sort(out);
		return (out);
	}

	/**
	 * 「待ち」に成りえるかどうか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isMachi(char[] tiles) {
		if (tiles.length == 2) {
			if (Math.abs(tiles[1] - tiles[0]) <= 2) {
				return (true);
			}
		}
		return (false);
	}

	/**
	 * 「頭」に成りえるかどうか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isAtama(char[] tiles) {
		if (tiles.length == 2) {
			if (tiles[0] == tiles[1]) {
				return (true);
			}
		}
		return (false);
	}

	/**
	 * 「順子」があるか調べる。あったら消す。
	 *
	 * @param tiles
	 * @param shuntsu
	 *            消した順子
	 * @param x
	 *            見つかっても無視する回数
	 * @return 順子をぬいたもの
	 */
	static private char[] getRemoveSheungFast(char[] tiles, char[] shuntsu,
			int x) {
		int[] tiletable = new int[9];
		for (int i = 0; i < tiles.length; i++) {
			tiletable[tiles[i] - '1']++;
		}
		boolean isshuntsu = false;
		for (int i = 0, j = 0; i < tiletable.length - 2; i++) {
			if ((tiletable[i] >= 1) && (tiletable[i + 1] >= 1)
					&& (tiletable[i + 2] >= 1)) {
				if (j < x) {
					j++;
					continue;
				}
				shuntsu[0] = (char) (i + '1');
				shuntsu[1] = (char) (i + '2');
				shuntsu[2] = (char) (i + '3');
				tiletable[i + 0]--;
				tiletable[i + 1]--;
				tiletable[i + 2]--;
				isshuntsu = true;
				break;
			}
		}
		if (!isshuntsu) {
			return (null);
		}
		return (getCharacters(tiletable));
	}

	/**
	 * 「刻子」があるか調べる。あったら消す。
	 *
	 * @param tiles
	 * @param kotsu
	 *            消した刻子
	 * @return 刻子をぬいたもの
	 */
	static private char[] getRemovePongFast(char[] tiles, char[] kotsu) {
		int[] tiletable = new int[9];
		for (int i = 0; i < tiles.length; i++) {
			tiletable[tiles[i] - '1']++;
		}
		int ispong = -1;
		for (int i = 0; i < tiletable.length; i++) {
if (tiletable[i] >= 3) {
				ispong = i;
				tiletable[i] -= 3;
				break;
			}
		}
		if (ispong == -1) {
			return (null);
		}
		for (int i = 0; i < 3; i++) {
			kotsu[i] = (char) (ispong + '1');
		}
		return (getCharacters(tiletable));
	}

	/**
	 * テーブル(9種の碑がそれぞれいくつあるか)から文字配列に変換します。
	 *
	 * @param characters
	 * @return
	 */
	static private char[] getCharacters(int[] tiletable) {
		int sum = 0;
		for (int i = 0; i < tiletable.length; i++) {
			sum += tiletable[i];
		}
		char[] out = new char[sum];
		for (int i = 0, k = 0; i < tiletable.length; i++) {
			for (int j = 0; j < tiletable[i]; j++) {
				out[k] = (char) (i + '1');
				k++;
			}
		}
		return (out);
	}

	/**
	 * 文字配列を文字列に変換します。
	 *
	 * @param characters
	 * @return
	 */
	static private String getString(char[] characters) {
		String out = "";
		for (int i = 0; i < characters.length; i++) {
			out = out.concat(String.valueOf(characters[i]));
		}
		return (out);
	}

	/**
	 * 与えられた麻雀の手牌をソートする
	 *
	 * @param tiles
	 * @return
	 */
	static private String getSortingCharacters(String tiles) {
		char[] data = tiles.toCharArray();
		Arrays.sort(data);
		return (getString(data));
	}

	/**
	 * 与えられた麻雀の手牌が条件にそっているか調べる。
	 *
	 * @param tiles
	 * @return
	 */
	static private boolean isNormal(String tiles) {
		tiles = tiles.replaceAll(" ", "");
		if (tiles.length() != 13) {
			return (false);
		}
		char[] data = tiles.toCharArray();
		boolean isnormal = true;
		for (int i = 0; i < data.length; i++) {
			if ((data[i] < '1') && ('9' < data[i])) {
				isnormal = false;
				break;
			}
		}
		return (isnormal);
	}
}

そういえばACM-ICPC 2008

投稿日: 更新日:


去年、つーささんのブログを見てACM-ICPCという面白そうな企画があることを知った。
 
そして今年は、初めてACM-ICPCに出場した。
うちも、一応それ系のサークル、何かを残さないとと思ったわけだ。
 
6月1日ぐらいから準備してたんだけど、チームの登録やら色々で、
結局登録確認できたのは、6月18日ぐらい。
登録するのに2週間以上掛かるとは思わなかった。締め切りぎりぎり。
学校のほうにも申請したり色々大変だし。
 
英語苦手な私が、何度も英語で、マネージャーのMarsha Poucherさんと連絡した。
翻訳ソフトで「すいません」が当たり前だが「I’m sorry」となる。
しかし、「Excuse me」が自然であることを知った。
 
締め切り過ぎた後は、なぜか締切日が伸びてたのが気になった。
多分、他のグループも色々あったんだろうなあ^^
 
ちなみにグループで集まったのは、
というかムリヤリ誘ったのは情報得意な2年の人aaさんと、
プログラミング経験がある3年の人bbさん。
どちらもサークルの人。うん。
aaさんは高校の頃も、それ関連の大会出たらしくて心強い。
 
んで、本番の2日前、7/2にaaさんが大事な用事のために、本番に出席できないことを知らされる。
うん。あせった。今度は日本支部のほうと何度も連絡取り合った。
2人で参加していいかとか、代理はどのようにすればいいとか。
 
代理とかそこまで考えていなかった。
大会の人からも、2人参加は禁止。補欠は6/20まで、情報更新は6/25までという回答。
完全に終わったかにみえた。
 
でも、正当な理由があるなら考慮するという回答も。
本当はとても大変で、滅多にないことかもしれないけど、
大会当日7/4になんとか選手の変更を行うことが出来た。
今度も半ムリヤリ誘った、プログラミング経験はない新入生の人。
 
パソコンは、木曜日にクリーンインストールして、VC++2008入れて
金曜日の昼に大会のために借りた部屋運んでもらった。みんなありがとう。
 
4問、又は高速で3問解く、という目標でついに本番がきた。
でもbbさんは実験で1時間遅れるらしい。
無理に誘ったものだし、大事な実験なので仕方がない。
 
まず落ち着いて大会のページへ。
って表示されねーよ。模擬練習会でも重かったけど、ここまで重くはなかった。
5分ぐらいでやっと表示。(後から5分延長が知らされた)
 
とにかくまず印刷し、簡単なものから手をつけはじめた。
 
A問題
これ総当りでいけば楽勝とか思ったけど、
結局それっぽいアルゴリズム書いて提出。Correct Answer。
 
B問題
なんか日本語がやばい。とにかく白紙の紙に、分かったことをメモしていく。
どうやら素数関連の問題。
エラトステネスのふるいでインプット通す前に、素数表の作成で楽勝だった。
ただ、Input1つに対して、素因数分解していき、最低いくつで分解できるかのようなプログラム書いちゃって
(実際はどのような素因数で作ることが出来るか)
サンプルとはもちろん合わなく、修正。ちょっと時間のロスしました。この時点で50分ぐらいかな。
これCorrect Answerしたころに、当初のメンバーbbさん登場。
 
C問題
bbさんがこれ簡単じゃんっていってた。
確かに問題としては簡単。真理値表もそれようのテーブル作っておけばいいし。
しかしInputが面倒。スタックは、なんとなく苦手。
模擬練習会でCの文字関連問題、もう少しということで時間切れになったという、
いい思いでなかったので、俺は手をつけなかった。うん。bbさんガンバレ!
 
D問題
時間的に無理だろこれ^^;
たいてい問題文が短いほど難しいという練習から色々あって。
とにかくこれ計算時間やばくね?とかで後回し^^
 
E問題
結局自分はこれといてた。
直線を引いて、4つの点を1グループと考えた時に、
1グループの各4点と、直線との距離で一番短い距離を考える。
一番短い距離の場合で、(a)の場合、(b)の場合で場合わけ。
これで楽勝と思って作ったらサンプル通らない。
線分と直線を考えていなかったことが分かったので、それ修正。通らない。
あ、四角形が、線分またいでたら進めないジャン。
 
終了ー。
多分予選通過は無理ということではい。
 
来年は、もう私は出れないので、OBに回って新入生を鍛えようと思います^^
 
同年代のHSPの師匠つーささんに会いたかったZE。

Fizz-Buzz問題だそうです

投稿日: 更新日:


今日はネットでFizz-Buzz問題というものを見つけた。
どうしてプログラマに・・・プログラムが書けないのか?

http://www.aoky.net/articles/jeff_atwood/why_cant_programmers_program.htm

>かなりの試行錯誤の末に、コードを書こうともがいている人たちというのは、
>単に大きな問題に対して苦労しているのではないことがわかった。
>やや小さな問題(連結リストを実装するというような)に対して苦労するということでさえない。
>彼らはまったくちっぽけな問題に苦労しているのだ。
>
>それで、そういった類の開発者を見分けるための質問を作り始め、
>私が「Fizz-Buzz問題」と呼んでいる問題のクラスを考え出した。
>これはイギリスの学校の子供たちがよくやっている遊び(というかやらされている遊び)にちなんで名付けた。
>Fizz-Buzz問題の例はこんな感じだ。
>
>1から100までの数をプリントするプログラムを書け。
>ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、
>3と5両方の倍数の場合には「FizzBuzz」とプリントすること。
うん。
実際に適当考えてみた^^
単純な問題なんだけど、どうすれば短くなるのか、効率よく作れるか、とか考えるのが面白い。
まず得意なHSP ^^
#runtime "hsp3cl.hrt"
for i,1,101,1:t="":f="":if i\3=0:t="Fizz"
if i\5=0:f="Buzz"
if t=""&f="":mes i:else:mes t+f
next

Size:122
Statistics:0B / 68B / 38B

次は1年間がんばったC ^^
#include <stdio.h>
main(){int i;for(i=1;i<101;i++){if(!!(i%3)&!!(i%5)){printf("%d\n",i);}else{printf("%s%s\n",i%3?"":"Fizz",i%5?"":"Buzz");}}}

Size:143
Statistics:0B / 71B / 68B

ここでみんなが投稿したコードのサイズや早さが見えるんだけど、

GolfScriptっていうのが、すごいファイルサイズ短くて気になった。Rubyで作られてるらしい

ちなみにサイズとか測るのはこんな感じで作ってみた。
p = "C:/****":exist p:i = strsize
sdim b,i:bload p,b,i:repeat i:n=peek(b,cnt)
if ' '=n|'\t'=n|$d=n|$a=n:else:if '/'<n&n<':'|'@'<n&n<'['|'`'<n&n<'{':a++:else:s++
loop:mes "Size:"+i:mes "Statistics:0B / "+a+"B / "+s+"B"

ところで

>実際的な問題を解くのに再帰が使えない候補者をたくさん面接してきた。
>これらは基本的なスキルであり、それを欠いた人に多くのプログラミング経験があるとは思えない。

って書いてあるけど、再帰は結構、苦手。再帰で応用とかかなり頭つかって面倒。
7月の最初までにはコツみたいなの勉強しておきたい。と書きつつ、しないと思うけど^^;

風来のシレン64

投稿日: 更新日:


久しぶりのgameカテゴリです^^
風来のシレン2、2度目のシレン城完成~鬼ケ島クリア。今回は簡単な制限プレイ。

制限プレイ (材料集めから鬼ケ島クリアまで全て)

  • 持込禁止・倉庫使用禁止・稽古禁止
  • 引き上げの巻物・持ち帰りの巻物使用禁止
  • NPCはイベント上強制的に仲間になる以外禁止(アスカ・キララ・マーモ・リク・ヒマキチ、それぞれ1回ずつ)
上級の女王と3階あたりで、計2回死亡。
まさか鬼の親分が毒草・火炎草・聖域全部使いものにならないとは。うん。
最後、特性おにぎりで全回復してなんとか持込不可の鬼ケ島は一発クリア。