田中 英行 / Hideyuki Tanaka

  • 東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 M1
  • 京都大学工学部情報学科計算機科学コース卒業 学士(工学)
  • とても遅筆なため、現在停滞気味

プログラミングコンテスト遍歴

SuperCon 2000

  • チーム名 combat
    • 優勝

ICPC

  • 2002年度:cherub (意味は知らない)
    • 国内予選:3問正解 17位(学内4位、繰上げ3位) → 予選落ち
  • 2003年度:combat (三年の時を経て再開したメンバーで結成)
    • 国内予選: 4問正解 10位(学内2位) → 通過
    • 会津大会: 3問正解 9th place → 敗退
      • 美術館と温泉が良かった
  • 2004年度:combat
    • 国内予選: 4問正解 5位(学内1位) → 通過
    • (夏合宿:4位)
      • 初めて体系的にアルゴリズムの勉強を始める
    • 愛媛大会: 7問正解 1st place → 通過
      • SJTUの恐ろしさを知る
      • 温泉がすごく良かった。みかんも良かった。
    • (冬合宿:1位)
    • 世界大会: 4問正解 29th place
      • 世界の壁はあまりにも厚い
      • グラフが苦手だということがはっきりする
  • 2005年度:combat
    • (模擬国内予選:1位)
    • 国内予選: 5問正解 2位(学内1位) → 通過&海外派遣獲得
      • GNCにしてやられる
      • GNCにマニラを取られたので、海外派遣はなぜか激戦区北京になった
    • (夏合宿:1位)
    • 東京大会: 7問正解 1st place → 通過
      • SJTUはまだ高みに
      • 宿泊施設が壮絶を極めた
    • 北京大会:3問正解 10th place(オープン参加)
      • このリージョンおかしいよ!
      • しかも北京大会の優勝チームは世界大会に行けないというありえない状態
    • (冬合宿:国内では1位)
    • 世界大会 3問正解 19th place
      • 鬼の問題セット
      • それに加え、準備不足に泣いた
      • 最後まで、メダルは取れずにICPC人生は終了

ICFP Programming Contest

  • 2004 年度:チーム名 hasKilled 3位
    • Haskellで出場
  • 2005 年度:チーム名 Combat-Tanteidan 3位
    • Haskellで出場
    • 称号を貰った
    • この年はICFPに招待されたけど、学科からお金が出なくて行けなかった!

Google CodeJam

  • 2005年度
    • 三次予選?まで行った
    • Tシャツをもらった

Haskellについて

Haskellは、 純粋関数型と呼ばれるカテゴリに属するプログラミング言語です。 純粋関数型というのは、おおまかに述べると、 式の評価における参照透過性が保たれた関数型言語ということができます。 参照透過性というのは、これまたおおまかに述べると、 同じ関数が同じ実引数において評価された場合、 かならず同じ値になるという性質です。 純粋関数型言語は参照透過性の確保のため、 副作用をともなう計算を単純にそのまま扱うことが出来ないため、 いずれも特殊な方法が用いられています。 Haskellにおいてはモナド(Monad)と呼ばれる 計算の抽象化を行うことによってこれを実現しています。 そのほかの純粋関数型言語だと、たとえばCleanという言語では Linear Typeと呼ばれる型システムの拡張によって 副作用を持つ式の参照透過性を確保しています。

モナドを知ることはHaskellを理解する近道です。 モナドは前述の副作用を扱うための枠組みとして 導入された側面もありますが、 それにも増して、プログラムの表現力の観点から、 現在ではHaskellの多くのライブラリが モナドスタイルで提供されています。 つまり、モナドを知ることは、Haskellを学ぶことであり、 同時に近代的なプログラム抽象化技法を学ぶことになるのです。 多くのプログラムはモナドとマッチし、 多くの抽象化がモナドによってこそ為し得ます。

Haskellは「目利きのハッカーが選ぶ言語」です。 ICFPが毎年開催しているプログラミングコンテストで 2004年度に1〜3位を独占、2005年度に1位と3位を占めました。 このプログラミングコンテストは誰が、何人で、 どんな計算機を用いても、 そして、どんなプログラミング言語を用いて出場しても良いという、 己が能力と己が用いるプログラミング言語が最強であることを証明する、 というコンセプトのコンテストです。 入賞するとチームとそのチームが用いたプログラミング言語に称号が与えられ、 一年間無制限に自慢できる権利が得られます。 そこでHaskellは「目利きのハッカーが選ぶ言語("Haskell is the programming tool of choice for discriminating hackers")」に2004年度、2005年度の二年連続で選ばれました。 これはある意味でのHaskellの有用性の証明であります。

Haskellには多くの最新のプログラミング言語の研究が取り入れられています。 GHC(Glasgow Haskell Compiler)というHaskellの処理系が 現在事実上のHaskellの仕様となっており、 そして、その処理系に積極的に新しい機能が追加されいます。 JavaやC#が最近のバージョンアップ、あるいは将来のバージョンアップにて 追加する予定の機能などはほとんどすべてHaskellには 搭載されている機能と言っても過言ではないでしょう。 このような他の言語が現在追加を検討している機能に加え、 数年前に論文が発表された最新の研究、 たとえば、GADT(Generalized Algebraic Data Type)や STM(Software Transactional Memory)などが すでに現在のGHCには実装されています。 そして何より重要なのは、 Haskellは今ここにある言語、今使える言語だということなのです。

Haskellは高度な抽象化能力により、 他の多くの言語よりハイレベルな抽象を行うことが可能です。 それはたとえばモナドに代表されるようなもので、 従来型のものとは別次元の抽象化の可能性があります。 また、強力な型システムと純粋関数型の持つ 参照透過性によって、コーディングの際に 入り込むバグのほとんどをコンパイル時に検出することができます。 たとえば、コンパイルが通るということは、 そのままセグメンテーションフォールトが起こらないことの 証明でもあります。 コンパイルの通ったコードに含まれるバグはもはや 本質的にロジカルなバグのみです。 ダングリングポインタやメモリリークや 実行時型エラーにはおびえる必要はもう無いのです。 参照透過性によりコードが実行されている時の 変数の状態を把握する必要が無くなります。 遅延評価によって式の順序に意味が無くなり、 注意深く式を特定の順番に配置する責任からプログラマを解放します。 無限を無限のまま扱うことを可能にします。 豊富なリスト処理関数によるループの抽象化が、 プログラマの書きたい処理と 書かなければならないプログラムの間の距離を縮めます。 書きたいように書けるようになります。 参照透過性を保ちつつも、 モナドの強力な抽象化能力と モナドに対する構文糖衣によって、 手続き型に近い形でのコーディングも可能です。 むしろ、手続きの抽象により、 手続き型よりも手続き型らしいコードを書くことが可能だとすら言えます。

まずは、Haskellに興味を持ってください。 そして、Haskellについて調べてみてください。 「やさしいHaskell入門」という文章が非常に難解でも投げ出さないでください。 世の中には「やさしい」と銘打った難解な文章も多数存在するものです。 最近では日本語の文献もいくつか出版されていますので、 それを読むのも良いかもしれません。 Web上の文章にも、本当にやさしい入門記事はあるはずです。 一時に比べてドキュメントの問題というものは急速に解消しつつあります。 そして、最後に。Haskellを使ってみてください。 やはり、使ってみなくては良さは見えてこないものです。 使ってみた感想はどうでしょう。 これまで使用されてきた言語との違いに戸惑われるでしょうか? あるいは意外とすんなり思い通りに書くことができて拍子抜けするでしょうか? いずれにせよ、Haskellをものにした時のリターンは 私と「目利きのハッカー」が保障します。 Haskellへの道は今ここに、あなたの前に開いています。 Haskellがもたらす利益を皆が享受せんことを。

2006年度模擬国内予選

  • 問題C(X-Ray Screening System)模範解答

そのほかの問題は裏で解いていました。

  • 問題A
  • 問題B
    • fileb.cpp fileB.hs
      • 関数合成で解くと二度おいしい
    • fileb.c
      • 入れ子関数を用いた方法。CにあってC++に無いもののひとつ。
  • 問題C
  • 問題D
    • filed.cpp
      • とくにいうことはなし
  • 問題E
    • filee.cpp
    • 二時間デバッグしたがバグがとれず…
    • kitsuneチームの実装力に脱帽…
    • 歳のせいにするのは良くないと思いつつも、最近歳を感じるなぁ…
    • 参った
  • 問題F
    • filef.cpp
      • とくにいうことはなし

考えさせる問題が皆無な上、 問題E以外実装が極端に簡単なものばかりなので、 さすがに本番では閾値は下降すると思われるがどうか。

2006年度 ACM-ICPC 国内予選

予想通り難化したが、 なんとボーダーは下がらなかった。 正直驚いた。 傾向は去年の東京大会の(予選じゃない方の)問題に限りなく近い…様な気がする。

  • 問題C
    • fileyokop_c.cpp
      • よく考えてみるとそんなに重い問題では無いなと思ったので解いてみた。
      • とはいえ、幅優先と深さ優先の両方を実装しないといけないので、多少面倒か。
      • 実行速度は遅い(C1:1分40秒 PentiumM 1.2Ghz)が、劇的に高速化する方法を 思いついたので、あとで実装してみようと思う。
    • fileyokop_c2.cpp
      • C1:10.5sec C2:8.5sec C3:8.3sec C4:13.1sec
      • 思ったほどじゃなかったなぁ…
    • fileyokop_c5.cpp
      • C1:3.5sec C2:3.2sec C3:3.0sec C4:3.8sec
      • ゴチゴチに最適化。ひとまず満足。
  • 問題E
    • fileyokop_E.hs
      • 遅延評価パワーをとくと見よ(…ヒープを512MBぐらいにして動かしてください)。

コメントをどうぞ!


添付ファイル: fileyokop_c5.cpp 1244件 [詳細] fileyokop_c3.cpp 457件 [詳細] fileyokop_c2.cpp 1230件 [詳細] fileyokop_E.hs 1219件 [詳細] fileyokop_c.cpp 1224件 [詳細] fileb.c 1359件 [詳細] filef.cpp 1228件 [詳細] filee.cpp 1429件 [詳細] filed.cpp 1302件 [詳細] filec.cpp 1325件 [詳細] fileB.hs 1238件 [詳細] fileb.cpp 1246件 [詳細] fileA.hs 1257件 [詳細] filea.cpp 1299件 [詳細] fileC.hs 1301件 [詳細]

Last-modified: 2009-11-06 (金) 13:29:44 (2963d)