アルゴリズムデザインコンテスト 2014 in DAシンポジウム

アルゴリズムデザインコンテスト
２０１４
in DAシンポジウム2014
開催結果
ナンバーリンクを自動で解け！
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
1
参加チーム紹介
チーム番号
T01
T02
T03
T04
T05
T06
T07
2014/8/28
発表者所属
チーム名
北九州市立大学
立命館大学
早稲田大学
JST ERATO
Numberlink Ganbaru Computer
戸川研究室D
ERATO Graphillion
会津大学
神戸大学
東京工業大学
Sugar+GlueMiniSat
TNT
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
2
ナンバーリンクパズルとは？
• 同じ数字同士を、一本線でつなぐ
– CADの「一層配線問題」に似ている
出題
解答
5
5
4
2
4
2
3
3
5
1 4 3
5
2 1
1 4 3
2 1
ペンシルパズル本156
ナンバーリンク4
株式会社ニコリ
ISBN978-4-89072-256-3
「ナンバーリンク」は株式会社ニコリの登録商標です。
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
3
当コンテストのルール概略説明
• 出題数：１６問
– サイズ 10x10 ～ 36x20
• 競技時間：４０分
• スコア計算方法：問題ごとに
（正解数）－（不正解数）＋（全問正解ボーナス 5）
– 短絡解（複数解）があるかもしれません。最大５個まで
採点
• ソルバ―は、会場に持参。ネットワーク経由アクセ
スは不可。実装はソフト／ハード問わず。
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
4
表彰
• 最優秀賞１チーム
– 最高スコアを獲得したチーム。
同点なら、求解時間が短い方
• 優秀賞１チーム
– スコア２位のチーム
• 特別賞１～２チーム
– オリジナリティ、コストパフォーマンス等をポスター展
示で審査
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
5
準備が整いましたら競技スタートです
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
6
競技中です。
ポスター展示をご覧ください
スタート時刻が15:24
予定の14分遅れだったため、
競技時間を短縮させてください。もうしわけありません
競技終了は15:55とします
配布済みのサンプル問題
にも挑戦してみてください
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
7
競技は間もなく終了ですが・・・
ここでサンプル問題の解答発表です
（あとで受付にて解答を配布します）
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
8
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
9
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
10
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
11
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
12
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
13
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
14
例題１
9
8
1
2 11
4
3
5
7 6
7
6
2014/8/28
1
4
5
11
2
9
3
8
10
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
10
15
例題２
12 8
1
2 6
6
2 1
12
10
10
9 3
4
5 7
2014/8/28
3
8
11
11
13
7
5 4
9 13
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
16
例題２
12 8
1
2 6
6
2 1
12
10
10
9 3
4
5 7
2014/8/28
3
8
11
11
13
7
5 4
9 13
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
17
例題２
12 8
1
2 6
6
2 1
12
10
10
9 3
4
5 7
2014/8/28
3
8
11
11
13
7
5 4
9 13
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
18
例題２
12 8
1
2 6
6
2 1
12
10
10
9 3
4
5 7
2014/8/28
3
8
11
11
13
7
5 4
9 13
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
19
例題３
11
11
1
2
3
14
13
8
10
4
15
14
9
13
8
5
10
4
9
6
7
5
1
15
12
6
2
7
3
12
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
20
例題３
11
11
1
2
3
14
13
8
10
4
15
14
9
13
8
5
10
4
9
6
7
5
1
15
12
6
2
7
3
12
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
21
例題３
11
11
1
2
3
14
13
8
10
4
15
14
9
13
8
5
10
4
9
6
7
5
1
15
12
6
2
7
3
12
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
22
例題３
11
11
1
2
3
14
13
8
10
4
15
14
9
13
8
5
10
4
9
6
7
5
1
15
12
6
2
7
3
12
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
23
例題３
11
11
1
2
3
14
13
8
10
4
15
14
9
13
8
5
10
4
9
6
7
5
1
15
12
6
2
7
3
12
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
24
ちなみに
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
25
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
26
今回の問題作成方法
1. Excelで描いてみる
2. Perlスクリプトでデータ変換
3. 解いてみる…
ソルバ―を貸してもらえるとあ
りがたいです
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
30
競技終了です
ただいま審議中
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
31
今回の出題１６問発表
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
32
今回の出題
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
名前
NL-sample05_Sheet1　オリジナル
NL-sample06_Sheet1　オリジナル
NL-sample07_Sheet1　オリジナル
NL-sample08_Sheet1　オリジナル
No.40 作・ぽっつ　Medium　※
NL-sample10_Sheet4r　オリジナル
NL-sample00_Sheet11　オリジナル
NL-sample01_Sheet10　オリジナル
NL-sample02_Sheet5　オリジナル
No.56 作・ねこあい護家　Medium　※
No.69 作・ぽっつ　Hard　※
No.73 作・まいなすよん　Hard　※
NL-sample03_Sheet10　オリジナル
NL-sample03_Sheet9　オリジナル
NL-sample09_Sheet1　オリジナル
No.91 作・おらけ　Hard　※
行
10
10
18
18
18
18
15
19
18
24
24
24
21
21
19
36
列
10
10
10
10
10
14
17
16
18
14
14
14
18
18
35
20
※ 「ペンシルパズル本156 ナンバーリンク4」(ニコリ) より引用
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
35
1. NL-sample05_Sheet1 オリジナル
10 行
10 列
0
0
1
2
3
4
5
6
7
8 4
9 3
2014/8/28
1
2
3
4
5
6
7
6
7
8 9
1
7
6
5
2
5
4
3
1
2
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
36
2. NL-sample06_Sheet1 オリジナル
10 行
10 列
0
0 1
1 2
2 3
3
4 4
5 5
6
7 6
8 7
9
2014/8/28
1
2
3
8
4
5
6
9
7
8
9
10
9 10
8
1
2
3
7
6
5
4
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
37
3. NL-sample07_Sheet1 オリジナル
18 行
10 列
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 1
2014/8/28
1
2
3
4
5
6
7
8 9
1
2
3
4
5
6
7
9
2
3
4
5
6
7
8
9 8
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
38
4. NL-sample08_Sheet1 オリジナル
18 行
10 列
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
13
1 13
4
5
6
12
8
2 14
3
6
12
8
4
9
10
8
9
1
16
17
16
17 14
4
7
7
5
6
3
11
20
7
10
11
5
15
19
18
19
18 15
9
2
20
CMOSインバーター？
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
39
5. No.40 作・ぽっつ Medium ※
18 行
10 列
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
※ 「ペンシルパズル本156 ナンバーリンク4」(ニコリ) より引用
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
40
6. NL-sample10_Sheet4r オリジナル
18 行
14 列
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2014/8/28
1
2
1
9
3
4
5
6
7
8
9 10 11 12 13
7
7
1
2
3
4
5
6
8
6
8
9
2
5
4
3
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
41
7. NL-sample00_Sheet11 オリジナル
15 行
17 列
0
0 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2014/8/28
1
2
3
4
5
6
7
4
11
8
9 10 11 12 13 14 15 16
10
10
3 12
9
9
6
2
5
13
2
12
3
6
1
8
5 13
11
4
8
7
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
7
42
8. NL-sample01_Sheet10 オリジナル
19 行
16 列
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2014/8/28
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15
25
24
26
1
5
2
6
5
8
3
7
6
9
7
26
28 24 25
21 27 28
8 10
9 11
21
4
15
15
12
13
14
17
10
11
17
1
12 2
13 3 14
19
19
23
27
22
4
16
22
16
18
18
20
20
23
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
43
9. NL-sample02_Sheet5 オリジナル
18 行
18 列
0
1
2
3
4
5
0
1
1
2
3
17
18 15
4
10 9
9
5
6
7
8
9
10
11
12
13
14
18
15
16
12
12 15
17 17
2014/8/28
6
7
8
2
5
4
3
4
9 10 11 12 13 14 15 16 17
10
1
8
6
7
5
3
6
11
13
7
8
2
11
16
14
14 13
16
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
44
10. No.56 作・かばしさま Medium ※
24 行
14 列
0
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
※ 「ペンシルパズル本156 ナンバーリンク4」(ニコリ) より引用
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
45
11. No.69 作・ぽっつ Hard ※
24 行
14 列
0
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
※ 「ペンシルパズル本156 ナンバーリンク4」(ニコリ) より引用
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
46
12. No.73 作・まいなすよん Hard ※
24 行
14 列
0
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
※ 「ペンシルパズル本156 ナンバーリンク4」(ニコリ) より引用
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
47
13. NL-sample03_Sheet10 オリジナル
21 行
18 列
0
0
1
2
3
4
5
6
7
8
9 12
10
11
12
13
14
15
16
17
18
19
20
2014/8/28
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17
7
6
8
7
6
8
1
15
17
2
13
2
3
14
12
16
17
15
3
5
1
13
4
9
10
14
4
10
16
5
11
11
9
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
48
14. NL-sample03_Sheet9 オリジナル
21 行
18 列
0
0
1
2
3
4
5
6
7
8
9 12
10
11
12
13
14
15
16
17
18
19
20
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17
7
6
8
7
6
8
1
15
17
2
13
2
3
14
12
16
17
15
3
5
1
13
4
9
14
4
10
10
16
5
11
11
9
短絡解３種類
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
49
15. NL-sample09_Sheet1 オリジナル
19 行
35 列
0 1 2 3 4 5
0
1
1
2
3
17
18 15
4
10 9
9
5
6
7
8
9
10
11
12
13
14
18
15
16
12
12 15
17
18
2014/8/28
6
7
8
2
5
4
3
4
5
6
7
8
2
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
10
1
8
6
35
7
25
24
26
25
24
26
35
19 20
20 19
3
30
21
32
31
17
33
34
34
32
33
21
30
31
11
23 22
22 23
27
28
13
28
29
29
27
11
16
14 13
14
16
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
50
16. No.91 作・おらけ Hard ※
36 行
20 列
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2014/8/28
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
※ 「ペンシルパズル
本156 ナンバーリン
ク4」(ニコリ) より引用
51
結果発表
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
52
チーム
T01
正解
不正解
ボーナス
計
問題番号
01
1
0
1
6
提出時刻
T02
正解
不正解
ボーナス
計
提出時刻
T03
正解
不正解
ボーナス
計
提出時刻
T04
正解
不正解
ボーナス
計
提出時刻
T05
正解
不正解
ボーナス
計
提出時刻
T06
正解
不正解
ボーナス
計
提出時刻
T07
正解
不正解
ボーナス
計
提出時刻
02
03
04
05
06
08
09
10
11
12
13
14
15
16
合計点正解数、他
0
0
0
15:35:59
15:00:00
15:00:00
15:00:00
15:42:51
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
0
0
0
0
0
0
0
0
0
0
0
15:38:19
15:43:11
15:55:34
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
1
0
1
6
0
0
0
0
0
0
0
0
0
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
1
0
1
6
1
0
1
6
1
0
1
6
3
0
1
8
0
0
15:42:35
15:29:27
15:42:35
15:42:35
15:00:00
15:00:00
1
0
0
1
0
0
2
0
0
0
0
0
0
0
0
0
0
0
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
12
特別賞
15:42:51
5
15:40:16
15:41:35
1
0
1
6
0
1
0
1
6
0
0
1
0
1
6
15:38:20
15:00:00
15:38:20
15:00:00
15:00:00
15:38:20
15:44:17
15:00:00
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
0
1
0
1
6
15:29:27
15:29:27
15:29:27
15:29:27
15:29:27
15:29:27
15:42:35
15:29:27
15:00:00
15:29:27
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
0
0
1
0
1
6
0
0
0
0
1
0
1
6
15:26:49
15:26:49
15:26:49
15:26:49
15:41:37
15:00:00
15:00:00
15:55:14
15:00:00
15:00:00
15:00:00
15:00:00
15:41:37
15:41:37
15:00:00
15:00:00
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
1
0
1
6
3
0
1
8
1
0
1
6
1
0
1
6
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:42:00
15:53:47
30
15:55:34
4
24
特別賞
15:44:17
15
80
優秀賞
15:42:35
8
43
15:55:14
18
98
最優秀賞
15:53:47
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
15:00:00
チーム番号
T01
T02
T03
T04
T05
T06
T07
2014/8/28
07
1
0
1
6
発表者所属
0
15:00:00
チーム名
北九州市立大学
立命館大学
早稲田大学
JST ERATO
Numberlink Ganbaru Computer
戸川研究室D
ERATO Graphillion
会津大学
神戸大学
東京工業大学
Sugar+GlueMiniSat
TNT
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
54
表彰
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
55
表彰
• 最優秀賞
– T06 (神戸大学) Sugar+GlueMiniSat
田村直之宋剛秀番原睦則鍋島英知
• 優秀賞
– T04 (JST ERATO) ERATO Graphillion
安田宜仁鈴木浩史岩下洋哲中澤吉男湊真一
• 特別賞
– T01 (北九州市立大学)
篠原明日香野村孔明手嶋一夫高島康裕
– T03 (早稲田大学戸川研究室D)
多和田雅師阿部晋矢川村一志藤代美佳
• 表彰状授与は、夕食時となります。
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
57
来年もよろしくおねがいします
2014/8/28
Copyright © 2014 情報処理学会システムとLSIの設計技術研究会
58

Download Report