先週の土曜日、 ロシアコードカップ2012プログラミングコンテストの2回目の予選ラウンドが開催されました 。







ロシアコードカップは、 Mail.Ru Groupが毎年開催する個々のスポーツプログラミング競技会です。 伝統的に3つのステージで構成されています。夏の初めには3つの予選ラウンドがあり、その後予選ラウンドに最高の参加があり、予選ラウンドの最初の50人の勝者が決勝戦に出場します。 それらのうち最後のものだけが個人的な存在を必要とし、残りはオンラインで行われます。 すべてのファイナリストには貴重なギフトが贈られ、1位の参加者の賞金は10,000ドルになります。 2位と3位は5,000ドルと3,000ドルです。



この記事では、コンテストに提出されたタスクを詳細に分析し、ラウンドの統計を共有します。 問題の解決策がまだ最初の一歩を踏み出している人々にとってさえ明確になるように、私は詳細を明確にしようとしました。 また、この資料は、ロシアコードカッププログラミングチャンピオンシップの予選段階でタスクがどれほど難しいかを理解するのに役立ちます。



今週の6月10日日曜日の11:00に最終予選が行われ、そこから200人の参加者が「準決勝」予選に進みます。 第2ラウンドでは、このために、単純な問題と困難な問題の2つの問題を解決し、同時に割り当てられた時間の半分を満たせば十分でした。 日曜日と幸運を待っています！



それでは、タスクに移りましょう。

「単純なタスク」

明らかに、「おしゃべり」な名前と内容のこのタスクは、ウォームアップのためのものでした-すぐに、最初の試行で解決する必要がありました。 参加者のプログラムは、単純なタスクの基準をチェックすることにより、タスクが単純かどうかに答える必要があります。 入力では、分岐演算子（OB）とループ演算子（OT）の数が指定されました。次の2つの場合のいずれかで、yesが表示されます。

-1 OM以下、2 OC以下

-2 OM以下、1 OC以下。

その他の場合はすべて、「no」が出力されます。



完全な状態、サイトRussianCodeCup.ruを参照



ここでこのタスクを詳細に分析するのは意味がありません-本当に簡単です。



この問題の解決策が単純なタスクの定義に再帰的に適合することは興味深いです。 最もエレガントなソリューションの1つは、入力された値の2乗の合計をチェックすることです：（OB * OB + OTs * OTs）<6。



合計1261の決定が検証のために送信されましたが、正しい決定は722（57％）でした。 ロシアコードカップの参加者の77％がこのタスクを完了しました。 最初の決定は、ラウンド開始から1分37秒後のAndrei Maksayから行われました。

キー

このタスクはもう少し複雑です。 問題の状況により、暗号化された文字列の中心に対して文字列がミラーリングされるため、暗号は次の構造になります。



（N文字）文字列（M文字）アコート（N文字）、



接頭辞と接尾辞が互いに交差しないすべての場合。 これが可能な場合の例が問題のステートメントで示されました-サフィックスとプレフィックスは同じ文字を決定しました：ababcは暗号化されたbabです。



完全な状態、サイトRussianCodeCup.ruを参照



明らかに、文字列を復元するには、正確な鏡像を持つシーケンスを見つける必要があります。 つまり、条件s [i] = s [l-i-1]が満たされる位置iの最大連続シーケンスが、目的の行を構成します。



これを行うために、各位置iに対してkの値-すべての文字が条件を満たしている最大部分文字列s [i — k..i]の長さを計算できます。 見つかった値は配列に格納され、その後、最大値の左端の出現位置を見つけます。



部分文字列p [i]の長さを計算するには、既に計算された値p [i – 1]を使用します。これにより、時間とリソースが大幅に削減されます。

• s [i] <> s [l-i-1]の場合、p [i] = 0
• i = 0かつs [0] = s [l –1]の場合、p [i] = 1
• i> 0かつs [i] = s [l-i-1]の場合、p [i] = p [i-1] + 1

いや	0	1	2	3	4	5	6	7	8	9	10
キャラクター	c	x	b	a	y	d	z	a	b	x	e
s [i] = s [li-1]？	c = e？	x = x？	b = b？	a = a？	y = z？	d = d？	z = y？	a = a？	b = b？	x = x？	e = c？
答え	いや	はい	はい	はい	いや	はい	いや	はい	はい	はい	いや
p [i]	0	0 + 1 =	1 + 1 =	2 + 1 =	0	0 + 1 =	0	0 + 1 =	1 + 1 =	2 + 1 =	0
	0	1	2	3	0	1	0	1	2	3	0
最大				3						3	0

答えは、番号maxの文字で終わる長さp [max]の部分文字列です。ここで、maxは配列pの最大値の左端の出現位置です。



合計1,158の決定が検証のために送信され、そのうち337が正しかった（29％）。 ロシアコードカップQR2参加者の36％がこのタスクを完了しました。 最初の決定は、ラウンド開始の9分後のKurtov Nikolayからのものでした。

四面体

最初の資格では、一致するタスクが最も簡単でした。指定されたセットから平行六面体を追加できるかどうかを計算する必要がありました。 同じ試合から四面体を追加するのはそれほど簡単ではないことが判明しました。トーナメントの開始から30分後に最初の正しい決定が下されました。



完全な状態、サイトRussianCodeCup.ruを参照



四面体は、その面が4つの三角形（言い換えれば、三角錐）である多面体であることを思い出させてください。



それはすべて、四面体のエッジの可能な一致を整理するという事実から始まります。 目的の四面体をABCDとして示します。 彼には6つのrib骨があります：AB、AC、AD、BC、BD、CD。 6つすべてを見ていきましょう！ = 720のオプション。一致はどのエッジに対応します。 ここで、対応する四面体が存在することを確認する必要があります。



四面体の存在を確認する方法は？ ここには少なくとも3つのソリューションがあります。



最初の解決策は、四面体の体積の計算に基づいています。 最も簡単な解決策は、面で四面体の体積を計算する式を見つけることです。 このタスク自体は簡単ではありません。ここで式を示します。







したがって、等式の右側が負であることが判明した場合、または面に三角形を構成できない場合（三角形の不等式）、四面体は収束しません。



興味がある人のために、ここにこの式が表示されます： http : //www.mccme.ru/free-books/mmmf-lectures/book.21.pdf



問題を解決する2番目のアプローチは幾何学的です。 最初に、ABCとBCDが存在することを確認します。 今、四面体を作ってみてください。 3次元図形を作成する場合、最後のエッジでのみ問題が発生する可能性があることは明らかです。長すぎるか、短すぎることが判明する可能性があります。 したがって、このソリューションでは、最後のリブの長さ範囲を見つけることが提案されています。



面を配置するための2つの制限オプションがあり、四面体が平面図になります。 1つ目-面が互いに対して180度回転している場合（CABおよびCBD）、2つ目-面が「折り畳まれ」て「ゼロ角」を形成している場合（CA'DおよびCDB）。 互いに相対的な面のすべての許容位置は、これらの境界面の間の範囲内にあります。 最後のエッジ（AD）は、最初の制限バリアント（AD）で最大長に達し、最後のエッジ（A'D）で最短になります。 そのため、この最後のエッジの長さが検出した範囲（A'DからAD）に収まる場合、四面体が存在します。



点AとD、およびA 'とDの間の距離を見つけるために、まず、三角形に共通の頂点の1つを0として、この頂点から出ているエッジの1つを通る横軸を描画して、座標を見つけます。 この座標系で他のすべての頂点の座標を見つけるのは非常に簡単です：アスペクト比と角度の余弦によって、極座標（角度、距離）で頂点の位置を決定し、それらをデカルト座標系に変換します。 頂点の座標がわかれば、接続されていない頂点間の最大距離と最小距離を計算するのは非常に簡単です。



プログラムは、残りの面の長さが指定された範囲に収まるかどうかを確認する必要があります。 その場合、そのような長さの四面体を「組み立てる」ことができます。









3番目の方法も幾何学的です。 まず、指定された辺を持つすべての三角形の存在を確認する必要があります。 指定された側面の値に従って少なくとも1つの三角形を構築できない場合、四面体も構築できません。 確認するには、非縮退三角形の不等式を確認する必要があります-その辺のいずれかは他の2つの合計より厳密に小さくなければなりません。



多くの場合、ソリューションはこれに限定されていました。 一方、指定された辺を持つ三角形を構築できる状況があり、それらから四面体を組み立てることは不可能です。



たとえば、面（100,100,2,101,100,2）がある場合、三角形（100,100,2）および（101,100,2）は正式に三角形の不等式を満たしますが、そのような三角形から四面体を追加することはできません。 図から、エッジACはABにほぼ平行であることがわかります。つまり、ABに対する面ABDの傾斜に対してDからCへの距離はほとんど変化せず、DBはBCにほぼ垂直であると結論付けることができます。 この場合、DCは脚の2乗和の根として近似的に推定できます。つまり、DCは条件で想定したように、2ではなく約10である必要があります。







したがって、面の三角形をチェックすることに加えて、三面角の追加テストを実行する必要があります。 三面角の存在には、2つの必要十分条件があります。

• 三面角の平面角の合計は360度未満でなければなりません。
• 三面角の各平面角は、他の2つの平面角の合計より小さくなければなりません。

平らな角度は、三角形の余弦定理により求められます。



合計で1088の決定がチェックを目的としており、そのうち74（7％）だけが正しいものでした。 ロシアコードカップQR2参加者の8％がこのタスクを完了しました。 最初の決定は、ラウンド開始から30分後にニックネームがAVictorの参加者から出されました。

「タスク」

タスクの条件により、要件が満たされる競合タスクのサブセットを見つける必要がありました：1）各難易度の1つのタスク、2）各トピックが提示される、3）トピックで重複する2つのタスクはありません。 入力データにはタスクの説明が含まれていました。どのセットがどのタスクに対応し、どのタスクが複雑かということです。 出力では、必要なタスクのサブセットをインデックス（数値）の形式で表示するか、そのようなサブセットが存在しない場合はImpossibleを出力する必要がありました。



完全な状態、サイトRussianCodeCup.ruを参照



この問題の主要な解決策は、サブセット（マスク）の動的プログラミング方法を選択することです。 この方法では、さらに操作しやすいように、ビットシーケンスを使用してセットをエンコードします。 小さいセットは、ビット操作で簡単に操作できます。 特に、トピックセットのコーディングには18ビットが必要です。 次に、数値の2進表記のi番目のビットは、 i番目のトピック（1）が既に使用されているかどうか（0）を担当します。 その結果、標準の32ビット全体では、多くのテーマをすべて保存できます。 合計で2 ^ 18個のマスクが取得され、2 ^ 18個のサブセットが定義されます。



ビット単位ANDの標準演算ではセットを交差でき、ビット単位OR（OR）ではセットを結合できるため、ビット単位のサブセットの保存も便利です。



問題のステートメントには、各レベルの複雑さのタスクを提示する必要があるという制限があるため、別の次元、配列dp [i] [j]を導入します。 彼は、最初のiレベルの難易度からタスクを取得し、取得したタスク間でトピックが交差することなく、ビットマスクjで定義されたトピックのセットを収集できるかどうかを判断します。



次に、次のレベル（i + 1）に進み、複雑さi + 1のタスクの中から、ビットマスクが状態マスクと交差しないタスクを選択します。すべてのトピックが使い果たされる状況に到達するまで（右上）マトリックス角）。 そのような複雑さの問題i + 1が見つからなかった場合、答えは不可能です。

for (int[] t : P) { Arrays.fill(t, -1);} //   “-1” P[0][0] = -2; //    for (int i = 0; i < tl.length; ++i) { //     for (Task t : tl[i]) { //    for (int mask = 0; mask < P[i].length; ++mask) { //     if ((mask & t.mask) == 0 && P[i][mask] != -1) { //         //       dp[i + 1][mask | t.mask] = t.num; } } } } //         if (dp[d][(1 << m) - 1] == -1) { out.println("Impossible"); // …   } else { out.println("OK"); int[] ans = new int[d]; int mask = (1 << m) - 1; //      for (int i = d; i > 0; --i) { ans[i - 1] = dp[i][mask] + 1; mask ^= mm[dp[i][mask]]; } for (int i : ans) { out.print(i + " "); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

検証のために合計407件の決定が送信され、そのうち115件（28％）のみが正しいものでした。 ロシアコードカップQR2参加者の12％がこのタスクを完了しました。 最初の決定は、ラウンド開始から16分後のニキータイオッフェからのものでした。

「テキストエディター」

入力のタスクでは、入力された位置と文字（アルファベット+角括弧）を取得し、出力では、角括弧の各入力で、以前に入力されたペア角括弧の位置を返すか、ペア角括弧が存在しない場合は-1を返す必要があります。 入力データが以前に追加されたブラケットを別のブラケットに変更する可能性がある状況、および多くの文字とブラケットがある可能性があるという状況（テキストサイズは100000）を正しく処理する必要があります。



完全な状態、サイトRussianCodeCup.ruを参照



かなり単純な声明にもかかわらず、このタスクは提示されたものの中で最も困難です。 ここでの主な難点は、テキストサイズが大きくなる可能性があり、連続スキャンと直接カウントの使用が非効率的であることです。



この問題を解決するために、「ツリーツリー」データ構造が使用されます。 これにより、要素を新しい値に変更する操作をすばやく実行し、iからjまでの任意の間隔でいくつかの関数（合計、最小、最大）をすばやく計算できます。 この場合の「高速」とはO（log n）を意味します。つまり、順次表示よりも大幅に高速です。



セグメントツリーの概念を実装するアルゴリズムは、 e-maxx.ru / algo / segment_treeにあります。



この場合、行ツリーでは、テキスト内の各位置のブラケットシーケンスの現在の「深さ」を格納します。 ツリーのリーフに保存され、最上部では計算された最小値がツリーのルートに保存されます。これはツリー全体の絶対最小値です。



したがって、閉じ括弧の検索は、右側（開き括弧）または左側（閉じ）の同じ深さの要素の検索に限定されます。 順次表示の代わりに、ツリーに沿って下降があります-開始ブラケットの前または終了ブラケットの前の深さを超えない最小値。



ブラケットを挿入する場合、その右側にあるすべての要素と、これらの要素をカバーする頂点のすべての最小値を再計算する必要があります。 ここで、いわゆる 「遅延」更新-変更に関する情報は最上部に残り、「リーフ」にアクセスする必要がある場合は「リーフ」に移動します。



合計159の決定が検証のために送信され、そのうち8（5％）だけが正しかった。 ロシアコードカップQR2参加者の1％未満がこのタスクを完了しました。 最初の決定は、ラウンド開始の54分後にセルゲイ・フェドロフから出されました。

---

• 最初の資格からの報告
  
  3番目の資格からのタスクの分析
  
  
  
  
  
  アリエフ・ラウフ
  
  研究教育ディレクター
  
  プロジェクトマネージャーRussian Code Cup
  
  Mail.Ruグループ