Sebastiaan ter Burg / Flickr / CC
コースについて
コース「 プログラミングコンテストで勝つ方法：チャンピオンの秘密 」は、今年10月に始まりました。 コースの著者とインストラクターは、異なる年にITMO大学の名誉を擁護した学生オリンピックのチャンピオンでした： マキシム・ブズダロフ 、ITMO大学のコンピューター技術の助教授、ACM ICPC 2009のチャンピオン、Pavel Krotkov、ITMO大学ITおよびプログラミング部門の卒業生、多くのコンテストの参加者および主催者ACM ICPC NEERC（パウロは今のFacebookで働いている）とを含め、ロシアでは、海外でのプログラミングダリアYakovlevaフロリダ州、大学ITMOの情報システム部門のシニアアシスタント 今年は女性のためのGoogle Codeのジャムをプログラミングする上で、国際競争の中でトップ10に入りました。
このコースは5週間にわたって設計され、スポーツプログラミングで使用される機能とアプローチを研究することを目的としています。 参加者は、競技会の開催方法を学び、問題とその使用例を解決するための最も一般的なアプローチを分析し、実際の状況に近い条件でオリンピックの課題を解決するための訓練を行います（最終試験は、実際の国際プログラミング競技会の形式で開催されます）。
コースの作成者は、生徒にオリンピアードのタスクを「訓練」するだけでなく、厳しい締め切りの状況で作業し、異常で効果的な解決策を見つける方法についても話します。
マキシム、パベル、ダリアから、プログラミングオリンピックの将来の勝者が持つべき知識、勝利のための「チップ」とライフハックの重要性、スポーツプログラミングの初心者の間違いを学びました。
最小プログラム：競争に勝つために知っておくべきこと
Pavel Krotkovは、オリンピックに勝つために必要な基本的なスキル、つまり数学、アルゴリズム、プログラミング言語の知識を呼び出します。 もちろん、この知識がなければ、成功することは不可能です。
重要なスキルの2番目のグループ：適切な戦術、「チップ」の知識。 チーム競技では、これはコンピューターでの時間を最適に使用する能力、分業、プログラムとチームメイトのプログラムをデバッグし、それらのエラーを探す能力です。 個人競技では、これらのスキルには、プログラムをデバッグ/テストし、特定の仮説をすばやくテストする能力が含まれます。
マキシム・ブズダロフはこのリストを補足し、プログラミング・オリンピックへの参加を成功させるために必要な7つのスキルを即座に特定します。
- 問題の解決策を考え出す能力。 これには、アイデアを生成およびテストする機能、1つのタスクを別のタスクに減らす機能などが含まれます。
- アルゴリズムとデータ構造の分野での博識、標準ではなく、非常に。 この知識は、どのアルゴリズム/構造が存在するか、どのタスクを解決するか、解決する問題に必要な特性、これらのアルゴリズムの漸近的な複雑さ、またはこれらのデータ構造での操作に関するものです。
- 実際にアルゴリズムとデータ構造を効果的に実装する能力。 さらに、「効果的に」という言葉は、相互に関連する2つのことを意味します。アルゴリズム/構造の機能に関する「効率」と、コンテストで作成された時間に関する「効率」です。
- プログラミング言語の知識と、この言語の操作の複雑さモデル。 そのため、C、C ++、Java、およびPythonで、必要な効率のためにいくつかのことを（データストレージ、コード構造化に異なるアプローチを使用して）別々に記述する必要があります。
- すでに正しく記述されたコードを高速化できるさまざまな「ハッキング」の知識。
- コード内のエラーを検索し、コードをデバッグする機能。
- 最大の結果を達成するために、リソース（個人リソース、チームリソース、コンピューティングリソース）を効率的に割り当てる機能。
マキシムは、異なるスキルには異なるトレーニングが必要であることを強調しています。 したがって、彼の意見では、文献を読むことはアルゴリズムとデータ構造をよりよく理解するのに役立ちますが、それ以上のことはありません。
数学の授業で教えられた問題の解決策を考え出す。 「産業用」プログラミング（つまり、プログラマがビジネスタスクの一部として通常行うこと）は、スキル＃4、＃5、および＃6を提供します。 しかし、マキシムによると、実際にアルゴリズムとデータ構造を効果的に実装する能力とリソースを効率的に割り当てる能力は、典型的な「スポーツ」スキルです-競技に参加する練習なしに開発するのは非常に困難です。
これらのアイテムのほとんどすべては、絶え間ない開発とあなた自身での継続的な作業を必要とします。 たとえば、アルゴリズムの実装に慣れていないが、よく考えると、すべての問題を（紙上で）解決できますが、（コンピューター上では）事実上何も解決できません
-マキシム・ブズダロフ
もう一度「チップ」について
数学とプログラミングを知っているが、チップ、ライフハック、その他の秘密の知識に精通していない新参者が競争に勝つことができるかどうか、コースの著者に尋ねました。 オリンピアードの勝者は、「チップ」がすべてではないことに同意しました。基本的な知識と努力がなければ、オリンピックの参加者ははるかに困難になります。
最初のカテゴリー[数学、アルゴリズム、プログラミング言語の知識]の知識しか持たない、ある程度の競争に勝つことは可能だと思います。 それにもかかわらず、第2のカテゴリの知識[適切な戦術、有能なリソース割り当てのスキルを理解する]は、人生を大幅に簡素化し、触媒として働きます。 他のスポーツと同様に、身体的スキルはありますが、技術、心理学などの知識があります。 あなたは最初のものを犠牲にしてのみ成功することができますが、2番目は触媒として機能します
-パベル・クロトコフ
オリンピアードで成功している（世界の主要な大会で賞品を獲得している）人は、段落5 [上記のリストから]で適度に無知である（「ハッキング」）ことができます。パラグラフ7（リソースの操作）を重視しない場合があります
-マキシム・ブズダロフ
Daria Yakovlevaは、オリンピアードの状況では、「チップ」の知識よりも創造的なアプローチの方が重要である可能性があるため、才能のある新人はまともな結果を期待できると述べました。
もちろん、問題を解決するためのさまざまな方法を知ることは重要ですが、オリンピアードの審査員は、参加者が最初に自分で解決策を思いつくような方法でタスクを策定しようとすることに注意する必要があります。 ただし、もちろん、複雑なタスクには追加の知識が必要です。 したがって、勝つことは難しいと思いますが、トップ10に入るのは本当です
-ダリア・ヤコブレバ
チームワークについて
シングルプログラミングとチームプログラミングの基本的なスキルは異なりますが、それほどではありません。 ダリアは明らかにします：
チーム競技では、チームには1台のコンピューターしかありません。 そのため、オリンピアードでは、コンピューターで問題の解決策を書くのは1人だけで、残りのメンバーは紙で他の問題を解決します。通常、チームには、非標準の問題を解決する数学者、プログラマー、アマチュア
-ダリア・ヤコブレバ
これは、チーム競技の参加者が1つまたは複数の領域に「集中」できることを意味します。この場合、彼の弱点は同僚によって補われます。 この点で、マキシムは2009 ACM ICPCトーナメントを回想します：
したがって、たとえば、私たちのチーム（2009年に世界プログラミングチャンピオンでした）では、Zhenya Kapunはソリューションの卓越した発明者であり、Slava Isenbaevは優れた「ユニバーサルファイター」であり、大量のきちんとしたコードを必要とするタスク（たとえば、計算ジオメトリのタスク）、何よりも書いた
-マキシム・ブズダロフ
マキシムとパベルは、チーム内の役割の分離は、最初の10回のトレーニングセッション中に自然に発生することがよくあります。 チームメイトの興味はわずかに異なり、その結果、異なる参加者が異なる分野に少しずつ専門化することが起こります（マキシムが明らかにするように、計算幾何学、フローのタスク、「トリッキーな」データ構造、接尾辞ツリーまたは接尾辞オートマタなど）さらに）。 誰かが標準アルゴリズムをより速く実装するか、数学の特定のセクションをうまくナビゲートします。これはすべて、チーム内の役割の非公式な分布に影響します。
発音された「数学者」と発音された「エンコーダー」を持つチームがあります。 もちろん、エンコーダーは数学を理解する必要があり、その逆も同様であるため、これらのスキルを完全に分離することは不可能です。 さらに、彼らが個人的な競争にも参加している場合、参加者が互いに学び合うにつれて、不平等は時間とともに減少する可能性があります。
いずれにせよ、チームに「数学者」、「エンコーダー」、「テスター」、またはサフィックスオートマトンの専門家がいる場合、これは適切なスキルを開発する必要がないという意味ではありません。 まったく逆です-学ぶべき人がいるので、それを使う必要があります
-マキシム・ブズダロフ
チームメイトの強度とスキルはほぼ同じです。その結果、チームで作業する戦術は、タスクを最初に解決した人がタスクを作成するという事実に帰着します。 ただし、Pavelが指摘しているように、役割の配分は特定の知識分野の専門化と常に関連付けられているわけではありません。ほとんどのチームには、困難な状況で決定を下せる人もいます。
落とし穴：未経験の参加者が失敗するもの
コースの著者が述べているように、初心者の主な問題は主に彼らの長所と能力の再評価に関連しています。 マキシム・ブズダロフは、彼らが書いたコードが未経験の参加者の真の惨劇として機能するという彼らの驚くべき自信を呼びます。
さらに、彼らは実質的に「作品」と「例と条件からの作品」を区別しません。 彼らは、コードを再度チェックし、反例を考え出し、最後に、解決策の正確性を証明しようとする考えを得ません。 したがって、特に、「Invalid answer、test 2」という形式の評決では、そのような参加者は非常に困惑し、列に並んだいくつかのそのような評決は徹底的な苦味の状態になります。
-マキシム・ブズダロフ
例として、マキシムは「プログラミング競技で勝つ方法：チャンピオンの秘密」コースのタスクの1つを挙げています。 3x3の数値のマトリックスが与えられます。このマトリックスから3つの数値を選択して、列または行で複数の数値が選択されず、数値の平方和のルートが最大になるようにする必要があります。
この問題の正しい解決策-それらの少なくとも1つ-は明らかです：列番号<a、b、c>のすべての可能なトリプルをソートし、各トリプルについて、最初の行で列aが選択され、2番目の行で列が選択されている選択肢をチェックしますb、3番目の列c。
ただし、コースの多くの参加者がそのようなソリューションを送信しました。最初にマトリックス内の最大数を選択し、次に対応する行と列を消してから、最大数を再度選択します。 これにより、6回目のテストで誤った回答が得られました。 このソリューションは「殺す」のが非常に簡単です。そのようなマトリックスで何が起こるかを考えてください。
9 8 1
8 1 1
1 1 1
正しい決定は2つの8と残りの単位を選択しますが、2乗の合計は129になります。「貪欲な」解法は9を選択し、単位のみを持ち、2乗の合計は83になります。もちろん、ルートの抽出はそれを変更しません最初の答えはより多く、したがってより良いです。
同様の例を受け取った多くの参加者は、すべての種類のケース分析を書き始め、同じテストまたは他のテストで間違った答えを受け取りましたが、主なものを見逃していました-意思決定の主要部分のロジックの単純な反例を受け取ったので、停止して考える必要があります。 穴を塞いだり、小道具を配置したり、松葉杖を作ったりする代わりに、ソリューションが機能する理由を正当化するのは良いことです。 そして理想的には、数学的に厳密に証明する
-マキシム・ブズダロフ
Dariaが指摘するもう1つのよくある間違いは、intデータ型のオーバーフローです。
許容範囲を超える値を変数に「入れ」ようとすると、[エラー]が発生します。 問題を解決する際には、注意して値の順序を評価する必要があり、すべてがうまくいきます
-ダリア・ヤコブレバ
パベル・クロトコフは、オリンピアードの経験豊富な参加者の別の重要な特徴であるストレス耐性に注目しています。 彼女の初心者も不足しています-そのため、間違った決定は簡単に当惑とパニックを引き起こし、貴重な時間の損失につながります。
ストレスを克服する能力については、会話の後半で説明します：コースの作成者とインストラクターは、競技の準備において心理学と正しい態度がどのような役割を果たしているかを伝え、ライフハックと小さなトリックを共有し、誰に（将来のオリンピックの勝者に加えて）も説明しますITMO大学のコーディングコンテストの勝ち方：Secrets of Championsコースに興味があるかもしれません。