狠狠撸

狠狠撸Share a Scribd company logo

Introduction to programming competition [revised][PDF]

?
?
Y
yak1ex

Presented at Open Source Conference 2011 Nagoya on 2011/8/20. (revised)

1 of 22
Download to read offline
はじめての竞技プログラミング OSC名古屋2011 8/20（土） @yak_ex / 新 康孝 (CSNagoya) @rofi
発表の流れ ?前半(45分)：競技プログラミング/サイトの紹介 (@yak_ex) ?競技プログラミングとは ?競技プログラミングサイト紹介（含む実演） ?後半(45分)：問題/アルゴリズム解説＋α (@rofi) ?基本的なデータ構造 ?実際の問題に合わせてアルゴリズム解説 ?競技プログラミングから見たC++0x (@yak_ex)
自己紹介 ? 氏名： 新 康孝 (あたらし やすたか) ? Twitter ID: yak_ex ? Web: http://yak3.myhome.cx:8080/junks ? C++ / Perl が主戦場 ? 仕事でコードに触れていないので 競技プログラミングで潤い補充 TopCoder 1577 / Codeforces 1762 ? 学生時代にACM/ICPC出場、1年くらい前に 競技プログラミングに復帰
オープンソースと競技プログラミング ? オープンソース ?世界中の開発者のコードが見られる ?世界中に潜在的利用者が居る ? 競技プログラミング ?世界中の参加者のコードが見られる ?世界中の参加者と腕を競える ? もっと被って良さそげなのにいまいちオープンソース 界と競技プログラミング界があまり被ってなさそげ → 布教
競技プログラミングとは ?制限された時間内に与えられた問題を解くた めのプログラムを作成、その速さと正確性を 競う知的スポーツ ?「プログラミングコンテスト」で思い浮かべる テーマに合わせたソフトを応募、審査する コンクール形式とは違って機械的に勝ち負け を判定可能
問題の例 ? ある東西に伸びたものすごく長い道路にホットドッグ 屋がたくさんいます。各ホットドッグ屋は東西1 m/s で移動できます。初期状態が与えられている時に、 どのホットドッグ屋間も最低D m離れている状態に なるまで最低何秒かかるでしょうか？ (Google Code Jam 2011 Round1B 抄訳) 1m/s 最低何秒かかるか？ Dm
問題の例 入力例 出力例 2 ←テストケース数 T Case #1: 1.0 32 ←位置の数C 距離D 01 ←位置P ホットドッグ屋数V Case #2: 2.5 32 C回 T回 1 ≤ T ≤ 50 繰り返し 61 繰り返し -10 5≦P≦10 5 ：整数 解答例 22 V：正の整数 03 1≦D≦106 ： 整数 11 1≦C≦200 ： 整数 ←問題文に ホットドッグ屋数≦10 6 ある条件 1m/s 最低何秒かかるか？ Dm
なぜ競技プログラミング？ ? 白黒はっきりするので目標にしやすい ?コード自体は複雑にならないので、入門書を終えて次に何 やっていいか分からない人に最適？ ? 計算量（時間／空間）の感覚が身につく ? デバッグ力があがる ? 他人のソースコードを読む力が付く ? テストケースを考えられる（コーナーケースが考えら れるようになる） ?何より楽しい
主な競技プログラミング大会 / サイト ? TopCoder ○ ? Codeforces ○ ? Google Code Jam ○ ? AOJ（会津大学オンラインジャッジ） ? ACM/ICPC（ACM国際大学対抗プログラミングコン テスト） ○が付いているサイトについて（練習モードで）実演
TopCoder ? http://community.topcoder.com/tc ? 競技プログラミングと言えばまずはここ ? コンテストは複数種開催されているが競技プログラミングとしては SRM(Short Round Match) が基本。月3回程度。 ? レーティング有り。Div1 (1200以上) / Div2 に分かれていて問題が違う 形式 ?３問 95分 / 問題によって最大得点が異なる ?典型的には 250, 500, 1000 ?時間に応じて得られる得点が減少していく ?Coding 75分→休憩 5分→Challenge 15分 ?2秒、64MB制限 ?正誤判定（システムテスト）は競技時間終了後 システム Java 使用による独自UI 使用可能言語 C/C++, C#, Java, VB 参加者数 アクティブ：8,600人 1SRM 2,000人強制限
Codeforces ? http://www.codeforces.com/ ? 比較的最近できたロシアの競技プログラミングサイト。月4回くらい。 ? 以前はよく落ちたりしていたが最近はシステムは安定している ? 英語が読みにくいと言われることが多い ? Gmail、OpenID でログイン可能 ? レーティング有り。Div1 (1650以上) / Div2 があるが一括開催だったり片方 のみ開催だったり色々 形式 ?5問 120分 / 最大得点が異なり時間に応じて減少 ?Challenge に相当する Hack が可能だが時間枠が 分かれていない ?実行時間、メモリ制約は問題毎に明示 ?正誤判定（システムテスト）は競技時間終了後 システム Web (Web2.0 による競技 PG サイトを標榜) 使用可能言語 Pascal, C, C++, C++0x, C#, Java, PHP, Python, Ruby, Haskell 参加者数 7,900人 1Round 1,500人強
Google Code Jam ? http://code.google.com/codejam/ ? Google が開催している年に1度のお祭り ? 決勝はオンサイトでやる 形式 ? 勝ち抜き制 予選＋4回くらい？予選は 24 時間 ? 各問題に対し、データ量等が少ない small input と 多い large input がある ? 提出に時間制限あり（small 4分 / large 8分） ? 問題、small or large で得点が異なる ? small input は即結果判定有りで、時間中に複数回提出可能 ? large input は一発勝負で結果は競技時間終了後判明 ? 得点と、正答累積時間＋4分×（正答迄の）誤答数で順位付け システム Web （ローカルで実行した結果を提出） 使用可能言語 自由 参加者数 13,000人(2011予選提出者)
AOJ(会津大学オンラインジャッジ) ? http://judge.u-aizu.ac.jp/onlinejudge/ ? 日本にあるオンラインジャッジ ?オンラインジャッジ： 用意された過去問等に対してソースを送信すると自動 で正誤を判定してくれるサイト ? 黙々と練習するのに良い システム Web 使用可能言語 C, C++, Java 参加者数 3,700人
ACM/ICPC (ACM国際大学対抗プログラミングコンテスト) ? http://cm.baylor.edu/welcome.icpc ? http://icpc2011.ait.kyushu-u.ac.jp/ja/home ? ACM(アメリカ計算機学会)主催のプログラミングコンテスト ? 大学生対象 ? チーム制で1チーム3人、1PC共用 ? 基本オンサイト 形式 ?国内予選→アジア予選→決勝 ?4,5時間7～10問程度 ?正答数と、正答累積時間＋20分×(正答迄の)誤答数で 順位付け ?電子的な事前準備禁止 システム 国内予選は Web 使用可能言語 C, C++, Java 参加者数 88カ国、2,070大学、8,305チーム(2010)
実演 ?TopCoder ?アカウント登録 ?SRM登録 ?SRM(今回はPractice) ?Codeforces ?Round登録 ?Round(今回はPractice) ?Google Code Jam ?Practice
TopCoder 実演 ? アカウント登録 ? http://community.topcoder.com/tc ? Register Now→on TopCoder→頑張って入力→メール受信→URL ref. http://mainly-coding.blogspot.com/2010/02/topcoder.html ? SRM登録(SRM開始3時間前から) ? (Java実行環境インストール) ? http://community.topcoder.com/tc ? Competitions→Algorithm→Single Round Matches (SRM)→Launch Arena ? Active Contests→どれか→Register ? SRM ? Launch Arena まで↑と一緒 ? 実際には Active Contests → Enter ? Practice は Practice Rooms→SRMs→どれか ? Challenge は Summary からダブルクリック ? Practice での System Test は Practice Options → Run System Test
Codeforces 実演 ? 設定 ? http://www.codeforces.com/contests ? 右上の Enter からログイン ? Settings → Social の Country に入れておくと国別ランキングに集計 ? ※CF / TC日本参加者比較表 http://yak2.myhome.cx/misc/cfjp.html ? Round登録(Round開始24時間前から) ? ログインまで↑と同じ ? Register ? Round ? ログインまで↑と同じ ? Enter (実際には時間になると勝手に Enter 伺いが出る) ? Practice は 適当な Round の Enter → Register for Practice ? Hack は Room からセルをダブルクリック(Practice 不可) ? Hack するためには Lock が必要 ? Hack されても Lock していなければ再提出が可能
Codeforces の問題状態遷移 システムテスト通過 初期状態 提出成功 ロック Passed 提出失敗 Locked System Test System Test 再提出 Pretest 成功 Passed Pretest ハックされる Failed システムテスト通過 再提出成功 の ならず 壁 ハックされる After lock Failed hacked System Test Hacked
Google Code Jam 実演 ?事前登録 ?http://code.google.com/codejam/ ?実際には Practice のところで登録が必要 ?Practice ?Input ファイルをダウンロードして実行、出力を提出 ?CUI ツールもできたが未使用なので説明できない ?実際には時間制限あり ?Short input はリトライ可能、Large input はリトライ不可
书籍?コミュニティ
用語集 用語 原語 意味 Red Coder レーティングが赤い人。殿上人。 Editorial 出題者による問題の解説 AC ACcepted 正解 WA Wrong Answer 誤答 RE Runtime Error 実行時エラー PE Presentation Error 出力形式エラー TLE Time Limit Exceeded 実行時間超過 MLE Memory Limit Exceeded メモリ制限超過 GL & HF Good Luck & Have Fun チャット等で良くある挨拶 DFS Depth-first search 深さ優先探索 BFS Breadth-first search 幅優先探索 DP Dynamic Programming チャット等で良くある挨拶(‘11/8/20-) 動的計画法
ご清聴ありがとうございました。

More Related Content

Introduction to programming competition [revised][PDF]

  • 1. はじめての竞技プログラミング OSC名古屋2011 8/20（土） @yak_ex / 新 康孝 (CSNagoya) @rofi
  • 2. 発表の流れ ?前半(45分)：競技プログラミング/サイトの紹介 (@yak_ex) ?競技プログラミングとは ?競技プログラミングサイト紹介（含む実演） ?後半(45分)：問題/アルゴリズム解説＋α (@rofi) ?基本的なデータ構造 ?実際の問題に合わせてアルゴリズム解説 ?競技プログラミングから見たC++0x (@yak_ex)
  • 3. 自己紹介 ? 氏名： 新 康孝 (あたらし やすたか) ? Twitter ID: yak_ex ? Web: http://yak3.myhome.cx:8080/junks ? C++ / Perl が主戦場 ? 仕事でコードに触れていないので 競技プログラミングで潤い補充 TopCoder 1577 / Codeforces 1762 ? 学生時代にACM/ICPC出場、1年くらい前に 競技プログラミングに復帰
  • 4. オープンソースと競技プログラミング ? オープンソース ?世界中の開発者のコードが見られる ?世界中に潜在的利用者が居る ? 競技プログラミング ?世界中の参加者のコードが見られる ?世界中の参加者と腕を競える ? もっと被って良さそげなのにいまいちオープンソース 界と競技プログラミング界があまり被ってなさそげ → 布教
  • 6. 問題の例 ? ある東西に伸びたものすごく長い道路にホットドッグ 屋がたくさんいます。各ホットドッグ屋は東西1 m/s で移動できます。初期状態が与えられている時に、 どのホットドッグ屋間も最低D m離れている状態に なるまで最低何秒かかるでしょうか？ (Google Code Jam 2011 Round1B 抄訳) 1m/s 最低何秒かかるか？ Dm
  • 7. 問題の例 入力例 出力例 2 ←テストケース数 T Case #1: 1.0 32 ←位置の数C 距離D 01 ←位置P ホットドッグ屋数V Case #2: 2.5 32 C回 T回 1 ≤ T ≤ 50 繰り返し 61 繰り返し -10 5≦P≦10 5 ：整数 解答例 22 V：正の整数 03 1≦D≦106 ： 整数 11 1≦C≦200 ： 整数 ←問題文に ホットドッグ屋数≦10 6 ある条件 1m/s 最低何秒かかるか？ Dm
  • 8. なぜ競技プログラミング？ ? 白黒はっきりするので目標にしやすい ?コード自体は複雑にならないので、入門書を終えて次に何 やっていいか分からない人に最適？ ? 計算量（時間／空間）の感覚が身につく ? デバッグ力があがる ? 他人のソースコードを読む力が付く ? テストケースを考えられる（コーナーケースが考えら れるようになる） ?何より楽しい
  • 9. 主な競技プログラミング大会 / サイト ? TopCoder ○ ? Codeforces ○ ? Google Code Jam ○ ? AOJ（会津大学オンラインジャッジ） ? ACM/ICPC（ACM国際大学対抗プログラミングコン テスト） ○が付いているサイトについて（練習モードで）実演
  • 10. TopCoder ? http://community.topcoder.com/tc ? 競技プログラミングと言えばまずはここ ? コンテストは複数種開催されているが競技プログラミングとしては SRM(Short Round Match) が基本。月3回程度。 ? レーティング有り。Div1 (1200以上) / Div2 に分かれていて問題が違う 形式 ?３問 95分 / 問題によって最大得点が異なる ?典型的には 250, 500, 1000 ?時間に応じて得られる得点が減少していく ?Coding 75分→休憩 5分→Challenge 15分 ?2秒、64MB制限 ?正誤判定（システムテスト）は競技時間終了後 システム Java 使用による独自UI 使用可能言語 C/C++, C#, Java, VB 参加者数 アクティブ：8,600人 1SRM 2,000人強制限
  • 11. Codeforces ? http://www.codeforces.com/ ? 比較的最近できたロシアの競技プログラミングサイト。月4回くらい。 ? 以前はよく落ちたりしていたが最近はシステムは安定している ? 英語が読みにくいと言われることが多い ? Gmail、OpenID でログイン可能 ? レーティング有り。Div1 (1650以上) / Div2 があるが一括開催だったり片方 のみ開催だったり色々 形式 ?5問 120分 / 最大得点が異なり時間に応じて減少 ?Challenge に相当する Hack が可能だが時間枠が 分かれていない ?実行時間、メモリ制約は問題毎に明示 ?正誤判定（システムテスト）は競技時間終了後 システム Web (Web2.0 による競技 PG サイトを標榜) 使用可能言語 Pascal, C, C++, C++0x, C#, Java, PHP, Python, Ruby, Haskell 参加者数 7,900人 1Round 1,500人強
  • 12. Google Code Jam ? http://code.google.com/codejam/ ? Google が開催している年に1度のお祭り ? 決勝はオンサイトでやる 形式 ? 勝ち抜き制 予選＋4回くらい？予選は 24 時間 ? 各問題に対し、データ量等が少ない small input と 多い large input がある ? 提出に時間制限あり（small 4分 / large 8分） ? 問題、small or large で得点が異なる ? small input は即結果判定有りで、時間中に複数回提出可能 ? large input は一発勝負で結果は競技時間終了後判明 ? 得点と、正答累積時間＋4分×（正答迄の）誤答数で順位付け システム Web （ローカルで実行した結果を提出） 使用可能言語 自由 参加者数 13,000人(2011予選提出者)
  • 13. AOJ(会津大学オンラインジャッジ) ? http://judge.u-aizu.ac.jp/onlinejudge/ ? 日本にあるオンラインジャッジ ?オンラインジャッジ： 用意された過去問等に対してソースを送信すると自動 で正誤を判定してくれるサイト ? 黙々と練習するのに良い システム Web 使用可能言語 C, C++, Java 参加者数 3,700人
  • 14. ACM/ICPC (ACM国際大学対抗プログラミングコンテスト) ? http://cm.baylor.edu/welcome.icpc ? http://icpc2011.ait.kyushu-u.ac.jp/ja/home ? ACM(アメリカ計算機学会)主催のプログラミングコンテスト ? 大学生対象 ? チーム制で1チーム3人、1PC共用 ? 基本オンサイト 形式 ?国内予選→アジア予選→決勝 ?4,5時間7～10問程度 ?正答数と、正答累積時間＋20分×(正答迄の)誤答数で 順位付け ?電子的な事前準備禁止 システム 国内予選は Web 使用可能言語 C, C++, Java 参加者数 88カ国、2,070大学、8,305チーム(2010)
  • 15. 実演 ?TopCoder ?アカウント登録 ?SRM登録 ?SRM(今回はPractice) ?Codeforces ?Round登録 ?Round(今回はPractice) ?Google Code Jam ?Practice
  • 16. TopCoder 実演 ? アカウント登録 ? http://community.topcoder.com/tc ? Register Now→on TopCoder→頑張って入力→メール受信→URL ref. http://mainly-coding.blogspot.com/2010/02/topcoder.html ? SRM登録(SRM開始3時間前から) ? (Java実行環境インストール) ? http://community.topcoder.com/tc ? Competitions→Algorithm→Single Round Matches (SRM)→Launch Arena ? Active Contests→どれか→Register ? SRM ? Launch Arena まで↑と一緒 ? 実際には Active Contests → Enter ? Practice は Practice Rooms→SRMs→どれか ? Challenge は Summary からダブルクリック ? Practice での System Test は Practice Options → Run System Test
  • 17. Codeforces 実演 ? 設定 ? http://www.codeforces.com/contests ? 右上の Enter からログイン ? Settings → Social の Country に入れておくと国別ランキングに集計 ? ※CF / TC日本参加者比較表 http://yak2.myhome.cx/misc/cfjp.html ? Round登録(Round開始24時間前から) ? ログインまで↑と同じ ? Register ? Round ? ログインまで↑と同じ ? Enter (実際には時間になると勝手に Enter 伺いが出る) ? Practice は 適当な Round の Enter → Register for Practice ? Hack は Room からセルをダブルクリック(Practice 不可) ? Hack するためには Lock が必要 ? Hack されても Lock していなければ再提出が可能
  • 18. Codeforces の問題状態遷移 システムテスト通過 初期状態 提出成功 ロック Passed 提出失敗 Locked System Test System Test 再提出 Pretest 成功 Passed Pretest ハックされる Failed システムテスト通過 再提出成功 の ならず 壁 ハックされる After lock Failed hacked System Test Hacked
  • 19. Google Code Jam 実演 ?事前登録 ?http://code.google.com/codejam/ ?実際には Practice のところで登録が必要 ?Practice ?Input ファイルをダウンロードして実行、出力を提出 ?CUI ツールもできたが未使用なので説明できない ?実際には時間制限あり ?Short input はリトライ可能、Large input はリトライ不可
  • 21. 用語集 用語 原語 意味 Red Coder レーティングが赤い人。殿上人。 Editorial 出題者による問題の解説 AC ACcepted 正解 WA Wrong Answer 誤答 RE Runtime Error 実行時エラー PE Presentation Error 出力形式エラー TLE Time Limit Exceeded 実行時間超過 MLE Memory Limit Exceeded メモリ制限超過 GL & HF Good Luck & Have Fun チャット等で良くある挨拶 DFS Depth-first search 深さ優先探索 BFS Breadth-first search 幅優先探索 DP Dynamic Programming チャット等で良くある挨拶(‘11/8/20-) 動的計画法