読者です 読者をやめる 読者になる 読者になる

chokudaiのブログ

chokudai(高橋直大)のブログです

ICFPC2016ぷち参戦記

国際関数型言語学会(ICFP)の併設コンテスト、ICFPC2016に、Unagi、というチーム名で参加してました。4年連続です。

最終結果はまだ出てませんが、72時間コンテストで、66時間時点での順位表まで公開されているのを見る限り、まず間違いなく優勝してるんじゃないのかなあ、と思ってます。

f:id:chokudai:20160814135255j:plain

メンバー

並べる順番に悩んだのでアルファベット順で。

  • chokudai(ソルバー担当)
  • imos(インフラ系担当)
  • iwi(リーダー。何でも担当)
  • sulume(インフラ系担当)
  • tos(数学・関数型担当)
  • wata(ソルバー担当)

割と反則級のメンバーだと思ってます。過去3年間の戦績は

問題内容

折り紙の完成形(必ずぺちゃんこになっている)が与えられるので、展開図を作成する問題。

与えられるのは以下の2つ

  • 外周、および穴を示す多角形
  • 折り目・境界線が存在する部分の線分

最初24時間は運営から与えられた問題のみでコンテストが行われ、残りの48時間は、1時間に1回各チームが出題することが出来る。(出題によってもポイントが得られる。)

自分のやったこと

多分まとめとかはiwiさんのブログとかでやってくれるので、あくまで自分がやったことだけ。ICFP前にどれくらいネタバレしていいのかよく判らないので割とざっくりと。

  • wataさんの探索に関するアイデア出し(外周の長さが1であることを利用して、外周をヒントとして与える、など)
  • 探索アルゴリズムでカバーしきれない問題の個別AI作成(ショートコーディング要素が必要な問題。複雑な問題の合同・相似形に対する対応・手動ソルバなど)

ってな感じで、割と、メインアルゴリズムというよりは、メインアルゴリズムに横から口を出しながら、メインアルゴリズムで取れない部分をやっつける、回収担当でした。

良い感じに役割分担が出来たのか、1問残して全ての問題を解くことが出来ました。わーい。

ただ、残り1問も、手動ソルバの方をもうちょっとちゃんと作っておけば解けたので、そこは割と悔しい感じ。ICFPCで全完なんてまず出来ないだろうから、もったいなかったなぁ・・・。

 

感想

自分がチーム戦で出るコンテストってICFPCくらいなのだけど、やっぱり楽しかったです。72時間コンテストなので、iwiさんのおうちに全員が泊まり込みで参加なので(途中離脱者もいますが)、普段のコンテストでは味わえない楽しみがあります。

特に今回の問題は完成度も高く、これまでのICFPCで最も楽しく参加できました。いつもの「問題の仕様を調べる」みたいな必要がほぼなく、明快なルールで良かったです。

半端な気持ちで参加できるコンテストじゃないですが、来年はぜひぜひ今年出ていなかった人にも出てもらいたいなと思います!

何かを極めるということ。

この記事は、社長としてではなく、競技プログラミングの1選手としての記事になります。あんまり初心者への配慮とかしてません。

おそらく多くの人は、実践的に使えるアルゴリズムとかの記事を望んでるんだと思うんだけど、僕はどちらかというと、精神論のほうが得意なので。

 

続きを読む

AtCoderはどうやって年商10億円を超えるのか?プログラミングコンテスト運営会社の野望

(16/02/01追記) タイトル釣りだって多くの人に言われたので、タイトルの「越えた」→「超える」に直しました。注釈芸と一貫性を持たせるとこういうタイトルが自然かなぁ、と思ってたので、タイトル釣りの自覚はあんまりなかったです>< ごめんなさい><

はじめに

この記事には、嘘が多く書かれています。タイトルも大嘘です。現状と展望を交えた記事が書きたかったんです。が、タイトルを除いて、明確に嘘である点には脚注をつけています。*1 嘘以外にも脚注がついてることもあります。もちろん、嘘だと思わずに本文で嘘を言っている可能性は0ではありません。

スマホは知りませんが、PCではマウスカーソルを合わせることにより脚注を見ることが可能です。脚注を見ながら記事を楽しんでください。

 

*1:こんな感じ

続きを読む

競技プログラミングってなあに?

近頃、「そもそも競技プログラミングって何?」と聞かれることが多かったので、説明用の記事を書いておこうかなと思います。

よくある質問的なものも少しだけ。

(間違えて記事消しちゃったので復旧しました)

そもそもプログラミングってなに?

プログラミングというのは、コンピュータが理解することが出来る言語を書くことにより、プログラムを作ることを言います。パソコンの中で動くものを作ることだと思って貰えば大体間違ってないです。

競技プログラミングとは?

 競技プログラミングとは、プログラミングの技術を競い合うコンテストの総称です。

色々なジャンルがありますが、今回は、出来るだけ狭義の競技プログラミング(AtCoderTopCoderなど)について説明します。

 

プログラミングの難しさは、組みたいプログラムによって違います。単純な計算を行うだけのプログラムは簡単に組めますが、難しい計算などを行うプログラムは、コードが複雑になったり、数学的な工夫をしないと、実行時間が長すぎて終わらなかったりします。

競技プログラミングでは、どんなプログラムを作るべきかが与えられる(以下、問題と呼ぶ)ので、要求通りのプログラムを作ることが目標です。問題が複数与えられるので、たくさん解けた人が勝ちで、正解数が同じ場合は早く解けた人の勝ちです。

 具体的にはどんな問題なの?

競技プログラミングで出てくる問題は、以下の4要素で大体出来てます。

  • 問題文
  • 入力形式
  • 出力形式
  • 入出力例

具体例を出すと、こんな感じです。

 

問題文

A,Bの2つの整数が与えられる。A+Bの値を出力しなさい。

入力形式

2つの整数A,Bが、スペース区切りで与えられる。

出力形式

求めるべき答えを1行で出力しなさい。

入出力例

6 3 → 9

123 555 → 678

 

これでは簡単すぎて問題になりませんが、形式としてはおおよそこんな感じになります。今回は整数が入力として与えられましたが、文字列(abcde、など)が与えられたりします。

 

難しい問題って、例えばどういうの?

イメージしやすいものだと、川渡り問題とかでしょうか?

川渡り問題 - Wikipedia

オオカミヤギを連れキャベツを持った農夫が川岸にいる。川にはボートがあるが農夫の他には動物一頭かキャベツ一個しか乗せられない。農夫がいなければオオカミはヤギを襲うし、ヤギはキャベツを食べてしまう。すべてを無事に対岸に渡すにはどうしたらよいか?

こういう問題、どうやって解けばいいか難しいので、うーんうーん、ってなると思います。大体、人間が「うーんうーん」ってなる問題は、コンピュータにも難しいです。

こういう問題で、人数や登場人物、関係性が変わっても解けるようなプログラムを書くのは、やっぱり難しいですし、書ける人はすごい!ってなるわけです。

結局どういう能力を競うことになるの?

これは多少主観が入りますが、

  • 書きたいプログラムを早く正確に書ける能力(実装力)
  • 普通に計算出来ないようなことも、数学的工夫により上手く計算出来るようにする能力(アルゴリズムを考える能力)

あたりは間違いないんじゃないのかな、と思います。

 

競技人口は?

日本人の競技人口ですが、AtCoderにコードを提出したことがある人、という基準でカウントすると、一応5桁に乗るくらいです。

そんなに多くないけれども、プログラムを書ける人口を考えると少なくもない、って感じでしょうか?

ほぼ毎週行われているAtCoderプログラミングコンテストでは、毎週300~600人程度がリアルタイムで参加しています。

 

就職に有利なの?

立場上、NDA的に話せないことが多いのですが、dwangoさんが記事を出してくれました。

dwango.co.jp

昨年実施した第1回dwangoプログラミングコンテストドワンゴからの挑戦状」では、社会人含めてコンテストへの参加者は590人となり、そのうち12名が2016年度ドワンゴ新卒採用にて内定するという結果となりました。

 競技プログラミングをすることで内定が得やすくなる、という証明にはなりませんが、競技プログラミングをしている人は内定が出やすい、程度の証明にはなっているかと思います。

他にAtCoderでコンテストを開いている、リクルートホールディングス(indeed)、KLab、Donutsなどは、似たような傾向があるのではないかと思います。

 

 

この記事は出来るだけ主観が入らないように書いているので、「仕事でどう役立つ」「どうやったら強くなる」「何が楽しい」「実際内定が出やすくなるか」などは(需要がありそうなら)また別の記事で!

ブログタイトルを変更しました

ブログタイトルを「AtCoder社長のブログ」から「chokudaiのブログ」に変更しました。

理由は簡単で、「社長として書くべきこと」をブログで書くなら別の場所の方が多分良くって、この場は「chokudai」としてのアホさを前面に押し出す方向の方がずっと書き易いからです。

ってことで、このブログでは、競プロの真面目なことは書くかもしれないけど、社長として真面目なことを書くことは、多分あんまり多くないです。最近変な記事が多いと思いますが、そういう方向性になります。

まぁそれでもいいよって人だけ、今後ともよろしくお願いします。

(社長として何か書いてほしい、というのがあれば、それ用の場所も用意するので、そういう人がいたら教えてくださいな)

仮説:ライトノベルの主人公風なツイートを適当に繋げるだけでブログ記事っぽくなるか?検証

 これを実践してみたもの。実はツイートが殆ど間に合わなかったので、

  • 思ったことを全て片っ端からevernoteにメモる
  • あとでメモから文章を復元する
  • それを全部繋げてラノベ風にブログに載せる

というルールです。黒歴史です。

続きを読む