【IQ240】ImagineCupアルゴリズム【日本ﾔﾊﾞｲ】

プログラム版のサーバー破壊により、こっちに移ってきました。

Imagine Cup アルゴリズム部門開催中！

30分で30問の質問に答える。学生のみ参加可能。
上位200名が第2ラウンドに進み、第2ラウンドの上位5名が世界大会進出。

締切は4月1日
賞金：1位 5,000ドル(53万)、2位 2,500ドル(26.5万)、3位1,000ドル(10.6万)

ここで出た質問の答えを話し合い、日本から上位を狙おう。
質問は英語で出るので、日本語訳も募集！英語の得意な人はどんどん訳してくれ。

Imagine Cup アルゴリズム部門
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/algorithm/default.aspx
Imagine Cup 参加登録方法
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/regist.aspx
Imagine Cup コンテストルール
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/contestrules.aspx

現在の上位200位
http://www.imaginecup.com/leaguetable.aspx

出される質問は以下の分野のもの。
アルゴリズム分析
幾何学
確率と統計
帰納 (再帰)
離散数学
集合論
代数
組み合わせ理論
頭の体操問題
有限オートマトン

現在の上位ランキングされている人の国
1位：中国
2位：フランス
3位：インド
4位：中国
5位：中国
6位：インド
7位：インド
8位：ベトナム
9位：中国
10位：アメリカ

日本人が100位にも入っていないぞ。
中国、インドにぼろ負け。

実際の問題1

Suppose that the ratio between the work done by (x - 1) people
in (x + 1) days to the work done by (x + 2) people in (x - 1) days
is 9:10. What is x?

7
8
9
10
11
------------
(x - 1) 人が (x + 1) 日間行った仕事量と、(x + 2) 人が (x - 1)日間に
行った仕事量の比率が 9:10 のとき、x は何？

実際の問題2

Mrs. James works in a book store. She has been assigned the task
of rearranging all information technology books on a particular
shelf in proper order at the end of each day. What would be her
best choice for a sorting algorithm?

Bubble Sort
Insertion Sort
Selection Sort
Heapsort
None of these
-------------
ジェームス婦人は書店で働いている。彼女は毎日終業時まで、特定の
本棚のIT関連の本を適切な順番に並びかえる仕事をしている。下記のうち、
どのアルゴリズムを使って並びかえるのが最適か？

実際の問題3

20 passengers are to travel on a train which can accommodate
13 in the upper berth and 7 in the lower deck. How many ways
can they be assigned berths if 5 refuse to be booked in the
upper berth and 8 refuse to be booked in the lower berth?

25
21
18
15
None of these
--------------
20人の乗客が乗っている寝台列車がある。上の寝台が13、下の寝台が
7つ空いている。しかし、20人のうち5人は上の寝台に寝るのが嫌で、
8人は下の寝台が嫌な場合、希望の寝台を割り振ると何通りの組み
合わせがあるか。

実際の問題4

Two squares are chosen at random on an 8 x 8 chessboard.
What is the probability that they have a side in common?

1/9
2/7
1/18
5/7
None of these
--------
8 x 8 のチェス版上で、ランダムに2つの四角を選んだとする。
その2つの四角が隣り合わせになる確率は？

実際の問題5

If my professor likes the number pair 1198911 and 1168611,
which of the following number pairs does he also like?

1689 and 6891
19 and 91
190 and 160
1981 and 1891
None of the above
------------
うちの教授は 1198911 と 1168611 の数字の組み合わせが好きだ。
以下の中で彼が好きだと思われる組み合わせは？

実際の問題6

John travels to Gotham everyday for his work. His wife picks him up at the train
station each evening at exactly 6 PM. One day, he left work early, and arrived at
the train station at 5 PM. He started walking home, but he met his wife en route
to the station and got into the car. They drove home and arrived 10 minutes
earlier than usual. How long did the man have to walk before he was picked up
by his wife?

55 minutes
45 minutes
35 minutes
25 minutes
57 minutes
-----------------
まさしは日暮里に毎日出勤している。かわいい奥さんは毎日午後6時きっかりに駅に
迎えに行く。ある日、まさしは仕事が早く終わり、5時に駅についてしまった。家に向かって
歩き始めたが、途中で迎えに来た奥さんにばったり会って車に乗って戻り、家に着いた
時間はいつもより10分早かった。まさしは、奥さんに会うまで何分歩いたか。

実際の問題7

How many plates can be placed on a table where the diameter of
the table is 15 times that of the plates? The plates can not
overlap each other or the edge of the table.

187
225
200
150
None of these
-------------------
お皿をテーブルの上に並べるとする。テーブルの直径はお皿の直径の15倍。
何枚のお皿を並べられるか？ お皿は重ねられないし、テーブルのふちにも
置けない。
たぶん、テーブルもお皿もまん丸なんだろうな。

実際の問題8

Let S be the set of strings defined by the regular expression (abb*c)* .
Which of the following regular expressions defines a set of strings
which is a subset of S?

a*b*c*
(a*b*c*)*
(aabb*cc)*
(aabb*c)*
None of the above
---------------
Sは正規表現 (abb*c)* という文字列だ。下記のうち、Sのサブセットとして
定義される正規表現の文字列は？

実際の問題9

From a pack of 52 cards with 4 suits, cards are drawn until a king appears.
What is the probability that a king is not drawn in first 26 cards?

46 / 153
23 / 27
109 / 153
1/2
None of these
---------
52枚組のトランプを良くきって、キングが出るまで引いていくとする。最初の26枚を
引いた段階でキングが出ない確率は？

※ 4suit は、スペード、ハート、ダイヤ、クラブのことなので、普通のババなしの
52枚組トランプと思われ。

実際の問題10

20 prisoners escape from jail. Each day after that, half of
those that are free are recaptured. How many are still free
at the end of the second day?

9
10
5
0
15
----------
20人の (　´∀｀) が逃げ出した。次の日から毎日半分の
(　´∀｀) を捕まえたとして、2日めが終わっても捕まって
いない (　´∀｀) は何人？

> Visual Studio の各言語

ってのがうんこだな。

ていうか、数学板に来んなよ。
http://pc4.2ch.net/pc2nanmin/
とか逝けよ。

>>14
問題はどう見ても数学じゃないか？

実際の問題11

What is the next number of the following sequence: 1, 3, 4, 9, 10, 12, 13,...?

14
23
27
28
25
--------------
1, 3, 4, 9, 10, 12, 13 の次に来る数は？

実際の問題12

60 students take tests in French and Astrology. 40 pass in French
and 30 in Astrology. If X is the number of students who pass in both
subjects then what is the range of possible values of X ?

10 ≦ X ≦ 30
X = 10
X ≧ 10
X < 60
30 ≦ X ≦ 40
-------------
60人の生徒が英語と保健体育のテストを受けている。40人が英語の
テストに受かり、30人が保健体育のテストに受かった。Xは英語と
保健体育の両方に受かった人数とすると、Xのとりうる範囲は？

実際の問題13

A box contains 2 green, 3 red and 4 yellow marbles. If after each
selection the marble is replaced, what is the probability of drawing
a green, a red and then a yellow marble (in order)?

8/243
4/27
8/247
1/729
Can't be determined
----------
箱の中に緑玉2個、赤玉3個、黄玉4個が入っている。そこから玉を抜き取っていった
とき、緑、赤、黄色の順で取り出す確率は？

実際の問題14

In a certain factory, there are 100 workers who have 3 commuting
options: their own vehicle, company bus, and public transport.
50 workers use the company bus, 70 use their own vehicle, and
60 use the public transport. 10 workers use only the company bus
or their own vehicle and avoid the public transport. 5 workers
do not have their own vehicle and hence use the other two only,
while 25 workers do not live on the route of the company bus and
hence use either the public transport or their own vehicle.
20 workers use all forms of transportation. How many workers
commute by own vehicle?

12
3
4
11
15
------------
キゴ工場では、100人が3つの方法で通っている。自家用車、会社のバス、
公共の乗り物の3種類だ。50人が会社のバスを使用し、70人が自家用車を
使い、60人が公共の乗り物で通っている。10人は会社のバスまたは自家用車
しか使わず、公共の乗り物には乗らない。5人は自家用車を持っていなくて
その他の2種類の方法を併用する。25人は会社のバスルートの近くに住んで
いないため公共の乗り物または自家用車を使っている。20人がすべての方法を
使用している。さて、自家用車だけで通っている人は何人？

日本人の成績が低いのは単に英語が読めないから。

問題1の答え
この文章を計算式に置き換えると、
(x - 1) * (x + 1) * 10 = (x + 2) * (x - 1) * 9
これをまとめると、
x^2 - 9x + 8 = 0
となり、
x = -1 または x = 8　となる。
x は負の数にはなりえないので、答えは x = 8

> 30分で30問の質問に答える。

>>21
無意味

実際の問題15

An insurance company has written 2 fire insurance policies of
$50,000, 4 of $25,000, and 9 of $10,000. If the probability of
a fire is 1/1000 per year, how much can the company expect
to pay during the first year of the policies?

$85
$290
$1275
0
None of these
-----
ある保険会社は50000ドルの火災保険を2件、25000ドルの火災保険を4件、
10000ドルの火災保険9件を請け負っている。もし火災が起きる確率が1年に
1/1000だったとすると、保険会社は最初の1年に払わなければならない
期待値はいくらか？

実際の問題16
A bag contains 5 brown and 4 white socks. A man pulls
out two socks. What is the probability that they are
the same color?

5/108
1/6
5/18
4/9
None of these
------
かばんの中に5足の茶色い靴下と4足の白い靴下が入っている。
この中から2つの靴下を取り出したとき、それらが同じ色である確率は？

>>5
挿入ソート

実際の問題17

There are 25 stations on a railroad line. At each of
the 25 stations the passengers can get tickets for
any of the other 24 stations. How many different kinds
of tickets do you think have to be printed?

600
500
450
460
650
----------
ある電車の路線上に25の駅がある。25駅ともその他の24駅行きの
切符を買うことができる。印刷された切符の種類は何種類？
※ 行き先の駅名が書かれている切符なんだろうな。

実際の問題18
Which of the following is not true?

The set of rational numbers is an abelian group under addition.
The set of rational integers is an abelian group under addition.
The set of rational numbers form an abelian group under multiplication.
The set of rational integers form an abelian group under multiplication.
None of these
-------------
どれがウソ？

>>20
数学できても英語ダメなら通用しない時代だからな

まあ、日本人は中国人やインド人にはかなわない負け組ってこと

いちいち母国語(日本語)に訳しながら問題を考えているようじゃ駄目だな。
数学センスの有無以前の問題だ。

何故わざわざ数学板に来て煽る人がいるのだろうか。

人それを劣等感という、とロム兄さんがいってた気がするな