etc...このブログは簡単な英語と、日本語とで書かれています。(現在、日本語のみで記事を書いています)日本語で読める方は日本語での閲覧をおすすめします。達哉んが競技プログラミングについて活動したことを記すブログです。23:30タイトルの通り、C言語テキスト&問題集を執筆しました!2012年9月25日に理論編(C言語テキスト)を、2016年2月9日に実習編(C言語問題集)を執筆完了しました。Calendarに記事を書くのは3年ぶりで、他の皆様の記事を見ているとその間に競プロを始められたという方もいて、気鋭の若手の活躍が身に染みます。競技プログラミングという言葉もまだなかったような10年少々前=私が始めたころと現在とで、競プロ事情を見比べてみれば、10年一昔とは実によく言ったもので、まったく風景が異なっています。何より、コンテストそのものがずいぶん増えました。Calendarには「競プロのコンテストを開いている企業に就職を!」という記事もありますが、それが言える時代になったことはすばらしいことだと思っています。その記事を書かれたchokudai氏をはじめ、同時期に楽しんでいた方々で今もこの世界にいる人たちは、努力を惜しまず今や競プロ界を牽引する存在となっています。それに比べれば私などは、別に特別な努力をしているわけでもなく、ただ楽しむだけです。そんな身だから書けるものを、ここではお話したいと思います。良い世の中になりました競プロの世界のレベルは確実に上がっており、サイトの数も増え、伴って開かれるコンテストの数も多くなっています。競プロを元に就職していく人も少なくなく、知己がそのような進路を採るのを見るにつけ聞くにつけ、随分この世界も広まったものだと思います。国内でこのように世界を広めた、私と同年代の方々には感謝と尊敬の念を持っています。未来ある若人たちがコンテストやサイトを"選べる"声を聞くと、"選べる"ぐらいまで恵まれた時代になったのだと痛感します。牽引する方々は大抵の場合強くて、実力によりオンサイトなどにも出場されています。学生さんなどは、青田買いになるからと企業がオンサイトに招待することも多いものです。一方で私はそこまでの実力はありませんし、就職して今年で9年目、学生でさえないですから企業開催コンテストのオンサイトからお声がかかることはありません。結果として、参加できるオンサイトはごく僅か、自分で申し込んで集まるようなオンサイトのみです。前に就職して、今の仕事に満足はしているけれども、競プロ趣味という観点ではほとんど後悔しかないような状況で年を無駄に重ねてきています。就職すると時間の縛りも大きくなり、参加できるコンテストの数や演習に掛けられる時間も学生さんよりは少ないのが実情です(少なくとも周囲の人を見る限りはそう見えます)。競プロをスポーツのリーグ等と比較して...実力がある人や、未来ある若人たちが、さまざまなオンサイトに招待されるのは当然です。それは、スポーツのプロの世界の話と同じようなものだと思っています。実力のある人が招待される。実力の付く人が招待される。Cupなどはワールドカップやオリンピック(IOIという意味にあらず)といった位置づけといえるでしょう。JOI本選やICPCアジア予選、あるいは国内の各種オンサイトは、国内のプロリーグの試合とたとえて差し支えないでしょう。学生さんのみが参加できるコンテストは、そのまま学生の選手権などの位置づけだといえます。各種のオンラインの誰でも参加できるコンテストは、無差別級の運動会のようなものでしょう。このように、スポーツの各種の試合と、競プロのコンテストを対応させて見たとき、少しさびしく感じるところがあります。それは、「学生でないアマチュアのためのオンサイトコンテストがない」ということです。スポーツの場合、社会人のアマチュアが集まって、参加者間で費用を出し合って競技を楽しんでいます(スポーツに限らず演劇や音楽などでもそうですが)。競プロの世界では、社会人のアマチュアが集まってのオンサイトは見当たりません。競プロ好きでも青田買いされるまでの実力に至らない学生さんも、同じような状況ではないでしょうか。私が"何か行いたい"と思ったのはここです。エンジョイ勢の人たちにも集まってもらって絆を深めつつ、より競プロを楽しんでもらえるように、何かイベントをしていきたい。この一年の、それらのイベントの報告をし、願わくばより多くの人に何かお力をいただければと思います。本編です私が今年一年で企画する段階から携わった大きなイベントは、3つほどあります。どれも一人では厳しい年になりましたので、何人も巻き込ませていただきました。この場を借りて厚く御礼を申し上げます。2校が近畿からWFに出られたということでこの2校を招いてのお疲れ様会を行いました。周辺の若い方が来るかと予想しましたが、それよりはどちらかというと年齢層が上の方が来られてのお祝いという感じになりました。中には東京から駆けつけてくださった方も...。全部で10名少々と、東京の会からすれば小さく、オフ会という感じでしたが、非常に豪華なメンバーの会でもありました。応援したいという気持ちの方は少なからずいるので活かすような会をうまく続けていきたいものです。いったお食事会的なイベントは、多くの人数が集まらなくても(店の都合さえ問題なければ)従量(人数)課金的な費用発生となるため、開催しやすいと思います。オフ会レベルのものをちょくちょく開いて、絆を深めていければいいな、なんて思ったりしています。・CP3翻訳企画おそらく今年やった企画の中で、(競プロ以外も含めて)最大規模の企画です。当初、幾人か懇意にしている人と「やってみたいね」という話をしていて、有言実行ということで、きちんと計画を整備して始めたものです。皐月に募集を始めたところ、あっという間に40名を越す参加があり、場所を選ばぬイベントは参加者が集まるものだと感嘆しました。私が統括ということで、なかなか段取りのうまくいかぬこともあり、40名という大人数で連絡が行き届かったなかったのもあってか、スロースタートとなりました。年内に無事最初の章を訳し終え、今は原著者に連絡をしているところです(原著者から「1章訳し終えたらTeXとか図あげるよ」と言われたもので)。ここからは実際の作業でどんどん進んでいくところに入りますから、おそるおそる踏み出したその一歩は確実な一歩だったと考えています。大掛かりな(泊まりの)決起会も行い、こちらも10名近くの参加となりました。いうところでできる絆というのは、企画にせよ何にせよ、駆動する大きな力の素となるものでしょう。成果を挙げることも勿論ですが、競プロ界内での交流を深め、絆を紡ぐことも大切にしていきたいと思います。CP3にも、ICPC向けにこんなTipsが載っています:練習やコンテストに限らず、チームメイトと仲良くあること。この企画の募集は締めておりますが、是非参加したいという方は応相談で対応します。・JOI非公式オンサイトかなり旬の話題で、一昨日、JOI予選に合わせて非公式オンサイトを開きました。ARC001が開かれたぐらいの時代だったか、何社かが会場を提供して、宵のうちのコンテストの非公式オンサイトをやっており、これに着想を得て企画したものです。先に書いた、「誰でも参加できる(が、費用が発生するのは許してください)オンサイト」として開催したものです。時節柄もあり、忘年会も付けました。近畿は人が少ないため、東京での別の非公式オンサイトほどは集まりませんでしたが、それでも10名少々の参加がありました。当日私はコンテストに参加せず、雑務担当としておりましたが、特に大過なく、皆さん笑って終わることが出来たのは成功の証だったと考えています。ないのでお金の負担が少なくない」「そもそも近畿だと東京と違いなかなか集まる人が少ない」などの問題も見えました。スポーツでもアマチュアチームの運営で、世話役が必要・お金の負担はよく考える必要がある・人数少ない時もあるという問題が時に見られますが、全く同種の問題と感じました。需要がないわけではないですし、続けていきたいものではありますが、継続のためには「運営側が息切れしない」工夫が必要になると考えています。最後に...こうあれば良いな、という願い競プロの世界は、どんどん発展して行っており、勿論その発展を大きく願っています。その中で、これらのイベントの活動を通じて、あるいはその元となった考えを通じて、私が競プロの世界に「こうあればもっと良いな」と思った3つの願いを記して、この記事の筆を置きたいと思います。ここで書いたとおり、"アマチュアのオンサイトコンテスト"は数が少ないです。各種のコンテストも実力で勝つ層だけでなく、"抽選枠"なり"自費参加枠"なりを設けてもらえると、もっと多くの人の交流が図れて嬉しく思いますが、難しいでしょうか。PCKの地域枠や、EPOCHの「他のコンテストで実績残した人は参加不可」はその例だと思うのですが...。企業の都合などもあり、競プロ愛好家は東京一極集中になっている傾向があります。東京以外のイベントは開くのが大変です。人が増えてくると楽になるでしょうか。先に書いたとおり、東京以外の開催は参加者数が少なくてつらいものがあります。無理は言えませんが、東京以外で競プロを愛好している方は、盛り上げるためにも、どんどん参加してもらいたいなと思います。イベントにはいろいろな役割がありますが、参加者という役割は必ず必要になるものですから、その役を果たす方がもっと増えてほしいと思います。色々なイベントが企画されていると聞いてもいますから、ぜひ、多く参加いただきたいものです。サンタさんからのプレゼントでもらえるようなものではありませんが、こうできれば、もっと嬉しい人が増えるんだろうな、って思った次第です。あとは、イベントをこれだけ開くと、ノウハウもできてきます。イベントを開こうと考えている方、ノウハウの共有も兼ねて、ぜひお声がけいただければと思います。2016、明日はryo33さんの「ジャッジサーバのフレームワークを作る話」とtorus711さんの「競技プログラミングを始めて人生が変わった話」みたいなポエム(?)が予定されています。ジャッジサーバのフレームワークの方は、競プロの運営の側としての面白いお話が聞けるのかもしれません。競技プログラミングを始めて人生が...というのは競プロ愛好家の皆様大なり小なりそうなのでしょうが、どのように変わったか興味深いですね。11:02プログラミングコンテストの、非公式オンサイトをやるかと考えています。6月24日までで、以下の内容のアンケートをとっていますので(Twitter)、興味のある方は投票ください。2016年6月17日それなりに集まっているので、興味深いです。23:37競技プログラミングの本といえば、邦書では「プログラミングコンテストチャレンジブック」「最強催促アルゴリズマー養成講座」「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」などが有名です。近年、このジャンルの書籍の出版はめざましく、私が競技にはじめて参加した2005年からすると今昔の感を禁じえません。10年一昔を地で行っているお話と思います。3は内容も充実しており、非常に良い本であると思います。3"翻訳企画をこの度立ち上げました!翻訳して、出版あるいは公開にこぎつけられれば、と思っています。この本の活動を通じて、日本の競技プログラミングに良い影響を与えると共に、その成果物が日本の競技プログラミングのさらなる飛躍に寄与するものになるように、とも願います。9:27久々に時間の都合がついたので参加。他の大会も含め、参加できる回数は減ってきていますが、それでも参加できるときは参加したい。A:くっつける靴を全探索するなどしても間に合いますが、靴のサイズが10以上40以下なので、左側の各サイズの個数を数えておき、右側で出てきた分だけ数えるというのが組みやすく早いでしょうか。B:シミュレーションでは間に合わないようだったので、とりあえず実験。基本的に変化するのは"同じ色のT本の木が連続している区間"で、これが$\lfloor\frac{T-1}{2}\rfloor$回後に「もう変化しない」状況になります。そこで、Tのうち、最大値を求めればOK、ということになります。最初から全ての木が同じ色の場合は無限に変化を続けてしまいます。いう事で組んでみたところ入出力例と少しずれる。「○回後」ではなく「○回目」という事だったらしいので、回数をずらして出力しました。C:時間内に組んだソースは、つまらないミスをしていて部分点しか取れませんでしたが、終わってから少々検討して直したところ普通に満点が取れました。問題文はちょっと要旨がつかみにくいので、整理すると「$N$文字の文字列$S$に対し、第$t$文字目から始まる連続$K$文字の部分文字列を$S_t$とする。K$)に対し、$S_i$と$S_j$が同じ文字からなる(順番は異なっても良い)ことはあり得るか判定せよ。過去の情報オリンピックで「マヤ語文献の読解」として似た問題が出ています。尺取り法で各部分列に対し、文字の頻度分析を行います。これによって、全ての部分文字列の頻度分析が$O(N)$で行われます。N)$程度でソートし、無駄が無いように比較すれば(ここで失敗していました)満点になります。以下の解答例はコンテスト後修正してACを取ったものです。oo△-,57位,245点でした。Div2013のDay.19thの投稿記事です。〜初心者への道標として〜」をその一部に含みます。Contestが開催され始めた2013年。競技プログラミングの世界は、リクルート分野での注目もあり、なお一層門戸を広げ始めています。この流れに乗る人に向けて、その最初の数歩の道標を示したい。そんな記事にしたい、と思います。Div2012の12月3日の記事です。昨年はつまらない記事でトリを務めることとなり恥を晒しましたが、今年はつまらないだけにとどまらず、おカタい記事で恥を晒すことにいたします。Div2013のDay.19thの投稿記事です。〜初心者への道標として〜」をその一部に含みます。「プログラミングコンテストチャレンジブック」や「世界で闘うプログラミング力を鍛える150問」の秋葉先生の記事が載っていました。Topcoder部のカレンダーは登録している人が自由に更新できます。日本国内予選(演習)参加資格はないのですが、ACM-ICPC2011日本国内予選の問題を時間を測って解いてみました。Aは似たような問題を昔自作して解いたことがあるので、あまり苦労しませんでした。その当時(数年前)は1個1個判定していましたが、今回はエラトステネスの篩で素数表...ARC#015とABC#001に思うことARC#015のB,Cと、ABC#001の全問の出題を担当していました。遅ればせながら、出題意図などを紹介します。解説はchokudaiさんが良いものを作ってくれているので、そちらをご覧ください。2011に参加しました。問題を俯瞰した後、Cから解き始めました。Jamの時にビット演算を利用する問題でミスりましたので、そのリベンジです。提出したのは、Small=44:59,Large=45...プログラミングコンテストの非公式オンサイトを検討していますプログラミングコンテストの、非公式オンサイトをやるかと考えています。6月24日までで、以下の内容のアンケートをとっていますので(Twitter)、興味のある方は投票ください。