オリンピアードプログラミングについての少年

こんにちは、Habr！

9年生が、あなたに手紙を書いています。これは、情報学における全ロシアのオリンピックの地域段階でメダリストです。 最近、プログラミングオリンピックへの関心がhabragiteliの間で高まっていることに気付き始めました。 彼らの積極的な参加者として、私はすべての質問に答え、私の道について話し、覚えている実際のタスクの例を挙げようとします。

トレーニングについて

私は学校で物理学、数学、コンピューターサイエンスの詳細な研究をしています。





私は常にプログラミングに魅了されてきました（これは4年生ですでに理解されていたことです）。 パスカルとさまざまな計算アルゴリズムが7年生で教えられ始めたとき、私は非常に喜んでいました。 そのとき、最初の「Hello World！」、ユークリッドアルゴリズムを書きました。 条件付きステートメント、ループ、配列を検討しました。

8年生から、教師はコンピューターサイエンスの選択科目に招待され、そこでグラフ、配列ソートアルゴリズムなどを学びました。

タスク

必要条件

Olympiadは、受け入れられた言語（通常、このセットはPascal（私自身が書いたもので、問題はなかった）、Delphi、C ++、Java、Visual Basic、最近追加されたC＃、Python）のいずれかでプログラムを作成する必要があります。 その後、ソースファイルはサンドボックスシステムに送信され、そこでテストグループでコンパイルおよび実行されます。 各テストについて、オリンピアードの参加者は特定のスコアを受け取り、合計します。 オリンピック後、結果は誰にでも見えるようになります。 合計スコアが高いほど、場所が高くなります。

原則として、検証システムがマネージコード（Java、C＃）を適切に処理しないことは注目に値します。 個人的には地域の段階で私の友人は、すべてが正常にチェックされたものの、実行時エラー（C＃で記述）のために4つのタスクのうち3つで0ポイントを受け取りました。 この場合、私も彼も何をすべきか理解していませんでした。 控訴審では、ju審員は単に肩をすくめた。

リスク

何を失うことができますか？ エラーには次の7種類があります。

オリンピック

情報学における全ロシアのオリンピックはどうですか？

学校での8-9学年、学校での8-11学年、市営ステージ、地域オリンピアードの遠足ツアー、地域オリンピアードの5つのステージのみを経験しました。 次は全ロシアツアーですが、残念ながら私はそれに乗りませんでした。 次に、私が本当に気に入ったタスクについて説明します。

高校生のステージ

ツアー中に、8年生から11年生の間でタスク「多項式ハッシュ関数」があり、その条件は2ページのA5形式で記録されました。 この条件では、ハッシュ関数とその履歴に関する簡単な情報が提供され、そのような関数の1つが提案されました。 タスクは、入力データの配列に対して計算することでした。 非常に恐ろしい名前、複雑な用語、その量をアイコン（文字Eのように見えるもの）で記録することに怖がっており、その結果、決定する人さえほとんどいませんでした。 残念ながら、今はその状態を見つけることができません。

市営ステージ

地方自治体の段階は、複雑さが単純に殺人的なものであることが判明しました。





オブジェクトだけで十分な場合、問題を解決します。 しかし、より多くのオブジェクトがある場合は、かなり複雑なプログラミングセクション「動的プログラミング」を適用する必要があります。 私たちの教授陣で教えた教師は、この問題を解決する方法についてのアイデアが乏しいことを認めました（一緒に作業することで、いくつかのグラフを作成するだけで最小化する必要がある値を思い付きました。

その結果、オリンピアードの1人の参加者のみが全得点の問題を解決しました。





かなり単純なタスク：アルバトロスが出現した日付で値をソートし、2つのポイント間の各アークの長さを計算してから、それらをすべて加算する必要があります。 この決定は、ピタゴラスの定理の使用を可能にする決定で行われます。

しかし、なぜ決定が再考されたのですか？ 分と秒の範囲を見てください。

0 <= m1 <= 90、0 <= s1 <= 90

おそらく、1度で60分と単純に仮定したのでしょうか？ それとも1分60秒で何が起こるのでしょうか？ ハハ すぐに「90」と書き込まれます。

テストは、特に1度60分、1分60秒で翻訳を考慮して行われました。 この不名誉は、私たちの教師によってうまく挑戦されています。

最も厄介なのは、例でさえ間違っていることが判明したことです

その結果、私の意見では、誰も問題を解決しませんでした。



市町村の段階の全文はここにあります 。

距離ツアー

距離ツアーのタスクははるかに興味深いものでした。 私は2つのタスクを覚えています。





このタスクの後に、「辞書」というアイデアが思い浮かびました。これは、人を簡単に検索できるデータ型です。 誰もが興味を持っている場合-私はコメントで書いて、あなたはPMで尋ねることができますが、私はこれが別の自転車だと感じています。

ビューの総数を持つ人のリストを作成する必要があります（Arnold Schwarzenegger識別子を持つ人を見てください。長い算術演算が必要です）。次に、リストから目的の人を選択します。 アルゴリズムを簡素化するため、11年生は名前にハッシュ関数（名前に含まれるすべてのASCII文字番号の合計）を使用しました。これにより、プログラムが大幅に加速され、衝突は小さくなりました。







かなり単純な圧縮アルゴリズム（私は何と呼ばれているのか覚えていません）。 実装に興味がありました。 単語の配列を作成し、そこに最初の単語を追加して、この問題を解決しました。 次に、次のすべての単語を読み、配列内にあるかどうかを確認しました。 そうである場合-出力ストリームにワード番号を書き込み、そうでない場合-配列に追加して、番号を書き込みました。

基本的に、私の決定は完全なスコアを取得しませんでした。

課題の全文はこちらで確認できます 。

遠征では、9年生の中で1位になりました。

地域ステージ

地域の段階では、それはそれほど面白くありませんでした; 2つのラウンドがありました。 私は学校をひどく見せるために、学校を次の段階に行かせずに行かせることを恐れていました。 したがって、タスクはそれほど楽しくなく快適でした。 一般的に、私はそこから何も覚えていませんでしたが、切望された卒業証書を受け取りました。 はい、条件が見つかりませんでした。

2日目には、地元企業「予測」の代表者がやってきて、「何？」 どこ？ いつ？」、クイズを開催しました。 受賞者には賞が与えられました。

準備する

どのように準備しましたか？

答えはとても簡単です。私には良い先生がいます。 私にとっては面白かったし、起こっていることすべてを楽しんだ。 私は一生懸命準備し、私が欲しかったものを手に入れました。



あなたもこれに興味があり、このすべてに参加したい場合はどうしますか？

1. オリンピックのプログラミングのために学生を準備するためのシステムがあり、テストシステムとソリューションを備えた多くの条件があります。 私が理解しているように、このようなシステムではすべて登録が必要です。 次の2つを使用して準備しました。
   • acmp.ruさまざまな複雑さのタスクがたくさんあります。セクション「オリンピアードのコース」も興味深いです
   • http://acm.timus.ru/さまざまなコンテストのタスクの集まり。一部は英語です。 セクションhttp://acm.timus.ru/offlineでは、リモートおよび地域のステージを実施しました。
2. オンラインオリンピックがありますが、私は1つだけに参加しました：ウクライナからのNetOI 。 レビューは次のとおりです。HARDCOR!!! 私は2回戦より先に進まなかった。 コードは非常に最適に記述する必要があります（方法はわかりません）。テストごとに個別の条件があります（審査プログラムの時間が2倍になります）。

次は？

これを言うことで、私はオリンピックが実際の状況で働くためにどのように適応されるかという問題を意味します。

私はまだIT業界で働いていませんが、私は信じています：オリンピアードは実際の仕事に適応していません。 このようなオリンピックでは、アルゴリズムをよく理解するために、「自転車」をすばやく発明できる必要があります。 私の友人と私は小さなゲームを書いていますが、あなたの目標に合ったテクノロジーを選択できること、開発をスピードアップする既製のソリューションを見つけることができることははるかに重要だと理解しています。「自転車は必要ありません。」 そうでない場合は修正してください。

誰かが私の人生に欲しいものに興味があるなら、実際、私はITとコンピューターサイエンスがあまり好きではないので、私の夢は理論物理学者になって研究をすることです。 ロシア連邦ではこれに問題があるので、カナダまたはアメリカに向けて出発する予定です。



私は、PMまたはコメントで希望を受け入れます。 この記事が長続きしないことを願っています。 彼女がおもしろかったと思います あなたが私の非識字に悩まされていないことを願っています。句読点はあまりよくわかりません。



トピックの写真では、 www.psu.ruの写真が使用されました