プログラミングオリンピアード、NSUの外観。 記事5-チームのプレー方法

以前の記事で、内部からのプログラミングに関する定期的なオリンピアードの典型的なツアーがどのように進むかについて、多少説明しました。 誰かがこの内部メカニズムに興味を持っていて、誰かがコーディング自体についてもっと知りたいと思っていました。 今日の記事では、ツアー中にチームが正確に何をするか、どのように、何をするのか、どのトリックを使用するのか、何が起こるのかについて説明します。 おそらくトレーニングと個人的なコンテストについては後で説明しますが、この記事の後はほとんど何も話すことはありません。



私は現在および元のACM羊からのコメントを待っています、私はいくつかの新しい微妙さと方法を学ぶことができます。



最初の記事は、タスクの作成に関するものです。

2番目の記事は、システムのテストに関するものです。

3番目の記事は、組織委員会の仕事に関するものです。

4番目の記事は、ツアー自体に関するものです。





チーム構成



チームは3人です。 もっと-ありえない、より少ない(現在の規則による)-も。 昨シーズン、ミーシャと私は最後の最後を求められました。 幸いなことに、Kolya Orfestは無料で、急いで行きました。 残念ながら、私たちの大学の最初の3チームのレベルでプレーする時間はなかったため、準決勝に再び行くことはありませんでした。 今年はチームワークの修復を試みます。



最高のチームでは、各参加者が個別にツアー全体(まあ、またはほとんどのタスク)を取ることができます。 下位レベルのチームでは、個々の参加者が特定のトピックに特化することがよくあります。 私たちと一緒に、ジオメトリのほとんどすべてがミーシャの肩にかかっており、数論や組み合わせのファブリケーションを解決しようとする人はいません。 そのため、さまざまなトピックに特化したため、個性の強いチームのレベルで総合的な知識を持つチームを獲得できます。



通常、チームでは、エンコーダー、数学者、アルゴリズム主義者という3つの役割を区別できます。 各参加者は少なくとも2つ、理想的にはすべて3を実行する必要があります。ただし、すべてのケースが理想的であるとは限りません。良い結果を達成します。 悪用する価値はありません。全員にすべてを知らせる方がよい=)



ツアー開始



チームの開始の約10分前にコンピューターを許可しました。 最速のコマンドエンコーダーがマシンに座って、書かれているはずの言語でテンプレートを詰め込み、IDEを調整します(Eclipseでお気に入りのパースペクティブをゼロから設定することは、すでにほとんど自動化されています)。 残りは職場を準備します-ペン、ノート、神経。



タスクは、通常紙の形式で表示されます。 理想的には、3コピー、参加者ごとに1つですが、それよりも少ないかもしれません。 2-便利な操作のための最小限。 次に、チームの2人のメンバーが、現時点ではキーボードに負担をかけずにタスクを熱心にスナップし、「コンソール」を探し始めます。 私が書いたツアーの90%には、少なくとも1つの問題があり、すぐに、迅速に、オプションなしで、最初の試行で解決する必要があります。 それを見つけた後(2分)、アルゴリズム主義者はエンコーダーに座って、一般的な言葉で彼に本質を紹介します-そのため、テキストを読んで翻訳することに煩わされません(ほとんどの競技では、テキストは英語であるため、不要なプラグを避ける方が良いです)。 さらに、エンコーダーはキーボードとこのタスクの状態に直面したままであり、他の2人はツアー全体を分解するために急いでいます。



彼らはツアー全体を読み、次に書くタスクを探します。 さらに、キーボードがビジーである間、コードはノートに注意深く書き込まれます。 概略的ではない、つまり、転送の準備ができているコード。 次に、高速でダーティなエンコーダーが1つのタスクに対処すると(外部干渉なしでこれを行うことができると想定されます)、残りの2つのうちの1つが代わりに座って、エンコーダーがツアーを注意深く読み取ります。 この瞬間の3番目の参加者は、コードの記述を観察するために出かけます。スポーツプログラミングのペアコーディングは非常に便利です。 同時に、この参加者は現在のタスクのテストを作成します。



はい、ほとんど言い忘れていました。 最初のタスクまたは2番目のタスクを書いている間、トーナメントのステータスは定期的に監視され、間違ったステップに行かないように人々が何を解決しているかがわかります。 同時に、チームのライティングタスクの個人的なキューは、複雑さ/知識/希望に基づいてコンパイルされます。



ミッドツアー



決定することがある限り、それはまさに決定されたものです:)通常、次のシステムに従って起こります。 + 2番目と3番目は、最初のタスクのテストで、結果を手動で計算します。 すべてが悪く、完了すべきすべてのタスクが終了した場合、チームは座り込みます。 ブレーンストーミングの技術はすでに誰もが知っているので、ここでは詳しく説明しません。



タスクが「書き込みキュー」に入ると、チーム数学トーナメントの次のテクノロジーが非常に役立ちます。 もちろん、正しい最良の解決策が誰かの頭の中で生まれたとき、彼はこの問題について考えなかった人のところに行き、問題の解決策を説明します。 それはナンセンスと混乱のスクリーニングに役立ちます。



ツアー終了



ツアーの終了は3つの異なる方法で行われます。 最初の最も美しいオプションは、1時間半から2時間から5時間のカットオフで、評価のすべての利点があり、誇らしげに頭を上げました。 これは2、3のトレーニングセッションでしかありませんでした。 モスクワとサンクトペテルブルクのチームの間では、これは準々決勝でも行われています=)



2番目のオプションは、まだ多くの落書きが残っているが、十分な時間がない場合です。 次に、チームの投票(ツアー終了の約1時間前)で、タスクに対する自信と書き込みの速度に応じて、書き込むタスクを決定します。



そして第三の方法は「バレエ」です。 アイデアがなくなったが、何かしたいとき。 それから、彼らは時間制限が私たちを迂回することを期待して、さまざまな汚い正面決定を書き始めます。 サーカスかもしれない。

そのため、CBOSSツアーでテストシステムのバイナリ検索の問題を解決しました。 私たちはタスクを書いたのですが、かなり愚かで額に。 経験的な理由により、最初の〜200万で何も修正されなければ、それ以上何も壊れないことが示唆されました。 期限が切れました。 彼らは50万に制限を設けました-それは精度が落ちます。 何もすることはなかったので、逐次近似により解に到達しました。 30日に失敗しました



トリックとジャンプ



ツアーを作成するとき、多くの場合、興味深く有用なさまざまなトリックが使用されます。 多くの場合、経験の浅いチームには驚くほど見えますが、誰にとっても便利です。



スライprecalc


多くのタスクは、予備的な誤算によって解決するのにコーシャーです。 前に書いたように、5分間のコンピューターの操作により、チームは次の方法で問題を解決できます。

read(a); write (res[a]);





しかし、多くの場合、タスクは額面でプレアルクまたは愚かに考えられているように見えますが、最初はコードに十分なスペースがなく、もう一方には時間制限があります。 その後、ダーティハックナンバーワンを適用できます。



この方法で解決さた問題の例を次に示します。 コリヤと私は同時にそれを解決し始め、彼はマタンの道を進み、トリッキーなタブレットを生成し、任意のポイントでそれから何らかの方法でソリューションを計算しました。 私は率直に行動しましたが、創造的な方法でもありました。 100,000の長さのサイクルが許容時間内に実行され、1000個の事前計算された値がコードに含まれます。 したがって、解のグリッドが計算され、次に最も近い値から額がカウントされました。 アプローチは科学的でスケーラブルではありませんが、私はより速く管理しました。



良い発電機


Dima Kovchinがチームにもたらしたテクニック。 主に整数の問題で使用されます。 すぐに、約10分で、目的関数の最初の20個の値を大胆に計算するジェネレーターが作成されます。 次に、チームの最高の頭脳が座って、艶出し分析の方法で一般的なパターンを明らかにしようとします。 多くの場合、最初の2〜3の値のパターンは誤っている可能性があります。20の値により、仮説をかなり確実に信じることができます。 紙に手書きするのにもっと時間がかかります。 ニュートン法では、任意の数のポイントを介して高次曲線を作成できるため、この方法を乱用しないでください。



Excelはプログラマの親友です


他の大学のチームがどのように持っているかはわかりませんが、私たちにとってこれはことわざです。 Excel(より正確にはOpenOffice Calc)でさまざまな卑劣なテストを常に記述しています。 Excelは、入力データのグラフィカルな分析に役立ちます。 そして、私たちのチームがACMで最高のKVNチームの中で常に1位を共有していたSibGUTIの面白い人たちは、しばらくの間、NSU MOMとNSU NANがexelの問題を解決し、xlsファイルをテストシステムに送信すると噂されていました。 もちろん、これはそうではありませんが、タスクを単純にどこでもモックするためのmacstestsを作成するのはExcelよりも優れています。



計算されたグーグル


ヒントにより、 OrfestはGoogleがなければ複雑になる可能性があることを思い出しました。 オールシベリアオリンピアードのタイプの主要なトーナメントでは、このような贅沢はもちろん与えられませんが、同じCBOSSでも問題なく使用できます。 GoogleとWikipediaでは、数学的な知識を更新して、目立たない何かの結論に煩わされないようにし、本当にしたい場合は、既製のアルゴリズムに侵入します。 これをすべての病気の万能薬と見なすべきではありません。多くのトーナメントでは、外部インターネット自体が禁止されていますが、Webサービスのサービスが役立つ場合もあります。 少なくとも、問題を解決する上で重要となる可能性のあるあいまいな単語の翻訳でも。 そして、「バレエ」の段階で、これは次のショーに至るかもしれません。

約3年前、私たちのチームはサンタクロースチームのエルフの座席に関する問題を解決していました。 それはすでにツアーの終わりで、脳の沸騰の程度にさらに早く達しました。 ショーは、シカの配列の変数に「ムース-ラップランドのムースです」というコメントが付いた「loses」という名前で始まったことから始まりました。 Yandexでアルゴリズムを探すことが決定されたとき、集合的な心は、「鹿のエルフを植えるエルフ」というような要求だけを生み出しました。 このリクエストのツアーは完了し、チームの実績に別の楽しい瞬間が追加されました。



これまでのところ、悲しいかな、スポーツプログラミングに関するトピックが不足しています。 誰かがアイデアを投げたら、私は他に何を書くことができますか、私は非常に感謝します。



All Articles