高専祭2014

こんにちは、部長の唐澤です。

本日2014年11月1日より11月2日の二日間、明石高専では高専祭を開催しております。
我が部では本校舎三階の合併教室でAIによるマリオの攻略動画とCGの展示を行っております。
天候は悪いですが、力作揃いですので是非いらっしゃってください!

全国高等専門学校プログラミングコンテスト2014 参加記

こんにちは、部長の唐澤です。 2014年10月18日から19日に岩手県一関で開催された全国高等専門学校プログラミングコンテストにチーム「人力の神話」として情研から唐澤・中田・立川が参加してきました。

高専プロコンとは、その名の通り全国の高専生によるプログラミングで何かを行うコンテストです。 コンテストは競技・課題・自由部門に別れ、競技部門では与えられた問題に回答するプログラムを数ヶ月かけて実装し、それを用いて他の高専と対戦します。 我々はこれに参加し決勝戦まで進出することが出来ました。

本日は問題の概要と我々の解法を紹介したいと思います。

問題概要

初めにある画像がサーバより与えられます。 この画像は基本的に風景画なのですが、縦横最大16に均等分割された小画像をランダムに並び替えた画像で構成されています。 この画像をいくつかの操作によって元の画像に戻すというのが今回の課題なのですが、まずはその小画像から元の画像を推測しなければなりません。 これには画像処理の技術が応用されることになります。
名称未設定

小画像を並び替える手順は、ある小画像を選択する選択操作と選択された画像を隣の画像と入れ替える交換操作に依って表されます。 選択回数には上限があり、単純に端のピースから揃えていくということは出来ません。 一つのピースをぐるぐる回して正しい並びに戻す様子はさながらパズドラのようです。 また選択・交換ともにコストが設定されているので出来るだけ短い操作で元の画像を復元しなければなりません。 回答をするまでに掛かった時間にはかなり大きめのコストがあり、長い時間をかけてスマートな復元手順を提出するより、愚直な手順でも短い時間で提出したほうが総コストは安くなったりします。

解法解説

前述のとおりこの問題は大きく画像処理部と復元手順探索部に分かれるのでそれぞれについて解説します。 なお唐澤は復元手順探索部の実装を担当しており、画像処理部の実装には関わっていないので、画像処理部の解説のみ立川が記述します。

なおソースは全てbitbucktで管理しており、ここに公開してあります。

画像処理部

去年同様に画像処理部を担当しました。最初に言ってしまうと、画像の復元はかなり運頼みでした。最終的に上の草原の写真は復元できていません。ここでは切り分けられた各画像を画像と呼び、復元された画像を元画像と呼ぶことにします。

今回の問題では、画像に評価値を割り振って貪欲的に評価値が良いものを結合していく、という手順を取りました。

評価値は、

[latex]a_0=1.0, a_1=0.15[/latex]

[latex]E=([sum_{i=0}^{1}a_isum_{k=0}^{l}(abs(R1^{(i)}_k-R2^{(i)}_k) + abs(G1^{(i)}_k-G2^{(i)}_k) + abs(B1^{(i)}_k-B2^{(i)}_k)]/l)^3 [/latex]

で決定しています。魔法の呪文です。ちょっとだけ補足しておくと、R1,R2,G1,G2,B1,B2は比較する2つの画像の画素値で、iは各画像の各画素値をi階微分したもので、正規化のためにlで割ってます。

探索方法について説明します。予めWxHの配列を用意します。最初に配置する画像は分かるわけがないため、ランダムに置く場所を決め、そこで全ての画像を配置するようにします。そこから、四方を見て上式で求めた評価値が一番小さくなるような画像をその場所に配置します。あとは空いている場所を埋める処理を書くだけです。

グラデーション系の画像にはかなり強いというのは経験則からわかるのですが、任意の二次元画像や端の画素が似ている画像は高確率で死ぬので人力で調整してくれるクライアントをチームメイトの中田に書いてもらいました。

後で府立の取った方針を見てみるとジグソーパズルのソルバーの論文を読んでいたみたいです。冷えました。

画像解析のソースはここにあります。

復元手順探索部

名称未設定1

復元手順は結局{ 00を選択, 01を選択, …, FFを選択, 上に交換, …, 左と交換 }という操作の配列で表現されるので、この操作列の探索を行うことに依って解を導出しています。 しかし一回の操作はWxHの盤面で約WH+4個あり、N回の操作列は(WH+4)^Nもの数だけ存在することになります。 このような膨大な手順を全て検証することは出来ないのである程度操作を繰り返して十分な数の操作列を生成したら、それらの操作列を評価関数にかけ、良い値が返って来た一部の操作列だけを元に次の探索を行うことにしました。 評価関数は正しい座標と現在の座標とのマンハッタン距離に選択している小画像の正しい座標とその小画像の正しい画像のマンハッタン距離の積で表しました。 選択している小画像より遠くにある画像の方がずれている時のペナルティが大きいわけですね。 選択している小画像はどの位置にあっても評価値に影響を与えないようにしたので、それをぐるぐる回して遠くのセルを揃え、最終的に正しい位置に戻ってくるようになります。 交換操作しか行わない場合は評価値の計算は交換を行った小画像の分しか変化しないので計算を省略することも出来ます。

選択回数は交換回数よりも遥かに少なくなるという性質を利用し、選択は確立的に行うようにもしました。 選択をする確立をP1、特にとある小画像で選択する確立をP2とすると一回の操作の数はWH+4個からWHP1P2+4に減らすことが出来ます。 はじめからとある小画像を選択する確立をP1とP2の積に設定しておけば良いと思われるかもしれませんが、P1とP2を分離することに依って1−P1の確立でWH個の小画像それぞれについて選択するかどうかの判断を行わなくても良くなります。

絶対に復元できない盤面はそれ以上探索をしないようにもしました。 選択回数が上限に達していてそれ以上選択できない時は、絶対に復元できない盤面が存在することが数学的に証明されており、またその理論を応用すれば簡単に不可能性を確認できるのです。 具体的な証明は省略致しますが「15パズル 不可能性」などで検索するとわかりやすい資料を読むことが出来るかと思います。 また不可能性は選択に依って変化し、交換に依っては絶対に変化しないので、前回不可能性を判定してから交換しか行っていない操作列は計算を省略することも出来ます。

この他にも類似の盤面を除いたりもしました。

ところで、このようにして無視する操作を増やしたり、探索を続ける操作列を制限したりすると問題も生じます。 「ある程度良い解には到達するが、一度盤面を大きく崩さないと完全な復元は出来ない時に、完全な復元が出来なくなる」のです。 15パズル(スライドパズルとも言われる)を一度でもやったことがあれば、正しい位置にあるピースを崩さずに解くのはかなり難しいというのが分かるかと思います。 この問題の対策として次の4点の工夫を行ないました。

  • 特に見込みのある操作列から生成される操作列は評価を見送る。
  • なかなか評価値が改善されなかった場合は選択確率P1,P2を大きくする。
  • 操作列の中から評価値が良くないものをランダムで選び出し探索を続ける。
  • 評価値が改善されなかった場合は操作を続ける操作列の絶対数を増やす。

このような改善を行った結果、極値に陥った時のリカバリをほぼ確実に行えるようになりました。

復元手順探索部の解説は以上になりますが、このアルゴリズムの問題点は無駄な操作列を沢山検査しなければならないので時間がかかることです。 それでも導出される解はかなり交換回数を抑えた解になっており、実際1回戦は1位で勝ち抜けることが出来ましたし、予行演習では(逆の復元手順を提出してしまうというバグが有り回答としては評価されませんでしたが)高選プロコンを優勝することになった大阪府立高専よりも良いスコアを出すことが出来ました。 決勝戦で敗北した原因は、16×16の最大ケースが出題されると確信し(実際は12×10の画像が出された)それ用のチューニングを行っていたことと、予想よりも交換コストが遥かに小さかったことにあります。 逆に交換コストが最大であれば今より少しだけ良い成績が取れたのではないかと思っています。

このアルゴリズムのソースは公開してありますので、解説で曖昧だったところはソースを見て頂ければ良く分かるかと思います。

総括

結果は1回戦、準決勝を勝ち抜き決勝戦で最下位を取るというものでした。 敗因は出題されるケースを穿ち過ぎ他のケースに対応できなかったことにあります。 かと言って他のケースに対応するだけの実装力と計画力があったかと言えば疑問があり、結局は実力通りの成績だったと思います。 しかし敗因が明快であるだけに強い悔恨の念も感じています。 私達は去年も高専プロコンに参加していますがそちらは散々な結果でした。 ですので今回の目標は決勝戦進出に設定していたのですが、それを達成できたにしても決勝最下位とは……やはり悔しいです。

来年は受験や卒業研究がありますのでプロコンには参加しないつもりです。 最後のプロコンをこのような悔しい思いで終えるのは本当に悲しいものですが、来年度以降はこの経験を活かし後輩のプロコンを全力で応援したいと思います。

結果については悲しい思いでいるとは言え、連日睡眠時間を削ってプログラムを実装したことや、他の高専との岩手での交流・観光は本当に楽しい思い出です。 一緒にお話してくれた府立・神戸・松江・福島・沖縄高専の方、東京大学の大城さん、本当にありがとうございました。 一緒に麻雀をして遊んでくれた久留米高専の方々は最早ソウルメイトだと思っています。 またお話出来たら良いですね。
(毎日毎日夜遅くまでプログラミングするのは……もういいかな……w)

「校内競技プログラミング定期勉強会」開催決定!

こんにちは、部長の唐澤です。

12月に迫る情報オリンピックに向けて、明石高専生限定の競技プログラミング勉強会を開こうと思っています。

対象:明石高専生(非部員、下級生、上級生、非電気科生、大歓迎!)
日程:11月11日(火)より毎週火曜日放課後
場所:情報センター(予定)
形式:コンテストとその問題に対する討論
前提知識:CやC++に関する初歩的な知識(制御構文や配列など)
応募方法:応募ページもしくはメール メール応募の場合は指名、学年、学科、学籍番号を本文に記載し、唐澤(e1110 [at] s.akashi.ac.jp)までお送りいただくようお願いいたします。

昨年まで我が校では、多くの下級生が情報オリンピックに一人で挑み、そして無残に敗北していきました。 情報オリンピックは本選までいくと本当に楽しいのです。 今年からは、適切な指導を受けなかったが故に辛酸を舐める学生を、一人でも多く減らしたいと考えています。 アルゴリズムの知識がなくても構いません。 たまにしか来れなくても構いません。 ですから、一緒に情報オリンピックに行きましょう。

JOI夏季セミナー 参加記

DTM班のYuZakuroです。

はじめに

8/25~8/29に、JOI夏季セミナーに参加してきました。

こちらはJokenの公式ブログということで真面目な内容を書いておりますので、不真面目な内容をご所望の方は私の個人ブログの方を御覧ください。

JOI夏季セミナーについて

JOI夏季セミナーとは情報オリンピック日本委員会が主催している合宿形式の勉強会で、いくつかのグループに分かれて計算機科学の本を読み、最終日にその成果を発表するものです。

このセミナーは毎年開かれており、高校三年生以下の参加者約25名が参加しています。

中には国際数学オリンピックや国際数学オリンピックの過去の日本代表も参加しており、非常にレベルの高いセミナーとなっています。

課題について

参加者は、いくつかのの本の中から好きな本を選択し、五日間その本を読み、同じ本を選んだ参加者とともに学びます。

今年はの課題は以下の五冊でした。どの本も長い名前なので、記事中では括弧内に示した略称を使用します。

  • Looking for a Challenge (L4C)
  • 並行コンピューティング技法 ― 実践マルチコア/マルチスレッドプログラミング (以下並行プログラミング)
  • 情報理論と符号理論 (黄色い本)
  • 集合知プログラミング (集合知)
  • 計算機プログラムの構造と解釈 (SICP)
  • 入門 自然言語処理 (自然言語処理)

私は自然言語処理を選択しました。

セミナーの内容について

1st day

この日は簡単な説明や自己紹介などを行ってから、本決めを行いました。

その後は夕飯を食べてから、最初のセミナーを行いました。どのグループも、まずは自己紹介を行ってから、発表内容を考えるために軽く本を読み始めていたように思います。

2nd day

この日から、軽くプログラムを書き始めていました。しかし、ライブラリや言語のバージョンの違いの関係でサンプルプログラムが動かなかったため、バージョンの違いによる書き方の差異を洗い出すことに一日かけてしまいました。

スムーズに進んでいた人はこの日の内に動くプログラムができていたように思います。しかし、まだ発表の内容を決めかねている人も一定数いるようでした。

3rd day

五日目は発表に、四日目はスライド作成や発表の準備に費やされると予想されるため、実質的にこの日が実装を行う最期の日でした。

私は午前中に一つ、午後に一つ、合計二つの構文解析器を書きました。

4th day

この日の午後にはほぼ全員がスライド作りを行っていました。

一人、スライドに一切着手せずに参加者のtwitterを分析していた集合知班の人もいましたが……

5th day

最終日は成果発表会でした。

発表は全体的にハイレベルで、作問をした人や件のtwitterの分析をした人など、聞いていて非常に楽しかったです。

私は「自然言語処理における構文解析器の構造と解釈」というタイトルで、合計101枚のスライドで発表しました。

さいごに

二年生の時は申し込みはしましたが、選考で落ちてしまい参加できなかったJOI夏季セミですが、非常に楽しく勉強になりました。

新しく仲良くなった人も多く、その点についてもとても有意義だったと感じています。

総じてレベルの高いセミナーではありますが、わからないところはチューターやメンバーが教えてくれたり、手伝ってくれたりするので心配する必要はないと思います。

私は三年生なので来年は参加できませんが、Jokenの二年生以下のみなさんや、これから明石高専に入りたいと思っている中学生のみなさんは、是非参加してみてはどうでしょうか。

興味のある方のために、当日の発表スライドや成果物を以下においておきます。

自然言語処理における構文解析器の構造と解釈

構文解析器ライブラリShino

パソコン甲子園2014予選 参加記

プログラミング班の割地です。

2014年9月13日(土)、パソコン甲子園のプログラミング部門にプログラミング班の松崎君とチーム「!thinkable」として参加しました。

問題数は10問でした。僕たちのチームは8問通しました。1->2->6->3->7->4->8->5の順番で解きました。

自明ではないような問題(今回は6番以降と予想)と簡単な問題(1番以降)を並行して解いていきました。 ちなみに6番はFirstAcceptだったみたいです。

各問題ごとの解法を簡単に書いていきます。

  1. 掛け算 
  2. 足し算して1000円以上なら1
  3. 剰余算
  4. ソートして重複するものは取り除く
  5. 買い物する駅は全て異なるので一周すれば解が求まるが、一周せずに折り返したほうが費用が安くなる場合があるのでそれも探索する
  6. 4種類の回転をswapで実装する
  7. 連想配列っぽいの作る
  8. priority_queueとしゃくとり法

相方との実力差を改めて感じたのでもっと精進しようと思いました。

SuperCon2014 参加記

こんにちは、プログラミング班班長の松崎です。 スーパーコンピューターを用いて1つの問題を解く、SupercomputingContest2014に参加しました。

東京工業大学で8/18(月)~8/22(金)の5日間開かれ、同級生と僕の3人でチームNITAkashとして参加しました。

1日目

無事到着。荷物が重い。太陽が眩しい。駅から東工大が見える。工業大学は田舎に隔離されてるかと思っていた。

開会式の後オリエンテーションが始まり問題の説明があった。どうやら今年はテトリスのような問題が出るらしい。

そして本選会場で問題の詳細が説明される。おおまかに言うと、テトリスのようなゲームで16種類用意されたピースのそれぞれの個数が渡されて、それをできるだけ高さが低くなるように積んでいくといった感じらしい (詳しくは公式を参照)。中には空洞のあるピースや某対戦ゲームのタイトルっぽい十字もあり、難しそうだった。

それから解法を考え始めるが、案が浮かばない。 しばらく経ってから、以下のような案が出た。

  • 人力解法

    人間の手で組み合わせを見つけるというもの。 人力解法を行ったチームの成績が良かったので、今思えばこれが正解だったかもしれない。

  • 遺伝的アルゴリズム

    答えを生物に見立てて生存競争させるメタヒューリスティクスアルゴリズムの一つ。 しかしこの時点では知識がほとんど無く、少し不安だった。

  • 隙間なくピースを詰めてそれが答えになるか確認する

    隙間なく詰めるのが難しそうだったので没にした。

他にも色々あったけど、覚えてるのはこれくらい。

人力解法はアルゴリズマーとして敗北した気持ちになりそうだったので、僕が遺伝的アルゴリズム+少しの人力解法と決めた。後々知った話だが、遺伝的アルゴリズムは経験と勘が物を言う素人には難しいものらしく、調整に悩まされることになった。

途中で休憩が入り(これは3日連続で開かれたが、実質twitterのオフ会のようなものだった) 、その後本格的に作業開始。

とはいえやはり説明や解法を考える時間が長く、コードはまだ未完成だった。

2日目

チームメイトが解析・デバッグ用にprocessingをダウンロード(ネットからのダウンロードは禁止なので、運営の人にUSB経由で貰った)。ある人から「processingで遊んでると負けるよ」と言われてしまった。 並列実行するコンピューターについての説明。どうやら本番ではCPUのコアが384個も使えるらしい! 休憩時間には実際に使用するスーパーコンピューターを見学した。自分達が開発中に用いるCPUを見つけ、チームメイトの一人が夢中で写真を取っていた。

この日で一応プログラムが動くようになった。しかし遺伝子がうまく競争せず、最下位不可避。

3日目

とにかく遺伝的アルゴリズムの調整。いいスコアを残したものとすると微妙で、できるだけ低く積んで限界が来たらそこで切り上げるという手法を取った。序盤は優秀だったが、息切れしてからが絶望的な酷さだった。

夕飯に評判の台湾ラーメン店こころに行ったが、まぜそばが非常に辛くて5日間の食事で最もつらかった。次に来るときは無難に塩ラーメンを食べたい。

4日目

いよいよ競技も終盤、最終日は発表会だったので、競技は実質4日目の1時15分までだった。 とにかく調整するが、うまくいかない。結局、開発したプログラムを提出したものの少し書いた人力解法の部分は切り捨てた。しかも設定ミスで使う使用コア数は開発中の64個のままだった。悔いの残るまま競技は終了した。その後の(黒歴史と化する)インタビューも終え、時間が余ったので秋葉原を観光をした。 3人ばらばらだったが、僕はラブライブのファンなので神田明神や竹むらに聖地巡礼に行った。 非常に楽しかったし、また情報オリンピックの時にも行きたい。神田明神の絵馬の絵が良かった。

5日目

いよいよ発表会。まず4日目に収録した各チームの黒歴史インタビューが放送され、成績発表という形。当然我がチームの入賞はなし。

その後の懇親会でジャンケン大会。チームメイトの一人はgoogle glass…風の伊達メガネをゲット。僕はジャンケンに負け続けおまけとしてgoogleストラップをもらった。

懇親会の途中で全体の成績が公開された。成績は21組中14位。解答のミス等で失格したチームを除けば最下位であり、ある人に言われた通り敗北。最下位も不可避だった。

まとめ

反省はアルゴリズムの選択のミス。チームの連携不足が痛かった。

残念な結果だったが、東工大で情熱をささげた5日間はとても楽しかった。 来年はもう少しヒューリスティクスアルゴリズムをよく学んで参加しようと思う。

ACM-ICPC2014 国内予選 参加記

こんにちは、部長の唐澤です。

ACM-ICPC (ACM International Collegeate Programming Contest: ACM国際大学対抗プログラミングコンテスト) とは、ACM (Association for Computing Machinery) 主催で 1976 年度から毎年行われている、世界規模の大学対抗チーム戦プログラミングコンテストです。

2014年7月11日に行われたACM-ICPCの国内予選に情報工学研究部から、唐澤・立川・中田がチーム「Humanity」として参加し、全体で42位の成績を獲得して今年10月に行われるアジア地区予選に招待されました(結果)。

問題はAからGまでの7問であり、我々はA,B,Dの3問を通しました。1人1問ですね。バグを起こしやすい問題もありましたが、全て一発Acceptでき嬉しく思います。またC問題はほとんど書き終わっていたのにも関わらず、最後を詰める段階で時間終了となってしまい悔しくもあります。

明石高専からICPCへの参加は2010年から4年ぶりのことでした。在学生の中に経験者がいないということで多少の不安もありましたが十分に実力を発揮できたと思います。

残念なことにアジア地区予選の日程は同メンバーが参加予定の全国高等専門学校プログラミングコンテストの本戦の日程と完全に被っています。高専プロコンの方は学校から支援金が出て多くの方に助けてもらっているので辞退するわけにはいかず、残念なことですがICPCは辞退することにしました。メンバーは全員4年生であり、来年度も出場のチャンスがあるので、来年度こそはアジア地区予選に行きたいと思います。

本当に残念な結果になってしまいましたが、ICPCに参加できなかった悔しさも高専プロコンで良い成績を残すための糧にしたいと思っています。どうか応援よろしくお願いいたします。