Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2011-10-05

[]Google Code Jam Japanの基礎体力作り 23:14

Project Eularの問題も、30問くらいが、だいたい限界かなという気持ちになってくる。ベタに解読すると躓く問題が、40問あたりからちらほらと出てきて、アルゴリズムというか、アプローチを転換しないといけないんだろうなーと思いつつ、あまり思いつかない。さすがに先に解答を見てしまうとゲンナリしてしまうので、気分転換に他のサイトを見て回っている。

だいたい見て回った感じだと、プログラミング競技系のサイトはだいたい「Online Judge」と呼ばれているようす。だいたいはコードをサーバー上にアップして動かすという仕組みになっているらしく、Java,Cがメインになっているので、なかなかLL系PythonとかRuby)が使えるサイトというのはないんだけど、その中でもPythonが使えるサイトといえば、Sphere Online Judge (SPOJ)あたりが有名。でも、これがかなーりしんどい。何がしんどいのかといえば、エラーメッセージがよくわからなくて、何が悪いのかさっぱりわからない。メモリが破綻したのか?それともコードが間違っているから違うエラーが出ているのか?それとも他の理由か?確かに、「競技」として考えると、エラーが曖昧な方がいいのかもしれないけど、「学習」として考えると、効率が悪いことこの上ないと思う。

そんな中で、別のサイトにno titleというのがあって、Python2.5エンジンを使っているということは、内部的に同じようなものを引っ張ってきているのかなとか邪推。問題も似たようなものが多いし。さっきのサイトと一番違うのは、このサイトは通ったコードが読めるということで、「あー、こういう風に動かせばいいのか」という勉強になる。さすがにコードを読んで納得しているだけではたぶん力にはならないので、指針めいたものを考えつつというところで。本業のアルゴリズム系の人には当たり前のことが多いのかもしれないけど。

結果から逆算する

例えば、"Google Code Jam Japan"の解説にもあるように、愚直に総当たりをするよりも、未来から過去に向かって逆算していけば、最短距離がわかったりする。ただ、これだと余りにも複雑なので、もっと簡単な問題で言うと、no titleで考えるとわかりやすい。下に問題の意訳めいたものを書いておきます。

問題

タイタニック号は船長は考えていた。というのも、彼は船員を選ぼうと思っていたからだ。ただ、志願者を見ていると、どれも適切のように見える。そこで、彼は彼らの「知性」を見るために、簡単なテストを行おうと思った。テストの概要は次のとおりだ。

まず、志願者は一列にならぶ。そして、志願者には1から順番に番号を振り当てられる。そこで、船長は奇数に振り当てられた志願者を、1名が残るまで外していく。例えば5人だったら次のような形になる。

1,2,3,4,5

2,4

4

この場合、4番目に並んだ人間が、船に乗車する権利を獲得する。

貴方は船員として船に乗り込みたいと考えている。全体の志願者の番号を与えるので、どの場所に立つと残れるのか、自動的に判定するプログラムを作ってください。

解答

馬鹿正直に配列を作って、奇数を潰していくというアプローチもあるんだけど、この問題が一番「未来から過去に向かって」という意味がわかりやすいものになっている。考えてみよう。まず、最後に残るのは一人だ。奇数がふるい落とされるということは、だいたい半分に減るということになる。半分ということは、戻るにしたがって倍数ごとに増えていく。問題は一番長く「偶数」が続く数字を求めればいいということになる。あとは、全体の志願者を超えないようにすればいい。

予め、結果を算出しておく

Project Eularの問題。

Problem 34 - PukiWiki

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.

注:1! = 1 と 2! = 2 は総和に含めてはならない.

解答

俺は馬鹿なので、いちいち階乗を求める関数を使って、そこから結果を引っ張ってきた。でも、このアプローチってCPUの無駄なので、当然のことながらお薦めすることはできない。ポイントは恐らく「各桁の数」というところで、桁数は0から9しか存在しない。つまり、実際に使う階乗は0から9の間しか存在しない。なので、予め0と9の階乗を計算しておくと、CPUの節約にもなっていいというわけです。こういう細かいテクニックが処理を軽くする方法だったりするんだろうなーと感心したりしていた。

必要なデータは何処までなの?

Project Eular系の問題に関しては、たいてい上限が決まっていないので、「この辺が上限になるんだろうな」というのを見極めなきゃいけなかったりする。つまり必要なデータは何処までなんだろう?というのを推測する必要がある。そういうことに関しては、30番の問題がもっともわかりやすい気がしている。

問題

no title

驚くべきことに, 各桁を4乗した和が元の数と一致する数は3つしかない.

1634 = 1**4 + 6**4 + 3**4 + 4**4

8208 = 8**4 + 2**4 + 0**4 + 8**4

9474 = 9**4 + 4**4 + 7**4 + 4**4

ただし, 1=14は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.

各桁を5乗した和が元の数と一致するような数の総和を求めよ.

解答

いったい最高は何処からだよ!というわけなんですけど、それに関しては 9の9乗の桁を一つずつ増やしていけばいいのかな。9の5乗桁の和が、9の5乗桁よりも小さくなれば、それ以上の数字の可能性は存在しない。で、ついでに最小は何処から始めるべきか、といえば2**5が実質のスタートで、しかし2**5乗は3桁なので、実質3桁からスタートというのが懸命な判断になる(と思う)。

小ネタ

Turbo Sort

個人的には好きだった問題。

http://www.codechef.com/problems/TSORT

要するに「最初の行にテストケースの数、次にソートするテストケースの一覧」という組み合わせになっている問題。で、俺みたいなボンクラPythonistaなら「なんだ、簡単じゃないか」といわんばかりに、配列に突っ込んでソートするみたいなことをするんだけど、圧倒的に時間が足りない。というか普通の実装をしていると、タイムアウトする。それもそのはずで、処理しなければいけない時間は5秒の間。配列をソートする、までは正しいのだけど、その方法が奮ってた。個人的に一番エレガントだなーと思ったコードを貼っておきます。

http://www.codechef.com/viewsolution/667882

Centauri Prime

EuroPythonの過去問を試訳してみる。 - 蟲!虫!蟲! - #!/usr/bin/bugrammer で意訳したEuroPythonの問題。この問題も好き。何が好きかといえば、初心者が陥りやすい罠がしかけられているのがいいです。前にも書いたとおり、このアルゴリズムの実装自体は時間が余りにもかからないんだけど、初心者だと躓いてしまう英語スペル上のひっかけが存在している。上記自分はテストケース文字列を見ていて「ああ、そういうことなのか」とは思った。

 |