プログラマメモ2 - programmer no memo2

目次

poj 解けない問題 2007/09/29

解けない問題を記録しておきます。

2819 数学の知識か...

poj 2506 - A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2] 2007/09/28

2506 -- Tiling

うーん、こういう問題をさくっと解くためにはどういうアプローチでいけばいいんだろう。

ヒントになるかな
フィボナッチ数 - Wikipedia
代数的組合せ論
ドミノタイリング
とかかかな。

解答が思いつかなかったので、いつものごとくdiscussをチラ見して、

A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2]


をみつけていろいろためして、正しそうな答えがでてきたので、submitしたのだけど、WA(Wrong Answer)。

それでdiscussをチラ見したら、inputが0の時の解答がミソっぽい。0がinputの時、１をoutputしたらacceptされた。

うーん、よくわからない....

static BigInteger f(int n) {
// A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2]
final BigInteger TWO = BigInteger.valueOf(2);
BigInteger a1 = BigInteger.ONE;
BigInteger a2 = BigInteger.valueOf(3);
if (n == 0)
return BigInteger.ONE;
if (n == 1)
return a1;
if (n == 2)
return a2;
for (int i = 2; i < n; i++) {
BigInteger tmp = a2.add(TWO.multiply(a1));
a1 = a2;
a2 = tmp;
}

return a2;
}

ファイル連番っぽいのとマッチ 2007/09/28

(.*)\\.txt(|\\.[0-9]*)$

aaaaaa.txt.1とかそういうファイルにマッチします。
へんかな。

groovyでListとMapの初期化 2007/09/25

list = []
map = [:]

簡単だ。

jarsignerメモ 2007/09/25

jar cvf ../my.jar .

jarsigner -keystore keystore -storepass password
-keypass password my.jar "My Alias"

ax+byの形であらわされない最大の数は 2007/09/25

ab-a-b

だそうです。

互いに素な２つの自然数aとbがあるとき、ab-a-bより大きなすべての自然数は０以上の整数xとyを使ってax+byの形に表せる。また、ab-a-bはこの形に表せない。チャレンジ!整数の問題100


なるほど。

evaluateを使ってみた。 2007/09/25

evaluateを使うと文字列を実行できる。
入力してもらった値を直接使うとかできる。

def s = "['OK':'o_o!']"

evaluate("val = ${ s }")

println val

poj 1032 2007/09/24

1032 -- Parliament


何となく再帰っぽいプログラムをしていたら、1000でやはり処理が帰ってこなくなって自力で解くのをあきらめた。

参考
1032 Parliament

規則をみつけてコードにしたほうがよいようだ。

poj 1811 ちょっと考えた。 2007/09/21

1811 -- Prime Test

素数を扱う問題だったので、なんとなくできるかなと思ったのが運のツキで、かなりてこずりました。
まず、だいいちに自分に数学の知識がないことが原因だと思いましたが、javaで解く場合には、大きな数の素数を判定する方法はjavaのほうで用意されているおり、あとは、最小の約数（素数の）を求めるところがキモのようです。

この問題を解くための基本のアイデアはあったのに、時間超過で泣かされて、もう少しもう少しとやり続けてかなりの時間の睡眠時間を削りました。

参考
Cozy Ozy - ハマッタ(;´д｀)
にあるように

(1)
素数判定
(2)
小さい素数で割り続けて判定

という流れは変わらずです。
（２）でいかに効率的にするかがキモだと思います。


で、実は、素数の判定が遅いからだめだと信じきって(javaの実装はだめだと信じきって)いろいろ素数判定のためのコードをみつけてきてはためしたのですが、もちろんはやければはやいほどいいのですが、（２）を劇的にはやくすることはできませんでした。

（２）をどういうふうに効率よくおこなうかといいますと、素数で割ればいいのですから、素数テーブルをもたせればよい、というのもありますが、簡単なのは、奇数のみで、割ること、つぎに奇数でなおかつ素数である可能性が高そうな値で割ること、に専念すればよしです。

12章 素因数分解アルゴリズムをみたら、あーなるほどでした。



30n＋１、30n＋７、30n＋11、30n＋13、30n＋17、30n＋19、30n＋23、30n＋29
12章 素因数分解アルゴリズム


ある意味、簡単かもしれませんね...

javaを使う場合は、直接の素数の判定はBigIntegerの実装を使い、（２）を解くための実装は上記のアルゴリズムでいけばOKです。


素数関連
ミラー-ラビン素数判定法 - Wikipedia
The Las Vegas algorithm/method at DataStructures
18446744073709551615
ポラード・ロー素因数分解法 - Wikipedia
The Prime Database: The List of Largest Known Primes Home Page
PollardRho.java
〜プログラム@Bal4u〜: 素数の判定 （ペパン判定法）　pepan
〜プログラム@Bal4u〜: 素数判定 Miller-Rabinテスト

poj 1811 - Time Limit Exceededで泣かされた。 2007/09/21

pojの1811で、すごく時間を費やしました。
http://acm.pku.edu.cn/JudgeOnline/status?problem_id=1811&user_id=nakawaka&result=&language=

昨日の夜中、あきらめて寝る直前に、
12章 素因数分解アルゴリズム
というページをみて、基本的なアイデアを思い浮かべてねた。

で、会社のお昼休みに
アイデアをコードにして、半ばあきらめもーどでサブミットしたら通った。

うれしい。

groovyのSpreadMapの実装について 2007/09/20

H氏に指摘されて、はじめきがつかなかったけど、やはり危険だなと思いました。

SpreadMap

引数の配列の数が奇数の場合、java.lang.ArrayIndexOutOfBoundsException
が容易に発生します。

そもそも、どういった目的のクラスなのかわかってないのですが。。。

public SpreadMap(Object[] values) {

super();

mapData = new HashMap(values.length / 2);

int i = 0;

while (i < values.length) {

mapData.put(values[i++], values[i++]);

}

}

goovy.sh かっこわるいけど、とりあえず 2007/09/20
2008/01/20

Groovy - Running

groovy.lang.GroovyShell
にファイルをわたせればよいのですね。

前半部分は、groovyにあったコードを拝借。

#!/bin/sh
# Determine the Java command to use to start the JVM.
if [ -z "$JAVACMD" ] ; then
if [ -n "$JAVA_HOME" ] ; then
if [ -x "$JAVA_HOME/jre/sh/java" ] ; then
# IBM's JDK on AIX uses strange locations for the executables
JAVACMD="$JAVA_HOME/jre/sh/java"
else
JAVACMD="$JAVA_HOME/bin/java"
fi
else
JAVACMD="java"
fi
fi
if [ ! -x "$JAVACMD" ] ; then
die "JAVA_HOME is not defined correctly, can not execute: $JAVACMD"
fi
if [ -z "$JAVA_HOME" ] ; then
warn "JAVA_HOME environment variable is not set"
fi
export CLASSPATH="$JAVA_HOME"/lib/tools.jar
#echo $0
R=`cd ..;pwd`"/lib"
#echo $R
export TARGET_DIR=$R
if [ -d "$TARGET_DIR" ]; then
for i in "$TARGET_DIR"/*.jar; do
CLASSPATH="$CLASSPATH":"$i"
done
fi
export CLASSPATH=$CLASSPATH
STARTER_MAIN_CLASS=groovy.lang.GroovyShell
CLASS=$1
shift
echo $CLASS
exec "$JAVACMD" $JAVA_OPTS \
-classpath "$CLASSPATH" \
$STARTER_MAIN_CLASS \
$CLASS \
"$@"
#echo $CLASSPATH


追記
この実装だと、bin以外のとこでうごかそうとするとだめですね。

下記のコードで修正
DIRNAME=`dirname "$0"`
R=`cd "$DIRNAME";cd ..;pwd`"/lib"

DecimalFormat の四捨五入？ 2007/09/20

DecimalFormat format = new DecimalFormat("00");
double d = 0.6;
d = 0.1;
System.out.println(d + ":" + format.format(d));
d = 0.5;
System.out.println(d + ":" + format.format(d));
d = 0.55;
System.out.println(d + ":" + format.format(d));
d = 0.545;
System.out.println(d + ":" + format.format(d));
d = 0.5445;
System.out.println(d + ":" + format.format(d));
d = 0.59;
System.out.println(d + ":" + format.format(d));
d = 0.59;
System.out.println(d + ":" + format.format(d));


小数点以下を切り捨てるわけではないことに注意！！

poj 1256 あなぐらむ 2007/09/18

へっぽこだけど記録のために公開。

メソッド名とうがとても適当。

はじめ、富豪的にコードかいて(TreeSetとか使って)、なんとなくだめだろうなぁと思いつつ、案の定だめで、
メモリーが足りないがでて、つぎに、時間がたりないがでて、最後に答えがまちがっているがでて、へこんで、
ソートの順序に工夫が必要なことに気がついて、ソートどうしようかなぁと悩んで、解答例をちら見して、見たことに後悔しつつ、Comparatorを使う方向でコードを書いてようやくsubmitされた。

しかし、意味不明な感じのコードになったなぁ。


package p1256;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
for (; 0 < n; n--) {
String line = scanner.nextLine();
char[] cs = line.toCharArray();
Character[] characters = new Character[cs.length];
for (int i = 0; i < characters.length; i++) {
characters[i] = cs[i];
}

Arrays.sort(characters, new Comparator<Character>() {

public int compare(Character o1, Character o2) {
char[] cs = { 'z', 'Z', 'y', 'Y', 'x', 'X', 'w', 'W', 'v',
'V', 'u', 'U', 't', 'T', 's', 'S', 'r', 'R', 'q',
'Q', 'p', 'P', 'o', 'O', 'n', 'N', 'm', 'M', 'l',
'L', 'k', 'K', 'j', 'J', 'i', 'I', 'h', 'H', 'g',
'G', 'f', 'F', 'e', 'E', 'd', 'D', 'c', 'C', 'b',
'B', 'a', 'A', };
char c1 = o1.charValue();
char c2 = o2.charValue();
int p1 = 0;
int p2 = 0;
for (int i = 0; i < cs.length; i++) {
if (cs[i] == c1) {
p1 = i;
}
if (cs[i] == c2) {
p2 = i;
}
}

return p2 - p1;

}
});

for (int i = 0; i < cs.length; i++) {
cs[i] = characters[i];
}

c1(cs);
}

}

static void c1(final char[] cs) {

char pre = (char) -1;

for (int i = 0; i < cs.length; i++) {
char c = cs[i];
if (pre == c) {
continue;
}
pre = c;

char[] ds = ccc(cs, i);
c(new char[] { c }, ds);
}

return;
}

static void c(char[] pc, char[] cs) {
if (cs.length == 0) {
System.out.println(new String(pc));
return;
}

char pre = (char) -1;
for (int i = 0; i < cs.length; i++) {
char c = cs[i];
if (pre == c) {
continue;
}
pre = c;
char[] ds = ccc(cs, i);

c(ddd(pc, c), ds);
}

}

static char[] ccc(char[] cs, int ep) {
char[] cs2 = new char[cs.length - 1];
int j = 0;
for (int i = 0; i < cs.length; i++) {
if (i != ep) {
cs2[j++] = cs[i];
}

}
return cs2;
}

static char[] ddd(char[] p, char c) {
char[] ds = new char[p.length + 1];
System.arraycopy(p, 0, ds, 0, p.length);
ds[ds.length - 1] = c;
return ds;

}
}

小数点以下に値があるか調べる方法 2007/09/18

小数点以下に値があるか調べるまたひとつの方法

H氏のコードをベースにしてメソッド化

static public boolean hasDecimalPart(BigDecimal bdx) {
BigDecimal reflectbdx = new BigDecimal(bdx.toBigInteger());
if (0 == reflectbdx.compareTo(bdx)) {
return false;
}
return true;
}

jxpath xmlns - ナントナクワカッタ 2007/09/18

jxpathです。

ルートのタグにxmlnsがある場合の、使用方法

不正確です。

ネームスペースが指定されている場合の注意点。


<?xml version="1.0" encoding="UTF-8"?>
<aaa xmlns='http://xxxx/'>
<a>OKAAAA</a>
</aaa>

って感じのXMLがある場合、

JXPathContextに
context.registerNamespace("A", "http://xxxx/");
って感じのことをしてXPathを記述する。

こんな感じ、
context.getValue("/A:aaa/A:a")

ネームスペースしないと例外でます。

poj 1007 2007/09/17

1007 -- DNA Sorting
バブルソート

ソートのカウントはバブルソートで。

このサブミットでようやく３７個終了。
簡単なもの（自分で解けるか、解答例があるもの）しか解いてないので、だめだめなんだけど。

package p1007;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
int n = scanner.nextInt();
List<DNAString> list = new ArrayList<DNAString>();
scanner.nextLine();
for (; 0 < n; n--) {
String line = scanner.nextLine();
list.add(new DNAString(line));
}

Collections.sort(list);
Iterator<DNAString> iterable = list.iterator();
while (iterable.hasNext()) {
System.out.println(iterable.next());

}
}

static class DNAString implements Comparable<Object> {
Integer d;
String s;

public DNAString(String s) {
this.s = s;
d = sort_count(s.toCharArray());
}

public int compareTo(Object o) {
return d.compareTo(((DNAString) o).d);
}

public String toString() {
return this.s;
}
}

static int sort_count(char[] cs) {
int cnt = 0;

for (int i = 0; i < cs.length - 1; i++) {

for (int j = cs.length - 1; j > i; j--) {

if (cs[j] < cs[j - 1]) {
char t = cs[j];
cs[j] = cs[j - 1];
cs[j - 1] = t;
cnt++;
}
}
}
return cnt;
}
}

Filthy Rich Clients: Developing Animated & Graphical Effects for Desktop Java Applications (The Java Series) - 買いました。 2007/09/17

0132413930Filthy Rich Clients: Developing Animated & Graphical Effects for Desktop Java Applications (The Java Series)
Chet Haase Romain Guy
Prentice Hall Ptr 2007-08-03

by G-Tools


買いました。

gcd 練習 2007/09/17

package gmc;

import java.math.BigInteger;

public class Test {

public static void main(String[] args) {

for (int i = 0; i < 10; i++) {
int m = (int) (Math.random() * 1000000);
int n = (int) (Math.random() * 1000000);

System.out.printf("%d: m=%d n=%d %s %n", i, m, n,
(gcd(m, n) == gcd_o(m, n)));

// System.out.println(gcd(m, n));
// System.out.println(gcd_r(m, n));
// System.out.println(gcd_o(m, n));

}
}

/**
* n,mに対して剰余の演算を行うことができる<br>
*
* 1. 入力をm,nとする。 <br>
* 2. nが0なら、mを出力してアルゴリズムを終了する。<br>
* 3. nがmを割り切るなら、nを出力してアルゴリズムを終了する。 <br>
* 4. そうでないなら、mをnで割った余りを新たにmとし、更にmとnを取り替えて3に戻る。<br>
*
*/
static int gcd(int m, int n) {
int state = 1;
while (true) {

switch (state) {

case 1:
if (m < n) {
int tmp = m;
m = n;
n = tmp;
}
case 2:
if (n == 0)
return m;
case 3:
int r = m % n;
if (r == 0)
return n;
m = n;
n = r;
state = 3;
}
}
}

static int gcd_r(int m, int n) {
if (m < n)
return gcd(n, m);
if (n == 0)
return m;
int r = m % n;
if (r == 0)
return n;
return gcd(n, r);
}

static public int gcd_o(int m, int n) {
return gcd(BigInteger.valueOf(m), BigInteger.valueOf(n)).intValue();
}

static public BigInteger gcd(BigInteger l, BigInteger r) {
return l.gcd(r);
}

}

ユークリッドの互除法 2007/09/16

ユークリッドの互除法 - Wikipedia

wikipediaに載っていたアルゴリズムをコードにしてみました。

ユークリッドの互除法

static int gcd(int m, int n) {
if (m < n)
return gcd(n, m);
if (n == 0)
return m;
int r = m % n;
if (r == 0)
return n;
// mをnで割った余りを新たにmとし、更にmとnを取り替えて3に戻る
return gcd(n, r);
}

poj 1917 でわかったことは＼にきおつけろ 2007/09/16

1917 -- Automatic Poetry

簡単そうだったのでチャレンジ。

なんとなくできたので、submitするとruntime errorばかし。
理由がわからず、仕方がないので、たまたまみつけた、コードをsubmitするとacceptされた。

MyWiki.jp - PKU Wiki - 1917 Automatic Poetry

自分のコードがよくないのはわかった。

で、いろいろサブミットして実験した結果、どうも正規表現のエスケープ文字で使っていた￥がいけないらしかった。

環境はmac osxでeclipse
作成手順はeclipseでコード書いて、それをコピーしてブラウザで貼付けていたのだけど、eclipseでの入力時にoption+￥で＼にしないとだめなようだ。

うーん、かなりへこんだ。

下記サイトの区分が参考になりそう。
易しい問題でコード量が少ない問題にチャレンジしようと思う。
MyWiki.jp - PKU Wiki - 分野別重要問題集

poj 2602 Superlong sums 2007/09/16
2007/09/16

Superlong sums
Cozy Ozy - Superlong sums(0)
Super_long_sums

はじめ、読み取った数字をStringBuilderにアペンドして最後にそれをBigIntegerにして計算させていました。
自分で実行させてみて計算できたので、submitしたのですが、やはりだめ。

問題文には、「1<=N<=1000000」とあるので、実験してみて、たしかに「1<=N<=1000000」な文字列からBigIntegerに直すにはそれなりのコストがかかっているようだったので、はじめのアイデアはボツ。


思いつかなかったので、shortcoderな方のサイトをみていて、char[]の配列を使っていたので、なんとなくその方向性でいくことにした。

変なところで、はまったのは問題文には、「the length of their sum does not exceed N」とあったことに気がつかず、足したら桁が増えるということを気にしてコードを書いていたこと。

最後に、Time Limit Exceededがでるようになった。で、悩んだあげく、Scannerを使っていたのをやめて、StreamTokenizerを使用したら、ようやくacceptedされた。

無駄な部分が多々ありますが、とりあえずコード。

コードは三つのパートに分かれてます。
１。入力読み取り
２。計算
３。出力のためにStringBuilderにつめてます。

package p2602;

import java.io.IOException;
import java.io.StreamTokenizer;

public class Main {
public static void main(String[] args) throws IOException {

//Scanner scanner = new Scanner(System.in);
StreamTokenizer tokenizer = new StreamTokenizer(System.in);
tokenizer.nextToken();
int n = (int)tokenizer.nval;

byte[] bs = new byte[n];
for (int i = 0; i < n; i++) {
tokenizer.nextToken();
int i1 = (int)tokenizer.nval;
tokenizer.nextToken();
int i2 = (int)tokenizer.nval;
bs[i] = (byte) (i1+ i2);
}

for (int i = bs.length - 1; 0 < i; i--) {
if (1 <= ((int) bs[i] / 10)) {
bs[i - 1]++;
bs[i] = (byte) ((int) bs[i] % 10);
}
}

StringBuilder sb = new StringBuilder();
for (int b : bs) {
sb.append(b);
}

System.out.println(sb);
}

}

階乗 2007/09/16

Cozy Ozy - Sum of Factorials(1)
1775 -- Sum of Factorials
階乗の計算

static int factorial(int n) {
int r = 1;
// for (int i = 1; i <= n; i++) {
// r = r * i;
// }
for (r = 1; n != 0; r *= n--)
;
return r;
}

Programming Collective Intelligence: Building Smart Web 2.0 Applications - 購入 2007/09/16

0596529325Programming Collective Intelligence: Building Smart Web 2.0 Applications
Toby Segaran
Oreilly & Associates Inc 2007-08

by G-Tools


本屋でみかけて、おもしろそうだと思いアマゾンで購入。
洋書の場合、買ってもすぐに読まない（読めない）ので、アマゾンで買ってもいいかな。

webはデータの宝庫だけで、それをどう扱っていくのかに興味があります。

素数判定 2007/09/15

pojでacceptされるためにはやいほうがよいようなので、ちょっと計測してみました。
マシンは、macbookでeclipse上での実行です。

calc:[2813]ms
BigInteger ver:[7337]ms
calc:[2790]ms
BigInteger ver:[7210]ms
same result?:true

わかりづらいですが、
calcのほうが自分で実装したもの、BigIntegerがisProbablePrimeメソッドを利用したものです。

数が大きい場合、
BigIntegerのisProbablePrimeを使用する場合、引数のcertaintyを少なくすると早くなるけど、精度が悪くなります。


コードは以下

package p2262;

import java.math.BigInteger;

public class Test2 {

public static void main(String[] args) {
int loop = 1000000;
a(loop);
b(loop);
a(loop);
b(loop);
System.out.println("same result?:" + checkLogic(loop));
}

static boolean checkLogic(int loop) {
for (int i = loop; 1 < i; i--) {
if (isPrime_1(i) != isPrime_2(i)) {
System.out.println("val:"+i);
return false;
}

}
return true;
}

static void a(int loop) {
long start = 0;
start = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
isPrime_2(i);

}
System.out.println("calc:[" + (System.currentTimeMillis() - start)
+ "]ms");
}

static void b(int loop) {
long start = 0;
start = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
isPrime_1(i);

}
System.out.println("BigInteger ver:["
+ (System.currentTimeMillis() - start) + "]ms");
}

static boolean isPrime_1(int p) {
return BigInteger.valueOf(p).isProbablePrime(10);
}

static boolean isPrime_2(int n) {
int i;
for (i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}

}

poj 2262 Goldbach's Conjecture 2007/09/15

2262 -- Goldbach's Conjecture

ゴールドバッハの予想 - Wikipedia

解き方がすぐにおもいつかなかったので、discussをチラ見して、すぐにコードを書いて、submitしたのですが、時間切れでacceptされず。

何度もためしてもだめ。

それで、C++のコードをみつけてコピーして試したら、あっさり、acceptされたので、悩みました。

isPrimeというメソッドを作成して素数判定していたのですが、やはりそれが遅かったです。

はじめの実装は、

static boolean isPrime_1(int p) {
return BigInteger.valueOf(p).isProbablePrime(10);
}

でした。

ちなみにjavadocの説明は、
この BigInteger が素数である可能性が高い場合は true を返し、必ず合成数である場合は false を返します。certainty が 0 以下である場合、true を返します。

パラメータ:
certainty - 呼び出し側が許容しない確率の尺度。この BigInteger が素数である確率が (1 - 1/2certainty) を超える場合は true を返す。実行時間はこのパラメータの値に比例する
戻り値:
この BigInteger が素数である可能性が高い場合は true、必ず合成数である場合は false


次に、これを変更したら時間超過で失敗せずにacceptされました。

変更後の実装は、
static boolean isPrime(int n) {
int i;
for (i = 2; i <= Math.sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}

poj 1656 2007/09/15

現在、Acceptedが多い問題で悩まずできそうな問題にチャレンジ中。

1656 -- Counting Black

こんな問題だと計算量とか考慮に入れないですむので、自分的には楽なのだけど。


package p1656;

import java.io.IOException;
import java.util.Scanner;

public class Main {

public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int x, y, l;
int[][] g = new int[100][100];

for (int i = 0; i < n; i++) {
String s = scanner.next();
x = scanner.nextInt() - 1;
y = scanner.nextInt() - 1;
l = scanner.nextInt();

if ("BLACK".equals(s)) {
black(g, x, y, l);
continue;
}

if ("WHITE".equals(s)) {
white(g, x, y, l);
continue;
}

if ("TEST".equals(s)) {
System.out.println(countBlack(g, x, y, l));
continue;
}
}

}

static void black(int[][] g, int x, int y, int l) {
for (int i = x; i < (x + l); i++) {
for (int j = y; j < (y + l); j++) {
g[i][j] = 1;
}
}
}

static void white(int[][] g, int x, int y, int l) {
for (int i = x; i < (x + l); i++) {
for (int j = y; j < (y + l); j++) {
g[i][j] = 0;
}
}
}

static int countBlack(int[][] g, int x, int y, int l) {
int count = 0;
for (int i = x; i < (x + l); i++) {
for (int j = y; j < (y + l); j++) {
if (g[i][j] == 1) {
count += 1;
}
}
}
return count;
}

}

poj 1844 2007/09/15

poj 1844です。

1844 -- Sum

はじめは、自力で解こうとして、やってました。
それで、なんとなく解答できるコードをつくったのですが、うう、やはり、10000とか100000とかで、答えが返ってこないOrz...

うーん、やはりこれはアルゴリズム！？を勉強しないといけないですね。

こういった問題苦手です。

package p1844;

import java.io.IOException;
import java.util.Scanner;

public class Main {

public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int i;
int sum = 0;
for (i = 1; sum < n || ((sum - n) % 2 == 1); i++)
sum += i;

System.out.println(i - 1);

}

}

poj 1146 - ID Codes 2007/09/13

1146 -- ID Codes

この問題の解法が知りたい。。。

ネットでpascalでかかれたコードを読み解きながら、なんとかjavaにしてみて、ようやくサブミットできた。

書き散らしたコードだけど公開しておきます。

package p1146;

import java.io.IOException;
import java.util.Scanner;

//abaacb
//cbbaa
//a
//cab
//abcd
//acbb
//azyxwvutsrqpppooonnnmmmlllkkkjjjiiihhhgfedcccbbaaa

//ababac
//No Successor
//No Successor
//cba
//abdc
//babc
//baaaabcccdefghhhiiijjjkkklllmmmnnnooopppqrstuvwxyz
public class Main {

public static void main(String[] args) throws IOException {

Scanner scanner = new Scanner(System.in);

while (true) {
String s = scanner.next();
if ("#".equals(s))
break;
int len, i, j;
char x;
char[] line = s.toCharArray();

len = line.length;
i = len;

do {
i = i - 1;
x = line[i];
j = i - 1;
while (-1 < j && x <= line[j]) {
j = j - 1;
}
// System.err.println("j==" + j + " i==" + i + " x==" + x);
} while (!(-1 < j || i == 0));

// for (i = len - 1; 0 < i && line[i - 1] >= line[i]; i--);
//System.err.println("j==" + j + " i==" + i + " x==" + x);
if (j == -1) {
System.out.println("No Successor");
continue;
}

// String leftPart = s.substring(0, j);
// System.out.print(leftPart);
//System.out.print("[");
for (int k = 0; k < j; k++)
System.out.print(line[k]);
//System.out.print("]");
//System.out.print("[");
System.out.print(x);
//System.out.print("]");

String rightPart = omit(s, i);

System.out.print(a(rightPart.substring(j, len - 1)));
//System.err.println(rightPart);
System.out.println();

}

}

public static String a(String s1) {
char[] s = s1.toCharArray();
int i, j, min;
char x;

for (i = 0; i < s.length - 1; i++) {
min = i;
for (j = i + 1; j < s.length; j++) {
if (s[j] < s[min]) {
min = j;
}
if (min != i) {
x = s[i];
s[i] = s[min];
s[min] = x;
}

}

}

return new String(s);
}

static String omit(String s, int i) {
if (s.length() <= i)
return s;
StringBuilder builder = new StringBuilder(s);
return new String(builder.deleteCharAt(i));
}
}

何度目かのためいき 2007/09/13

やはりデータベース周りなんでしょうかね。
まあわたしは傍観者ですから、斜め視線でみているわけですよ、うーん、お世辞でもかっこいいとは思えないわけです。

クローズもれが潜在的におこりうるコードなんて、言語道断の極みですよ（と強い口調でいってみる）。
いや、わたしも人のことは言えないですよ。ですが、自分のコードを棚にあげて、ライブラリやフレームワーク、他の開発者のコードを疑うなんて。。。まあ、まっさきに疑いますけど（笑）。

確かに、ネットで調べるとドライバの問題だとか、使用している言語のライブラリにバグがとか、そういう情報はすぐにみつかりますが、自分のコードを疑うことをしないと。

で、今後、自分がデータベース周りを担当するようであれば、

（A）はじめから大規模なデータを見越して考えよう。
（B）インデックスを作ればよいわけではなくて、データに見合ったインデックスの作り方があるはずだ。
（C）１００万レコードなんてあたりまえ、大量データで試験できるようにしよう。
（D）大量テストデータを自動生成できるツールをつくろう。
（E）コードに計測用のコードを入れておく、もしくはあとからでも、きちんとはかれるようにしておく。
（F）ログのだしかたを工夫しておく。

反省ですが、計測することを軽んじてはいけませんね。

で、問題がおきてからそれに対処するという方法は確かにおちいりやすい仕事のすすめかたですね。
それが楽になるんですよね。仕事した気になりますが、そもそも問題が起きるようなものを作ってしまったことにたいして考えをおよぼさないと。

反省します。


最短かつ最速にアクセスする「DB高速化技術」（後編）：ITpro

パイプをつなげる 2007/09/13

pojの1146にチャレンジしていて、手で入力するのが面倒になったので、標準出力、標準入力を他のストリームにつなげて、自動化を試みた。
テスト結果を判定するまでにはいたってない
Orz...

package p1146;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PipedInputStream;
import java.io.PipedOutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;

//abaacb
//cbbaa
//a
//cab
//abcd
//acbb
//azyxwvutsrqpppooonnnmmmlllkkkjjjiiihhhgfedcccbbaaa

//ababac
//No Successor
//No Successor
//cba
//abdc
//babc
//baaaabcccdefghhhiiijjjkkklllmmmnnnooopppqrstuvwxyz
public class TestMain {

public static void main(String[] args) throws IOException {
PipedOutputStream outputStream = new PipedOutputStream();
PipedInputStream inputStream = new PipedInputStream();

outputStream.connect(inputStream);
System.setIn(inputStream);

PipedOutputStream outputStream2 = new PipedOutputStream();
PipedInputStream inputStream2 = new PipedInputStream();
inputStream2.connect(outputStream2);
System.setOut(new PrintStream(outputStream2));

Thread thread = new Thread(new Runnable() {

public void run() {
try {
Main.main(null);
} catch (IOException e) {
e.printStackTrace();
}

}
});

thread.start();
String[] ss = { "abaacb", "cbbaa", "a", "cab", "abcd", "acbb¥n",
"azyxwvutsrqpppooonnnmmmlllkkkjjjiiihhhgfedcccbbaaa", };

BufferedReader reader = new BufferedReader(new InputStreamReader(
inputStream2));
PrintWriter writer = new PrintWriter(outputStream);

for (String s : ss) {
write(writer, s);
System.err.println(reader.readLine());
}

write(writer, "#");
// System.out.println("OK");

}

static void write(PrintWriter writer, String s){
writer.write(s + "¥n");
writer.flush();
}

}

SQL接続確認 2007/09/13

select 1 from dual

で接続確認。

そもそも
dual表って何だ？

[pgsql-jp: 29926] Re: ORACLEでいう DUAL 表は？
あべしの壺/技術の壺/Ｏｒａｃｅｌの壺/SQL*Plus/kiso


このDUAL表を使用したSELECT文は、Oracle Databaseの他にMySQLでもサポートしていますが、PostgreSQLはサポートしていません。このため、Oracle用に開発されたアプリケーションをPostgreSQL用に修正する時は注意が必要です。[ThinkIT] 第2回：拡張部分によって違いがでてくるSQL文 (1/3)

pascalのwhile文 2007/09/13
2007/09/13

while文 - Wikipedia
repeat-until文( Pascal)とdo-while文( C)

結構、ちょっと古いコンピュータの本（アカデミックよりな）にpascalとかでコードが載ってたりするので、メモ。

while 条件 do 文

repeat 文; 文...; 文 until 条件

Scalaメモ 2007/09/09

HHa（H派）メモ - ほぼりスクリプト言語Scalaの情報ソース

Scalaという言語があるらしい。


Groovyよりはやそうだ。
※groovyにはやさを求めてはいないけど。
coding, by Derek Young: Scala vs. Groovy: static typing is key to performance


Scala言語というのは何やらエレガントらしい。


ちょいとためしてみよう。頭がすっきりする言語ならいいなぁ。

Smalltalkを学びたいと思うもうひとつの理由が増えてました。 2007/09/07

sumim’s smalltalking-tos - Smalltalk は死につつある…とかってバカじゃね？

やばい、そろそろSmalltalkの勉強スタートしないと！！

現在、Smalltalkを勉強したい(まだスタートしていません。)気持ちがちょっとづつ上昇中。

java 非公式なVE eclipseプラグインが更新されていました。- 09/03 Choose Beanが使えるようになっていました。 2007/09/07

Erik Hechtさんが作成された、非公式なVE eclipseプラグインがChooseBeanに対応したようです。
windows版で試したら検索して選択できました。

Erik Hechtさんのサイト
www.ehecht.com

VEの動向は気になりますね。

関連
プログラマメモ2: java 非公式なVE eclipseプラグインが更新されていました。- 08/02 Choose Beanが使えない。

最小公倍数をjavaで求める 2007/09/06
2007/09/06

インターネットで調べればすぐにでてくると思いますが、とりあえず。

最小公倍数 - Wikipedia
を参考にしてみます。



えーと、
gcdは最大公約数 GCD (Greatest Common Divisor)というものらしいです。

API標準のBigIntegerに、gcdというメソッドがありますね。
これを利用して、
最小公倍数は、LCM (Least Common Multiple)を求めてみます。

ユーティリティメソッドにしてみました。

static public BigInteger gcd(BigInteger l, BigInteger r){
return l.gcd(r);
}

static public BigInteger lcm(BigInteger l, BigInteger r){
return l.multiply(r).divide(gcd(l, r));
}



複数の数の最小公倍数を求めるユーティリティメソッドです。上記のメソッドと一緒に使います。
再帰がかっこいいだろうなぁと思ったのですが、すぐに思いつかなかったので、下記のようにループにしてます。java5から導入された可変長引数を使用しています。便利だなぁと思いましたよ可変長引数。

static public BigInteger lcm(BigInteger l, BigInteger... rs){
BigInteger b = l;
for(BigInteger r:rs){
b = lcm(b, r);
}
return b;
}


使い方は、
BigInteger b2 = BigInteger.valueOf(3);
BigInteger b3 = BigInteger.valueOf(2);
BigInteger b4 = BigInteger.valueOf(4);
BigInteger b5 = BigInteger.valueOf(5);
System.out.println(lcm(b2, b3, b4, b5));


gcmを標準APIで間に合わせましたが、実装が気になるところです。

コネクションは閉じろ - 開けたら最後まで責任とってと彼女はいった 2007/09/06

今後何かの役にたつかもしれないのでメモ

おおざっぱにですが。

まず最初にアプリケーションサーバを疑った。
そして、maxThreadsとかの値を変更した。

で、つぎに、データベースのコネクションプールを疑った。
使用しているのは、Overview - Commons DBCP
で、調べるとBasicDataSource (Commons DBCP 1.3-SNAPSHOT API)のmaxActiveの初期値が小さいという判断で、大きくした。
そして、maxWaitが-1(無限)だったので、10000にした。

そうするとクライアントが固まってみえることはなくなった。データベース接続エラーがでるようになったけど。

ほんのちょっとだけ、状況は解決したように見えたけど、だめだった。

で、コードのある部分のロジックのミス(if文の判定が逆)から一度だけ動作を期待している箇所が、何度も動いていることがわかった。
※でも、これログがでているはずだから開発中に気がついてもよかったのかもしれない。

で、その何度も動作している箇所のコードがマルチスレッド環境で、運が悪ければ、connectionを閉じない可能性があった。コネクションの使い回しの仕組みが危うかった。
※実験してたしかに閉じてないないだろうケースがでた。

で、どの点においても、曖昧な知識で試行錯誤しているのが残念無念。

メモ　org.apache.commons.dbcp.BasicDataSourceの設定 2007/09/05

org.apache.commons.dbcp.BasicDataSource



下記のふたつの設定結構重要かも。

maxActive
The maximum number of active connections that can be allocated from this pool at the same time, or non-positive for no limit.

maxWait
The maximum number of milliseconds that the pool will wait (when there are no available connections) for a connection to be returned before throwing an exception, or -1 to wait indefinitely.


maxWiatはデフォルトで無限なので、要求をだしたいてる部分が固まってみえるようになる可能性大。

printf printlnでの簡単な注意 2007/09/04

ちなみに、POJで改行ではまって少しロスしたので、このメモを残します。

1.5から導入されたprintfでの注意。
System.out.printfで改行コードを含める際に注意すること。
注意するのが面倒ならいっそ、System.out.printlnつかったほうがよいかも。
windowsとosxあとブラウザがからんだ状態で、ソースコードをいったりきたりさせていると、自分の書いた\nが正しいかどうかがだんだん疑わしくなる。。。

あと、
１００問を解くのを目指す人がいたりしますね。pojで検索したらみつけました。
replore的日記 - [poj] とりあえず１００問解く事を目指すか

僕は、shortcoder本の影響ではじめました。

groovy method aliasing 2007/09/02

プログラマメモ2: groovy メソッドポインタ - printlnとうつのが面倒なときに

以前の記事ではメソッドポインタとかいってたけど、どういう呼び方がいいのかなぁ。

Grな日々(uehajの日記) - Groovyの奇妙な演算子(その１）

aliasing

このブログだとmethod aliasingとか言い方しているぽいし。

poj 1003 2007/09/02


pojです。

ハングオーバーですね。よくわかってないですが。

はじめにテーブルを作成してデータを用意してやっています。

1/2,1/3,1/4,1/5,1/6,1/7,1/8...
この数列の足し算なんていうんだろう?

実は何故解けたのかよくわっていない。
はじめ電卓で、計算して試していたりしたのだけども、プログラム書いたら、すぐに解けた...

関連


package p1003;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

double[] t = t(274);

BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String line;
while ((line = reader.readLine()) != null && !"0.00".equals(line)) {
double d = Double.parseDouble(line);
// System.out.println(d);
int n = 1;
if (d < t[0]) {
p(1);
continue;
}

for (int i = 0; i < t.length; i++) {
if (t[i] < d)
continue;
n = i + 1;
// System.out.println(">>"+i);
p(n);
break;
}

}

}

static void p(int n) {
System.out.println(n + " card(s)");
}

static double[] t(int i) {
double[] t = new double[i - 1];
double sum = 0.0;
for (int d = 2; d <= i; d++) {
sum += 1.0 / (double) d;
t[d - 2] = sum;
// System.out.println(t[d - 2]);
}

return t;
}
}

javascriptで逆ポーランド記法 2007/09/01

逆ポーランド記法の勉強のために作成。



言語にpop,push命令あると作成しやすいですね。
あとevalを使ってます。

あと配列をぐるぐるまわすときにtokens[index] != undefinedでチェックするのは楽かもしれないですね。

ちょっとかっこわるいと思っているのが、splitでわけたあと、空の文字が入っているかもしれないので長さをはじくために、t.length == 0 入れているのが...



実行をクリックすると上記の入力したスクリプトが実行されます。
実行

 



スクリプトの、1 2 2 / + 3 4 5 * + -を書き直して、実行おすといろいろ試せます。

参考


少しだけ参考にしました。

投稿 ()