Imagine Cup アルゴリズム部門 世界 3 位の学生に挑戦しよう
アルゴリズムとは ?「計算や問題を解決するための手順、方式。特にコンピューターのプログラムに適用可能な手続きをいうことが多い。(大辞林 第二版)」と意味が表現されています。
問題を解決のための手順や方式をプログラミングを利用することで、より難問を解決することができる。ということでしょう。
マイクロソフトでは、毎年、世界規模で行う学生技術コンテストがあります。Imagine Cup (イマジンカップ) というこの大会では、6 回目を迎えた今年、アルゴリズム部門で、134 カ国、15,394 名の出場者中、見事日本代表が第 3 位を獲得しました。
その受賞者、高橋直大君が世界大会で実際に解いた問題の簡易版です。どうぞ、チャレンジください。
＊世界大会で高橋さんが解いた問題は、一辺が 120 マスでした !
SWAMP (沼地)
沼地というのは水と土が混ざり合った状態で、陸を歩く私たちにとっても、そして水を泳ぐ生き物にとっても通ることが難しい部分です。沼地はそれぞれが点在していますが、沼地同士を結合させれば湖を形成するための水分量は十分にあります。
それではここで問題です。沼地と陸 (緑の乾燥部分) を入れ替えて点在した沼地を湖に変えましょう。
5 回の入れ替えで湖を形成させてください。
ルール :
沼地と乾燥部分のグリッドを縦・横に入れ替え (斜め不可)、沼地のグリッドをすべて縦か横でつながっている状態にしてください。沼地と沼地を入れ替えることはできません。斜めを除く、隣り合ったグリッドしか入れ替えることができません。
得点計算方法 :
沼地の合計入れ替え回数 (マンハッタン距離)
問題 1
解答例 :
下記は入れ替え数 9 回の例。問題は 5 回での入れ替えです !
(0,0) → (1,3) 入れ替え回数 4
(4,0) → (2,1) 入れ替え回数 3
(4,2) → (3,3) 入れ替え回数 2
合計 : 4 + 3 + 2 = 9
上記は入れ替え数 9 回の例
解答はページの一番下で !
問題 2
解答はページの一番下で !
この下に解答があります。
問題 1 の解答
下記どちらも正解です。
(0,0) → (2,1) 入れ替え回数 3
(4,0) → (4,1) 入れ替え回数 1
(3,4) → (2,4) 入れ替え回数 1
(0,0) → (2,0) 入れ替え回数 2
(1,1) → (2,1) 入れ替え回数 1
(4,0) → (4,1) 入れ替え回数 1
(3,4) → (2,4) 入れ替え回数 1
問題 2 の解答
(1,0) → (1,1) 入れ替え回数 1
(3,0) → (3,1) 入れ替え回数 1
(0,4) → (0,3) 入れ替え回数 1
(2,2) → (2,3) 入れ替え回数 1
(4,4) → (4,3) 入れ替え回数 1
こんなの簡単だ !
ぜひ世界大会の問題を解きたいという方は、問題をダウンロードすることができますので挑戦してみてください。
Imagine Cup 2008 世界大会 アルゴリズム問題
リンク
