世界チャンピオン-スポーツプログラミングについて

DataArtは長年にわたりITMOスポーツプログラミングチームとの友好関係を築き、支援しています。 この夏、イリヤ・ズバン、イワン・ベロノゴフ、ウラジミール・スミカロフがサンクトペテルブルクの開発センターを訪れました。 2017年の世界チャンピオンは、プログラマーが互いにどのように競争するか、トレーニングキャンプ、お気に入りのタスク、最強のライバルについて話しました。

プログラミングオリンピック

プログラマーの主な競争-ACM（ACM-ICPC、または単にICPC）の後援の下での留学生オリンピックは、1970年代から開催され、1989年に今日に近い形で成立しました。 オリンピアードは、まれな例外を除いて、学生と大学院生を対象としています。24歳以上のプログラマーは競争できません。 さらに、最終テストでは2回しか自分の強さをテストできず、地域選択には5回しか参加できません。 数千のチームが世界中の初期段階で競争しています。 約100人がファイナルに到達します。

基本的なルール

チームは3人で構成されますが、各チームが自由に使用できるのは1台のコンピューターのみです。 コンテストの開始前に、5〜8時間で解決する必要がある8〜13個のアルゴリズム的または数学的な問題のある封筒が全員に配布されます。 この問題の解決策は、テキスト要求を読み取り、テキスト応答を生成するプログラムです。 テストするために、ソリューションは事前にju審員によって準備された約100のテストで実行されます。各テストで答えが正しい場合にのみ、真であると認識されます。



ICPCのルールは、ウラルプログラミングチャンピオンシップ用に公開されたビデオに非常に明確に記載されています。これは、オリンピックの主要な選択段階の1つです。 これらはすべての地域で同じであり、2013年以降は変更されていません。

言語と環境

2017年の最後には、Java、C ++、Pythonの言語を使用できます。 ただし、Pythonが原則として非常に高速ではないことは明らかです。審査員は、タスクを引き渡すことができることを保証しませんでした。 ただし、これらの言語で書かれたソリューションがすべてのテストに合格することは保証されていました。



異なる競技会では、言語のセットが異なる場合があります。 たとえば、約20の言語がCodeforcesオンラインプラットフォームで許可されています：C ++およびJavaからHaskellおよびPerlまで。



決勝戦のほとんどのチームは、速度が前面に出てくるため、C ++で記述します。 開発環境として、多くのチームがVIM（たとえば、IvanとIlyaが働いた）またはGina（Vladimirが働いた）を使用します。 まだJavaで書く人は、通常、Eclipseのような環境を使用します。これは、オートコンプリートなしでJavaで書くのがはるかに難しいからです。



決勝戦は現在JetBrainsがスポンサーとなっているため、近い将来変更が予想されます（2017年5月末までの20年間、IBMはICPCのスポンサーでした）。 これは、スポンサー製品も表示されることを意味します：IDEA for JavaおよびCLion for C ++。 おそらくこの後、チームはデバッガーを広く使用し始めますが、現時点では、より頻繁にデバッガーなしで使用できます。

タスクの進化

2000年代初頭には、ブルートフォースタスクにわずかな制限がありましたが、データ構造にはさらに多くのタスクがあります。 同時に、世界にはスポーツプログラミングのためのまったく別の学校がいくつかあります。ポーランドでは、イデオロギー、多くの場合、数学的なタスクが好きな場合、中国では、複雑な技術的なものを好みます。たとえば、組み合わせ論を検討するなど、多くのコードを書く必要があります



目標は常に、迅速に機能するソリューションを考え出し、実装することです。 たとえば、考えられるすべてのオプションを単純に実行するプログラムを作成することで、少なくとも何らかの形で問題を解決できます。 しかし、最近では、ブルートフォースの作成に関連するタスクはほとんど発生しません。



時間とメモリには制限がありますが、実際には、ソリューションが使用するメモリが多すぎるという問題はまれにしか発生しません。 各テストの制限時間は、タスクに応じて通常1〜3秒です。これも条件で示されます。

タスクの例

タスクは異なります。グラフ、線、ジオメトリなどです。地図上の都市間の最短経路を計算するとします。 または、島に可能な限り最長の滑走路を建設し、非凸多角形の形で提示します。 タスクはテキストを比較することです-文字列のペアの最大の共通部分文字列を見つけます。







もう1つの形式は、tasks審員によって書かれたシステムでゲームをプレイするための対話型タスクです。 準決勝の1つでは、tic-tac-toeで提案されたアルゴリズムを90％の時間で破ることができるプログラムを作成する必要がありました。 最後を含む過去の決勝からのタスクは、 ここで見ることができます 。

決定プロセス

基本的に、チームメンバーは、個人の好みに応じた条件でシートを整理します。誰かがライン上のタスクを好み、ジオメトリ上の誰かが好きです。 一般的に、ここでの個々の作業はチームに優先します。



まず、問題の1つを解決するためのアルゴリズムを考え出す必要があります。 ソリューションの作成者がチームと話し合い、ソリューションが数学的に正しいことを確認する場合があります。 その後、著者はコードを書くために座ります-現時点で他の2人の参加者は、他の問題の解決策について考え続けています。 コードが作成されると、通常は条件に添付されているテストケースでチェックし、評価のためにシステムに送信できます。 コンピューターの時間は限られているため（参加者はコンピューターを1台しか持っていないことを思い出してください）、プリンターは常に競技会に参加しています：ソリューションが機能しない場合、誰か（通常はその作者）がコードを紙に印刷してエラーを探しています。

コード機能

一方では、スポーツプログラミングに携わる人々は、ストレスの多い条件下で、迅速かつ明確にコードを書くことができます。 一方、彼らはこのコードがあいまいな変数を含んでおり、読みにくいという事実についてしばしば批判されます。 コンテストで書かれたコードには、長くて理解しやすい変数名は実際にはありません。結局、1年でサポートされる必要はありません。 ただし、高レベルでは、この問題はそれほど深刻ではありません。チームメイトにはコードがまだ明確である必要があるからです。



スポーツプログラミングのもう1つの特徴は、メモリシステムがテストシステムによって評価されないことです。このソリューションは数秒間しか機能しません。

アルゴリズム

私たちは非常に多くのアルゴリズムを知っており、セグメントのツリー、フェンウィックツリー、デカルトツリーなどの異なるデータ構造を使用します。時には、バランスのとれた検索ツリーを自分で記述し、問題の状態によって決定される情報を読み取るように並行して修正する必要があります。 たとえば、C ++には、多数の数値をサポートできる集合構造があり、たとえば次のようなものがあります。 ただし、タスクでは、次の数値ではなく、指定された数値以下のすべての数値の合計を見つける必要があります。 標準構造ではうまくいきません。



コードの断片を持ち込むことはできませんが、ワールドカップでは、いわゆるチームリファレンス、つまり紙に印刷されたアルゴリズムのセットを使用できます。 その場でたくさん書くことができますが、今年はそれを準備するのに多くの時間を費やしました-より複雑なアルゴリズムをテストしました。 しかし、結局、録音はまったく使用されませんでした。



コードの量は最終評点に直接影響しません。割り当てられた時間内に1000行を書くのが難しいこともまた別の問題です。 そして、美しい簡潔なソリューションを思いついたら、わずか10〜15分以内に保つことができます。 ソリューションの平均ボリュームはコードの100〜200行ですが、場合によっては300行に達することもあります。通常の生活では、300行はそれほど多くありませんが、ここでは5時間しかありません。すべての問題の解決策。 すばやく書く必要があり、300行間違えた場合、タスクは機能しません。つまり、それを解決するためのすべての時間が単に失われます。 さらに、コードが長いほど、印刷版でエラーを見つけるのが難しくなります。

その他のトーナメントとトレーニング

賞金は、トーナメント参加者の主な動機とはほど遠いものです。 写真：Ivan BelonogovとIlya Zban-VKカップ2015の優勝者（出典-Ivan Belonogovページ）。 2017年、VKカップの優勝者はITMOチャンピオンチームのウラジミールスミカロフの3人目のメンバーでした。



私たちは常に個々のトーナメントに参加しています-多くのトーナメントがあります。 たとえば、ロシアのコードフォースのウェブサイトでの競争は、定期的に数千人を引き付け、そのうちロシア人は通常約20％を占めています。 ここでの標準ツアーは、2時間で解決する必要がある5つのアルゴリズム問題で構成されています。 このリソースを中心に開発されたコミュニティで最も重要なことは、チェスのようにEloシステムに従って計算された個人評価です。 トーナメントで成功裏に話すと、プログラマーはポイントを獲得します-それらの一定数がニックネームの色を自動的に変更します。 赤いニックネームを持つ人々は、助けの要請だけでなく、雇用主からの申し出も受け取ります。 そして最も重要なことは、他のチャンピオンアスリートと同様に、彼らは普遍的に尊敬されています-多くの参加者にとって、「赤いニック」はそれ自体が戦うための十分な動機として機能します。





赤いニックよりも急勾配で、最初の黒い文字が付いた赤いニックのみ。 7月13日、Codeforceの上位20人には、ロシア人8人、ウクライナ人2人、ポーランド人、中国人、およびスイス、オーストラリア、韓国、米国、台湾、ベラルーシの代表者1人が含まれていました。 同時に、ベラルーシのプログラマーは現在、評価をリードしていますが、原則として、テーブル内の順列は絶えず発生しています。



主要なコンペティションは、 Mail.ru 、 Yandex 、 Facebook 、 Googleおよびその他の企業によって開催されます。 たとえば、現在のGoogle Code Jamトーナメントの第1ラウンドでは、2万人が参加しました。 数千の最高のブランドTシャツ、25-が今年のダブリンで開催される決勝戦に進みます。



Google Code Jamに加えて、Googleは別のトーナメント-Hash Codeを開催しました。HashCodeの最終は会社の本社で開催されました。 特に参加者には、可能な限り少ないルーターとワイヤを使用して、Wi-Fiポイントのネットワークで可能な限りカバーする必要があるフロアプランが与えられました 。 このような問題に対する最適な解決策はありませんが、もちろん、他の問題よりもうまく解決することは可能です。





Googleハッシュコードの主催者がルーターの配置を提案した建物の1つは、パリグランドオペラです。



別のタイプの競争はAIカップであり、そこでは主催者がライブラリの形で提供する元のプログラムと対戦できる人工知能プログラムを書く必要があります。 ゲームはトーナメント専用に作成されています。つまり、原則として手でプレイすることはできません。 しかし、スクリプトは、それらの戦略を書くことが興味深いように選択されます。





今年のゲームは最新のMOBAに似ていました。解決策は、5人のウィザードからなるチームを管理し、コードワードを使用してチームを交換することでした。



このような競技は、フランスのサイトCodinGameで常に開催されています。 また、AIトーナメントでは、最初の2〜20日間でトレーニングがまったく行われずに良い結果が得られたことは素晴らしいことです。 それでも、スポーツプログラミングの主なスキルは、座って考え、コードを書くことです。



Topcoderプラットフォームでは、マラソンが数週間続くことがあります。 Deadline24やChallenge24など、いくつかのトーナメントがあり、最終日は1日続きます。 それらは選択され、通常のアルゴリズムの問​​題を解決し、最終的にはゲームを制御するための戦略を作成する必要があります。 このトーナメントでは、最初の12時間はコードを記述し、休憩後にエラーを修正することが最も効果的であると思われました。



オンラインプラットフォームを使用すると、健康を維持できます。そうしないと、タスク解決スキルがすぐに失われます。 しかし、彼らはもちろん、トレーニングとしてだけでなく興味深いものです。 競争は常に意欲と感情であり、競争なしでは見逃せません。

トレーニング

最も重要な競技と同様に、ほとんどすべてのトレーニングは5時間続きます。 通常、過去のトーナメントの1つから問題を解決するだけです。 多くの新しいアルゴリズムを知っているため、実際には新しいアルゴリズムを学習しません。 結局、私たちに期待されるのは、複雑なデータ構造の知識ではなく、すぐに解決策を考え出す能力です。 したがって、特別な本は本当に助けにはなりません。 個々の記事を読んだり、インターネット上の特定のトピックに関する講義を聞いたりする方がはるかに効率的です。



年に数回、トレーニングキャンプが開催され、さまざまな国のチームが集まります。 特に、今年は強いポーランド人がペトロザヴォーツクに来て、中国とオーストラリアのプログラマーがドルゴプルドニのMIPTに来ました。 トレーニングキャンプでは、他のチームによってもたらされたものを含む、特別に準備された1週間半の新しいタスクを分析します。



スポーツプログラミングと学習を組み合わせるのは最初の2年間は困難でした。大学での授業以来、3番目と4番目のコースでは簡単になりました。 原則として、現時点では、多くの学生がすでに働き始めています。 もちろん、トーナメント後にオファーを受け取りますが、本格的な仕事をする時間はありません。

ライバル

最強のチームは、ロシア、ポーランド、中国、韓国、日本の大学を一貫して収集しています。 成功するチームは、西ヨーロッパまたはアメリカの大学から選ばれることもありますが、一般的にスポーツプログラミングにはあまり興味がありません。 東ヨーロッパとアジアは、 コードフォースなどの個々のトーナメントを支配しています 。 多くの競技会の参加者の数では、インドが常に最初ですが、ほとんどの場合、代表者の結果は最高ではありません。 インド人は設計上の問題を解決することに長けていますが、これはTopcoderの特別なトーナメントで明らかになっています。





2017/18シーズンのアメリカの学校チーム。 アメリカでのスポーツプログラミングの成功は、主にアジアのバックグラウンドを持つ若者によって達成されています。



最も神秘的なライバルは、北朝鮮からのプログラマーのようで、インターネットへのアクセスが制限されている状況で、まだ訓練を受けており、しばしばかなりうまく機能しています。 確かに、今年彼らはアメリカの決勝戦に出場せず、Codeforcesでは不正行為者としての評判がありました。 特に、オンライントーナメントの北朝鮮の参加者は、明らかに異なる人々が1つのアカウントからコードを書いたと非難されました。 そして、これは規則によって厳しく禁止されています。





今年、ストックホルムの王立工科大学の学生である西ヨーロッパのチームは、国際オリンピックでトップ10に入りました。



ロシアの成功は非常に理解しやすいようです。なぜなら、ここで、そして非常に強力な数学の学校、そして確立されたオリンピアードの党で、初心者を助ける用意ができているからです。 ロシアでは、ITMOに加えて、非常に強力なチームが、サンクトペテルブルク州立大学（昨年のチャンピオン）、モスクワ州立大学、モスクワ物理工科大学、およびエカテリンブルクとサラトフの大学によって代表されていますが、時には良い大学も他の大学を集めています。





別のITMOチームが描かれています：Artyom Vasiliev and Boris Minaev and Gennady Korotkevich-2015 world champions。 International Programming Olympiadのカップは譲渡できません-現在、7つはすでにITMOに保存されています。