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

こんにちは、部長の松崎です。

今月17日から21日までの5日間、東京工業大学・大阪大学主催のSupercomputingContest に参加しました。ShinQ(3人全員が部員)とReewNen(3人中2人が部員)というチームで参加し、ReewNenは3位に入賞しました。

大会でやったことは主にベクトル化・並列化を意識したプログラミングですが、それだけではなく休憩時間には他校の選手とアニメを見たり、雑談したりして交流しました。以下は参加部員の感想です。

松崎:二度目の参加で、優勝には届かなかったものの3位に入賞できたのでよかった。プログラムのベクトル化には苦労したが、1問で10分以上かかったプログラムが最終日に1問3分弱で解けるようなるまで高速化できたときは嬉しかった。

 

国際情報オリンピックで銅メダルを獲得しました

こんにちは、部長の松崎です。

今年7月26日から8月2日にかけて国際情報オリンピック(IOI)に日本代表として参加し、銅メダルを獲得しました。IOIの様子はこちらに、感想は後日JOIのサイトにアップされる予定ですので、そちら読んでいただければ幸いです。

 

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

こんにちは、部長の松崎です。

今月12日から16日にかけて、情報オリンピック日本委員会主催のJOI夏季セミナーに参加してきました。情報工学研究部からは2名が参加しました。

僕はここに書いてある6冊の中から超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-を選びました。発表に使用したスライドはこちらです。

この本は主にZDD/BDDと呼ばれる組み合わせ集合を表すデータ構造について書かれていました。ZDDの概念はそんなに難しくないのですが、ZDDを作る手法については理解するのに苦労しました。

最終日前日はスライドを完成させるために深夜二時までスライドを作ったりと大変でしたが、他の参加者と交流したり、深層学習などの講義を聴いたり、他の参加者の発表を聴いたり、夕食にわたがしを作ったりと、充実した日々を過ごせました。

僕は三年生なので今年が最後ですが、後輩や中学生のみなさんは来年以降も参加することができます。とても良い学び、経験になるので是非参加しましょう!

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

こんにちは、新しく部長になりました松崎です。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への入賞を狙いたいと思います。

全国高等専門学校プログラミングコンテスト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)

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