「情報処理」最新号の秋葉先生の記事について

先週届いた情報処理学会の学会誌「情報処理」に「プログラミングコンテストチャレンジブック」や「世界で闘うプログラミング力を鍛える150問」の秋葉先生の記事が載っていました。

なお、この記事はpro-con blogに先行で載せていたものをこちらにも掲載したものです。

「やってなんぼ」で普及しよう

万年筆愛好家と会うことが多く有ります。それはそうでしょう、私だってその中の一人なのですから…。競技プログラミングを普及しようとしている方とお話する機会が多く有ります。それはそうでしょう、私だって思いを共にしているのですから…。

ロベール本のレビューに見るプログラミング習得について

ロベール本

は、C++の入門書籍として、私がイチオシの書籍で、いつもこれを読んで学んでいます(今はストラウストラップのプログラミング入門に移っていますが。)後輩にも、この本を勧めることが多くあります。(ただ、0から始める人には少々厳しいかも、という意見が多いようです。私は、そもそもC++を0から始めるのは厳しいと思っているので、勧める相手は概ね別言語での経験があり、そのあたりは心配していません)

Amazonにおけるこの本のレビューは非常に有用で、プログラミングを学んだり教えたり摺る機会がある人にとって、有意義なものです。レビューとしては勿論ですが、ここではプログラミング習得に関する意見として、このレビューを取り上げてみたいと思います。

Code Golfは役立つか

ずいぶんサボっていますが、3月になったらちゃんと復活させようと思います。
・中古PCの有効利用
・ICS導入
・新しく買った万年筆のReview
・新しく買った紅茶のReview
・中島みゆきのインストゥルメンタルCD関連
等、ネタは大いにありますが、バタバタしていて書くことができていません。

数学とアルゴリズム

いつだったか、プログラマーへ100の質問か何かに挑戦したとき、数学ができないプログラマーをどう思うかという問がありました。それに対して、アルゴリズムを立てられないほど数学ができないのは困るのでは、と答えた記憶があります。

その後、数学ができないとアルゴリズムでも困る例はどんなものかと考えてみたのです。

日本のプログラミング大会とGCJJ

あちこちのプログラミングコンペティションに参加して、その参加記録をもうひとつのブログTatuyan's Pro-con blog!で公開しているわけですが、日本の大会と他の国の大会の違いが見えてきます。

夏期にC++を

幾度となくやると言っていながらやっていなかったのがC++の学習でした。C++を学習するのに十分な本は持っているのですが、それを勉強するためのまとまった時間が取りにくいと感じていたのです。

プログラムの汎用性

お世話になっている先生とプログラミングの話をしていたときに聞いた話です。

プログラミング仲間が欲しい

ずいぶん長い間、プログラミング仲間なる人間がいない状況です。プログラミングが大好きだからこそ、誰かプログラミング仲間が出来ればいいなと思うのですが、なかなか簡単にはできません。

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

燦燦たる出来でした。

Aを5分で解答…まではいつも通り。

Bの問題の入力条件を「入力される2進数は10進法で10の6乗以下である」と勘違い。当然正解できるはずもなく、これに30分悩みます。(入力要件が実際は違ったので、方針自体を変えないと解ける問題ではありません)

その後、Cの問題に行きますが、いい解法を思いつかず、力任せで、当然TLE.

Dの問題もよく意味がわからず、今回はさっぱりでした。498位/937人、490点、当然Green落ち。
次回リベンジで、なんとか青になりましょう。

熱拡散方程式の数値解法について(3)

これで最終回です。全体的にはメモ程度ですが、何かの足がかりになった人がいれば幸いです。

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

おなじみの参戦記です。

開始。万全の状態で、なにか後に控えていることもなく、気持よく参戦。
解き始めて、7分。まずはA問題をPretest Passedでした。

丁寧に考えて、計算回数が増えないように丁寧に組みなおして、32分でB問題Pretest Passedです。万全です。

その後C問題にとりかかりますが、ぱっと見ではやや難しいですが、丁寧に考えていきます。いろいろなケースを紙に書いて、じっくりと解いていきます。走行していくうちに、解き方が見えてきました。無事に解いて、ちょうど1時間でPretest Passed!です。

その後のD-E問題はとく気になりませんでしたし、また、hackにも取り組みましたが、なぜかなかなか表示されず、腹がたったので途中でやめて寝てしまいました。

朝起きてから確認すると、3問ともAcceptedで、2498点、39位/896人でした。そして、青くなることができました！嬉しい限りです♪

プログラミング大会の記事

少なからず、競技プログラミング/プログラミング大会の記事を載せています。そして、最近はTopCoder部の日記からもリンクを張っています。それを書いていて、どうすべきかと思ったのは…。

熱拡散方程式の数値解法について(2)

前回の続きです。今回はクランク・ニコルソン(Crank-Nicholson)スキームです。

熱拡散方程式の数値解法について(1)

所要により、熱拡散方程式の数値解法を扱うことになり、それを調べてみて、日本語でまとまったものを見つけるのに苦労したので、自分のところで3回にわたってまとめてみました。必要だったのが1次元塩分拡散だったので、数値計算するのに必要な拡散係数などは塩分濃度のものに合わせていますが、それ以外は特段の変更を伴わなくとも一般に適用できるかと思います。

Topcoder SRM509(Div.2) 参戦記

前に用事があったので、10分ほど遅れての開始。

まず、250を見ます。回文数は再帰関数で組むことが多いので、久しぶりにJavaで再帰関数を組みました。今考えたら文字列化したほうが早かった気がします。Javaで文字列化する方法を調べるのが面倒だったので、ゆっくりやってしまいました。やはり、JavaやC++を鍛える必要がありそうです。Submitは151.78。ちょっと遅すぎです。

その後、500に移ります。今回は少し遅目の参加だったので後回しにしたのですが、ほとんど問題なく、アルゴリズムも悩まずに立ちました。Submitして、419.42。部屋内では2番目で、かなりありがたいスピードでした。

1000は解けず。1000を解けるように、もっと精進しないといけません。

結果、120/1204で、かなり良い成績。571.2でした。

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

ちょっと疲れていたので、ゆっくりする感じで参加。

問題Aを読み、解きます。ギターのコードの問題。普通に解きましたが、だいぶゆっくりだったため、解き終わったのは36分。

次いで問題B。方針はあっていると思うのですが、すごく汚いコード。WAでしたが、Pretest1とのこと。しかし、どの入力例に対しても、ローカルでは正しく出力しています。何が悪いのかがわからない…。もしわかる方がいらしたら教えてください。仕方ないので、問題Cに移ります。

問題Cは比較的好きな漸化式の問題。先にこちらを溶いておいたらよかったと思いましたが後の祭り。問題Bを諦めたのが残り20分で、コーディング間に合わず、結局問題Aしか解けませんでした。

順位は361/946で、得点は428でした。今ひとつです。最近ちょっと下降線なので、少し上げていきたいですね。問題はこちら。

それはハミルトン閉路から始まった

今でこそ競技プログラミングに数多く出ている私ですが、半年前～4年前は英語の大会を敬遠していましたので、出ている大会はほんの僅かでした。そもそも、出られる資格のある大会など、ほとんど知りませんでした。JAVAをそれなりに組めるようになり、英語も敬遠するほどではなくなって、今はプログラミング大会、週に一度は出ています。

UAPC2011/IPSC2011 参戦記

6月5日はUAPC2011/IPSC2011の両方が行われる日でした。両方共フル参加すれば楽しいのでしょうか、いろいろ立て込んでいましたので、UAPCは2時半から4時半、IPSCは7時から9時までの時間限定で参加しました。他の時間は、テスト勉強等で忙しくしていました。

今回色々読みましたが、テスト勉強できもそぞろだったからか、どちらも解けたのは一問目だけでした。もう少し落ち着いて大会に出たいものです。一息付ける時期がきたらSuperconの問題を解かないと…。

UAPCの第1問(A)は初心者の練習問題にも出来る問題で、ifを用いて丁寧に書けば書くことができました。

一方で、IPSCの第1問(A)はそれなりの問題でした。ジャンケンに似たゲームの問題です。私は一種のバックトラックで書きましたが、もっと効率的な解法があったのでしょうか。

UAPCはこちら、IPSCはこちらです。

Topcoder SRM508(Div.2) 参戦記

いまいちでした。

いつも通り500点からやろうとしたのですが、何をいっているかがわからない。しばらく考えても全くわからないので、250にチェンジ。250はそれなりに理解でき、何度か組み直しつつSubmit。でも、この段階で半分が過ぎていました。173.50。

それから1000へ。問題の意味はわかりましたが、さてどう解くか。いろいろ迷って、ビットに注目するのかな？と考えましたが、結局答えは出ませんでした。諦めついでに残り10分でSummaryを見ると…

ーーー250以外は誰も解けていないし、250も部屋内3位…

かなり難しかったのかもしれません。

そして撃墜ラウンド。私のすぐ下にいた人のコードを読んでみると、再帰処理をたくさん使っている。
「これは撃墜できるかも」
慣れないながらデータを作り、再帰回数ができるだけ多くなるようにして投げました。

--Challenging Success--

今までで初めて、私は撃墜することができました。
そしてその後です。
自分自身も撃墜されてしまい…。(よく読めば、問題にそぐわない回を出していたことがわかりました)

結果は50点、372/1362でした。