年々、「ロシアのプログラマーが再び勝った」のような鮮やかなフレーズを見出しに見ることができます。 はい、社長はこの問題を回避しません。 もちろん、言葉は楽しいですが、これはどういう意味ですか？

選手権はどうですか

世界には多くのプログラミング競技会がありますが、 ACM ICPC - Association for Computing Machinery International Collegiate Programming Contest -International Interuniversity Programming Championshipは、悪名高いACMを開催しており、特に優れています。 コンテストの構造は単純です-大学から準々決勝までは12チームまで、準決勝までは4チームまで、決勝までは1チームのみです。 技術的な詳細を除き、5時間続く競技の1ラウンド中、各チームは提案された数から問題を解決するプログラムを最大数書く必要があります。 通常は8〜16です。 技術的な観点から見ると、プログラムは最も単純です。GUIもデータベースも、その他の同様のホイッスルも必要ありません。シンプルなコンソールアプリケーション-何かを読み、計算の結果を処理して表示します。

しかし、すべては一見しただけで非常に単純に思えます。問題を解決するために深刻な数学的知識と工夫が必要なだけでなく、評価基準は非常に厳格です。

• 正しさ：プログラムは常に正しい答えを出力する必要があります。
• 信頼性：プログラムは「落ちる」べきではありません。
• 時間効率：すべてのテストでのプログラムの合計時間が、設定された制限を超えてはなりません。 ほとんどの場合-一瞬から数秒まで。
• メモリ効率：プログラムが作業に使用するメモリの量は非常に限られています。

そして今、入力データには数百万または数十億の値が含まれることがあり、また、多くの（少なくとも数が千を超える）テストの少なくとも1つがプログラムが上記の少なくとも1つのポイントを満たさない場合、タスクを渡そうとしないことを追加しますカウントされ、ペナルティ時間がチームに追加されます。 言うまでもなく、テストデータは参加者に知られていませんか？

オリンピックの問題の例

簡単な例を考えてみましょう。数字の配列を入力として受け取り、 getmax



などのクエリを実行して最大数を取得するgetmax



をgetmax



するかmodify ab



をmodify ab



してaをbに置き換えます。 しかし、配列のサイズが100万で、10万のクエリを完了する必要がある場合はどうでしょうか。 しかし、数字を削除できるとしたらどうでしょうか？ しかし、 k番目に大きい数を出力する場合はどうでしょうか？ しかし、数字が文字列に置き換えられたらどうなるでしょうか？ そして同時に-すべてのためのほんの一秒とメモリのメガバイトのある種の哀れなカップルがあります。 すべてはもはやそれほど些細なことではないようですね。 そして、この例は最も簡単な例です。オリンピアードは数分でこのようなタスクを実行します。

そして、私はそれと何をしなければなりませんか？

オリンピアードのプログラミングのスキルはどの専門家にとっても有用であると仮定するのは論理的です。なぜなら、彼は創造物の有効性を真剣に監視し始めるからです。 これが読者に興味があるなら、私はこの方向で出版を続けることを非常にうれしく思います。すなわち、まず、「オリンピアードになる方法」、「どんな習慣を放棄すべきか」、そしてブログ「アルゴリズム」を補充し、いくつかの特に興味深い注目すべきオリンピアードの問題を検討します。



PS私はここの初心者なので、わかりません。そのような投稿を投稿する方が良いでしょうか？ アルゴリズムと異常プログラミングと学習プロセスの間で引き裂かれた。 どう思いますか？ -ありがとう、 ハイロフ

PPSもちろん、カルマがないため、対応するブログに転送することはできません。 ちなみに、私は集合的なブログでの出版物の初心者のための制限に関するヘルプで何も見つけませんでした。 私はひどく見えましたか、それとも本当になくなっていますか？ -おかげでMithgol

PPPS著作権写真： David Hill 、ACM ICPC 写真アーカイブから取得。



UPD： スポーツプログラミングをブログにもたらしました。 カルマと説明をありがとう。

UPD2： ＃2を投稿してください。