4 TopCoder

SRM432

2009-01-07T01:14:00.005+09:00

SRM432に挑戦。前回から6ヶ月以上たってるよ。6ヶ月以上、参戦してないと、ランキングから除外されるんですねー。今までは、ThinkPad + Linux (もち、Gentoo Linux) + Eclipse + Javaという環境でやってたんですが、ThinkPadが壊れてからは、なかなか環境を整えることをしないまま、時間がたってしまいました。今回は、Macbook Pro + Eclipse + Javaという環境で、久しぶりに参戦してみました。レーティングが下がるフラグがたちまくりの状態だったんですが、結果は、250 Passed, 500 Passed, 4 successful challengesで、レーティングは2121 -> 2220と上昇。ようやくRedになりました。

SRM405 - 5ヵ月ぶりの参戦

2008-06-15T04:02:00.001+09:00

久しぶりのSRM。実に5ヶ月ぶりですよ。 C++にスイッチするはずが、手元の環境の問題で、やむなくJavaで参加してみる。 250はやるだけの問題。 500はいい解法がなかなか思いつかないまま、時間がなくなってきたので、エレガントな解法はもうあきらめてBrute-force的に解いてみる。コンテスト中は解法として正しいかどうか証明できなかったので、自信がなかったんですけど、 Passしました。ちょっと驚き。レーティングは、2000 -> 2121と上昇。賞金つきマッチでしたので、おそらく賞金ももらえます。

SRM386

2008-01-06T18:40:00.001+09:00

2008年あけましておめでとう。今年最初のSRM、 SRM386 に挑戦。今回も、ハード問題は解いた人が一人だけというスーパーハードでした。

Room Statistics
Class Name	Method Name	Difficulty	Coding Time	Status	Points
CandidateKeys	getKeys	Level One	0:15:25.443	Passed System Test	197.99
PolygonCover	getArea	Level Two	0:22:50.327	Passed System Test	331.60
EscapeArtist	bestRoute	Level Three	0:24:44.715	Opened	0.00

レーティングは、1918 -> 2009と上昇。自己ベストは、2040ですので、あと一歩。このあたりのレーティングだと、ハードが解けなくても、コンスタントにEasyとMediumを解くことができれば、大抵レーティングは上昇しますね。

SRM385

2007-12-28T03:13:00.001+09:00

SRM385 に挑戦。今年、最後のSRMです。

今回は、1100点問題は誰も解けないほどのハードな問題、 250点問題と500点問題はとっても素直な問題なんですけど、 500点問題はワーストケースのタイムアウトで落ちてしまいました。

2.004s

うーん。惜しい。0.004秒ほどオーバー。

メモするところで、HashMapではなく、普通に配列使っとく
または、ゴールに達したらすぐ値を返す

でなんの問題なかったんですよね。状態のサイズは、最大でも7 * 7 * 2^14 = 802,816 ですので、 HashMap使ってもまあ楽勝で2秒以内だろ。と勝手に思い込んだ、私の負けです。ちゃんとTopCoderのシステム上で計測しとかないとだめですね。

SRM384 - ゲーム

2007-12-27T01:53:00.002+09:00

SRM384 に挑戦。結果は、以下の通り。

Room Statistics
Class Name	Method Name	Difficulty	Coding Time	Status	Points
Library	documentAccess	Level One	0:06:01.087	Passed System Test	239.41
SchoolTrip	duration	Level Two	0:51:13.541	Passed System Test	211.78
ChessTraining	game	Level Three	0:10:44.830	Opened	0.00

今回は、500点問題は正確に確率を求めようとすると、かなり面倒くさいです。何も考えずに、メモつき再帰などで計算しようとすると、「あれ、元の状態に戻ってしまうよ。延々とループしてしまうよね。これ?どーしよ。。」となってしまいます。私は、これで30分くらい悩みました。

うまく場合分けをすれば正確に求めることも可能ですが、そうではなく、強引にシミュレーション(?)で求めてしまうって方法が、一番楽だったようです。ちなみに、このような強引に一定回数ループを回して計算する方法って、なにか名前がついていないんですかね? シミュレーションって言葉も、ちょっと正しくないような気もするんですけど。

1000点問題は、ゲームの問題です。ひとつひとつのゲームの結果を求めるのは簡単なんですが、それが複数組み合わさるときの求めかたがわかりませんでした。「なんらかの、Nimのようなゲームの考え方に落ち着くんだろうな。」とは思ってたんですけど。

TopCoderのForumによりますと、このような複合ゲームの場合の考え方は、以下の論文(TopCoderのメンバーである raso6sk の学士論文)が参考になります。

http://www.fmph.uniba.sk/fileadmin/user_upload/editors/studium/svk/2007/INF/lenhardt.pdf

しかし、この1000点問題を解いた人は、24人もいるんですよね。みんな、よく知ってますね。さすが。

SRM368

2007-10-02T23:39:00.001+09:00

SRM368 に挑戦。結果は以下の通り。

Room Statistics
Class Name	Method Name	Difficulty	Coding Time	Status	Points
JumpingBoard	maxJumps	Level One	0:16:20.551	Challenge Succeeded	168.66
PolylineUnion	countComponents	Level Two	0:38:47.847	Passed System Test	245.21
BinaryCodes	ambiguous	Level Three	0:15:17.316	Opened	0.00

JumpingBoard

これを、1). 普通にさくっと解くか、2). 解いたつもりで間違いに気付かず次の問題にいってしまうか、で落ち着きのある・なしが判定できますね。。

まー、私は後者だったわけだが。多くの人がサイクルの判定で同じようなミスをしてました。

PolylineUnion

500点問題。Geometry問題。セグメントの交差判定が問題の中心。最初は交点の座標を求めようとしたんですけど誤差の精度に確信が持てなかったので、方針を変えて交差判定を整数のみを使用してがんばってみた。

BinaryCodes

1000点問題。とても手が回らず。解けた人は一人だけというハードな問題でした。

結果

レーティングは、1760 > 1853と上昇。 Javaじゃなくて、C++にスイッチしようかなと思う、今日、このごろ。。

SRM366 - typo2連発

2007-09-18T22:35:00.001+09:00

久しぶりのSRM。 SRM366 に挑戦。

ChangingSounds (code)

250点問題。典型的DP。

GuitarConcert (code)

500点問題。N=10なので、2^NのBrute-forceでいけます。結果を、lexicographicallyで優先順位をつけるところだけが注意点です。

ですが、System Testに落ちました。えーと、ここの、

void sort(String[] a, String[] b) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for (int j = N-2; j >= i; j--) {
            if (a[j+1].compareTo(a[i]) < 0) {
                swap(a, j, j+1);
                swap(b, j, j+1);
            }
        }
    }
}

この行ですね。

if (a[j+1].compareTo(a[i]) < 0) {

iではなくjですよー。気付きましょうよー > 私。

if (a[j+1].compareTo(a[j]) < 0) {

これでSystem Testに通りました。 typoのままで、Example Caseに通ってしまったのが、運のつき。

LateForConcert (code)

1000点問題にもかかわらず特に悩むところはない珍しく簡単な問題。ですが、どうしても答えがあわない。。そのまま時間ぎれ。

やはり、一箇所ミスってました。

double[][][] next = new double[R][C][4];
fill(dp, INF);

dpではなくnextですよー。気付きましょうよー > 私。

double[][][] next = new double[R][C][4];
fill(next, INF);

これでSystem Testに通りました。 typoというよりは、典型的なコピペ後の修正し忘れってやつですね。

結果

System Testの結果です． ( Room Statistics )

今回は、3問全部解くべき簡単な問題セットだったと思うんですけど。ミス2連発では、お話になりません。

レーティングは、1856 > 1760とまとも低下。やむなし。。

Python - generatorで素数生成

2007-07-31T00:07:00.001+09:00

Pythonのgeneratorは無限ストリームを実現するのに便利。たとえば、 SICP 3.5.2 節にでてくる素数の無限ストリーム

Scheme:

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

をPythonで実現すると、こうなります。

Python:

>>> from itertools import ifilter, count
>>> def sieve(g):
...      prime = g.next()
...      yield prime
...      for i in sieve(ifilter(lambda x: x%prime, g)):
...          yield i
...
>>> primes = sieve(count(2))
>>> primes.next()
2
>>> primes.next()
3
>>> primes.next()
5
>>> primes.next()
7
>>> primes.next()
11

しかし、Schemeと異なり、Pythonの場合は、

>>> for i, prime in enumerate(sieve(count(2))):
...     print "%d th prime is %d" % (i, prime)
...
0 th prime is 2
1 th prime is 3
2 th prime is 5
3 th prime is 7
4 th prime is 11
5 th prime is 13
..
986 th prime is 7793
987 th prime is 7817
988 th prime is 7823
989 th prime is 7829
<type 'exceptions.RuntimeError'>: maximum recursion depth exceeded

と、再帰レベルのリミット(デフォルトでは1000レベル)に引っかかります。

Schemeではtail-recursionの処理が行われますが、Pythonでは行われないからですね。パフォーマンスは悪くてもよいとして、上手に再帰を避けつつ、エレガントに無限ストリームを書くにはどうしたらいいのやら?

[2007-07-31] 追記

発見しました。これでいけます。

>>> from itertools import ifilter, count
>>> def sieve():
...     g = count(2)
...     while True:
...         prime = g.next()
...         yield prime
...         g = ifilter(lambda x, prime=prime: x%prime, g)
...
>>> primes = sieve()
>>> for i, prime in enumerate(primes):
...     if i%1000 == 0:
...         print "%d th prime is %d" % (i, prime)
...
0 th prime is 2
1000 th prime is 7927
2000 th prime is 17393
3000 th prime is 27457
4000 th prime is 37831
5000 th prime is 48619
6000 th prime is 59369
7000 th prime is 70663
8000 th prime is 81817
9000 th prime is 93187
10000 th prime is 104743
11000 th prime is 116461
12000 th prime is 128201
13000 th prime is 139907
14000 th prime is 151717
..

また、標準のitertools.ifilterではなく、自前のもの、例えば、

>>> def sieve():
...
...     def myfilter(pred, g):
...         for i in g:
...             if pred(i):
...                 yield i
...
...     g = count(2)
...     while True:
...         prime = g.next()
...         yield prime
...         g = myfilter(lambda x, prime=prime: x%prime, g)

とした場合は、スタックフレームを消費してしまい、成功しません。標準のitertools.ifilterを使用すると、Stacklessになるようです。面白い。

New Launguage - 新言語追加の予定?

2007-07-25T00:57:00.001+09:00

現在、TopCoderのアルゴリズム・マッチで使用できる言語は、 C++, C#, Java, VBの4つです。ちなみに、この前のSRM356で使用された数は以下のとおり。

C++ - 723
C# - 71
Java - 296
VB - 4

C++が一番人気。VBが圧倒的不人気です。 TopCoderのForumによりますと、

Haskell support?

The next language supported has been chosen and will begin work soon; unfortunately it's not Haskell.

新しい言語が数ヶ月後に追加されるようですよ。残念なことに、Haskellではないことだけは確定していますが。

Python, Ruby, Erlang, OCaml, Pascalあたりが予想されていますが。はたして何が追加されることやら。

とりあえず個人的に予想しておくとするなら、OCamlに一票。

lxmlでHTMLスクレーピング

2007-07-19T23:26:00.001+09:00

たまにはPythonでTopCoderの問題を解いてみようと思ってはみたものの，書いたコードが正しいがどうかどうやってチェックすればいいんだろう？サポートされているJavaやC++なら，TopCoderのプラクティスルームでSubmitして，テストを走らせればいいんですけど．

問題文に付属しているような数個のサンプルケースだけでは，テストとしてはもちろん不十分．実際のシステムテストで使用された入力と正解のフルセットさえ入手できれば，ローカルでもテストを走らせることができるはず．そう思い，そのようなデータがTopCoderで提供されているかというとちょっと探してみる． Data Feeds を発見したけど，該当データは提供されていない．

システムテストでどのようなテストが走ったかは，たしかWebでもみれたはず．たとえば，SRM354のHard問題，RookPlacementなら，正解を提出したPetrの Code を見れば，システムテストで使用されたテストケースもすべて載っています．

「このHTMLページから抜き出せばいいじゃん．」ということでスクレーピングしてみる．

まずは、HTMLファイルの取得。もちろん，ブラウザ上でアクセスしてHTMLを保存してもいいですけど、ここでは、プログラムの中から取得してみる。認証チェックがあるので、ページを取得する際は，認証済みCookieが入ったリクエストでないとはじかれてしまいます．ふだんブラウザで使用しているCookieを渡してしまうのが一番楽． Pythonなら，こんな感じ．

In [1]: import cookielib, urllib2
In [2]: cj = cookielib.MozillaCookieJar()
In [3]: cj.load('cookies.txt')
In [4]: opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))
In [5]: html = opener.open(url).read()

あとは，HTMLをパース． lxml を使用．

In [6]: from StringIO import StringIO
In [7]: from lxml import etree
In [8]: tree = etree.parse(StringIO(html), etree.HTMLParser())

lxmlは，HTMLが多少壊れていても，リカバーしてくれるので，このようなスクレーピング用途にはもってこいです． Well-FormattedでないHTMLやXMLをパースするのって，結構，テーマとしては奥が深いような気もするんですけど，どういうアルゴリズムになってるんですかね．

HTMLを見る限り、欲しいデータはすべて、このような

<td class='statText' ...>190</td>

エレメント内であることがわかりますので、 xpathで該当エレメント内テキストをとりあえず全部取得．

In [9]: ts = [t.strip() for t in tree.xpath("//td[@class='statText']/text()")]

結果を表示してみると，最初の方は余分なごみです．

In [10]: ts[30:40]
Out[11]:
['',
 '',
 '',
 'Test\n            Arguments',
 'Expected Results',
 'Success',
 '4,\n5,\n2',
 '190',
 'Passed',
 '2,\n3,\n3']

'Success'文字列以降だけに絞る．

In [12]: ts = ts[ts.index('Success')+1:]
In [13]: ts
Out[14]:
['4,\n5,\n2',
 '190',
 'Passed',
 '2,\n3,\n3',
 '6',
 'Passed',
 '6,\n7,\n20',
 '0',
 'Passed',
 '50,\n25,\n50',
 '879507',
 'Passed',

入力，正解はそれぞれ，3つおきに出現するので

In [15]: testcases = zip(ts[::3], ts[1::3])
In [16]: testcases
Out[17]:
[('4,\n5,\n2', '190'),
 ('2,\n3,\n3', '6'),
 ('6,\n7,\n20', '0'),

入力の各パラメータは，',\n'がセパレータになってるので

In [18]: import re
In [19]: testcases = [(re.split(r',\n', input), expected) for (input, expected) in testcases]
In [20]: testcases
Out[21]:
[(['4', '5', '2'], '190'),
 (['2', '3', '3'], '6'),
 (['6', '7', '20'], '0'),

各データは文字列ですので、evalします．今回のデータには含まれていないですけど、TopCoderの配列のリテラルは'{..}'形式ですので、evalできるように'[..]'に変換してから． evalが怖いなら，JSONとしてパースしてもいいです．

In [22]: def evalf(s):
    ...:     if len(s) >= 2 and s[0] == '{' and s[-1] == '}':
    ...:         s = '[' + s[1:-1] + ']'
    ...:     return eval(s)
    ...:
In [23]: testcases = [(map(evalf, input), evalf(expected)) for (input, expected) in testcases]
In [24]: testcases
Out[25]:
[([4, 5, 2], 190),
 ([2, 3, 3], 6),
 ([6, 7, 20], 0),

これでOK。あとはテストするだけ。

In [26]: for input, expected in testcases:
    ...:     assert RooksPlacement().countPlacements(*input) == expected

テストケースを抜き出す部分は、まとめると最終的にはこうなります。

def extract_testcases(url, cookie_file='cookies.txt'):
    cj = cookielib.MozillaCookieJar()
    cj.load(cookie_file)
    opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj))
    html = opener.open(url).read()
    tree = etree.parse(StringIO(html), etree.HTMLParser())
    ts = [t.strip() for t in tree.xpath("//td[@class='statText']/text()")]
    ts = ts[ts.index('Success')+1:]
    return [(map(evalf, re.split(r',\n', input)), evalf(expected))
            for (input, expected) in zip(ts[::3], ts[1::3])]

昔はこういうことをしたかったら，Perlで正規表現を書いて抜きだしていたけど，どうしてもコードが長くなりがち．いまは，大抵どの言語でも便利なXMLライブラリが付属しているので，楽ちん．

SRM358 - Today is a Bad Day (-50).

2007-07-18T21:16:00.001+09:00

SRM358 に挑戦。

BrokenButtons (code)

250点問題。いかにケアレスミスをしないか?を問われる問題。で、見事にミスをしてしまいました。しかも、2つも。 5分の休憩時間中に、自分の誤りに気がついたんですけど、ときすでに遅し。なぜか、自分は、250点問題のミスに、休憩時間中に気付くパターンが多いような。他人へのチャレンジ・ケースを考えているうちに、自分のミスに気付かされるといういつものパターン。

BalanceScale

500点問題。苦手な整数問題。最大サイズが50なので、探索できっこないと思い込む。なにかクレバーなアイデアがあるはずと思いつつ、しかし、時間内に思いつく自信がなかったため、早めにパスして、1000点問題へ。

SharksDinner (code)

1000点問題．500点問題よりは取り組みやすそうに思えたので、今回は、ずっとこれに取り組んでいました。まったく同じ鮫をのぞいてしまえば、グラフはDAG(directed acyclic graph)になるので、まったく同じ鮫をどのように扱うか考えていました。結局提出まで至らず時間切れ。後で、コードを振り返ってみると、全体としての方針は間違っていなかったんですけど(DAGにしてマッチング問題に帰着)、前半部分で、「同じ鮫をひとつにまとめてしまっても大丈夫なはずだ」という、致命的な勘違いをしていました。なぜ、そう思ったのだろう。。。

ほとんどのひとは、MaxFlowで解いていますね。なるほど。

結果

System Testの結果です． ( Room Statistics )

チャレンジも2つ失敗して、結局スコア-50で終わるという過去最低の結果に。レーティングも2040->1856とものの見事な低下っぷり。この悔しさが、次回へのモチベーションにつながるんですけどね。

SRM349 FizzBuzz問題が簡単すぎるそんなあなたへ。「赤いマーブル問題」。

2007-05-18T23:54:00.001+09:00

SRM349 に挑戦。

今回は、1000点問題が、なかなかいい問題でした。 Division1の人達の多くを見事にひっかけた良問です。超絶アルゴリズムが必要なわけではなく、最初にちょっとしたアイデアに気付くかどうかで、十分に解ける問題と化すという、素晴らしい問題だなと。

世間ではFizzBuzz問題がはやっていたようですが、それに飽きたという方は、この1000点問題「赤いマーブル問題」に挑戦してみてください。

中が見えないバッグに、赤いマーブルがred個、青いマーブルがblue個、入っています。あなた(A君)と相手(B君)は、交互に、バッグから1個、あるいは2個、あるいは3個のマーブルをまとめて取り出します。取り出したマーブルの色は自分だけでなく相手にも教えてあげます。このように交互にマーブルを1個から3個ずつ取り出していき、バッグに入っている最後の(ラスト一個の)赤いマーブルを取り出した人が負けになります。

それでは、ゲームスタートです。といいたいところですが、ここで第3者(C君)が現れて、ゲームをはじめる前に、バッグからマーブルを、ランダムにremoved個、取り出してしまいました。 A君もB君も、取り出されたremoved個のマーブルがそれぞれ何色だったかは教えてもらえませんでした。

この状態からゲームはスタートします。すなわち、A君とB君は、もともとの赤いマーブル, 青いマーブルの個数と, C君が取り出した個数は知っていますが、現在のバッグについては、(red + blue - removed)個のマーブルが入っていることがわかっているだけで、どの色がそれぞれ何個入っているかはわかっていません。

ゲームスタート。最初に取り出しのはあなた(A君)からです。お互いが最適な戦略をとる場合、あなたが勝つ確率はいくつになるでしょうか?

という問題です。

red, blue, removedは、以下の条件を満たすものとします。

1<= red <= 100
1<= blue <= 100
removed < red

つまり、ゲーム開始時は、少なくとも1個、赤いマーブルがバッグに残っています。

では、どうぞ!

public double winningChance(int red, int blue, int removed) {
    ...
}

ちなみに

red=1, blue=1, removed=0 の場合は、答えは、0.5
red=1, blue=2, removed=0 の場合は、答えは、0.33333333333333...
red=2, blue=1, removed=1 の場合は、答えは、0.5
red=100, blue=1, removed=99 の場合は、答えは、0.9900990099009901...
red=100, blue=100, removed=50 の場合は、答えは、0.5379240275007613...

になります。正しく解けたかどうかの検証用にどうぞ。

ちなみに、トップのひとは、この問題を23分で解いています。。。

Suffix Array

2007-03-27T00:15:00.000+09:00

TopCoder SRM187、 DNAMultiMatcher は、

Stringが3つ(それぞれの長さは最大2500)与えられたとき、 3つ全てに含まれる最長のSubstringの長さを求めなさい。

という問題です。これに対して、

長さをBinary-Searchで絞りながら、
Stringが含まれるかどうかの判定をJava標準のjava.lang.String#containsを使用

という方針で解く場合は、こうなります。

public class DNAMultiMatcher {

  public int longestMatch(String[] sequence1, String[] sequence2, String[] sequence3) {
      String s1 = join(sequence1);
      String s2 = join(sequence2);
      String s3 = join(sequence3);

      int low = 0;
      int high = s1.length();

      while (low < high) {
          int mid = low + (high-low+1)/2;
          boolean found = false;
          for (int i = 0; i + mid <= s1.length(); i++) {
              String p = s1.substring(i, i+mid);
              if (s2.contains(p) && s3.contains(p)) {
                  found = true;
                  break;
              }
          }
          if (found) {
              low = mid;
          } else {
              high = mid-1;
          }
      }
      return low;
  }

  String join(String[] sa) {
      StringBuilder sb = new StringBuilder();
      for (String s : sa) sb.append(s);
      return sb.toString();
  }
}

この場合は、ワーストケースで軽く2分以上かかってしまい、タイムアウトです。 String Aの長さをn、String Bの長さをmとした場合、JavaのA.contains(B)は、普通にO(m*n)っぽいですね。

AがBを含んでいるか?を高速に判定するときに使用できるのが、 Suffix Array です。

ナイーブに実装してみると、

class SuffixArray {
    int len;
    String[] suffixes;

    SuffixArray(String s) {
        len = s.length();
        suffixes = new String[len];
        for (int i = 0; i < len; i++) {
            suffixes[i] = s.substring(i);
        }
        Arrays.sort(suffixes);
    }

    int find(String p) {
        if (len == 0) {
            return p.length() == 0 ? 0 : -1;
        }
        int low = 0;
        int high = suffixes.length-1;
        while (low < high) {
            int middle = low + (high-low)/2;
            if (suffixes[middle].compareTo(p) >= 0) {
                high = middle;
            } else {
                low = middle+1;
            }
        }
        if (suffixes[high].startsWith(p)) {
            return len - suffixes[high].length();
        }
        return -1;
    }
}

Javaのjava.lang.String#substringメソッドは、もとのStringと内部の配列char[]を共有したStringを返すので、この実装でも無駄にメモリを消費しないはずです。

オーダーは、

Aに対するSuffix Arrayの構築: O(n^2 log(n))
AがBを含んでいるかの判定: O(m log(n))

になるでしょうか? 改良の余地はまだまだ残っていますが、今回の目的にはこれで十分です。 (Suffix ArrayをO(n)で作成するアルゴリズムもあるようです。。。)

先ほどの例を、Suffix Arrayを使用して書き直すとこうなります。

public class DNAMultiMatcher {

  public int longestMatch(String[] sequence1, String[] sequence2, String[] sequence3) {
      String s1 = join(sequence1);
      String s2 = join(sequence2);
      String s3 = join(sequence3);

      SuffixArray sa2 = new SuffixArray(s2);
      SuffixArray sa3 = new SuffixArray(s3);

      int low = 0;
      int high = s1.length();

      while (low < high) {
          int mid = low + (high-low+1)/2;
          boolean found = false;
          for (int i = 0; i + mid <= s1.length(); i++) {
              String p = s1.substring(i, i+mid);
              if (sa2.find(p) >= 0 && sa3.find(p) >= 0) {
                  found = true;
                  break;
              }
          }
          if (found) {
              low = mid;
          } else {
              high = mid-1;
          }
      }
      return low;
  }

これで、ワーストケースでも1秒以内に処理できるようになり、システムテストに通ります。 Suffix Arrayの応用例はほかにもいろいろあり、全文検索などでもよく使われるようです。

google-code-prettifyを導入してみる

2007-03-26T23:45:00.000+09:00

google-code-prettify を導入してみました。 JavaScript + CSSでコード部分の色つけをしてくれるものです。

デフォルトでは、class属性が"prettyprint"となっている、 <pre>タグや<code>タグがシンタックス・ハイライトの対象になるようです。このブログはreStructuredTextで書いているので、 <pre>タグのclass属性は、clsss="literal-block"となっています。 <pre>タグの方を直すのはいまさら面倒なので、prettify.jsの方を少し修正して導入しました。 PythonとJavaは両方ともサポート言語ですので、どちらもなかなか派手に色がつきます。

Subsetの生成

2007-03-02T01:00:00.000+09:00

いままで、あるビットマスクsupersetのサブセットをすべて生成するには、

for (int subset = 1; subset < superset; subset++) {
 if ((subset|superset) == superset) {
   // do with subset
 }
}

としていたんですけど、これだと、 superset = 10011(2)などの場合でも、約10011(2)回のループが必要です。生成されるサブセットは、

{10010, 10001, 00011, 10000, 00010, 00001,}

と6つしかないのに。すごい無駄です。

もっとうまい方法がありました。

for (int subset = superset; subset > 0; subset = (subset-1) & superset) {
  // do with subset
}

これなら、サブセットのみをうまく生成できます。この場合のサブセットはsupersetを含み、空セットは含みません。

2006年のまとめ - SRM332

2006-12-31T01:17:00.000+09:00

SRM332 に挑戦。2006年、最後のSRMになります。

CreatePairs (code)

250点問題。Greedyですね。落ち着けばとけます。

RestoringPolygon (Code)

550点問題。2次元平面上で水平の線分(セグメント)がいくつか与えられます。このセグメントに垂直のセグメントを好きなだけ足して、最大のポリゴンを作成して、その辺の数を返しなさい。という問題です。

単純に考えてそのまま強引に解いてしまいました。ワーストケースでのタイムアウトが気になりましたが大丈夫だったようです。

LadderPermutation

950点問題．Openしませんでした。

結果

System Testの結果です． ( Room Statistics )

550点問題のRestoringPolygonをシステムテストで落とされた人が続出 ( 309人中、提出が144、正解が16と正解率が11%ほど )したため、全体的に点数が低めでした。 950点問題のほうが、550点問題より正解者が多い。。。

なぜか同じルーム内にはRed Coderがいなかったため、ルーム内ではトップのポイント。レーティングは1532->1678と上昇しました。

2006年のまとめ

2006年も終了。この時点でのStatsを記録として残しておきます。

今年のはじめはレーティングが1630で、今は1678ですのであんまり変わってません。

まだまだRed Coderへは遠い道のりです。。

Pythonはどうなった?

TopCoderに参加するときはこれまでのところJavaをずっと使用していますが、 TopCoder以外の個人的な場面ではJavaを使用することはすっかりなくなり、大抵の場合Pythonを使用しています。でもあいかわらず、TopCoderのアルゴリズム・マッチで使用できる言語は、 Java、C#、C++、VBの4つだけでPythonは採用されそうもありません。他言語とのスピード差がその理由だそうです。アルゴリズム・マッチで走らせるプログラムは外とのI/OがまったくなくほぼCPUだけに全体の処理時間が依存してしまうので、どうしてもスピード差が顕著になってしまうわけですね。そうはいっても、今年のGoogle Code JamではPythonは採用されたわけだが。。。

と思っていたら、TopCoderのマラソン・マッチでは Pythonがいつのまにか使用言語として採用されています。アルゴリズム・マッチと異なり、マラソン・マッチはコンテストの性質上、処理時間をあまり気にする必要がないのでPythonを加えたそうです。じっくり未解決の難問に取り組むマラソン・マッチもやってみたいところだが、さすがにアルゴリズム部門と比べて時間がそれなりにとられそうなのでしばらくは見送り。

SRM331 - お釣りを受け取らないで、ちょうど支払うには?

2006-12-26T01:59:00.001+09:00

SRM331 に挑戦。今回は、500点問題がシンプルでいい問題でした。

CarolsSinging (code)

250点問題。総当たりでいけます。

Shopping (Code)

500点問題。

買いものにでかけるところです。目的の商品の値段は、1円以上X円以下であることが事前にわかっていますが、実際の値段はお店に着いてみないとわかりません。そのお店はどういうわけかお釣りを出してくれないお店です。そこで損をしないためには、商品がどんな値段であっても、手持ちの何種類かの小銭(コイン)を組み合わせて値段ちょうどの金額を支払うことができるように準備しておきたいところです。コインは必要以上にたくさん持ち歩きたくはありません。あらかじめ用意しておかなければいけない、最低限必要なコインは何枚でしょうか? という問題です。

問題の入力と条件は、

商品の値段: int X (1<=X<=1000)
コインの種類: int[] values
- 10種類まで (values.length <= 10) です。
- たとえば日本の硬貨の場合は、int[] values = {1, 5, 10, 50, 100, 500}。
- 各コインは家には無限個あるとします。

求められる出力は

必要なコインの最小枚数。もちろん、コインの種類によっては不可能な場合もありますので、その場合は -1。

たとえば、X = 100, values = {1, 5, 10, 50, 100, 500} の場合は、答えは、11枚になります。 11枚の例としては、[1,1,1,1,5,10,10,10,10,50,100]などです。これなら、1円から100円までどんな値段であってもきっちり支払うことができます。

さあ、挑戦してみてください。

int minNumber(int X, int[] values) {
   ?????
}

10分以内にできたら、なかなかのものです。
30分以内にできたら、わたしとおんなじ位です。まだまだTopCoderには及びません...。

HiddenSquares

1000点問題．時間さえあればなんとかなるという問題なんですけど、間に合いませんでした。。

結果

System Testの結果です． ( Room Statistics )

ここのところレーティングが下がる一方だったんですけど、今回はようやく1445->1532と上昇。 Yellow Nameに返り咲きました。

Google Code Jam 2006 - Championship Round

2006-10-31T23:00:00.000+09:00

Google Code Jam 2006、Championship Roundが開催されました。オンラインラウンドを勝ち抜いた100名が、Googleニューヨーク・オフィスに招待されて対決です。結果は、

見事Petrが栄冠を勝ち取りました。Petr強い。 Googleからプレス・リリースもでてます。

Google Code Jamの問題は、これまでのところ公開されていないようです。いま、Code Jamのアリーナにアクセスすると、出題された問題セットを見ることができますので、見たい人はお早めにどうぞ。

Blogger Betaに移行

2006-10-31T04:04:00.001+09:00

Blogger Betaに移行してみました。大きな変更点としては

Labelが使えるようになった
テンプレート・システムがまったく新しくなっている
ページを動的に作成するようになったので、テンプレートを変更するとすぐにページに反映される

といったところでしょうか？

テンプレート・システム

新しいテンプレート・システムのうりのひとつは、ブラウザ上でGUIでデザインできることです。必ずGUIを使う必要はなく、全部自分で手作業で設定することももちろん可能でした。いい機会ですので、新規にテンプレート・CSSを作成してみました。テンプレートのタグも新規タグが用意されています。これまでより細部で機能アップしてますね。ほとんど全ての箇所をいじることができる自由度は相変わらず健在ですので、特にデザイン上支障はありません。 GUIデザイン用に使用されるテンプレート内の変数部分は、わずらわしいので全部消去しました。

スタイルシートの動的切り替え

「Printer Friendly View」は Alternative Style: Working With Alternate Style Sheets を参考にしてみました。スタイルシートを動的に切り替えることができます。

Google Data APIs

ブラウザから記事を投稿する人には関係のない話ですが、私の場合は、記事は reStructuredText 形式でローカルで書いてから、自作のPythonスクリプトで記事を投稿できるようにしています。 Bloggerでは、そのためにATOM APIが用意されています。こちらもBetaでは変更が入り、 Google Data APIs を用いるようになりました。

主な変更点としては、

ATOM APIのバージョンが0.3から1.0に変更
認証システムも、Basic認証から、 Google Account Authentication に変更

といったところです。 Blogger Data API として使用方法が解説してありますので、ここを見れば簡単です。

JavaやC#用のクライアント・ライブラリも用意されていましたが、 reStructutedTextの変換を考えるとやはりPythonのほうがよいと思い、 Pythonでクライアントを書きました。 ATOMを使用するにあたり、いくつかすんなりとはいかなかった点としては、

指定されたPost先にPost要求を出すと、Betaのサーバはリダイレクトを返してきます。
投稿に成功した場合、ステータスコード201を返してきます。

この2点です。 Pythonの標準のAPI(urllib/urllib2)では、Post要求に対してリダイレクトが返って来ると、リダイレクト先へPostを再送するのではなくGet要求を出してしまいます。また、ステータスコード201もエラー扱いするようになっていました。そのため、自分で urllib2.HTTPRedirectHandler をもとにした、ちょっとしたハックが必要になります。

その他に気づいた問題点は、新規記事をATOM 1.0で送る時、<published>での日付指定が無視されてしまうことです。これは、現在サーバ側の問題らしく、 Blogger Dev Group で議論されていますのでいずれ解決しそうです。

これでほぼ移行作業が完了しましたが、全体としてはBetaの方がはるかに使いやすくなりましたね。なによりラベルが使えるようになったのがいちばんうれしいですね。

Google Code Jam 2006 - Round1に挑戦 - GenericsとAutoBoxing

2006-09-15T18:30:00.000+09:00

Google Code Jam 2006 Round1に挑戦。予選を通過した1000名のうち500名が通過できます。

NearFrac

250点問題。問題の条件をまちがって解釈してしまいました。解が複数あった場合、たとえば「-1/3, -2/3」の場合は、「小さいほう」である「-2/3」を優先しなければいけないんですが、「小さいほう」の説明を逆に解釈してしまい、「-1/3」を優先するようなコードを書いてしまいました。よく問題を読めばちゃんと説明してあるんですけどね。反省。

BadBinary

500点問題。問題自体は難しくなくコーディングはさくさく10分ほどで完了。しかし、Javaの罠にはまってしまいました。。。たとえば、

Map<Long, Long> memo = new HashMap<Long, Long>();
long i = 1;
memo.put(i, 2);

として、このMapから値を取得しようと、

int j = 1;
memo.get(j);

とします。するとmemo.get(j)の結果は、2ではなくnullになってしまいます。 memoは

Map<Long, Long> memo

と宣言しているので、memo.get(j)の部分は、AutoBoxingが働いて

memo.get(new Long(j))

と解釈されると思っていたのですが、実際は

memo.get(new Integer(j))

とIntegerになるようですね。int->longの変換は行われません。当然、memo.put(new Long(1), ..)したものは、memo.get(new Integer(1))では取得できません。

「Genericsのもつコンパイル時の型チェックは機能しないのか？」と思ったら、そもそもMapのメソッドgetは

public interface Map<K,V> {
  V get(Object key);

と定義されているんですね。てっきり

public interface Map<K,V> {
  V get(K key);

だと思いこんでいました。パラメータの型チェックは行われないのか。。がく。

本番中はまさかこの部分に問題があるとは気づくことができず右往左往。なぜかこういうときだけ無駄な想像力が異様に働き、関係ないところばかり追いかけてしまいました。むなしく時間（50分も。。）を費やしたあげく、結局最後まで気づくことができないまま時間切れ。 memo.get(j)ではなくmemo.get((long)j)とするだけでよかったんですけど。気づくべきでした。 Google Code Jamくん、楽しませてもらったよ。また来年までさようなら。

Google Code Jam 2006 - Qualification Round通過

2006-09-09T23:00:00.000+09:00

予選通過のメールがきました。

From: The Google Code Jam Team

Subject: Google(TM) Code Jam 2006 Results

Hello gentoo,

Congratulations! The results of the Google Code Jam 2006 Qualification Round have been officially tabulated, and we're happy to announce that you have advanced to Round 1. This is a great accomplishment.

Round 1 of Google Code Jam 2006 takes place online at 10:00 AM EDT (GMT/UTC -4) on Thursday, September 14. Registration is required for this round and will be open from 7:00 AM to 9:55 AM EDT (GMT/UTC -4) on the day of the event. To register for Round 1, log in to the Competition Arena, click on the Active Contests menu item, select Round One, and select Register: www.google.com/codejam2006.

Of those who participate in Round 1, the top 500 scores will advance to Round 2 on Tuesday, September 19, at 10:00 AM EDT (GMT/UTC -4).

Congratulations again on successfully making it through the Qualification Round of Google Code Jam 2006.

- The Google Code Jam Team

Google Code Jam 2006のサイトにも通過者の一覧が正式に出ていますね。次は、Round1、1000名から500名です。

Google Code Jam 2006 - Qualification Roundに挑戦

2006-09-06T18:30:00.000+09:00

いよいよ始まりましたGoogle Code Jam 2006。予選に挑戦です。 5つあるセットのうち、Set 5にアサインされました。各セットの上位200名、計1000名が予選を通過できます。

ちょうど、17:00に開始しました。

(17:00:02) System> gentoo is opening the 250-point problem.

250点問題にちょっとてこずり、15分以上かかり提出。

(17:15:51) System> gentoo is compiling the 250-point problem.
(17:15:58) System> gentoo is testing the 250-point problem.
(17:16:08) System> gentoo has submitted the 250-point problem for 176.79 points

この250点問題のスコアでは、とれもこれだけで予選を通過できそうもありません。確実に750点問題を解かなければいけない状況になってしまいました。 750点問題をオープン。

(17:16:14) System> gentoo is opening the 750-point problem.

15分ほどで提出。これで通るだろうと思いほっと一息。

(17:31:24) System> gentoo is compiling the 750-point problem.
(17:31:30) System> gentoo is testing the 750-point problem.
(17:31:35) System> gentoo has submitted the 750-point problem for 542.17 points

ところが見直してみると、バグ発見。。。修正して、再提出。

(17:37:12) System> gentoo is compiling the 750-point problem.
(17:37:17) System> gentoo has submitted the 750-point problem for 385.45 points

542 -> 385 と大幅に再提出ペナルティを食らいます。。。いたい。。

最終的はポイントは、176.79 + 385.45 = 562.24。Set 5内の順位は、現在のところ109位です。まだ全員が参加しているわけではないのでなんともいえませんが、システムテストに2問ともパスすれば予選通過できそうな範囲にはなんとかおさまりました。ふー。あとは祈るのみです。

Google Code Jam 2006 - Practice1

2006-08-16T22:00:00.000+09:00

Google Code Jam 2006 、練習部屋が用意されていたので早速練習してみました。

まず、250点問題。スタート都市(index=0)からゴールの都市(index=1)まで、セールスマンを何人派遣できるでしょうか？という問題です。都市通しのつながり(adj)は、

"001111",
"001111",
"110000",
"110000",
"110000",
"110000"

このようにマトリックス形式で与えられます。都市の数は最大12です。入力の条件としてスタート都市とゴール都市は、直接つながっていないことが保障されています（adj[0][1] == adj[1][0] == 0です）。スタート都市とゴールの都市を除いた、途中の通過都市はそれぞれ最大1人のセールスマンだけが通過できます。つまりあるセールスマンが通過した都市は、別のセールスマンは通過できません。この入力の場合は、正解は4人です([0 -> 2 -> 1], [0 -> 3 -> 1], [0 -> 4 -> 1], [0 -> 5 -> 1]の4通り)。

いつもはJavaですが、せっかくですのでPythonで書いてみました。

class SalesRouting:

  def howMany(self, adj):

      def doit(u, mask):
          if (u, mask) in memo: return memo[u,mask]
          if adj[u][1] == '1': return doit(0, mask) + 1
          memo[u,mask] = max([0] +
                             [doit(v, mask | 1<<v) for v in range(2, len(adj))
                              if adj[u][v] == '1' and (mask & (1<<v)) == 0])
          return memo[u,mask]

      memo = {}
      return doit(0, 0)

状態空間は、現在いるcity: u(N通り) と、これまで通過したcity全て: mask(2^N通り)の組み合わせになります。ワーストケースでもたかだか12 * 2^12 = 50,000ほどですので、Pythonでも十分通ります。

Google Code Jam 2006 - 開催決定

2006-08-15T22:00:00.000+09:00

Google Code Jam 、今年も開催がアナウンスされました。

注目すべきは、なんといってもここでしょう。

The competition is available in five programming languages - Java, C++, C#, VB.NET and Python.

おー、Pythonが追加されています！！本家、TopCoderのシステムでは、使用できる言語は、Java, C++, C#, VB.NETだけで、Pythonは使用できません。にもかかわらず、Google Code Jamといういちイベントのために、わざわざシステムを修正してまでPythonを入れてきたことから、GoogleのPythonに対する意気込みが伝わってきますね。この思いに答えて、Javaではなく、Pythonでいきたいですね。

しかし、JavaにくらべてPythonは10倍くらい遅いんですけど、今回はそれほど時間がシビアな問題は出題されないってことでしょうか？ TopCoderの通常のSRMでは、ワーストケースのオーダーが10,000,000ほどになり、、実行時間がC++で500ms、Javaで1000msくらいかかってしまう問題が時々出題されます。と思っていたら、

NOTE: All submissions have a maximum of 2 seconds of runtime per test case. This limit is used in harder problems to force submissions to be of a certain complexity. Because of the inherent speed differences between Python and the other offered languages is large, some problems may require extra optimization or not be solvable using the Python language.

と書いてありました。主催者側もPythonで解けない問題を出してしまうことへあらかじめ保険をかけてますね

しかし、Pythonが追加されたことでますます盛り上がりそうですね。普段のTopCoderでもPythonを追加してくれという要望は非常に多かったです。いったいどれくらいの人がPythonにスイッチするでしょうかね？楽しみです。

Stay tuned... Global Google Code Jam 2006 - 秋に開催?

2006-07-19T20:18:00.000+09:00

毎年、恒例らしいGoogle Code Jamですが、今年はこれまで

と地域限定で開催されていました。世界中の誰でも参加できるグローバルなやつは果たして今年は開催されるのか？と思っていたら、既に終了したGoogle Code Jam Europeのサイトに以下の記述がありました。

秋に開催されるみたいですよ。

SRM308 - はーどDP

2006-06-26T00:30:00.000+09:00

SRM308 に挑戦。

Division1の問題です．

HuffmanDecoding (code)

200点問題。ハフマン・コードの復号化です。悩むところはなく、いわれたとおり実装するだけです。

CornersGame (Code)

500点問題。

右下のコイン4つを左上に移動させる最短手順は？という問題です。いくつか移動の条件が指定されます。状態空間はたかだか 64 C 4 ほどですので、BFSで解けました。

Wardrobe (code)

1000点問題．一見簡単そうなんですけど、この問題を解けたのはDivision1参加者319人中1人だけという超難問でした。非常に難しい関係式を用いたDPで解けるそうです ( 正解例）。いまだに理解できていません。。。

結果

System Testの結果です． ( Room Statistics )

レーティングは1696->1782と上昇。

SRM304 - 条件付確率

2006-05-29T00:30:00.000+09:00

SRM304 に挑戦．実に1ヶ月半ぶりの参戦です。

Division1の問題です．

PolyMove (code)

300点問題．限られた条件のもとで、ポリゴンの頂点を移動させ、面積を最大化せよ、という問題です。古典的なDPでとける問題なんですけど。。つまらないミスを（実は2つも）してしまいました。

Conditional

450点問題．条件付確率の問題です。十分解けるレベルの問題だったのに、題意をひとつ勘違いしていて、いつまでたってもExample Caseに通らず。。。結局、Submitできませんでした。

TheXGame

1000点問題．Openできませんでした。

結果

System Testの結果です． ( Room Statistics )

チャレンジも成功2、失敗4で、差し引きゼロ。結果ポイントゼロでした。。レーティングは1775->1696と大幅低下。

2006 TopCoder Open Final Round

2006-05-07T23:30:00.000+09:00

2006 TopCoder Open - Algorithm Competition の決勝戦が行われました。オンライン・ラウンドを勝ち抜けた48人が、ラスベガス・アラジンホテルに招待されオンサイトで5/3-5/5の3日間にわたり戦いを繰り広げました。最後に勝ち残った8名による決勝戦の模様は通常のTopCoderのアリーナ上でリアルタイムで見ることができました。といっても、ライブ映像が流れていたわけではなくて、こんな感じで

競技者が行っている「問題をOpen」「コンパイル」「テスト」「コードを提出」等の行動をリアルタイムで知ることができたわけです。問題の内容や各競技者が提出したコードもリアルタイムで見ることができました。アリーナ上では見学者が集まって、それを見ながら「あーだこーだ」いって楽しんでいます。

Finalに残ったのは以下の8名。

tomek : ポーランド・Purdue大学。現在TopCoderでレーティングトップ。優勝候補の最右翼。
Petr : ロシア・モスクワ大学。TopCoderでは珍しいC#使い。数々のプログラミングコンテストで名を残しているそうです。Google Code Jam 2005でも3位に入っています。いつも綺麗な読みやすいコードを書いてくれるので、参考になります。
misof : スロバキア・Comenius大学。
John Dethridge: オーストラリア・メルボルン大学。
andrewzta: ロシア。
cyfra: ポーランド・ワルシャワ大学。
natori : 上位陣には珍しいJava使い。日本人です。
fuwenjie: 中国・TsingHua大学。

蒼々たる面子です。。ホスト国のUS勢はひとりもFinalに残れなかったのか。。問題セットはFinalにふさわしく通常のSRMよりもはるかに難しいものばかりそろっています。

実況開始！

250点問題は比較的容易だったらしく、ほとんどの競技者はそれほど苦労せずにSubmit。 500点問題もfuwenjie, Petr, tomekと続々とSubmit。こんな感じでリアルタイムに問題と提出されたコードを見ることができました。

優勝するには1000点問題を解く必要がある雰囲気が漂いはじめました。そんな中残り時間26分でtomekが1000点問題を提出！

この時点でトップに立ちます。

Petrが続きます。

Petr人気者です。「go Petr!!!」

見学者たちは、「tomekの1000点理解できねー。」「tomekのはgreedy algorithmだ」「Petrのはよさそうだ」とわいわいチャットしてました。

Petrの1k(1000点問題）を見てみましたが、binary searchを使用しています。。。この問題からbinary searchを思いつくとは。。その発想がすごい。。そうこういってるうちに、なんとnatoriが1kを提出！

Petr残り5分というところで、500点問題を再提出。。

コーディング・フェーズ終了。現時点での順位はこのとおり。natoriがトップ。tomek、Petrが続きます。

チャレンジ・フェーズ

5分間の休憩後、チャレンジ・フェーズの始まりです。 Petr開始直後に立て続けに500点問題で3つ撃破！！いっきょにもりあがります。

tomekとnatoriの1kも撃墜されました。チャレンジ・フェーズ終了時点でPetrがトップにたちます。

いよいよ、あとはシステム・テストの結果まちです。。。。

結果

見事、Petrが栄冠に輝きました。賞金2万ドルGetです。。おめでとう！！結局1kに正解したのはPetrだけでしたね。Petrの1kは

Binary Search
SortしてからGreedy
union-find

と基本的なアルゴリズムの組み合わせって感じですね。見事です。。。

SRM298 - ひとふで書き

2006-04-13T00:30:00.000+09:00

SRM298 に挑戦．

Division1の問題です．

FibonacciPositioning (code)

250点問題．フィボナッチ数列に関する問題ですが，なにも考えず実装して終わりです．

OrderDoesMatter (code)

500点問題．行列が複数個あるとします．それぞれの行と列のサイズが与えられます．たとえば，以下の3個の行列が与えられたとします．

A = 7 x 3, B = 3 x 7, C = 3 x 3

これら行列を全て使用して掛け算を行い，最終的にできる行列の行と列をかけたものの最大値を求めなさい．という問題です. たとえば，このケースなら

A * C * B = (7x3) * (3x3) * (3x7) = (7x7)

で，49が最大です．全て使用した掛け算ができない場合は，-1を返します．たとえば

A = 3 x 5, B = 5 x 2, C = 5 x 4

だと，全て使用した掛け算ができないので，-1が答えになります．

．．．うーん，間違って解いてしまいました． bipertite matchigでいけると思ったのですけど，私のコードでは，

A = 1 x 2, B = 2 x 1, C = 3 x 4, D = 4 x 3

のようなケースでも，-1を返しません．．根本的に間違っていました.

これは，有向グラフを一筆書きできるかどうかって問題に落ち着くんですよね．グラフ理論的には， Euler Path というそうです．

CountingCommonSubsequences

1000点問題．長さが50以下の文字列が3つ与えられます．この3つの文字列に対して，共通するユニークなsubsequenceの数を求めなさい．という問題です.

subsequenceとは，文字列から任意個の文字を取り除いてできる残りの文字列です．

たとえば，"call"，"accelerate"，"candle"ならば，答えは6です． "c", "a", "l", "al", "ca" ,"cl"が共通するsubsequenceです．

ちなみに，

"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb"
"abababababababababababababababababababab"
"aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb"

なら，答えは，1725660です．

30分ほど考えたんですが，できませんでした． SRM後に書いてみました.

public class CountingCommonSubsequences {
  char[] s1;
  char[] s2;
  char[] s3;
  int N = 50;
  long[][][] memo = new long[N][N][N];
  public long countCommonSubsequences(String a, String b, String c) {
      this.s1 = a.toCharArray();
      this.s2 = b.toCharArray();
      this.s3 = c.toCharArray();
      for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
              Arrays.fill(memo[i][j], -1);
          }
      }
      return count(0, 0, 0);
  }

  long count(int n1, int n2, int n3) {
      if (n1 >= s1.length || n2 >= s2.length || n3 >= s3.length) return 0;
      if (memo[n1][n2][n3] != -1) return memo[n1][n2][n3];

      long res = 0;

      nextchar:
      for (char c = 'a'; c <= 'z'; c++) {
          for (int i = n1; i < s1.length; i++) if (s1[i] == c) {
              for (int j = n2; j < s2.length; j++) if (s2[j] == c) {
                  for (int k = n3; k < s3.length; k++) if (s3[k] == c) {
                      res += 1 + count(i+1, j+1, k+1);
                      continue nextchar;
                  }
              }
          }
      }
      return memo[n1][n2][n3] = res;
  }

結果

System Testの結果です． ( Room Statistics )

今日は，だめだめでしたね．．レーティングは，1789->1775とやや低下．

SRM293 - ビンゴ!

2006-03-27T00:30:00.000+09:00

SRM293 に挑戦．

ScrabbleBet (code)

300点問題．確率計算の問題です．セオリーどおりに組み合わせの数を求めて計算してもよいですし， DP的に解いてもいいです．

Bingo (code)

450点問題．いわゆる5x5のビンゴのシミュレーションです．アルゴリズム的に悩むところはまったくなく，ただ単に実装にちょっと手間がかかってしまう問題です．参加者の間ではこの手の問題はあまり人気がありません．例のごとく目いっぱい時間がかかってしまいました．．

CirclesOfDestruction

1000点問題． SRM中はオープンしませんでした． SRM後に，挑戦してみました．いい問題ですね．．

問題を解くアイデア自体はすぐに思い浮かびました．「自分のスタート地点」と「円の中心」の垂直2等分線がちょうどOKな地域とNGの地域の境目になります．これでゴール地点の候補が絞れるので，条件を満たすゴール地点のうち距離が一番短いものを返せばよいです．

なんとか自力で解けましたが，やはり時間がかかってしまいました．とてもSRM本番では時間がたらなそうです．

結果

System Testの結果です． ( Room Statistics )

レーティングは，1730->1789と少し上昇しました．

今日の教訓

全体的に時間かけすぎなので，今後上を狙うにはもう少しスピードアップが必要か．．まあでもしばらくは，あまりスピードは意識せずのんびりとやっていきたいと．．

2006 TopCoder Open - Round1 撃墜

2006-03-05T21:33:00.000+09:00

2006 TopCoder Open - Round1 に挑戦． 750名から400名へふるい落とされます．予選と違い，Round1以降は，通常のSRMと同様の形式です．チャレンジ・フェーズもあります．

ラウンドへの登録時，アンケートがありました．「コンタクト先をスポンサーであるNSA(National Security Agency)に教えてもいいかい？」というものでした． TopCoderはいい就職・転職の機会の場になってますね．実際には，NSAはUS市民でないと勤務できないそうですが．．．

ラウンド本番中，ちょっとした運営側の不手際がありました． 350点問題を開くと，実際には500点問題が， 500点問題を開くと，実際には350点問題が表示されてしまっていたようです．

FirstToLast (code)

500点問題．最初にOpenした問題です．本番中はこれが350点問題だと思っていました．．

整数 p, q (1 <= p <= 100, 1 <= q <= 100) が与えられます. このとき，以下の条件を満たす正の整数 a を（存在しない場合は-1 を）返しなさいという問題です．

a の各桁を左に回転シフトした結果を a_rotate とすると， a * p/q = a_rotate
a < 2,000,000,000 (2 billionです．)

条件を満たす a が複数ある場合は，そのうちもっとも小さいものを返します．たとえば，p = 1, q = 4 ならば，答えは a = 102564 になります．

"102564" の左端の1 を右にくっつけて， a_rotate = 25641
a * p / q = 102564 * 1/ 4 = 25641 = a_rotate

ですね．

うーん方針が浮かびませんでした．とりあえずExample Case に通るようにしてからSubmitしました．不完全だというのはわかっていましたが，もうあきらめて次の問題に移りました．．

SeparateConnections (code)

実は，こっちが，350点問題でした．本番中は，500点問題だと思って取り組んでいました．

ノードがn個与えられます．各ノード間が通信可能かどうがが，マトリックス形式で与えられます．

ノードが5個の場合です．Yが通信可能．Nは通信不可能です．

"NYYYY",
"YNNNN",
"YNNNY",
"YNNNY",
"YNYYN"

各ノードは同時に1つの他のノードと通信できるとします．2つ以上とは通信できません．この場合，お互いに通信しているノードのペアを最大いくつ作成できるか？その通信しているノード数（ペア数 x 2 になります）を求めなさいという問題です．

本番中は，思いっきり問題を勘違いしてしまって，Bipertite Matching を使用して解いてしまいました．普通にDPで解くべき問題でした．こんな感じになります．

public class SeparateConnections {

  public int howMany(String[] mat) {
      int N = mat.length;
      int max = 0;
      boolean[] ok = new boolean[1<<N];
      ok[0] = true;
      for (int i = 0; i < (1<<N); i++) {
          if (!ok[i]) continue;
          max = Math.max(max, Integer.bitCount(i));
          for (int n1 = 0; n1 < N; n1++) {
              for (int n2 = n1+1; n2 < N; n2++) {
                  if ( mat[n1].charAt(n2) == 'Y'
                          && (i & (1 << n1)) == 0
                          && (i & (1 << n2)) == 0) {
                      ok[ i | (1 << n1) | (1 << n2)] = true;
                  }
              }
          }
      }
      return max;
  }
}

NumPermutationOrders

1000点問題．ていうか無理．

結果

System Testの結果です． ( Room Statistics )

スコア0です．．．敗退決定です．スコア0は，401位でした． 1点でもスコアがあったら，400位以内に入っていたようです．

今日の教訓

あー勘違い．

2006 TopCoder Open - Odds発表

2006-03-03T23:30:00.001+09:00

予選通過のお知らせメールがきました．

Hello gentoo,

Congratulations! The results of the Qualification Round of the 2006 TopCoder(R) Open, Sponsored by AMD, are official. You have advanced into Round #1, which will take place on Saturday, March 4 at Noon EST (GMT -5). Registration opens at 9:00am and closes at 11:55am EST. All participants in Round #1 will win a 2006 TCO t-shirt.

...

Congratulations again. And, as always, best of luck to you in the Arena!

The TopCoder Competitions Team

Webサイトにも，予選通過者の一覧が発表されていました．

で，面白いものを発見しました．予選通過者の，レーティングと変動率(Volatility) をもとにした，オッズの一覧です．モンテカルロ・シミュレーションにより値を計算しているそうです．

こういう盛り上げ方はうまいですね．．ちなみに私は，

Round1通過: 57.28%
Round2通過: 17.12%
Round3通過: 2.41%
Round4通過: 0.11%

と予想されています．ラスベガスにいける確率は，0.11%ってことですね．．

2006 TopCoder Open Qualification Round

2006-03-02T23:30:00.000+09:00

2006 TopCoder Open - Algorithm Competition - の予選 (Qualification Round)に挑戦です．いよいよ，始まりました． TopCoder Open はTopCoder の "Crown of Jewels" ．一番，盛り上がるイベント・お祭りだそうです．

予選を通過できるのは750名．普段のレーティングが上位の100名は，自動的に予選を免除されますので，残された650の椅子を巡る戦いです．

予選 (Qualification Round): 750名通過
Round1: 750名 -> 400名
Round2: 400名 -> 200名
Round3: 200名 -> 100名
Round4: 100名 -> 48名

見事，Round4を勝ち抜いた48名は，ラスベガスにご招待され，オンサイトで決勝です．

通常のSRMと異なり，予選はちょっと形式が異なります．

問題は2問，制限時間は1時間
開始時間は決まっていない．24時間以内ならいつ挑戦をはじめてもよい
チャレンジ・フェーズはなし

問題セットは，5種類用意され，そのうちどれか1種類が自動的にアサインされます．各問題セットから，上位 (650/5 =) 130 名が予選を通過できます．早速，アリーナに参加してみると

Set14にアサインされました．問題1種類につき，Roomが3つ用意されていますね．計15Roomです．

各Roomごとに，およそ170名ほど割り振られていました．ということは，参加者の総数は 170 x 15 = 2550 名ほどか．

予選通過のためには各Room 内で，130 /3 = 43 位くらいに入るのが目安になるか．自分が挑戦した時間が終了近かったので，もうすでに終わっている人のスコアをあらかじめみることができました．自分がアサインされたRoom14では，こんな様子でした．

なるほど，ボーダーラインの43位に入るためには，2問とも確実に，その上ある程度スピードも要求されそうです．まだシステムテストは終わっていないから，ボーダーはこれより下がるでしょうが，思っていたより，レベルが高そう．．それとも問題が簡単なのか？．．

と思いつつ，自分もスタート．

SlowKeyboard (code)

250点問題．問題の意味をつかむのに，一苦労．

結局，Brute Force で全パターンを調べました．この時点で，18分ほど時間をとられました．まずい．

DigitFilter (code)

750点問題．

数字が与えられます．

k = "12XX355"

Xのところは判明しない桁です．この数字kが(num)で割り切れるとした場合，このような数字kは何通りありますか？という問題です.たとえば，

k = "1X"，num=3

ならば，"12", "15", "18" の3通りです．

k = "23X34XX24XX34X", num=17

ならば，58823通りです．

DPでいけると思い，方針じたいは結構早めに決まったのですが，実装にとまどる，とまどる．あせっていたのか．．結局，30分ほどかかり，Submit．

2問あわせてスコアは536.71． Room14内で，65位ほどでした．．これはだめか．．

結果

最終的なシステムテストの結果です．( Room Statistics )

Room7/9/14 は同じ問題セットだったそうです．そのRoom7/9/14をあわせた中での順位は，

85位．130位以内なので，予選通過ですよね？まだ正式連絡はきていないけれど．

Room14だけ，なぜかハイスコアの人が多かったこと
750点問題に落ちた人が，相当多かった

ということで，85位に入り込めたっぽいですね．

750点問題で落ちた人は，可能な数字をすべて生成してから，それらをnumで割り切れるかどうかをチェックしている人が多かったようです． kの最大の長さの条件は18ですので，k = "XXXXXXXXXXXXXXXXXX" の場合，必要な数字は10^18通りになってしまいます．これを全て調べるのは，絶対無理ですね．．

今日の教訓

もっと正確かつ早い実装力が必要．．

SRM291 - OutOfMemory

2006-02-23T00:30:00.001+09:00

SRM291 に挑戦．

2006 TopCoder Open - Algorithm Competition が来週の2月28日から始まります．今日は，それに向けて最後のSRMになります．

Snowflakes (code)

250点問題．折り紙で雪の結晶をつくりましょう．

このように8等分に折った折り紙に対して，

穴をあけてから，もとの大きさに広げると，あら不思議．雪の結晶のように，対称な，きれいな形ができますねー．あ，そう．って感じですが，，，

問題は，以下のような，8等分に折った折り紙の穴のパターンが与えられたとき，

{"*",
 "..",
 ".*.",
 ".**.",
 ".*.**"}

広げた形のパターンを求めてください．という問題です. 例の場合は，答えはこのようになります．:

{"**.*..*.**",
 "*.**..**.*",
 ".*.*..*.*.",
 "***....***",
 "....**....",
 "....**....",
 "***....***",
 ".*.*..*.*.",
 "*.**..**.*",
 "**.*..*.**" }

悩むところは特にないですが，いかに時間をかけないでサクサクすませられるか勝負です．私は，14分もかかってしまいましたが，早い人は，3分かからずにすませています．．

CrazySwitches (code)

500点問題．素直にBFSでいけました．

StickedWords

1000点問題． Level1，Level2問題を終えた時点で，30分ほど時間がありましたので，1000点問題にチャレンジ．

単語(Word)がいくつか与えられます．

{"salad", "sandwich", "hamburger", "rings"}

これらの単語の最初の文字と最後の文字をつなげて，文字列をつくっていきます．

"hamburgeringsandwichamburger..."

「しりとり」ですね．こうしてできる文字列のうち，長さが (len) 以上のもので，辞書的に一番最初にくる文字列を返しなさい．という問題です．たとえば，入力が

{"abd", "dgga", "abdg", "gga", "gg", "gaader"}
len: 22

ならば，

"abdggabdggabdggabdgaader"

が答えになります．

ちょっと考え，「DPでいける！」と思い，コーディング開始. 1000点問題をはじめて解けるか？！と思ったのですが，時間が足りませんでした．． SRM後，悔しいので完成させました．

public class StickedWords {

  public String constructLine(String[] dict, int len) {

      String[][] dp = new String[len+51][26];
      for (int i = 1; i < dp.length; i++) {
          for (int j = 0; j < 26; j++) {
              for (String word : dict) {
                  if (word.charAt(word.length()-1) - 'a' != j) continue;
                  if (i == word.length()) {
                      if (dp[i][j] == null || word.compareTo(dp[i][j]) < 0) {
                          dp[i][j] = word;
                      }
                      continue;
                  }
                  int pre = i - (word.length() - 1);
                  if (pre <= 0) continue;
                  int first = word.charAt(0) - 'a';
                  if (dp[pre][first] == null) continue;
                  String next = dp[pre][first] + word.substring(1);
                  if (dp[i][j] == null || next.compareTo(dp[i][j]) < 0) {
                      dp[i][j] = next;
                  }
              }
          }
      }
      String res = null;
      for (int i = len; i < len+51; i++) {
          for (int j = 0; j < 26; j++) {
              if (dp[i][j] == null) continue;
              if (res == null || dp[i][j].compareTo(res) < 0) {
                  res = dp[i][j];
              }
          }
      }
      return (res == null) ? "" : res;
  }
}

もうちょっとだったのになーと思っていたけど，実は，ぜんぜんもうちょっとではありませんでした．落とし穴がまっていました．．最悪のケース (len=2500)では,

java.lang.OutOfMemoryError...

を引き起こしてしまいます． TopCoderでは時間（2秒以内）という制限だけではなく，使用メモリの制限 (64Mbyte)もありました．最悪のケース (len=2500)では，最終的にはメモリ使用量は，

2500 x (2500 / 2) x 26 = 81250000

ですから，80MByte を超えますね.．．これはトリッキーだ．．普通，気づかないよな．． 1000点問題にしてはとっかかりやすいと思ったけど，こういう側面があったとは．．こういうのは，問題作成者が意図的にやってるんですね．

ひとつあたりの単語の長さは最大50なので，DPをしつつ，最近の50ステップ分だけ，覚えるようにして，いらなくなったものには，null をいれると．

}
if (i - 51 >= 0) {
    dp[i-51] = null;
}

これで，なんとか System Testに通るようになります．

結果

System Testの結果です． ( Room Statistics )

レーティングは 1626 -> 1730 と100ほど上昇しました．いよいよ来週は，2006 TopCoder Open の予選です．

今日の教訓

メモリ使用量に注意．

SRM287 - 気分は中学生？連立２元方程式

2006-02-05T14:46:00.000+09:00

SRM287 に挑戦． 1ヶ月ぶりの参戦．

TwoEquations (code)

300点問題．以下のような2つの文字列が与えられます．:

"1*X + 2*Y = 6"
"1*X + (-4)*Y = (-3)"

連立2元方程式です．「中学生か俺は？」でした．．これを解いて，解が唯一存在するならば，以下のように解を文字列で

"X=(-7)/3 Y=3/4"

解がないならば

"NO SOLUTIONS"

を，解が複数存在するならば

"MULTIPLE SOLUTIONS"

を返しなさい．という問題です. 250点問題ではなく300点問題ですのでちょっと面倒です．ですがそれほど難しい問題ではないと一見思ったのですが．．

方針としては，各係数A1-A3, B1-B3

A1 * X + A2 * Y = A3
B1 * X + B2 * Y = B3

をパースしてから，

int det = A1 * B2 - A2 * B1;
int x = B2 * A3 - A2 * B3;
int y = A1 * B3 - B1 * A3;

を計算して，det == 0 ならば，「解がない」か「解が複数」

if (det == 0) {
    if (x == 0) {
        return "MULTIPLE SOLUTIONS";
    }
    return "NO SOLUTIONS";
}

それ以外ならば，「解がひとつ」ということで，

"X=x/det Y=y/det"

として，約分等・正しくフォーマットして返せばよい．これでいけると思ってSubmitしたのですが，甘かったです．

これだけでは，以下のような係数がゼロの場合に対処できませんでした．

"0*X + 0*Y = 1"
"0*X + 0*Y = 2"

この場合は，正しい正解は"NO SOLUTIONS"ですが，上記ロジックだけだと"MULTIPLE SOLUTIONS"を返してしまいます．

以下のように係数ゼロを特別に扱う必要性がありました．

if (A1 == 0 && A2 == 0 && A3 != 0) return "NO SOLUTIONS";
if (B1 == 0 && B2 == 0 && B3 != 0) return "NO SOLUTIONS";
if (A1 == 0 && B1 == 0 && (A2 * B3 - B2 * A3) != 0) return "NO SOLUTIONS";
if (A2 == 0 && B2 == 0 && (A1 * B3 - B1 * A3) != 0) return "NO SOLUTIONS";

私も含めて多くの人はゼロのケースを考慮しないCodeを書いてしまったようです．これに気づいた人は，チャレンジタイムで大稼ぎしていました．

この問題のDivision1での正解率は11%，同じ問題がDivision2のレベル2問題にも使用されていましたがDivision2ではなんと正解率0%，誰ひとり正解できなかったようです．．

MooresLaw (code)

450点問題．

「ムーアの法則」: コンピュータのスピードは，18ヶ月で2倍になる

今，計算を始めると14年かかる問題があるとします．今すぐ始めるのではなく，18ヶ月待ってスピードが2倍の新しいコンピュータを買ってそれで計算を始めると7年ですみます． 14年かかる計算が，合計 (1.5 + 7 = ) 8.5年ですむわけです．この例だと，約4年まってから計算を始めるのがベストです．合計( 4 + 2.2 = ) 6.2年ですみます.

このように，計算にかかる年数 (years) が与えられた場合，ムーアの法則が成り立つとすると，最短・今から何年後に計算を終わらせることができるでしょうか？という問題です．いつ新しいコンピュータを買い計算をはじめるか？がポイントになります．

x年後に，新しいコンピュータを買って計算を始めるとすると，トータルでは

y = x + (years / 2^(x / 1.5) )

かかることになります．このyが最小になるxを探せばよいことになります．数学的に解くことはできるのでしょうが（微分してゼロになるところを求める）．．数学的に悩むよりは，このようなU字型の関数の場合は，いわゆるbinary searchではなく，ternary search で，yが最小になるxを探すことができます．

区間 ( [left, right] ) 内の2点(x1, x2)をとり，y1, y2 を計算して，

y1 > y2 ならば，left = x1
y1 < y2 ならば，right = x2

として，区間を狭めていけば，最終的には，最小のyをとるxaにたどり着きます.

public class MooresLaw {

  public double shortestComputationTime(int years) {

      double left = 0;
      double right = years;

      while (right - left > 1e-11) {
          double x1 = (left * 2 + right) / 3.0;
          double x2 = (left + right * 2) / 3.0;
          if (cal(x1, years) > cal(x2, years)) {
              left = x1;
          } else {
              right = x2;
          }
      }
      return cal(right, years);
  }

  double cal(double x, int years) {
      return x + years / Math.pow(2, x / 1.5);
  }

SRM中は，x年後のコンピュータのスピードが，Math.pow(2, x / 1.5) で表せることにきずかず，前半部分・回りくどいことをしていまいました．．．なんとか正解しましたが．

CoinGame

1000点問題． Openしたものの，手が出ず．．

結果

System Testの結果です． ( Room Statistics )

全体的にポイントが低かったためか，レーティングは 1542 -> 1626 と上昇しました．

SRM281 - 2006年はポイントゼロスタート

2006-01-07T00:30:00.000+09:00

SRM281 に挑戦．今年，最初のSRMです．例のごとく日本時間の深夜1:00スタートという，ありがたいんだが，ありがたくないんだがよくわかりませんが，やはり眠いなかでの参戦となりました．まあ，平日昼間だと参加できないので，ありがたいんでしょうが．．

IntegerGenerator (code)

250点問題．

int[] allowed: 使用が許されている数字(0-9のいずれか)のリスト
String current: 現在の数 (整数)

が与えられます．この時，

与えられた数 currentの各桁が許可数字だけを使用しているかどうかをチェック
1がOKなら，許可数字だけを使用して currentより大きい次の数字を生成して返しなさい

という問題です．たとえば，

allowed: {1, 2, 3}
current: "2133"

ならば，current: 2133 の各桁は，許可数字{1, 2, 3}に含まれているものだけを使用しているのでOKです．また，currentより大きい，許可数字だけを使用した次の数は，"2211" になります．

最初は，ただ単にcurrentを1ずつincrementしてOKかどうかチェックするという単純な方法で十分と思い込み，8分ほどでSubmitしました． Submit後に，いくつかチェックしていると，入力条件によってはこれではタイムアウトすることに気づきました．入力が

{9}, "9999999999" (10桁)

でタイムアウトです．この場合の正解は"99999999999" (11桁) ですが，1ずつincrementしていては，とてもじゃないが2秒以内には終わりません．

慌ててやり直しましたが．．．はまりました．．完全に方針を誤り右往左往でした．最終的になんとか完成させ再提出したのですが (提出時点ではポイント75と最低点でした...），それでもバグがひとつ入っていたため，System Testに落ちました．入力のint配列: allowed が空のケースで，ArrayIndexOutOfExceptionが発生させてしまっています．

初歩的な入力条件のチェックミス．．空かどうかチェックを一行いれておけば，SystemTestに通っていましたね．

SRM後に，冷静になって，コードを書き直してみました．使用できる数字が限られたケースで，1を足す動作を，シミュレートするだけです．

public class IntegerGenerator {
  public String nextInteger(int[] allowed, String current) {
      Arrays.sort(allowed);
      char[] ca = current.toCharArray();
      if (ca[0] == '0') return "INVALID INPUT";
      for (char c : ca) {
          if (Arrays.binarySearch(allowed, c - '0') < 0) return "INVALID INPUT";
      }
      for (int i = ca.length - 1; i >= 0; i--) {
          int index = Arrays.binarySearch(allowed, ca[i] - '0');
          if (index == allowed.length - 1) {
              ca[i] = (char) ('0' + allowed[0]);
          } else {
              ca[i] = (char) ('0' + allowed[index + 1]);
              return new String(ca);
          }
      }
      return ((allowed[0] == 0) ? allowed[1]: allowed[0]) + new String(ca);
  }
}

こうしてみるとそんなに難しい問題ではなかったですね．やっぱり250点問題です．本番中は，頭が回りませんでした．．．

BallBouncing

600点問題．Openしませんでした．

Equidistance

1000点問題．Openしませんでした．

結果

System Testの結果です． ( Room Statistics )

今日は，惨敗です．チャレンジタイムも，ターゲットが次々とほかの人にさらわれてしまい，結局，チャレンジゼロでした．．

レーティングは 1630 -> 1542 と，100近く低下しました．

今日の教訓

当たり前ですが，入力条件をよく読むように．

SRM280 - Challenge祭り

2005-12-30T00:30:00.003+09:00

SRM280 に挑戦．今年，最後のSRMになります．思えば今年の後半は，TopCoderで楽しませてもらいました．いまや，2週間に一度ほどの「趣味」です．

CompletingBrackets (code)

250点問題． " ]][][]][ "のように閉じ括弧・開き括弧のみを含んだ文字列が与えられます．この文字列の最初・または最後に，できるだけ最小限の" ] "または " [ "を与えて，ちょうど括弧が対応するように文字列を完成させその文字列を返す問題です．例の場合は，最初に " [ "を3個，最後に" ] "を1個加えた，" [[[]][][]][] "が正解になります．

これまでは250点問題は，何も考えずにただ実装ということが多かったいのですが，今回は一瞬，どうしたらよいかわかりませんでした．「まずい」と思いましたが，力任せに「うまくいくであろう」方法でなんとか仕上げました．はっきりいって根拠なしでしたが，手元で試した限りでは，あらゆるケースで問題がなかったので，そのままSubmitしました．

GridCut (code)

500点問題．幅 (width) cm x 高さ (height) cm の紙があります．紙には，方眼紙のように1cm間隔で格子状に線が引いてあるとします．この紙をはさみを使って，n セルだけ面積を残して切り取りたいとします．最低，何cmはさみで紙を切る必要があるでしょうか？という問題です．はさみは格子状の線に沿ってしか使用できません．ななめにきってはだめです．

図のような，5 x 10 の紙の場合，

10セルだけ残すときは，左の赤のラインが最小の長さです．答えは5
18セルだけ残すときは，左の緑のラインが最小の長さです．答えは6

アルゴリズムの知識というよりは，論理的思考力を問われる問題です．いわゆる小学生でもその気になれば解ける問題です．散々，悩んだあげく，とりあえず提出しました．

．．ですが，Level 3 問題があまりに手がでなかったのであきらめて，Level2問題を見直していたところ，バグにきずいて，再提出しました．再提出するとポイントは30%のペナルティが与えられます．

「n」セル残すというのは，「 width * height - n 」セル残すということと同じことなんですね．．．それをまったく考慮していなかったため，それに対応させました．

DrawPlanar

1100点問題．いつもの「1000点」じゃなくて，「1100点」ってだけで，もう恐ろしさ満点です．まったくお手上げでした．さすがに，正解できた人は，Division1 304人中3人だけでした． (Problem Detail)

結果

今回は，チャレンジタイムでは，GridCutの問題で，(100, 100, 9001) という入力でチャレンジしまくりました．自分がミスっていたところは，きっと他人もミスっているに違いないと勝手に思い込んで．手当たり次第，チャレンジして，12チャレンジ，8個撃墜しました．

System Testの結果です． ( Room Statistics )

チャレンジしまくった結果です．自分も同じ問題を，チャレンジされ撃墜されたというオチまでついています． square * (square-1) のケースを考慮していませんでした．．

レーティングは1520 -> 1630 と上昇しました．

SRM277 - 初賞金げっと

2005-12-27T01:39:00.000+09:00

SRM277 に挑戦．ちょうど10回目のSRMです．土曜の深夜2:00が開始時間でしたので，眠かった．．．

RogersPhenomenon (code)

250点問題． Division1にしては比較的容易でした．

AirlinerSeats (code)

500点問題．飛行機内のいわゆる「通路側座席」の数が最大になるように座席を配置する問題です．これも，500点問題にしては簡単な方だと思います．小学生でも十分できる問題です．

SafeJourney

1000点問題．うーん，できませんでした．方針すら浮かびませんでした．問題空間をコンパクト化するのがポイントだったようです．あー，なるほど．そうすれば，十分，BFSでいけます．

結果

System Testの結果です． ( Room Statistics )

レーティングは1500台になり，イエローネームになりました．今回でちょうど10回目のSRMでしたので，記念に，現時点の状況を残しておきます．レーティングの推移です．

まだ，初登場時のレーティングには届いていません.

今回のSRMは，MSNがスポンサーで上位の人には賞金が出ます．自分には縁がないと思っていたのですけど，後日，メールが来て

Congratulations! The results of TopCoder SRM 277 are official. You have won $32.0.

In order for TopCoder to release payment to you, you must complete certain steps within 60 days of this email. Please follow the instructions here: http://www.topcoder.com/PactsMemberServlet?t=affidavit&c=affidavit_history

Unless you have previously specified otherwise, your prize money will, by default, be paid by check. If you would like to be paid by wire transfer or PayPal, send an email to XXXXXXXXX with the details of your preferred payment method. Remember to include your TopCoder handle in the email.

Please keep in mind that you have 60 days to claim your prize. Your prize will be forfeited if it is not claimed within 60 days.

Congratulations again on your SRM performance.

As always, best of luck to you in the Arena!

The TopCoder Competitions Team

$32 賞金がもらえることになりました．「どうやって，賞金をうけとればよいのか？？？」と思って調べていたのですけど，やはり手続きが面倒そうです．．

宣誓証書
Tax Form

などを一度は郵送でTopCoderへ送っておく必要があります．賞金を受け取らずにチャリティーに寄付することもできるそうなので，寄付しようかな．

今日の教訓

問題空間のコンパクト化

マラソン・マッチ

2005-12-17T00:30:00.000+09:00

TopCoder が新しい形式のアルゴリズム・コンテストを開始しました．マラソン・マッチです．現在，ベータ・テストを行っています.

通常の短期決戦のSRMと違い長期戦です．

期間は1週間
与えられる問題は，いわゆる「正解」があるような問題ではない．
期間内なら何回でもSubmitできる
SubmitしたCodeは，ある基準（問題による）に従い採点されスコアがつけられる

なるほど面白そうです. どんな問題が出題されているのか，興味があったので参加してみました．まだコンテスト期間内なので，問題の内容について書くことはできないですが，うーんなるほど．って感じです．既に参加者は700名を超えているようです．

早速，誰もが思いつくような方法でCodeを書いてみてSubmitしてみました．現在，43位です．

reStructuredTextでblogger

2005-12-16T00:30:00.000+09:00

このBlogは，もともとは reStructuredText 形式で書いています．ここで公開しているのはそれをHTMLに変換した結果です． Blogger では， ATOM API が用意されているので，ありがたいことにブラウザを使用しなくてもBlogの更新ができます．

以下のような手順をとっています．

reStructuredText形式で，テキストファイルを作成
Python，docutils で html に変換
2のhtmlを ATOM API で Blogger.comへ更新

2と3はひとつのPythonスクリプト内で行っています． reStructuredText から html への変換は，docutilsで行えます．

from docutils.core import publish_parts
parts = publish_parts(
    content,
    writer_name='blogwriter'
    )

docutils付属の html_writer を継承して・ほんの少しだけ修正した自作のblogwriter を使用しています．変換された，htmlのタイトル( parts['title'] )と，body部分 parts['body'] を，以下のテンプレートにセットして

entrytemplate = u'''<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<entry xmlns="http://purl.org/atom/ns#">
 <title mode="escaped" type="text/plain">%(title)s</title>
 <issued>%(issued)s</issued>
 <generator url="http://www.yoursitesurlhere.com">python</generator>
 <content type="application/xhtml+xml">
   <div xmlns="http://www.w3.org/1999/xhtml">
   %(content)s
   </div>
 </content>
%(draft)s
</entry>'''

ATOM API で送れば，Blogの更新が行えます．これらの一連の作業を行う myblogger.py というPythonスクリプトを作成して使用しています．テキストファイルを入力として，コマンド一発でBlogエントリの新規作成・更新を行えます．以下のような感じです

myblogger.py merge 273.txt

書きなれた reStructuredText 形式で Blogを書けるのは快適です． ATOM API はほとんどのBlogサービスがサポートしているはずですので，もし将来Blogを引越しすることになっても，ローカルにあるテキストを全部再発行するだけですみます．

TopCoder のコンテストでは，現在，使用できる言語はJava, C#, C++, VB の4つだけです． Pythonが使えるようにならないかなー．

2006 TopCoder Open - NSAがスポンサーに

2005-12-13T02:28:00.000+09:00

2006 TopCoder Open が開催されるようです．

賞金総額は，$150,000 です．予選，Round1,2,3,4，そしてオンサイト（ラスベガス）でのファイナルというふうに，何回かにわけて行われる形式のようです. あの NSA (National Security Agency) がスポンサーになるようですね．いい成績を残せた人は，NSAから声がかかるのでしょうか？

予選は，来年2月28日です．とりあえず，予選通過(750名)を目標に挑戦してみたいと思います.

SRM276 - お買い物は楽しくDPで

2005-12-09T02:28:00.000+09:00

SRM276 に挑戦．かなーり，眠かったので，スルーしようかと思ったのですが，挑戦しました．

VolumeDiscount (code)

250点問題．お買い物です．たとえば，

1個なら4$
3個まとめて買うと10$
20個まとめて買うと48$

だったとします．50個，買いたいとします．最低何$ですむか？という問題です. この例だと

20個 x 2 + 3個 x 3 + 1個 x 1= 50個 (48$ x 2 + 10$ x 3 + 4$ x 1 = 130$)

がベストな買い方で，答えは 130 です．しかし，50個ではなく，55個買いたいとすると，ベストな買い方は

20個 x 2 + 3個 x 5 = 55個 (48$ x 2 + 10$ x 5 = 146$)

ではなく

20個 x 3 = 60個 ( 48$ x 3 = 144$)

です．答えは，144 になります． SRM中は，入力条件が緩いのでBrute-Forceで十分いけると思ってSubmitしました．チャレンジタイムでは，MemoizationなしのBrute-Forceではタイムアウトすると思われたのか, 2回チャレンジをうけました．チャレンジで使用された入力は

と明らかに2秒タイムオーバー狙いです．チャレンジタイム後に，チャレンジしてきた人に質問されました． 2秒以内に終わったのが，信じられなかったようです.

その後, HiltonLange さんには，さらに

{"51 1","1 99"}, 99 だと，失敗するんじゃない？

と指摘されました．そのとおりです．この入力だと51個x2=101個，2ドルが正解ですが，SubmitしたCodeでは

for (int i = 0; q + i * unit[n] < 100; i++) {

このように上限を100にしていたため，51 x 1 + 99 * 48 = 4803ドルを出力していまいます．上限は，最低200じゃないと．System Testに落ちますね．．．

for (int i = 0; q + i * unit[n] < 200; i++) {

このように上限200にしておくと，2秒近くかかりますが，なんとかSystem Testに通っていました．それでも無駄だらけなので，無駄をなくすと共に，Memoizationを併用すれば，劇的に早くなります．以下のようになります．

int go(int q, int n) {
   if (n == N) {
       if (q < quantity) return 1000000;
       return 0;
   }
   if (cache[q][n] != 0) return cache[q][n];
   int min = Integer.MAX_VALUE;
   for (int i = 0;; i++) {
       min = Math.min(min, cost[n] * i + go(q + unit[n] * i, n+1));
       if (q + i * unit[n] >= quantity) break;
   }
   return cache[q][n] = min;
}

この手の問題は，やはりDP(Dynamic Programming)を使うのが常套手段でしたね． SRM後に書いてみました.

public int bestDeal(String[] priceList, int quantity) {
    int N = priceList.length;
    int[] unit = new int[N];
    int[] cost = new int[N];
    for (int i = 0; i < N; i++) {
        unit[i] = Integer.parseInt(priceList[i].split(" ")[0]);
        cost[i] = Integer.parseInt(priceList[i].split(" ")[1]);
    }

    int[] best = new int[300];
    Arrays.fill(best, Integer.MAX_VALUE);
    best[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < quantity; j++) {
            if (best[j] != Integer.MAX_VALUE) {
                if (best[j] + cost[i] < best[j + unit[i]]) {
                    best[j+unit[i]] = best[j] + cost[i];
                }
            }
        }
    }

    int min = Integer.MAX_VALUE;
    for (int i = quantity; i < quantity + 100; i++) {
        min = Math.min(min, best[i]);
    }
    return min;
}

ほとんどの人は，さくっと躊躇することなくDPを使用していました．さすが，Division1．

TestingCar

500点問題．レーシングカーの試験走行をします．ただし，時間帯により制限速度の条件がいくつか与えられます.

[5秒から10秒の間は，10 m/s以上スピードを出してはいけない ]
[15秒から20秒の間は，15 m/s以上スピードを出してはいけない ]
[30秒から40秒の間は，5 m/s以上スピードを出してはいけない ]

というふうにです．入力として

レーシングカーの加速度 a (m / s^2 ) (減速度(?) も兼ねています．）
試験走行の時間 (duratation) が与えられます.

この条件のもとで，レーシングカーが出せる最高速度はいくつになるかという問題です. SRM中は，途中で方針が間違っていたことことにきずき，お手上げでした．（つぎのつぎの制限速度の変更を考慮していなかったため減速が間に合わない．）

ForceTest

1000点問題． Openしませんでした．

結果

System Testの結果です． ( Room Statistics )

レーティングは低下．今日は，敗北感が強いな．．

今日の教訓

DPをちゃんとマスターしておく

SRM273 - bit演算はintで行われるのね

2005-11-22T00:30:00.000+09:00

SRM273 に挑戦．はじめて，平日の昼に挑戦です．今までは，日本時間の夜に開催されるSRMにしか参加しませんでした．

FallingCoconuts (code)

250点問題．ココナッツを上から落としておとしていきます．積みあがった形を返す問題です．テトリスみたいなものですね．番人(Sentinel)というちょっとしてTipsを使いました．あらかじめ，一番下の段にココナツを敷き詰めておけば，ココナツが下にはみだすことはありません．一番下までココナツが落ちたときの条件をチェックする必要がなくなります．一番下の段に敷き詰めたココナツば番人がわりになってくれるわけです．今回は，特にSentinel を使うまでもないですが，ときどきあらかじめSentinelを用意しておけば，条件チェックが非常に楽になるケースがあります．

SnakeTurbo (code)

500点問題．

o---o-o-S--o--o--------G---o

Sが Snake(へび)がいるスタート地点，Gがゴール地点です．へびは1秒に1単位進むことができます． o はパワーアップえさです． o を食べるたびに，へびはスピードが2倍になります．

2つ食べれば4倍
3つ食べれば8倍
4つ食べれば16倍

というふうに，効果は累積します．へびがスタート地点からゴールするまでの最短時間を求める問題です．

これも，前回のSRM272のLevel2問題，RoundTableと同様に，Recursive + Memoization で解きました. 自信があったんですけど，System Testに落ちました．うーん，どこがおかしいかしばらく気づきませんでした．．発見してみてください．ここです

double boost = 1 << (right - left);

ここは，現在のへびのスピード，すなわち 2の (right - left) 乗を求めているところです．入力の条件は，

orbs will contain between 0 and 50 elements, inclusive.

なので，(right - left) は32以上になる可能性があります．右辺のビットシフトは int で計算が行われます． int は32ビットなので，(right - left) が32以上のときは対応できません．素直に

double boost = Math.pow(2, (right - left) );

または

double boost = 1L << (right - left);

とlongを使用しておけば，何の問題もなく，System Testに通っていました．残念．

RobotCollision

900点問題．時間たりず．Level3 問題にしては，簡単なほうだったみたいです．条件を絞れば，Brute-force でいけます．

結果

System Testの結果です． ( Room Statistics )

レーティングはちょっとだけ上昇しました．

SRM272 - Division1 - 4度目の正直

2005-11-20T00:30:00.000+09:00

SRM272 に挑戦．今回のSRMは，msnがスポンサーです．$5,000の賞金がでます． TopCoderでは，ときどきこのようなSponsored Match が行わています．優秀な人材がほしい企業と，名を売りたい人たちの出会いの場の役目も果たしています.

FewestFactors (code)

250点問題．数字(0〜9)が最大5個与えられます．それらを並べ替えてできる最大5桁の数のうち，Factor(約数)の数が最も少ないものを求める問題です．たかだか最大5個ですので，全ての並び方を試せばOKです．いわゆるpermutationです． C++ だと， STL にその名もずばり next_permutation() がありますので，それを使うとよいです． C++以外の言語では，DFS (depth first search)で再帰的にpermutationを生成すればよいでしょう．

RoundTable (code)

500点問題． A社の代表 (countA)人と B社の代表 (countB) 人が円卓に座ってミーティングをします．椅子の数は (chairs) です．同じ会社の人どおしは，隣り合って座ってもよいですが， A社の人とB社の人は，間に距離をいす(minDistance) 分だけあけて座らなければいけません．

minDistance = 1 は，隣り合っていてもいいです．
minDistance = 2 だと，間に最低1つのいすが必要．
minDistance = 3 だと，間に最低2つのいすが必要．
...

というわけです．可能な座り方の数はいくつか? という問題です． SRMでは，Recursive と Memoization というパターンでときました．この手の問題は，DP(Dynamic Programming:動的計画法)を用いることもできます．こんな感じになります．

public class RoundTable {

  public long arrangements(int countA, int countB, int chairs, int minDis) {
    long[][][][][] dp = new long[chairs][minDis][minDis][countA+1][countB+1];
    dp[0][0][minDis-1][countA-1][countB] = 1;
    for (int c = 1; c < chairs; c++) {
        for (int pa = 0; pa < minDis; pa++) {
            for (int pb = 0; pb < minDis; pb++) {
                for (int a = 0; a <= countA; a++) {
                    for (int b = 0; b <= countB; b++) {
                        int npa = Math.min(minDis-1, pa+1);
                        int npb = Math.min(minDis-1, pb+1);
                        // Neither sit on the chair
                        dp[c][npa][npb][a][b] += dp[c-1][pa][pb][a][b];

                        // Arep can sit on the chair
                        if (pb == minDis-1 && a > 0)
                            dp[c][0][minDis-1][a-1][b] += dp[c-1][pa][pb][a][b] * a;

                        // Brep can sit on the chair
                        if (pa == minDis-1 && b > 0 && c + minDis <= chairs )
                            dp[c][minDis-1][0][a][b-1] += dp[c-1][pa][pb][a][b] * b;
                    }
                }
            }
        }
    }

    long ret = 0;
    for (int pa = 0; pa < minDis; pa++) {
        for (int pb = 0; pb < minDis; pb++) {
            ret += dp[chairs-1][pa][pb][0][0];
        }
    }
    return ret * chairs;
  }
}

レーティングが高い人たちは，平気でDPを使用してきます.

ManhattanDistance

1000点問題．これも，DPでいけると思ったのですけど，500点問題で時間をほとんど使いきったため，さすがに時間が足りませんでした. グラフをつくって，Dijkstra法でもいけます．1000点問題にしては，とっかかりやすいかと．

結果

System Testの結果です． ( Room Statistics )

ようやく，Division1ではじめてSystem Testに通りました． Level2問題も解けたので，充実感．レーティングは 1214 -> 1429 と上昇しました．

SRM270 - Integer == Integer

2005-11-04T00:30:00.001+09:00

SRM270 に挑戦．Division1に挑戦するのはこれが3回目ですが，前の2回は，

Level1問題 - どちらもSubmitするも，単純なミスでSystem Testに落ちる.
Level2問題 - どちらも時間切れ．
Level3問題 - Openしたことさえありません．．

とまだ1問もSystem Testに通ったことがありません．今度こそは1問は通るように．．

CountriesRanklist (code)

300点問題． Codeは提出．今度こそ大丈夫と思っていたもの，またSystem Testで落ちてしまいました．どこがおかしいんだろとCodeを見ていて，5分ほど．ようやく間違いを発見しました．ここです

if (l.get(i) == maxscore.get(key))

Integer と Integer を == で比較しています．．．あーやってしまった． J2SE5からautoboxing/unboxing が使えるようになりましたが，すっかりそれに頼りきっていました．このように左辺と右辺ともに Integer の場合は，だめですね．．equals(..) じゃないと．どちらかがintならよかったんだけど．また単純ミスだ．．

SalesmanDilemma

600点問題．巡回セールスマン問題．．ではありません．基本的には最短経路を求める問題に落ち着くのですが，やっかいな点としてネガティブ・ループの考慮をする必要があります． SRM中は，時間切れでSubmitできませんでした．もう少しだったんですけど．

SRM後に，完成させたコードです．タイムオーバーになるかと思ったのですが，今回の条件ではこれでも十分2秒以内でした．

import java.util.Scanner;
public class SalesmansDilemma {

int[][] p;
int[] visited;
int destination;

final int NA = Integer.MIN_VALUE;
final int ENDLESS = Integer.MAX_VALUE;
final int IMPOSSIBLE = Integer.MIN_VALUE;

int goal = IMPOSSIBLE;

public String bestRoute(int towns, int origin, int destination,
        String[] travelCosts, int[] profits) {
    this.destination = destination;
    p = new int[towns][towns];
    for (int i = 0; i < towns; i++) Arrays.fill(p[i], NA);
    for (int i = 0; i < travelCosts.length; i++) {
        Scanner s = new Scanner(travelCosts[i]);
        int from = s.nextInt();
        int to = s.nextInt();
        int cost = s.nextInt();
        p[from][to] = Math.max(p[from][to], profits[to] - cost);
    }

    visited = new int[towns];
    Arrays.fill(visited, IMPOSSIBLE);
    visited[origin] = 0;
    go(origin);

    if (goal == IMPOSSIBLE) return "IMPOSSIBLE";
    if (goal == ENDLESS) return "ENDLESS PROFIT";
    return "BEST PROFIT: " + (goal + profits[origin]);
}

void go(int town) {
    if (town == destination) goal = Math.max(goal, visited[town]);

    for (int i = 0; i < p[town].length; i++) {
        if (p[town][i] == NA) continue;

        int old = visited[i];
        int update = (visited[town] == ENDLESS) ?
                     ENDLESS : visited[town] + p[town][i];

        if (old == IMPOSSIBLE) {
            visited[i] = update;
            go(i);
            visited[i] = old;
        } else if (update > old) {
            visited[i] = ENDLESS;
            go(i);
            visited[i] = old;
        }
    }
}

この手の問題では，Bellman-Ford アルゴリズムを用いるのが定石のようです．ある地点からある地点までの，最短経路，およびネガティブ・ループを発見するアルゴリズムです．練習がてら，Javaで実装してみました．

import java.util.Scanner;
public class SalesmansDilemma {

class Edge {
    int source;
    int destination;
    int weight;
}

public String bestRoute(int towns, int origin, int destination,
        String[] travelCosts, int[] profits) {
    Edge[] edges  = new Edge[travelCosts.length];
    for (int i = 0; i < travelCosts.length; i++) {
        Scanner scan  = new Scanner(travelCosts[i]);
        edges[i] = new Edge();
        edges[i].source = scan.nextInt();
        edges[i].destination = scan.nextInt();
        edges[i].weight = scan.nextInt()
                         - profits[edges[i].destination];
    }
    long[] verticles = new long[towns];
    long INFINITY = Long.MAX_VALUE;
    for (int i = 0; i < verticles.length; i++) {
        verticles[i] = INFINITY;
    }
    verticles[origin] = 0;

    boolean[] negative = new boolean[towns];

    // relax and find negative cycle
    for (int i = 0; i < verticles.length + 1; i++) {
        for (Edge e : edges) {
            int u = e.source;
            int v = e.destination;
            if (verticles[u] == INFINITY) continue;
            if (verticles[v] > verticles[u] + e.weight) {
                verticles[v] = verticles[u] + e.weight;
                if (i == verticles.length) {
                    negative[v] = true;
                }
            }
        }
    }

    if (verticles[destination] == INFINITY) return "IMPOSSIBLE";

    boolean[] mark = new boolean[towns];
    for (int i = 0; i < towns; i++) {
        if (negative[i] && !mark[i]) {
            go(i, mark, edges);
        }
    }
    if (mark[destination]) return "ENDLESS PROFIT";

    return "BEST PROFIT: " +
           -(verticles[destination] - profits[origin]);
}

void go(int v, boolean[] mark, Edge[] edges) {
    mark[v] = true;
    for (Edge e : edges) {
        if (v == e.source && !mark[e.destination]) {
            go(e.destination, mark, edges);
        }
    }
}
}

PackingShapes

900点問題． SRM中はOpenしませんでした．ある長方形のなかに，別の長方形をはみださないようにいれることができるか判定する問題です．たとえば，幅100 x 高さ100 の長方形には，幅140 x 高さ1 の長方形は（傾ければ）いれることができます．幅140 x 50 の長方形はどんなにがんばってもはいりません．

結果

System Testの結果です． ( Room Statistics )

レーティングは 1303 -> 1214 と低下．かろうじてDivision1には残っています.

今日の教訓

Primitive とラッパー．．Javaを使い続ける限りつきまとう，もっとも頭のいたい問題です． autoboxing/unboxing には惑わされないように．

SRM268 - Division2脱出

2005-10-19T00:30:00.000+09:00

SRM268 に挑戦．Division2の問題です．

CrossWordPuzzle (code)

250点問題． 1文字・1文字，順にチェックしている人が多かったようですが，正規表現を使用した文字列分割 (いわゆる split(..)) が利用できる言語なら，それを使えば簡単です．今回は正規表現を使用するほどでもないですが，正規表現を使用すれば，ずっと簡単になる問題もTopCoderではときどき出題されるようです．

CmpdWords (code)

500点問題．一見，問題がわかりにくいですが，ハッシュテーブルを使用して，合成文字列の重複のカウントをすれば，これも簡単です．

TriArea

1000点問題．重なり合う2等辺三角形が複数与えられます．それらがカバーする面積をもとめる問題です. 3角形の重なりを判定して全体の面積を求めようととしたのですが， 1時間以上，格闘したあげく，時間切れでした．

パラメータの条件として

Each element of xCenter and yCenter will be between -100 and 100, inclusive.

とあるので，全2次元空間をひたすら調べたほうが簡単でした. 1 x 1 のグリッドをさらに4つのエリアにわけて，そのエリアが三角形に含まれているなら

(面積) += 0.25

とすればよいです．

public class TriArea {

  public double area(int[] xCenter,
                     int[] yCenter, int[] height) {
    double res = 0;
    int N = xCenter.length;
    int[] dx = {1, 2, 2, 3};
    int[] dy = {2, 1, 3, 2};
    for (int x = -200; x < 200; x++) {
      for (int y = -100; y < 200; y++) {
        for (int d = 0; d < 4; d++) {
          double nx = x + dx[d] / 4.0;
          double ny = y + dy[d] / 4.0;
          for (int i = 0; i < N; i++) {
            if (ny < yCenter[i]) continue;
            if ( height[i] > Math.abs(xCenter[i] - nx)
                  + (ny - yCenter[i])) {
              res += 0.25;
              break;
            }
          }
        }
      }
    }
    return res;
  }
}

これでも，Order は 400 x 400 x 4 x 25(3角形の最大数) ですから，これで十分いけましたね．．

結果

System Testの結果です． ( Room Statistics )

1000点問題ができなかったのが悔やまれますが,250点問題と500点問題は早めにSubmitできたためか，ルーム内ではTopのポイントでした．レーティングは 1152 -> 1303 と 1200を超えたので，Division2脱出です．

今日の教訓

入力条件をよくチェックする．入力条件によっては，エレガントに解く必要はない．全部調べても大丈夫な場合がある．特にDivision2は．

SRM266 - NASA, we have a problem...

2005-10-02T00:30:00.000+09:00

SRM266 に挑戦． Division2落ちしたので，今日からはDivision2．一発でDivision1に復帰するのが目標．前回，TopCoderに初挑戦したときは，Division2の問題は3問ともSubmitできたので（1問は間違っていたけど．．），今回もなんとかなるか，と甘い気持ちでスタート．

SwimmersDelight (code)

250点問題．幅が10フィートの川があります．間には足場となる2つの石があります．最適な飛び方をした場合,もっとも長いジャンプはどれだけの長さですむか？という問題です．石の座標(x, y) (xが川の幅方向: 0<=x<=10) が(3, 5), (6, 2)だとすると，

スタート (0, 5) --(距離3)--> (3, 5) --(距離4.24..)--> (6, 2) --(距離4)--> (10, 2) 到着

といけば，最大のジャンプは 4.24.. ですみます. 全部のパスを調べればよいだけの問題ですので，さくっと終わらせて（といっても13分かかってますけど）．

ExploringEuropa

550点問題．木星の月・Europa上の地表探査機に対して，NASAから指示（「REVERSE」「STOP」）を出して，ちょうど探査対象の上に探査機を停めたい．いつ指示をだすのがBestか？という問題です. NASAと探査機の間は，すぐに指示が伝わらなくDelayが生じる．のが問題の肝です．問題文が長いのはいいとして，問題を呼んだ直後はそんなに難しいとは思わなかったのですけど，，はまりました．．． 1時間以上格闘したあげく，結局時間切れでした．

ZCurve

900点問題． SRM中はOpenしませんでしたが，こちらのほうが簡単でした． ExploringEuropa はとっとと捨てて，こちらににとりかかればよかった．

結果

System Testの結果です． ( Room Statistics )

ExploringEuropa と ZCurve は Division1のLevel1(300点)問題, Level2(450点)問題にも使用されていました．どちらのDivisionの結果をみても，ExploringEuropaの方が，あきらかに正解率が悪かったです．なかなか状況把握やとっかかりがつかみにくいようで，みなさん苦労したようです．難易度とポイントのバランスを考えると，「問題をいれかえるべきだったのでは?」という声が多かったです. その気になれば，手作業・手計算でも正解を導き出せる問題なんですけどね．レーティングはさすがに下がると思っていたけれど，ちょっとだけ上昇でした．

今日の教訓

はまったときはその問題を捨てて次の問題へ．必ずしも順番に解いていく必要はなし．

Division2脱出はならず．．次回もDivision2です．．

SRM265 - Division2落ち...

2005-09-28T00:30:00.001+09:00

SRM265 に挑戦．前回急降下したレーティングは1255です．まだ1200以上なのでかろうじてDivision1には残っています．前回はポイントゼロだったので，今回こそは一問でいいからSystem Testに通ることを目標に．今回もゼロだとおそらく1200以下に落ちます．

ScheduleStrength (code)

250点問題．リーグ戦において

ある2チームの勝率が同じだった
どちらか1チームをプレーオフに進出させなければいけない

このような状況のとき，より厳しいスケジュール・強い対戦相手と戦ってきたチームを優先させましょう．このスケジュールの厳しさを計算せよという問題です．これもやはりただ実装するだけという問題なのですが，最初，意味を勘違いしていたこともあり，大幅に時間がとられてしまいました．しかし，44分は時間かけすぎ．

Recipe

500点問題．料理の正しいレシピ (例 - 塩:大さじ4，砂糖:小さじ18, 醤油: カップ2杯) と，実際にボールに入れて混ぜてしまった量(例 - 塩:大さじ4，砂糖:小さじ19, 醤油: カップ3杯)が与えられます．この時，正しいレシピの割合にするには，ボールにあとどれだけ各調味料をいれればよいでしょうか？という問題です．必要以上にいれてはいけません．この例の場合は，あと (塩:大さじ4，砂糖:小さじ17, 醤油: カップ1杯) 追加はいれすぎです．正解は(塩:大さじ2，砂糖:小さじ8, 醤油: カップ0杯) になります．

うーん，時間切れでした．最大公約数を使用すれば，エレガントにとけますが，それ以外の方法では制限時間の2秒以内には終わらない可能性があります．実際，SRM後にコードを完成させたのですが，最悪の入力ケースでは2秒以内に終了しませんでした．

PokerDeck

1000点問題．SRM中はOpenできませんでした．この問題に正解したのは，Division1参加者333人中1人だけです．． ( Problem Detail )

結果

今度こそ，250点問題はPassすると思ったのけど..．System Testの結果です． ( Room Statistics )

あれー．またSystem Testに落ちてる．ここでした．．

t.p = (double) w / (double) l;

勝率の計算を win / (win + lose) でなく，win / lose で行っています．またもや，あきれるくらいの単純なミス．これでExampleにすべて通ってしまったのが，運が悪かった．．今回も，Challenge Timeでは誰もここにきずかなかったのか，誰もチャレンジしてきませんでした．

他の人のソースを見てみると，あらかじめ，勝率を

(double)w / (double) total

と（勝数) / (試合数) を計算しておいて，doubleになった勝率どおしを比較するのではなく，

my.win * your.total - your.win * my.total

として，比較しているのが見受けられます．全て整数どおしの計算になるので，doubleにまつわる問題を避けることができます．なるほど．

今日の教訓

Example Caseにとおったからといって，正解とはかぎらない．
おちつけ
doubleどおしの比較は避けれるものなら避ける．整数ですべて片付くならそちらを採用. (a / b) と (c / d) を比較するには a/b - c/d ではなく，a * d - c * b のほうがよい．

レートは 1255 -> 1097 とやはり急降下．Division2行きが決定しました．．．名前も緑に． 2軍におちる選手の心境がすこしはわかったような．

SRM262 - 初Division1はTypoに終わる

2005-09-10T00:30:00.000+09:00

SRM262 に挑戦．レートが1200以上の人はDivision1なので，今日からはDivision1． 75分で3問という点はDivision2と同じだが，問題の内容はDivision2と比べてかなーり難しい（はず）．

SortBooks (code)

250点問題．本のタイトルの条件をみたすものをピックアップする問題．アルゴリズム的には悩むところはなくただ実装するだけ．コーディングそのものは10分ほどで終わりましたが，作成したものにExampleと同じ入力を与えても，正解例と異なる値が出力され，なかなかSubmitできません． Exampleというのは，入力の例とその入力に対する正しい出力例のことです．各問題には数個のExampleがついてきます．最低限，Exampleで動作確認してから，Submitすべきです．

そのExample Caseに通りません．．．おかしいとおもいつつ，あせりまくり，デバッグをはじめたが，なにがおかしいかさっぱり．とりあえずこれ以上250点問題に時間をかけるわけにはいかないので30分過ぎたところでSubmitしました．

BestYahtzeeScore

500点問題． 5個のダイスを3回まで振ることができた場合（2回目以降は，振らずに残しておいてもいいです）， 5個の目の組み合わせで決まるスコアの最大値を返す問題．ダイスをふると何がでるかは，あらかじめ長さが15の文字列で与えられます． ...時間切れでした．最終的に可能な5個の目の組み合わせをすべて試せばいいのですが，そこで手間取りました．

MagicBoxes

1000点問題．コンテスト中はOpenできませんでした．

結果

System Testの結果です． ( Room Statistics )

やはり，250点問題はSystem Testに落ちました．結果，Scoreはゼロです．．．あー，Typoでした．．ここです

if (w.equalsIgnoreCase("the") || w.equalsIgnoreCase("and")
        || w.equalsIgnoreCase("or")) {
    return 1;

"of" とするべきところを，"or" としています．．本番中はまったく気づきませんでした．ちなみにこの問題，はやい人は3分もかからずにSubmitしています ( Problem Details )

こうしてみると，Division2ではJavaとC++使用者は同数ほどなのに，Division1 では C++使いが多いですね．

今日の教訓

文字列リテラルは問題文からコピーandペーストすべき．
Example Case はすべて通してからSubmit．やけになって途中でSubmitしても無意味です．必ずどこかが間違っていますし，他の参加者にChallengeの機会を増やすことにもなります．

そういえば，今回はChallenge Time では，自分の250点問題には誰もChallengeしてきませんでした．あまりに単純なミスすぎて逆に発見できなかったのか... レートは 1579 -> 1255 と大幅に減りました．かろうじてDivision1には残っています．

SRM260 - TopCoderへの挑戦のはじまり

2005-08-28T02:28:00.000+09:00

TopCoder とは，世界中のトッププログラマが集まり，プログラミングスキルを競いあっているサイトです．毎週のようにオンラインでプログラミングコンテストが行われています．面白そうなので参加してみました． SRM260 に挑戦です．SRMとはSingle Round Match のことです．定期的に（週に1回ほど）開催されています．

先日開催されたGoogle Code Jam 2005でこのサイトを知った人が多いのかいつもより参加者が多いらしく（私もその一人），驚いている様子が伺えます(800名オーバー)．

レーティングが1200以上の人はDivision1，それ以下の人はDivision2になります． Division1の方が問題が比較的易しくなっています．初参加の自分は，Devision2．

簡単にSRMの流れをおさらいしておくと

開始時間の5分前までにRegistrationを行う
参加者は約20名づつ，Roomにアサインされる
問題は3問．制限時間は75分．言語は Java, C++, C#, VB から選択できます．
5分休憩
15分のチャレンジタイム．この時間では，同じルームの参加者が提出したコードを見ることができます．バグを発見し「チャレンジ」に成功すると50ポイントもらえます．

ということです．この4つから選ぶなら(無難に?)Javaでいきます．以下のような問題が出題されました．(code) は私が提出したコードです．

IsingModel (code)

250点問題．特に難しいところはないです．軽くこなしたいところ．

GridPointsOnCircle (code)

500点問題．中心(0,0)，半径rの円上に座標が(整数, 整数)の形式を満たす点はいくつ存在する？って問題です．ちょっと，なやむ．単に (x, y) ( 0 <= x, y <= r) を全部調べていたらタイムオーバするってのが目に見えてるので，なんらかのちょっとした工夫が必要．

RollingBlock (code)

1000点問題. サイズがrows x cols の盤上を 1 x 1 x 3 のブロックがごろんごろんと動くとき，ある地点からゴールの地点まで最短，何Moveで到達できるか？という問題です．条件として，

rows and cols will be between 1 and 100, inclusive.

とあるので，状態空間はたかだか 100 x 100 x 3 くらいです． BFS (Breadth First Search) で問題ない（はず）．不正な状態（盤からはみだす)をちゃんとチェックしてやれば，なんとかなるか．．

結果

制限時間つきでコーディングするなんていう経験が普段ないもんだから，あせるあせる．で，なんとか3問ともSubmitしました．問題をOpenしてから，Submitするまでの時間が早ければ早いほどポイントが高くなります．

75分のコーディングタイムが終了すると，5分の休憩があります．その後，15分間のChallenge Timeが始まりました．

自分の500点コードが撃墜された瞬間．．

Challengeで使用されたパラメータ(円の半径)は入力条件の最大値である2000000000です．その結果は

"The code execution time exceeded the 2 second time limit."

2秒以上実行時間がかかるのは認められないってことですね．．なるほど．．このように，あらかじめ，必要な上限のみに制限しておけば2秒以内だったか．．

long r = (long) Math.sqrt(rSquare) + 1;
long y = r;
for (long x = 0; x < r; x++) {

自分もどきどきしながらひとつChallengeしてみました．結果は成功(+50点)．

Challenge Timeが終わると，ひとまず終了です．全員のSubmitされたコードに対してSystem Testが走ります． System Testに落ちると，どんなに早くその問題をSubmitしていてもゼロ点です．

System Testの結果です． ( Room Statistics )

250点問題と1000点問題は無事System Testに通りました． 1000点問題は2回チャレンジをうけています．そんなに「間違えてる」ふうに見えたのかなー．

レーティングはこうなりました．

今日の教訓

2秒以内という時間制限を忘れないように
いちばん時間がかかるケースをちゃんと考慮しておくように

なかなか普段は味わえない緊張感があって，面白かったです. レーティングシステムというのがいいですね．また挑戦してみたいです．