最近、
スポーツプログラミングのタスクの競争を発表しました。 コンテストの主催者は、ABBYYブログにコンテストに関する短い発表を書くよう求めましたが、厳密な編集者は、オリンピックの問題が何であるかを説明せずに発表を印刷することを拒否しました。 これから、記事全体が生まれました。 オリンピアッドの問題の
例から始めましょう。
リンクをたどらないようにするための同じ例ITレストラン
テストごとの制限時間：4秒
テストごとのメモリ制限：256メガバイト
入力：標準入力
出力：標準出力
N市は道路、フードサービス、ITインフラストラクチャが非常に貧弱です。 市内にはnの交差点があり、その一部は双方向道路で接続されています。 道路ネットワークは、n-1本の道路で構成され、どの交差点から他の道路にも到達できます。 はい、あなたは正しいです-道路網は無向ツリーを形成します。
最近、市長はケータリングとITインフラストラクチャに関する問題を排除する方法を思い付きました。 IT従業員向けの2つの有名なカフェネットワーク「iMac D0naldz」と「Burger Bing」の市内レストランの交差点に置くことが決定されました。 ネットワークの所有者は友人ではないため、2つの異なるネットワークのレストランを隣接する交差点に置くことは固く禁じられています。 他の要件があります。 完全なリストは次のとおりです。
- 各交差点には、レストランは1つしかありません。
- 各レストランはiMac D0naldzまたはBurger Bingが所有しています。
- 各ネットワークは少なくとも1つのレストランを構築する必要があります。
- 道路で接続され、異なるネットワークのレストランがある交差点のペアはありません。
市長は各レストランに良い税を課そうとしているので、彼は最大数のレストランに興味を持っています。
市長が状況を分析するのを助けてください。 レストランがiMac D0naldzに属し、bがBurger Bingに属し、合計a + bが最大になるようなペア（a、b）をすべて見つけます。
入力データ
入力の最初の行には整数n（3≤n≤5000）-都市の交差点の数が含まれます。 次に、n-1行に、すべての道路がリストされます（1行に1つの道路）。 各道路は、ペアの数値x
i 、y
i （1≤x
i 、y i≤n）-接続された交差点の番号で与えられます。 1からnまでの番号が付けられた交差点を考えます。
特定の道路網が、n個の頂点を持つ無指向性ツリーであることは保証されています。
インプリント
最初の行に整数z-検索するペアの数を出力します。 次に、必要なすべてのペア（a、b）を最初のコンポーネントaの昇順で印刷します。
試験例入力データ
5
1 2
2 3
3 4
4 5
インプリント
3
1 3
2 2
3 1
入力データ
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
インプリント
6
1 8
2 7
3 6
6 3
7 2
8 1
最初に目を引くのは、異常な状態です。 このアプローチは歴史的に発展してきました：短い数学的な定式化を書くことは受け入れられません。 通常、彼らはそれを実際の生活と、または
そうでないものと接続しようとします。 たとえば、
USACOでは、すべてのタスク
のヒーローは農家のジョンと牛です。 条件を読んで解決策を進める前に、参加者は問題の数学的定式化を強調する必要があります。
olympiad問題の解決策は、プログラミング言語の1つで書かれたプログラムです。 最も一般的な言語は、C ++、C＃、Java、Pascalです。 パスカルは古くなっていると言うかもしれません。 ただし、過小評価しないでください！ 経験豊富なスポーツプログラマは、Pascalで標準アルゴリズムを書くことができます。Pascalは既にC ++であり、普通の人がタスクの状態を読むよりも高速です。 。 第一に、ソリューションはすべての言語に存在するわけではなく、第二に、一部の言語で書かれたソリューションは他の言語よりも効率が悪い場合があります。
条件の説明に戻ります。 オリンピックのタスクは非常に
形式化されています：
- 厳密な入力/出力形式、場合によってはスペースや改行までも正確。
- 原則として、条件には厳密な明確な解釈があります。 それが顧客がTKを書くことを学ぶことができる場所です！
- ランタイムと使用メモリの厳密な制限。 実際の開発では、むしろ、「 あのようなハードウェアとそのようなOSで動作させたい 」または「 聞いて、プログラムがメモリを使いすぎる 」というスタイルで何かを言うでしょう。 「 プログラムは1.5秒以内で実行する必要が あります 」、「 64メガバイトを超えるメモリを使用しないでください 」などのフレーズを聞くことはほとんどありません 。
- すべての初期値は厳密に制限されています。
このような厳密な形式化は正当化されます。 競技参加者のすべての決定は、オリンピアードの審査員によって準備され、通常は事前に参加者に知られていない特定のテストセットでチェックされます。
次の機能はタスク分析です。 olympiad問題の作成者は、参加者の何パーセントがこの問題を解決するか、どのくらいの時間（最大数分）、この問題がどのトピック（たとえば、グラフタスクや貪欲なアルゴリズムタスク）に解決するかを考えます。
一般に、オリンピアッド問題には「
古典的 」と「
発見的 」の2つのタイプがあります。 古典的な問題には、厳密で厳密に証明された解決策が必要です。 ヒューリスティックな問題を解決するとき、参加者は最良の答えを得ることができる彼ら自身の間で競います。 たとえば、そのソリューションはより多くの文字を正しく認識します。 通常、ヒューリスティックタスクには正確な解決策はありません。 ここでは、実際の開発に最も近いものです。 たとえば、文字認識は非常に「ヒューリスティック」なタスクです。
「クラシック」タスクのソリューションを評価する方法は多数あります。
- 参加者のソリューションがすべてのテストで正しく機能した場合、タスクは解決されたと見なされます。 このような評価システムは、 ACMコンテストで使用されます。
- 決定に対してポイントが付与されます。これは、プログラムによって正常に合格したテストの数によって異なります。 このアプローチは、多くの場合、学校のオリンピックで使用されます。誰も競争からresし、少なくとも0.5ポイントを獲得しません。
- テストはグループにまとめられ、グループごとに一定数のポイントが付与されます。 グループのポイントは、グループのすべてのテストでソリューションが正常に機能した場合にのみ付与されることに注意してください。 これは、参加者の正義と満足の間の妥協案です。 ABBYY Cupは、まさにこの形式の決定評価を公言しています。
- 参加者が受け取るポイントの数は、問題の解決に費やされた時間に依存する場合があります。 たとえば、このようなシステムはCodeforcesおよびTopcoderで使用されます。
各ケースにおける「ヒューリスティック」問題の解決策の評価は、個別に開発されます。 ABBYY Cup 2.0ファイナリストが解決するように求められた
ヒューリスティックなタスクでは、主題ごとにドキュメントを分類するためのプログラムを開発する必要がありました。 ソリューションは一連のテストでテストされ、各テストには異なるトピックに関する特定のテキストセットが含まれていました。 合計で3人の被験者がいて、それぞれが異なる量で各グループに提示されました。 ソリューションが最大数のテストグループに合格したものが勝ちました。 ほとんどのテストプラットフォームは従来のタスクを評価するために「調整」されているため、「ヒューリスティック」タスクをテストプラットフォームにインストールするときに、変更する必要がある場合があります。
もちろん、オリンピアッドの問題の特徴について延々と話すことができます。 最も重要な点のみを強調しました。 質問やコメントがある場合は、コメントを歓迎します。 また、記事で説明されているタスクの作成方法と作成方法がわかっている場合は、
ここで説明でき
ます 。
NLC技術部Vladimir Minyailov、
Ruzana Miniakhmetova、教育プロジェクトのグループ。