2011年4月2日土曜日

今こそわかる、あのときの「嬉しかった」

数年前、プログラミングの大会に参加して楽しんでいて、優勝した人の感想を聞いた時の一言目が
「嬉しかった」
でした。

2011年4月1日金曜日

新年度を迎えて

新年度を迎えました。

物語はドラマチックな方がいいという人もいると思うのですが、私が好きなのは、淡々とした物語です。最近読んだ「つむじ風食堂の夜」や「図書館の神様」は、本当に淡々としていて、山というような感じもなく、静かに始まり,静かに進み,静かに幕をおろします。その中にこそ、日常があるのではないかと思います。

新年度が始まりましたが、私はドラマチックな日々を期待していません。
淡々と、淡々と
ただ、自分の中のいい人と談笑をして
ただ、自分の好きな人の幸せを喜び
ただ、自分の好きな趣味を深める
そんな日々を過ごしたいと思っています。

弱くて、寂しがりやで、恨み屋の卑屈な人間でも、淡々とした日々を送る権利はあるのではないかと、そう思います。どうか、淡々と、日々を過ごさせてください。平和に、乱れずに・・・。

2011年3月31日木曜日

Codeforces Beta Round #65(Div.2) 参戦記

恒例になってきた感のある参戦記です。

まず問題をざっと読み、Aは面倒臭そうなので一旦飛ばしました。Bに行き、Bの問題を読み終えて、少々あやふやながらも組んで、提出しました。あやふやですが、現在の進行状況をバーで表したとき,どうなりますか,というような問題。ここまで10分少々。

続いてCの問題に行き、これを読んで、解けそうだったので解いていきます。初めは少々面倒な操作をしていたのですが、馬鹿な操作をなくし、枝刈りを施して、3度の誤提出の後に無事Pretestを通過。ここまでで約40分かかっています。C問題は円上に等間隔に取られた点に対し、「使っていい点」と「使ってはいけない点」を入力させ、この内「使っていい点」だけを用いて三角形以上の正多角形が作れるかどうか判定せよ、という問題でした。単純に効率よく判定していけば、さして難しい問題ではありませんでした。

D,Eをざっと読み、Dの方がEより難しそうだと思いつつも、どちらも実装が面倒そうだったのでAの実装に取り掛かります。strlen関数を使えばさして難しくない問題だったので、少々デバッグをして完了。苦労なく仕上がりました。これで50分強。後1時間10分。

この後、D,Eを見比べて
D:なんとなくアルゴリズムは見えているような気がする。
E:アルゴリズムは明確だけど、調べなければならず、実装している暇がないように思える。
という結論に至り、Dを解くことにしました。ここまでで1時間10分が経過していました。

約20分間、Dを書きますが、20分かけて書いたのがようやく初期化・入力処理だけでした。この後15分ぐらいアルゴリズムを正確に実装する方法を考えたのですが、確信が持てず、ソースをロックしてハックに移行。Cのハックを始めたのですが、特に見つからないまま終了。

問題はこちら
結果、Bは誤りだったようで、A,CがAcceptedであり、205/1103位でした。上位20%層に入っていますから、まだまだ捨てたものではないのかもしれません。もっと精進していきたいものですね。
以下、いつもどおり、答案を載せておきます。Bは誤っているそうですが、まだ検討していません。誤りを出す入力を見つけたら教えていただければ幸いです。


Topcoder SRM501 参戦記

3月30日はTopcoderSRMとCodeforcesの両方が開催される、忙しい一日でした。日が変わる頃に始まったCodeforcesを戦った後、20時からTopcoderのSRMに参加するというバタバタです。

最低限のレベルの確保という観点では、C++よりもJAVAの方が出来がいいので、JAVAで参加することにしました。初参加で、勝手がわからないままでしたので、問題をまず全部開いてしまうという失態を(^^;;。問題を開かない方が点数が高くなるのです。

ひとまず、250の問題に解答を与えます。内容としては
「引数として与えられる整数列に対し、次の1項を付け加える。付け加えられた整数列が等差数列または等比数列になるような「次の1項」は何通りあるか返却するメソッドを作成せよ。但し、無数にある場合は-1を返せ」
というものです。
配列等が使えれば苦もなく解ける問題なので、丁寧に処理を書いてaccepted。これで約30分が経過していました。問題を全部読むなどしなければもっと早かったのかもしれません。

次いで、500の問題を読みます。初めの一読ではよく意味がわからなかったのですが、再読してみるとそれほど難しい問題ではありませんでした。簡単には
「0に対して、AをnA回足し、BをnB回かけるとする。この順序を任意にとることができるとき、その最大値を返却するメソッドを作成せよ。A,Bは負の数もありうる」
というものでした。
A>0,B>=1ならば単純にAばかり全部足してからBを書ければよいのですが、それ以外の場合は少々処理に困ります。「初めが0」というのが味噌で、余分なBをここで使うことで、値を調整することができます。具体的には
・Bが0以上1未満の時は、A>0なら最初に、A<0なら和をとってからかける。
・Bが-1以上0未満の時は、A>0なら最初に、A<0なら和をとった後1回だけかける。←ここの実装を誤って、下の場合に含めてしまっていました。
・Bが-1未満の時には、A>0なら最初に、A<0なら和をとった後奇数の最大回数かける。
という形になりました。
これをJAVAで記し、残り時間はもう少し。

だったのですが、1000の問題を解けるほどの時間はなさそうだったので、そこで終了。チャレンジフェイズも特にみつけられずでした。もっと早く読む力が必要なのかもしれません。

結果、Division2において324/1003(とはいえ,半分以上は提出すら出来ていないようでした)、スコアは149.89(提出分のMAX:388.78)でした。不慣れなのもありますが、上のミスは大きいですね。
いつもどおり、答案を載せておきます。

2011年3月30日水曜日

徒然草を読む

書籍は様々ありますが、古典を読むというのは高校生以来しない,という人もいるのではないでしょうか。

古典の現代語訳はできなくても、古典を読むことには多くの楽しみがあると思っています。ちくま学芸文庫から昨年出た「徒然草」は文庫ながら1500円という高めの本ですが、原文・現代語訳・注・評がついており、知識がなくても読み楽しむことができます。500ページ弱で、そのうえ古典であるので、読み慣れておらず、結構長い間楽しむことができそうです。

2011年3月29日火曜日

笛吹けども踊らず

ことわざは
昔から好きで
今も見たり
つかったりするけど
とみに意識するのは
笛吹けども踊らず
だったり

初めて読んだとき
意味がわからなかった
15年前の記憶

今はその意味が
痛いほどわかる
身を刺すようにわかる
胸にしみわたってわかる
涙こぼしそうなほどわかる

笛は踊るものじゃない
ただ聴くだけのものだ
そういう人もいるかもしれない
笛吹きの私は
一本の笛を
今日もまた吹き続ける
ただ聴かれるだけで
それは聞いてないのと
傍目には変わらない現状で

笛を吹いて笛を吹いて
私は道化師になっていく
私は顔をなくしていく
私は存在を崩していく
もう誰も私を見ていない

やがて疎まれて
笛の折られるときがくる
笛吹きの唯一の
たった一つの
存在証明たる笛が
折られてしまう時がくる

笛は今日も
かそけき音を立てる
誰に聞かせる強さでは吹けず
もう消えていくだけの笛が
私の胸に残る

笛吹きの私が
白鳥の歌を吹くとき
いったい幾人に
その歌は聴こえるだろうか
冷たいような美しさの
笛の音は
白鳥の歌を運ぶのだろうか

2011年3月28日月曜日

Codeforces Beta Round #64 参戦記

今度は#64、Div.1のハイレベルな人も参加するコンテストに参加してきました。

Aから順に問題を読んでいきますが、なかなか理解がはかどりません。一通り読み終えた段階で30分、何とかなりそうか?と思ってCをやりますが、全くにっちもさっちも行きません。仕方がないので、Dにくら替えして、この段階で残り1時間5分。

Dは、非常に数学的な問題で、ものすごく単純には「入力される点が入力される凸多角形の内部に入っているかどうか判定」する問題でした。ただ、入っているかどうかの判定方法は思い当たらなかったので、自分で20分強試行錯誤して導き出しました。

導いたのは「判定点から多角形の各頂点へのベクトルを求め、これが連続180度未満に分布していれば判定点は外側にある」というもの。その方針で書いていって、30分ほどで、何とか書き上げました。

そして提出すると…なんと、pretest5で引っかかったという報告が!慌てて直しますが、時間切れで、結局一問も解けませんでした。話にならないもんだなぁ…。

あとで結果を見ると、この問題の正解者は8/897。挑もうとしたのが無謀だったのかもしれません。

問題はこちら
当該問題のソースは、続きに載せておきます。


2011年3月27日日曜日

汎用プログラミングシートの作成

プログラミングをするとき、何らかの問題があるわけですが、これをすぐさま解けることはまずありません。プログラミングではコンピュータは必須ですが、紙とペンもそれと同じぐらい大切です。私は、アルゴリズムを考えるのに複数枚の紙を使いますが(これは簡単な問題であっても、何種類か検討するからです)、初心者の場合、そこまで複雑なアルゴリズムを考える必要はないし、複数検討するのも大変ですので、1〜2枚あれば十分です。

ところが、その1〜2枚でも、初心者の人はなかなか使えないし、また、何をかけばいいのかわからないことが多いです。それで、以前からトップダウンタスク分析法(これはダイテル本による)を用いて指導していたのですが、それをシートに書き直したのが、次の内容です。