DevQuizの回答受付期間が終了しましたね.
みなさん様々な方法で解かれたと思います.
結構面白かったですね.
一応僕の解いたやり方をメモしておきます.
(と言っても特にユニークなやり方でもないと思います)
僕の点数は下記の通りです.
■ラウンド2: Google Maps API
経路最適化問題です.
以下,DevQuizの問題文より
日本国内の場所のリストが与えられます。あなたはそれらをすべて通るようなルートのうち、最短時間のものを計算して、提出してください。ルートの開始点は最初に与えられる場所とし、最後にはもとの位置にもどって来て下さい。 また、各地点を移動するのに必要な時間は Google Maps API の運転ルート案内で得られる秒数を使ってください。
入力:
入力は地点のリストからなります。リストは改行で区切られます。各地点は、地点の名称、緯度、経度からなり、それぞれ空白文字で区切られます。
例) 東京都庁 35.6894875 139.6917064
札幌市役所 43.0627820 141.3535990
:
出力:
解答フォーマットは、地点の名称を空白で区切ったリストとします。始点と終点も与えてください。
例) 東京都庁 札幌市役所 ... 東京都庁
[レベル1]
東京タワー 35.658570 139.745484宮崎県庁 31.911096 131.423893
佐多岬 30.994560 130.660638
[レベル2]
兼六園 36.562070 136.662419
五条大橋 34.995682 135.767890
襟裳岬 41.926490 143.246642
東京大学 35.712940 139.759590
両国国技館 35.697080 139.792280
鷲宮神社 36.100240 139.656800
[レベル3]
通天閣 34.652554 135.506333
兼六園 36.562070 136.662419
ハウステンボス駅 33.091673 129.796602
襟裳岬 41.926490 143.246642
日本銀行 35.686839 139.771438
国会正門前 35.676293 139.746927
秋吉台 34.234753 131.310094
日本科学未来館 35.619415 139.776550
両国国技館 35.697080 139.792280
幕張メッセ 35.646701 140.036654
レベル1は自分の手でGoogle Mapsから経路探索を行えば十分ですね.
問題はレベル2とレベル3です.
とりあえずレベル2について見ると,兼六園→○→×→□→△→☆→兼六園となり,探索すべきルートは,5!となります.5!=120なので,Google Maps APIより全探索してもOKでしょう.正確には計っていませんが,検索にかかる時間は数秒ですんでいたと思います.
次にレベル3についてです.
レベル3は,通天閣→9カ所→通天閣となり,全探索すると9!回となります.9!=362880となり,これは全探索するには少しつらい.
どうしようか考えたのですが,経由すべき場所をよく見ると,主に東京周辺とそれ以外に分けられることがわかります.
つまり東京周辺グループ{日本銀行,国会正門前,日本科学未来館,両国国技館,幕張メッセ}(幕張メッセだけ千葉ですが)とその他グループ{兼六園,ハウステンボス駅,襟裳岬,秋吉台}です.
ここで,まず,通天閣からその他グループの全ての地域と東京周辺グループの一地域(例えば日本銀行)を通り, 通天閣に戻るルートを検索します.その他グループの地域数は4で,これに東京グループの一地域を加え5!の問題を解きます.これはレベル2と同じ数ですね.そして,例えば下記のような答えが得られたとします.
(これは答えではありません)
通天閣→兼六園→ハウステンボス駅→日本銀行→襟裳岬→秋吉台→ 通天閣
今度は,ハウステンボス駅から東京グループの各地域を通り,襟裳岬にたどり着くルートを検索します.東京グループの地域数も5なので検索するルート数は5!となり,これも探索可能となります.
■Super Hackers:Shiritori
決められた単語を用いて,サーバーとしりとりで勝負します.
単語が無くなったら負けとなります.
レベル1とレベル2の回答は省きます.
レベル3について.
使う単語は,
xjkfkwvpt,tzsmq,pxbmcesnjns,egcllbcbh,
thbtdo,tkssgbvja,qxbrgzcmfo,qpnkhoirma,qylomri,
onkwrscza,ojpyyi,ohkhkmavpx,aeuni,akgrx,
awhveplfw,idaslbxx,izcwbqihw,ifncjdqsjcb,xmgkmcsw,
xbyhupb,xbcmpszfm,wyccb,wojkom,wzpnyonhet,
bdetytm,bnccrpxt,bngxufabq,mlyiesuet,mnoyargccqq,
mawvlvo,ttsey,ykplamk,yrhtmqv,yygjpuwyp,
qhfag,gnfbckn,gfvnrdfmr,ghnhwrrtmc,ouiimevu,
ucszjfgsf,upxpqzmvie,ueexd,apayifgy,iqjqg,
xpwxsiu,wffhsfwqwjy,bdcrgyg,mjqdu,kkgen,
kexref,kbkrev,kqqwqezr,koucaoe,kvzkcosfllp,
knwdc,kykdnd,krwgpol,kwqulsbbs,kgvwosyh,
nurzk,nvrwtuzkf,ndvlgjvv,nfzhudxnr,npdyzvje,
nkjynp,nqjeefpnwpc,njrhvudad,nemsl,nysikxzxs,
nvzayoh,frkxeqek,fjadqgyn,fqfcbv,fxomlbwkotr,
fakwkpjge,fiwchp,frrlricvsc,fvtcqunvoyd,foqpsspyl,
fggikoous,ffyrh,vhwcvgk,voqtn,vrdomf,
vtnyr,vfiote,vyxfbdp,vqsaeqlc,vsnqd,
vttsaizbdl,veals,vfprmoxmmh,rzttstqlk,reoirnyn,
rfdeienf,rkaibcv,rybmcce,rnoup,rgpuhstjc,
rzfrosbakid,rylywizybzl,rdmcss,rljpgznoh,eltsk,
exdxiyfbugn,eeublwiiidf,ediov,ehvftymilr,esfjynnnp,
esmsxsymcpc,eahgoobid,ewnreexvmtl,eimtomus,
plpykovffk,ptvpsdmjjn,pvlajfcf,pbtvpnnnpv,pvedaer,
piywsfve,puggdtmymhc,pfmywnd,ptkkxjal,
pusevvmqvuh,cwfrgkbodik,clqcn,ccdbuf,cvfdrtdv,
cpltr,cskkmnine,czqzzzwxvp,chwtukwd,cafluoehbl,
cblwnbois,cbsyh,dliovokk,dzfmcbenffn,dcmuejvggkf,
djvzgpspv,dgdhxibsepr,debtnxtqe,dufwuvdp,dwurgc,
dkuol,dohbzxpxshs,dydwrdzadch,ltuck,lxlxaen,
lqxxrf,lecjbv,lghpeqlwxtr,lfpmtue,lvpncp,
lkgqghhc,lzjuud,lchljus,lzzkxh,slxaek,
srten,steeycpf,sepuwxzv,snlonbntjr,shske,
saynsxp,sjvqgzdkpec,suvzved,sjgtl,spmxdoh,
hwfptlzbk,hqgbwovn,hutfyojmqzf,hnusersv,hmber,
hdowqwfe,hooihp,hutlc,hvyzebbd,hykmzl,
hajyxs,llxlapt,lxgcfykha,ljwgmgjjw,shutpq,
snzbqki,sjzgb,hrfjso,hplgjpjcx,hcqim
(相手始まりで相手は最初にxjkfkwvptを選択する)
これ何回か手動でプレイするとわかるのですが,ある文字で始まる単語ではめられます.
例えば「c」で始まる単語は11こあるのですが,これに対して「c」で終わる単語は12個あり,一度「c」で始まる単語を選ぶと,相手は常に「c」で終わる単語を選び,最後には単語が無くなってしまいます.もちろんプログラムを組んで探索しても良いと思いますが,少し単語を分析してみると解法が導けます.
まず,aからzまでの単語の先頭数と末尾数をチェックします.
文字 | 先頭数 | 末尾数 |
a | 4 | 4 |
b | 4 | 4 |
c | 11 | 12 |
d | 11 | 12 |
e | 11 | 12 |
f | 11 | 12 |
g | 3 | 3 |
h | 14 | 11 |
i | 4 | 4 |
j | 0 | 0 |
k | 11 | 12 |
l | 14 | 11 |
m | 4 | 4 |
n | 11 | 12 |
o | 4 | 4 |
p | 11 | 12 |
q | 4 | 4 |
r | 11 | 12 |
s | 14 | 11 |
t | 4 | 4 |
u | 3 | 3 |
v | 11 | 12 |
w | 4 | 4 |
x | 4 | 4 |
y | 3 | 3 |
z | 0 | 0 |
表からわかるようにいくつかのパターンが見えてきます.
パターン1:先頭数と末尾数が4 {a,b,i,m,o,q,t,w,x}
パターン2:先頭数と末尾数が3 {g,u,y}
パターン3:先頭数が11,末尾数が12 {c,d,e,f,k,n,p,r,v}
パターン4:先頭数が14,末尾数が11 {h,l,s}
(関係のないjとzは無視します)
ここでパターン3は先ほど言ったように,先にパターン3で始まる単語を選択する状況になったら負けます.
では,パターン3の文字で始まる単語を相手に選択させるためには,パターン3の文字で終わる単語を自分が選択する必要があります.
これは具体的にはパターン2の単語です.例えば,パターン2の一つであるgで始まる単語は,{gfvnrdfmr, ghnhwrrtmc, gnfbckn}があり,全て末尾がパターン3の文字で終わります.
そして,上記の事から,パターン2の文字で終わる単語を相手に選択させれば勝ちとなることがわかります.
少しまとめると
パターン3始まりの単語を相手に選択させる→パターン3終わりの単語を自分が選択する(=パターン2始まるの単語を自分が選択する)→パターン2終わりの単語を相手に選択させるとなります.
さて,ここでパターン1の文字で始まる単語は,4つありますが,その中でパターン2の文字で終わる単語を1つずつあります.
具体的には下記のようになります.
先頭 | パターン1の末尾 | パターン2の末尾 |
b | mqt | g |
i | bwx | g |
q | aio | g |
a | iwx | y |
t | aoq | y |
w | mbt | y |
x | bmw | u |
m | oqt | u |
o | aix | u |
相手は初めにxjkfkwvptを選んでるためtからyを取らないように他の単語(末尾がa,o,p)を選択します.後は,g,y,uを取らないように,ゲームを進めていけば勝ちます.
■Super Hackers:PAC-MAN
50 11 7 ########### #.V..#..H.# #.##...##.# #L#..#..R.# #.#.###.#.# #....@....# ###########
上記のような文字列が与えられ,自機が@で,VHRなどは敵を表します.
#は壁でドットはポイントを表します(ポイントは一度とったら消える)
上下左右及び停止しながら,ポイントを多く集めると言った問題.
とりあえず,敵の動きが決められているので,そのように動く簡単なシミュレータを作り,自機は再帰で探索を行うことにした.
上記の例のような問題だとすぐ解けるのだが,レベル2,レベル3のような問題は,時間がかかり解けない.
例えば迷路探索のように,進む方向がある程度決まっている場合,全探索でも問題はないのだが,今回のように来た道を戻った方が良い場合や,一時停止をして敵が通り過ぎるのを待つ方が良い場合があり,探索数が莫大に増える.
結局,これに対してのいい案は思い浮かばずに,できるだけ長い間プログラムを走らせて良い結果がでたら随時表示してサーバに答えをアップロードした.
他の人を見ると,シミュレータを作って人力でパックマンをプレイして,かなりの高得点(レベル3で500点超え)を出されている方がいたので,その方が手っ取り早かったみたい.