こんにちは、エンジニアの澤です。

10/22に開催されたKLabの社内勉強会ALM(All Layer Meeting)にて、「天下一プログラマーコンテストの裏舞台」についての発表を行いました。

天下一プログラマーコンテストとは?

KLabがAtCoder社と協力して開催しているガチンコの競技プログラミングコンテストです。今年は、8月から予選が始まり9月14日に決勝が行われました。

天下一プログラマーコンテスト2013

それでは、ALMで発表した内容についてご紹介します。


天下一プログラマーコンテストの舞台裏(運営編)

発表者: 2013新卒 ___Johniel

そもそも、競技プログラミングって何?

  • 問題に対する速さや正確さを競う。本コンテスト以外にも、ARC、ACM/ICPC、TopCoder SRMなどが有名。

運営の主なお仕事

  • 原案制作、解答制作、問題文制作、入出力データ制作、本番対応など。
  • 問題原案は、タイトルから、ストーリーから、解法から考える方法がある。
  • 本番対応が、運営のお仕事のおもしろいところ。予選、本戦中に参加者からの質問や、アクシデントに対して対応する。

天下一プログラマーコンテストの舞台裏(問題編)

発表者:2013新卒 澤

天下一プログラマーコンテスト2013決勝で出題された問題を題材に、プログラミングコンテストの基本的な問題の解法について解説を行いました。

「全探索」について

  • 安易だけど、さまざまな場面で使える。

「動的計画法」について

  • サイズの小さい問題の答えを使って、順々に大きい問題を解いていく手法。
  • 全探索できない問題を短い計算時間でとけることがある。
  • コンテストでも、コンテスト以外のプログラミングでも頻出。

解答にたどり着くための考え方について

  • 問題のサイズが小さければ、全パターン試せば良い。
  • 問題のサイズが大きい場合、数字が小さい場合の問題を考えると、その答えや、解き方がヒントになる。

若手エンジニアブログでは、引き続きALMのレポートをしていきます。お楽しみに!