KLab若手エンジニアの これなぁに?

KLab株式会社の若手エンジニアによる技術ブログです。phpやRubyなどの汎用LLやJavaScript/actionScript等のクライアントサイドの内容、MySQL等のデータベース、その他フレームワークまで幅広く面白い情報を発信します。

天下一

天下一プログラマーの予選・本戦問題の公開

本日は天下一(10/1)の日です。 天下一といえば7、8月にかけ 天下一プログラマーの予選・本戦をやりましたが、未だ全ての問題を公開していませんでした。 ということで遅くなりましたが今回出題した問題を全て公開します。
  1. WEB予選第1回(2009/7/5)
  2. WEB予選第2回(2009/7/15)
  3. WEB予選第3回(2009/7/25)
  4. 本戦(2009/8/1,2)
それぞれの問題の解説については準備が出来次第、更新するため今暫くお待ちください。

天下一プログラマー本戦:決勝戦

54階建てのビルに、22人乗りのエレベータが一機ある。
このエレベータは、人数に関係なく一回の乗降に10秒かかり、1階あたり1秒の速度で昇降する。

a 秒時点で b 階に c 階へ行きたい ddd さんが来るという情報を、

a, b, c, ddd

というcsv形式で与える。このデータは時刻aで昇順にソートされており、同時に二人の人物が来た場合は2行に分けられる。

これを元に、入力に出現した全員を目的の階に降ろすまでのエレベータの昇降と人物の乗降を、各人の所要時間
の合計が最小になるようにスケジューリングし、e 秒時点に f 階で ggg, hhh, iii さ
んが乗降するというデータを

e, f, ggg, hhh, iii

という形式で出力せよ。 e は乗降開始の時刻であり、同時に乗降する人物は一列にまとめよ。出力は e で昇順にソートせよ。同一人物は出力の中に二度出現し、一度目は乗車、二度目は降車を表す必要がある。

回答フォームには、規定された出力と、各人の所要時間の合計を入力せよ。

なお、各変数の定義域と値域は次の通りである.

  * 時点をあらわす a, e は、スケジュール開始時点を 0 とする非負の整数である.
    値域は、 [1, 1000000] の範囲である。(スケジュール開始と同時には人は来ない)
  * 階をあらわす b, c, fは、1階を1, 54階を54とする正の整数である. 値域は
    [1, 54] である。
  * 人物を表す ddd, ggg, hhh, iii は、asciiのアルファベット小文字3つで構成
    される三文字の文字列である。 aaa, aab, ... ,zzz の値をとる。

また、詳細な条件は以下の通りである。

  * 入力には、同一人物は一度しか出現しない。
  * 出力では、同一人物を必ず二回出現させる必要がある。目的の階に到着するとは
    目的の階で降車することであり、出発階以外の階からの乗車や目的階以外の階への
    降車は認めない。
  * スケジューリング開始時点 (時刻 0[sec]) に、エレベータは1階で、すぐに移動可能
    な状態で待機している。 (たとえば、時刻 3[sec] に 3階 で乗降を開始することが出来る)
  * 乗降は、乗降終了時点 (=移動開始時点) まで可能である。

    たとえば、20[sec] 時点に 10階に出現する abc が、 10[sec] 時点に
    10 階で乗降を開始したエレベータに乗車し、30[sec] 時点で 20 階で
    降車することが可能である。この場合、abcの所要時間とは、降車時点の30
    から出現時点の20[sec]を引いた10[sec]になる。

データ: schedule.csv 

1, 16, 1, aaa
20, 20, 10, aab
75, 1, 6, aac
101, 15, 1, aad
127, 13, 1, aae
156, 13, 1, aaf
185, 4, 1, aag
213, 17, 10, aah
226, 1, 7, aai
286, 1, 5, aaj
302, 16, 10, aak
373, 8, 18, aal
432, 13, 1, aam
498, 12, 10, aan
573, 13, 1, aao
解説はこちらとなります。

天下一プログラマー本戦:3問目

以下に定義された言語GNの実行環境を作成し、以下のコードの出力を答えよ。
コード: sample.gn
GNのソースコードは単一の自然数である。
自然数を素因数分解することで指数の列が得られる。これがGNの実行時コードであり、命令および引数の列として解釈される。

たとえば、140は以下のように素因数分解され、下のLのような指数列(実行時コード)が得られる(以下aのb乗を a^b と表記する)。
22 × 30 × 51 × 71
L = [2, 0, 1, 1]

GN処理系は実行時コードの他にメモリとポインタを持つ。メモリは0で初期化された配列である。ポインタは配列の1つの位置を指す。
配列のサイズに制限はない。
ポインタは初期状態では配列の先頭を指し、初期状態では配列の要素はすべて0である。
また、処理系はプログラムカウンタを持ち、実行時コードを順次読み取って実行していく。
GNには以下の命令がある。
1, 2, 3, 4は引数を取り、実行時コードにおける命令の次の数が引数と見なされる。

1: ポインタをn進める
2: ポインタをn戻す
3: ポインタが指す値に n 加算する
4: ポインタが指す値から n 減算する
5: ポインタが指す値をアスキーコードとして出力する
6: ポインタが指す値が0なら対応する7の直後までプログラムカウンタをジャンプする
7: ポインタが指す値が0でないなら対応する6までプログラムカウンタジャンプする

注:
-ポインタは初期地点より前には移動しない。
-ポインタが指す値は0以下にならない。
-引数以外の位置にある0は無視される。
-6および7は入れ子になることがある。たとえば[6, 1, 1, 6, 2, 2, 7, 1, 2, 7] は2重ループと見なされる。最初の6を読み取った際、ポインタが指す値が0ならば、[1, 2, 7]の直後までプログラムカウンタを進める。一方、2つ目の6を読み取った際、ポインタが指す値が0ならば、[2, 2, 7]の直後までプログラムカウンタを進める。

例: : gn.txt 
以下の自然数はGN上で実行すると"Hello, world"と出力する。
(10進数で2549桁の単一の自然数である)。

2958106527037147932522799632893684637443193969398590127391830758248732725171494768562797967767791353683984427
18417530573877274081779430311745932689954120650305923259595867797790830861414486245570197481943009141937393478519254592623804
60776409945241666135623515576457155760725038527507713373195753840321861085031489701564491750744098878985806591816523081908294
61283105527716558509971171005858411245808421769992246863114351254431335737223878383791011620893422481505646222666688253017465
57802716259139633848866741528740719414914728858637969588791966689851317063150884185898981960460675295937735497349287973702957
38620574941857589823049829705846049461413969644779874433999329064371847480353568185103295523592054828279601510522112950624511
84595936474900730437224772695520567438056979131690276862280608024105855730894533729219856785845215550245697436767104075456221
81498088386167225544770290201359679919065682293247595708926680895742113997918052225689520959952562522489027195263944251298935
18226411894600368673452988892889242744668250530926131889228788353279891196002953863955036988620551780208216820904096713956573
11787584626222645802734068774871855690123741533898666352151559757643205001049057050452790789700919148880305662491890796783445
56881682765949453424229590336098515172543904288108103237904757179714193677589032225540163775143775195191697235338607548787578
38609665665451910531236989859315547896023826570664551604385678906166598725895539784981711730494441169160256011603297319575708
03475380231503771671324112842032176089902223607357360446669794097958394002228305251661924188244948685091993871616027726151260
93725457017922790196670773561594574106588867246715198548570684119344631762247386048909463390838468264616513375339015154144366
37401501770107202075869618193853996294474182147934132492506951195055315858141503877465911044521931727076612267111611092259163
43023548069059880484911832762839120688365473963014977648452152737797917653276358529255902736894343871854272216226959652772794
27775521306040911872171851035663187888059868529870606313778126063559058600073876724536181539541709228914525108195864442580453
66147848520158737104588535487342991983517189086079652855792142819089521183481046000133327452610029862345142900147219564761990
58988934466328196341675351313211247983750860548134170636123186528053423211684906781420107343182818289592512789947557613546855
41039542627630216183485152228986444577683303886169445507956368365573042442042440205283976192126925913420446498648255688324533
46114451256340883492092941868462221894307267118598466547706749550

素因数分解すると以下の実行時コードが得られる。

[1, 2, 2, 1, 3, 72, 6, 2, 1, 3, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 3, 2, 2, 3, 2,
 9, 6, 2, 1, 3, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 4, 2, 3, 3, 7, 6, 2, 1, 3, 1, 1, 1,
 4, 1, 7, 2, 1, 5, 1, 5, 2, 4, 3, 0, 6, 2, 1, 3, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 6,
 2, 5, 3, 3, 6, 2, 1, 3, 1, 1, 1, 4, 1, 7,
 2, 1, 5, 1, 7, 2, 6, 3, 67, 6, 2, 1,
 4, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 8, 2, 7, 3, 12, 6,
 2, 1, 4, 1, 1, 1, 4, 1, 7,
 2, 1, 5, 1, 9, 2, 8, 3, 87, 6, 2, 1, 3, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 10, 2, 9,
 3, 8, 6, 2, 1, 4, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 11, 2, 10, 3, 3, 6, 2, 1, 3, 1,
 1, 1, 4, 1, 7, 2, 1, 5, 1, 12, 2, 11, 3, 6, 6, 2, 1, 4, 1, 1, 1, 4, 1, 7, 2, 1,
 5, 1, 13, 2, 12, 3, 8, 6, 2, 1, 4, 1, 1, 1, 4, 1, 7, 2, 1, 5, 1, 14]

天下一プログラマー本戦:2問目

ナンクロとは、ナンバークロスワードの略称で、ヒントとなるカギ(補足説明)のないクロスワードパズルです。
文字の並びから単語を推理し、マスに文字を埋め、解いていくパズルになります。

通常のクロスワードとは異なり、すべてのマスに番号がついています。
同じ番号には同じ文字が入るので、他のマスでも単語の一部として使えるようにマスに文字を埋めなくてはなりません。
なお、1つの番号に2つの文字が当てはまったり、逆に2つの番号に同じ文字が当てはまることはありません。
また、同じ単語が2度出てくることもありません。

このルールを踏まえ、下記のナンクロ問題を解くプログラムを作成し、ナンクロを解いてください。
なお、この問題を解く際には、下記に指定された辞書ファイルを使用してください。

 numbercross.PNG 

english.dic

解説はこちらとなります。

天下一プログラマー本戦:1問目

8x8のチェス盤でクイーンは以下のように移動が可能である。

  x-x-x---
  -xxx----
  xxQxxxxx
  -xxx----
  x-x-x---
  --x--x--  -:移動不可
  --x---x-  x:移動可能
  --x----x  Q:クイーン

※: Qの配置されたマスから縦・横・斜めのすべての方向に何マスでも移動が可能

エイト・クイーン問題とは8x8のチェス盤に対しどのクイーンも他のクイーンに一手で移動できないような配置する問題である。

例:
  ----Q---
  ------Q-
  Q-------
  --Q-----
  -------Q
  -----Q--
  ---Q----  -:空いているマス
  -Q------  Q:クイーン

ここでチェス盤の一部のマスに障害物があるとする。
この障害物に対してクイーンを配置することはできず、またクイーンの移動上で衝突する場合はその先にも配置することはできないとする。

例
  x-x-x---
  -xxx*---
  xxQx****
  -xxx*---
  x-x-*---  -:移動不可
  --x**---  x:移動可能
  --**----  * :障害物
  --*-----  Q:クイーン

この時以下のように16x16のチェス盤に障害物があるとき最大で何個のクイーンを配置可能か求めなさい。
 queen.txt 

 ----*******-----
 ----*******-----
 ----******------
 -----****-------
 -----***--------
 ------*---------
 -----------*****
 ----------******
 ----------******
 -----------*****
 ------*---------
 -----***--------
 -----****-------
 ----******------
 ----*******-----
 ----*******-----

またその時のチェス盤の様子を一つ
「-:空いているマス」
「Q:クイーン」
「*:障害物」
(※「-」「Q」「*」は一つのマス)
を使用し16x16のアスキーアートとして示しなさい。

 KLab若手エンジニアブログのフッター