SuperComputingコンテストに参加しました&3位に入賞しました。

こんにちは、部長の松崎です。
今月17日から21日までの5日間、東京工業大学・大阪大学主催のSupercomputingContest に参加しました。ShinQ(3人全員が部員)とReewNen(3人中2人が部員)というチームで参加し、ReewNenは3位に入賞しました。
大会でやったことは主にベクトル化・並列化を意識したプログラミングですが、それだけではなく休憩時間には他校の選手とアニメを見たり、雑談したりして交流しました。以下は参加部員の感想です。
松崎:二度目の参加で、優勝には届かなかったものの3位に入賞できたのでよかった。プログラムのベクトル化には苦労したが、1問で10分以上かかったプログラムが最終日に1問3分弱で解けるようなるまで高速化できたときは嬉しかった。
 

情報工学研究部2015年活動紹介

ここでは2015年度の情報工学研究部の活動や実績を掲載します。(10/13 現在)
2月 部員2名が日本情報オリンピック本選に出場し、1名がBランク、1名が近畿地区優秀賞を獲得
6月 新入生歓迎会開催
7月-8月 部員1名が国際情報オリンピックに出場し、銅メダル獲得
8月 部員2名が日本情報オリンピック夏季セミナーに参加
8月 Supercomputing Contest で2チーム(内1チームは3人中2名のみが部員)が本選に出場し、1チームが銅賞を獲得
9月 パソコン甲子園で1チームが本戦出場決定、1チームが近畿地区新人賞を獲得
10月 高専プログラミングコンテスト競技部門で部員2名と他1名で構成されたチームが準決勝進出

JOI夏季セミナーに参加しました

こんにちは、部長の松崎です。
今月12日から16日にかけて、情報オリンピック日本委員会主催のJOI夏季セミナーに参加してきました。情報工学研究部からは2名が参加しました。
僕はここに書いてある6冊の中から超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-を選びました。発表に使用したスライドはこちらです。
この本は主にZDD/BDDと呼ばれる組み合わせ集合を表すデータ構造について書かれていました。ZDDの概念はそんなに難しくないのですが、ZDDを作る手法については理解するのに苦労しました。
最終日前日はスライドを完成させるために深夜二時までスライドを作ったりと大変でしたが、他の参加者と交流したり、深層学習などの講義を聴いたり、他の参加者の発表を聴いたり、夕食にわたがしを作ったりと、充実した日々を過ごせました。
僕は三年生なので今年が最後ですが、後輩や中学生のみなさんは来年以降も参加することができます。とても良い学び、経験になるので是非参加しましょう!

情報工学研究部について(新入生向け) ~2015年度版~

概要
情報工学研究部は以下の班があります。

  • プログラミング班
  • 2DCG班
  • 3DCG班
  • DTM班
  • Web班

各班学校での活動は基本的に週1~2回程度です。場合によっては活動が自宅のみの場合もあります。
DTMはdesktop musicの略でPCでの作曲などを行います。
活動場所・時間に関して
仮入部期間中は平日毎日部室で4限終了後から18:00前後まで活動しています。常に見学(相談)を受け付けていますので気になる方はどうぞ。
仮入部期間終了後は活動日は上記の通り週1~2回程度に変更します。活動時間は据え置きです。プログラミング班のみ図書館下の演習室に活動場所を移します。
活動曜日は新入生の都合に合わせて調整中ですが、水曜日になる見込みです。
講習に関して
プログラミング班ではC++によるプログラミング講習と競技プログラミングを通したアルゴリズムとデータ構造の講習を週1~2回の頻度で行う予定です。
他の班での講習は現在予定しておりません。
 
 

国際情報オリンピック日本代表に選出されました

こんにちは、新しく部長になりました松崎です。2015年3月19日(木)から3月25日(水)にかけて開催された日本情報オリンピック春季トレーニング合宿に参加してきました。
情報オリンピック春季トレーニング合宿(通称JOI春合宿)は、国際情報オリンピック(通称IOI)の日本代表となる4名を決める合宿です。JOI本選参加者80名中Aランクの19名が参加しました。
春季トレーニング合宿と大変そうな名前ですが特に運動したりはしないです。問題をプログラミングで解きます。
合宿の内容について
day 1
この日は3時頃に受付し、実機練習(競技で使用するパソコンに慣れる)をした後、フローについての講義を受けました。
3時までは自由なので観光したり遊んだりできるのですが、無計画に渋谷に行ったら何もすることがなくて観光を満喫できませんでした。残念。
実機演習の問題は流石に簡単で全部満点。講義はネットワークフローに関してでした。競技プログラミングにおいては頻出ですがJOIではあまり馴染みがなかったのでためになりました。
day 2
この日から競技が始まります。競技時間は9時から14時の5時間と非常に長く大変です。これを4日間連続で行うので集中力や耐久力も試されます。
この日の問題は4問ありました。競技が始まった後、まず全体に目を通して2番が尺取り法でできることに気づきAC。
その後4番が表裏の境目がたった4つであること、a~b,b~cの反転がa~cと言った感じで結合できることに気づき、グラフに帰着してAC。
3番目はそこそこ難しくて、左から日光を浴びる場合と右からの場合で問題を分割したのち、頑張ってDPに帰着させてAC。
残る1番の問題に取りりかかりますが、数列に数列を持たせるような変な考えをしてハマってしまい、諦めて簡単だった部分点を取りました。
この日の点数は310/400でした。この時点で全体では満点が5名居たらしく、代表の枠が4名なのでかなり絶望していました。講義は昨日に引き続きネットワークフローに関してでした。
day 3
この日の問題は3問ありました。昨日と同様に全ての問題に目を通し、2番に可能性を感じたので考えていくと、普通にDPしようとするとある人が外出した後ある人が帰ってくるパターンが解決できずに困りましたが、変則的な順番にDPすることで解決してACできました。グラフに帰着せずにゴリ押したので少し実装が大変でした。
その後うまく読解できてなかった1番を冷静になって読んでみると、簡単に解ける事に気づきAC。
3番は木であることに気づいた後は適当に木に関するアルゴリズムを試しまくったらなんとかなりました。唯一道路の整備の処理に困りましたが、分割統治法で解決。200行近くにも及ぶコードを書いてAC。
この日の点数は300/300で満点でした。全体では2日連続満点が3人で、ギリギリ4位に滑り込める可能性が出てきて希望の光が見えてきました。講義は数え上げ入門でしたが、入門とは思えない難しさでした。
day 4
この日も3問で、1問応答型課題がありました。まずカードゲーマーなのも相まって2番を考察していくと、前から3枚と山札の一番上を記憶するDPを思いつきましたが、このままでは満点が取れないのでもっと考察していくと前から3枚目のカードは2枚目か山札の一番上のカードのどちらかの次である事に気づきAC。無駄な場合分けをしたせいでメモリ制限を超えてしまい、int型からbool型にして累積和を取ったりしてました。
その後過去の傾向から応答型課題はそこまで難しくないと踏んで道案内に挑戦しました。部分点は全て取れて、番号の高低を利用するところまで思いついたものの、辺に方向を付ける発想が出ずに、長いこと考えるも解けず。最後に1番の部分点を取ろうとするもバグってしまい0点。実装の負担を軽減するために部分点は解法だけ考えて実装を後回しにする戦略を取っていましたが、ここだけは裏目に出てしまいました。
この日の点数は145/300でした。自分と得点が近い人も同程度の点数だったようで決着は明日に持ち越す形となりました。この時自分は推定4位で5位の人とは10点差だったので、結構動揺していました。講義は機械学習についてでした。
day 5
いよいよ競技最終日。昨日と同様3問で応答型課題が1問ありました。まず1番を少し読むと鉄道が木になることから最大全域木を作ってやればいいことに気づきAC。誰に辺を渡すかを二分探索できるか微妙でしたが、自分の直感を信じて書いたら通って一安心しました。
次に2番をさらっと読むと、小課題5が<をストックしている数と今調べている場所を覚えるだけだとすぐにわかりました。5点は順位に影響しないと踏んで小課題3について考えると、かっこの左側(<,[)のストックしている数とその種類と調べている場所を覚えればいいとわかりました。実装が難解で手こずるもののなんとか部分点獲得。15000日電子メールを送れることをうまく活用できないかなぁと思ったりもしました。
その後一度2番を諦め3番を考えるも小課題1しか思いつかずに焦りました。小課題2が解ければちょっと場合分けすれば満点取れそうなので満点狙うも頭が混乱してきて断念。諦めて小課題2を狙うも微妙にうまくいかず。気分転換に2に戻ってみるとSを「いい文字列であるかどうか」ではなく「いい文字列ではないかどうか」を考えてみるといけそうな事に気づき2番を頑張ることに。それぞれのかっこに対応するかっこを探せばいいことに気づきAC。
3番に戻るも最後までわからずに終了。部分点で終わりました。
最終日の得点は210/300で、総得点は965/1300でした。講習はSATソルバー入門で、SATソルバーすげえええって思ってました。
day 6
競技も終わり、この日はJ言語コンテストと表彰式がありました。まるで古代文明の文章みたいなコードを解読するコンテストで、楽しかったです。
表彰式。日本代表に選ばれました。ありがとうございました。
day 7
アンケートを書いて解散。合宿中に仲良くなった人々と共に秋葉原を観光。とても楽しかったです。オリセン脱出からの解放感と、合宿が終わる名残惜しさと共に帰路につきました。
最後に
国際情報オリンピック金メダル目指して頑張ります。

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

プログラミング班の松崎です。
2014年11月8日(土)から二日間、パソコン甲子園のプログラミング部門にプログラミング班の割地君とチーム「!thinkable」として参加し、6位に入賞しました。
問題数は10問でした。僕たちのチームは1~6,8の7問通しました。
自明ではないような問題(今回は4番以降と予想)と簡単な問題(1番以降)を並行して解いていきました。 ちなみに5番はFirstAcceptでした。
各問題ごとの解法を簡単に書いていきます。

  1. 書いておいて
  2. デッドロックの問題で、閉路検出をやればおわり
  3. 組み合わせの総数を求める問題、treeとしてみて葉から解いていき、ノードごとに場合分けすればよい
  4. 累積和を使ったO(n^4)解法は間に合わないので、枠の左右を固定し、尺取法を行うO(n^3)
  5. 解けず
  6. まず、各本棚についてn冊目から始めたとき何冊目まで入るかを調べ、その後bitDPを行う

6位と自分の目標の順位より下でしたが、実力を出しきった結果だと思います。僕が問6で3回間違えてしまい、順位を落としたのは少し残念でした。来年はWAを減らし、より多くの問題を解くことでベスト3への入賞を狙いたいと思います。

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日間はとても楽しかった。 来年はもう少しヒューリスティクスアルゴリズムをよく学んで参加しようと思う。