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に参加できなかった悔しさも高専プロコンで良い成績を残すための糧にしたいと思っています。どうか応援よろしくお願いいたします。