世界中から10,000人以上の腕に覚えのあるプログラマーたちが参加しました。
プログラムは得意だけど、英語が苦手で参加できないという方のために日本語要約をつくりました。あと、参加したけど英語がよく分からなかったという人も読むといいかもしれません。
実際の問題（英文）はこちら：
Problem A. Bot Trust
[問題概要]
BlueとOrangeというロボットを２つの廊下に置いて仕事をさせる。
仕事の内容は、地点xにあるボタンを押すというもの。
仕事のリストは、
O 2, B 1, B 2, O 4
のように与えられる。上記の意味は、
まず、Orangeが地点2のボタンを押す
次に、Blueが地点1のボタンを押す
次に、Blueが地点2のボタンを押す
最後に、Orangeが地点4のボタンを押す
ということ。
初期状態で、2つのロボットは地点1にいるものとし、地点xから地点yまでは時間 |x-y|で移動できる。
このとき、リストの仕事を完了させるのにかかる最小時間を求めよ。
但し、仕事リストの順番は順守しないといけないことに注意。（例えば、Blueがボタンを押せる状態でも、先行のOrangeのタスクが完了していない場合は、Blueはその完了を待たないといけない）
Problem B. Magicka
[問題概要]
魔法使いが、呪文を唱える。
呪文の基本エレメントは、 {Q, W, E, R, A, S, D, F}から成り立つ。
呪文合成リスト、呪文組み合わせ禁止リストが与えられるので、最終的な呪文を求める。
呪文合成リストとは、基本エレメントから基本エレメントにない呪文を生成するルールを表す。
例えば、合成リストの中に、"QFT"という要素があれば、呪文を読んでいる時点で"QF"または、"FQ"が連続した場合、
それは"T"になることを意味する。
呪文組み合わせ禁止リストとは、呪文中に同時に存在してはいけない基本エレメントの組を定義したものである。
禁止リストにある組み合わせが呪文中に存在した場合、いままで唱えた呪文はクリアされる。
魔法使いが唱える呪文が与えられたとき、最終的に呪文はどう変化するか求める。
呪文合成、呪文組み合わせチェックは、逐次的に評価されることに注意。
呪文組み合わせチェックより先に呪文合成が評価される。
Problem C. Candy Splitting
兄弟が複数個ある飴のかたまり（一つの塊にはCi個の飴が入っている）を分ける。
まず、兄が適当に２分割して、それを弟に渡す。
弟は、分割された飴を見て、それが２等分されていない場合は泣いてしまう。
しかし弟はまだ幼いので、足算ができない。でも何故か二進数の足算はできる（どんなコンピュータおたくだよっ笑）
二進数で足算はできるが、繰り上がりをすることができない。
例えば、12+5は、
1100
+ 0101
------
1001
のように計算してしまう。よって弟が計算すると、12+5=9になる。
兄は、正しく足算ができる。兄は弟を泣かせることなく、飴のかたまりを２分割して多い方を自分が取りたい。（悪い兄貴。。）
弟を泣かせない方法が存在しない場合はNoと出力、存在する場合は、弟を泣かせずに兄がもらうことのできる飴玉の総数の最大値を求める。
Problem D. GoroSort
五郎とよばれる謎の生物がいる。五郎は腕が４本、指がN本ある。（エイリアン？？想像すると、怖い。。）
五郎は、N個の数字がランダムにならんだ配列を持っている。（積み木の箱に数字が書かれたブロックがN個あるのをイメージしてください）
五郎は、配列を昇順にソートしたいがアルゴリズムが得意じゃない。
毎回五郎は、N個の数字のうち、M個の数字を抑えて、配列をテーブルに叩きつける。
抑えつけたM個の数字は動かないが、それ以外の数字は空中に飛んで、バラバラになって、また配列に戻ってくる。
このバラバラになるという過程で数字がソートされる。ソートのされ方は、同一で一様な分布とする。
五郎は、毎回配列のおさえるべき部分を賢くえらぶ。どこを抑えれば速くソートされるかを知っている。
（アルゴリズム得意じゃないとか言いながら、実は賢い生物だね。）
配列の初期状態が与えられたとき、五郎がソートするために必要な、テーブルにたたきつける数の期待値を求める。
0 件のコメント:
コメントを投稿