Hatena::Groupbugrammer

蟲!虫!蟲!

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

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

 | 

2011-10-04

[]EuroPythonの過去問を試訳してみる。 03:15

Google Code Jam Japanに生き残ってしまった関係、さすがに何か練習をしておかなきゃ不味いなーと思ったので、no titleを解き始める。日本語訳はProject Euler - PukiWiki。だいたい20問解けたので、いい滑り出し。Google Code Jam過去問題を解いていってもいいんだけど、さすがにそこまでに集中力が無いのが残念なところ。今年の"Google Code Jam"(Japanの無いほうね)の翻訳はここで参照ができる。Google Code Jam 2011 Qualification Round (日本語訳) - KUT-PG 高知工科大学 プログラミング集団 Wiki*。競技プログラミングに興味を持っている人は、元々英語でゴリゴリ書いちゃうので、あんまり翻訳が出回っていないみたいなので、少しずつ翻訳した方が他の人の勉強になっていいのかなという気はするので、練習の空き時間に、翻訳できそうなものは翻訳してみることにする。今回はEuroPythonです。(EuroPythonと言われているけど、別に解答はPythonである必要はない)。あと超絶意訳なので、若干間違いもあるかとは思います。

Dashboard - EuroPython 2011 - Google Code Jam

Problem A. Centauri Prime

昔々あるところに、王国がありました。この王国、最後が子音で終わっていると王様に支配されることになり、最後が母音になっていると女王に支配されることになります。でも、最後の文字が"y"になっていると、誰からも支配されることはありません。というわけで、誰に支配されているかを判定できるようなプログラムを書いてくださいね!頼みましたよ。

注記

Pythonistaなら10分くらいで実装できる問題。母音規則は小難しく考えずに"a,o,u,i,e"だけでいい。これ以外の例外はない。しかし、あんまり考えずに実装すると、Small-Aだけ解けて、Small-Bは解けないというような、変な間違いをする(自分も引っかかってすこし悩んだ)。どちらかというと、「こういう入力もありえるよね」ということに対してちょっとした想像が出来るかという問題。実際のスコアボードを見ると、38人中、10人しか正解出来ていないので、どれだけこの引っ掛けが、単純かつ強力かもわかる。

Program B. Music Collection

フィルは音楽プレイヤーで曲を聞こうと思ってます。この音楽プレイヤーは、検索ワードを入力すると、プレイリストの中から該当するものを探し出して、表示してくれます。フィルはマウスを使うのが大嫌いで、キーボードだけで済まそうと思っています。そこで、今からそれぞれプレイリストを与えるので、そのプレイリストから個々の音楽を最短入力で探し出す方法を見つけてください。頼みましたよ!

ちなみに、このプレイヤー、大文字と小文字を区別しないし、入力するときは大文字です。無いときは「:(」って出力してくださいね。

Problem C. Irregular Expressions

世界魔女・魔法使い選手権が開催されました。彼らの魔法というのは、三つの単語で成り立っています。最初の言葉と、真ん中の言葉と、最後の言葉という、三つの言葉でなっています。最初の言葉は、最低でも二つの音節からなり、そして最後の言葉と一緒です。それぞれの音節はちょうど一つの母音によってなりたっています。その母音とは、"a,e,o,i,u"の五つですね。他は"y"を含む子音よって成り立っています。なので、"ab", "ra", "cad", "o" という音節は成り立つんですけど、"ero" や "grrgh"という単語は成り立ちません。

たちが悪いことに、この人たち、とても言葉が早くて、どこが始まりなのかどこが終わりなのかさっぱりわかりません。さらにわけのわからない言葉をスペルの前後に混ぜ込んだりします。

"abracadabra"は、"abra" "cad" "abra"で成り立っているのでスペル。"kajabbamajabbajab"は"jabba ma jabba"が入っているのでスペル。でも"frufrumfuffle"は上記要素を満たすものがないので、スペルじゃないですね。

で、貴方にお願いしたいのは、データを渡しますので、そのデータの中にスペルがあるかどうかを判別して欲しいということです。

Problem D.Twibet

聖なる国であるチベットには、N人の僧侶がいます。それぞれの僧侶は1からNの個別ナンバーを持っています。彼らは宗教上の理由により、名前を使いません。彼らはゆっくりとチベットを回っています。そして、それぞれの僧侶には、一人の僧侶が付いています。

彼らは多くの時間を寡黙に暮らしますが、Kの日付になると、ナンバーKの僧侶はとまって振り返り、140文字の知恵をつぶやきます。そのつぶやきは余りにも静かなので、付き添いの僧侶にしか聞こえません。そして、そのつぶやきを聞くと、彼に付き添っていた僧侶も振り返って、同じ言葉を、彼自身の付き添いの僧侶につぶやきます。これらは連鎖していって、その言葉を二度聞くまで、続けられます。二度めに聞くと、その言葉をつぶやくのをやめます。そして、普段どおりに歩きつづけます。そして次の日になると、また同じようにつぶやきはじめるのですが、しかし今度は違う僧侶からつぶやきが始まります。

さて、問題はKの日付につぶやかれた140文字の言葉は、1からNのどれだけの僧侶につぶやかれるんでしょうか。教えてください。

注記

140文字の呟き……これってTwitterなんだろうな……(そういう話もヤボか)

 |