Clever Geek Handbook

ロシアコヌドカップ2012最初の資栌からのタスクの詳现な分析

5月27日に、 Mail.Ru Groupプログラミングコンテストのロシアコヌドカップ2012の第1ステヌゞが完了したした 。 合蚈で、1000人以䞊がRCC'12に参加し、そのうち200人が予遞ラりンドの準決勝に進みたした。 最初の予遞ラりンドの勝者は、ニゞニノノゎロド出身のUNNのMechmath、Vladislav Epifanovの孊生でした。 参加者は3391件の決定を送信し、そのうち1066件がシステムによっお真であるず受け入れられたした。 634人たたは参加者総数の63が少なくずも1぀の問題を解決したした。



ロシアコヌドカップは、Mail.Ru Groupが毎幎開催する個々のスポヌツプログラミング競技䌚です。 䌝統的に3぀のステヌゞで構成されおいたす。倏の初めには3぀の予遞ラりンドがあり、その埌予遞ラりンドに最高の参加があり、予遞ラりンドの最初の50人の勝者が決勝戊に出堎したす。 それらのうち最埌のものだけが個人的な存圚を必芁ずし、残りはオンラむンで行われたす。 すべおのファむナリストには貎重なギフトが莈られ、1䜍の参加者の賞金は10,000ドルになりたす。 2䜍ず3䜍は5,000ドルず3,000ドルです。



この蚘事では、参加者に提䟛されたタスクずその解決方法に぀いお説明したす。 タスクの簡単な分析は、RCCの完了埌すぐにサむトで公開されたす。その埌、初心者プログラマヌでも解決策が明確になるように、詳现を明確にしようずしたす。





合蚈5぀のタスクがツアヌに提案されたした「ボックス」、「ペレストロむカ」、「戊争」、「ラベル」、「ゞャワの歊噚」。



「平行六面䜓」

「Parallelepiped」のタスクは、既知の12マッチの長さから、平行六面䜓のフレヌムをそこから接着できるかどうかを確認するこずでした。 このタスクは最も簡単で、すべおの参加者がそれを解決し始めたした。



ボックスは、底面が平行四蟺圢である図であるこずに泚意しおください-四角圢は、蟺がペアワむズ平行です。 ボックスには、長さ、幅、高さの12゚ッゞの3぀の次元がありたす。 したがっお、入力デヌタの䞭に4぀の同じ数のグルヌプが正確に3぀あるかどうかずいう質問に答える必芁がありたす。



これを理解するには、すべおの数字を䞊べ替え、4぀の同䞀の数字からなる3぀のグルヌプ少なくずも各グルヌプ内で同じを取埗する必芁がありたす。 その堎合、yesを印刷し、そうでない堎合はnoを印刷したす。 



#include <iostream> #include <cstdio> using namespace std; int main() { int a[12]; while (true) { bool ex = true; for (int i = 0; i < 12; i++) cin >> a[i]; for (int i = 0; i < 12; i++) if (a[i] != 0) ex = false; if (ex) break; bool ans = true; for (int i = 0; i < 12; i++) { int k = 0; for (int j = 0; j < 12; j++) k += (a[i] == a[j]); if (k % 4 != 0) ans = false; } cout << ((ans) ? "yes" : "no") << endl; } }




Parallelepipedタスクを枡す詊みは1479回あり、そのうち639回が成功したした43。 このタスクは最もアクセスしやすいこずが刀明したした-詊行回数は他のタスクの2倍以䞊で、高い成功率です。

RussianCodeCup.Ru問題の声明

RussianCodeCup.Ruタスクの解析



ペレストロむカ

2番目のタスクはより困難でした。



問題の状況に応じお、郜垂間に倚くの道路がありたした。 2぀の郜垂の間には、1぀の道路しか敷蚭されおいたせん。 䜕らかの道路改革の結果ずしお、既存の道路の1぀が砎壊されるこずになっおおり、以前に敷蚭されおいなかった道路のもう1぀が建蚭され、最終的にはどの郜垂からいずれかの道路に到達できるようになりたした最初はそうではありたせんでした 。 たた、道路は郜垂からそこに通じるこずができないずいう明確化もありたす。 この改革を実斜するためのオプションの数を蚈算する必芁がありたした。




このタスクには、グラフ理論の分野の知識が含たれたす。 私たちの数の頂点は郜垂であり、rib骚は道路です。 グラフ理論では、接続されおいるグラフの抂念がありたす-任意の頂点から任意のパスぞのパスの存圚。 この堎合、最初は未知の接続性のグラフがありたすが、最終的には必ず接続されおいるグラフを取埗する必芁がありたす。 グラフ接続コンポヌネントの抂念がありたす-これは、盞互接続された頂点のセットの最倧包含数です。 したがっお、接続されたコンポヌネントの数は、接続されおいない頂点グルヌプの数です。 たずえば、グラフの゚ッゞがない=道路堎合、接続されたコンポヌネントの数は、頂点の数=郜垂に等しくなりたす。 たた、「ブリッゞ」の抂念も導入したす。゚ッゞを削陀するず、グラフが切断されたす。぀たり、グラフが切断された郚分に分割されたす。



そこで、問題の声明から改革の本質を思い出しおみたしょう。1぀の既存のrib骚=道路が削陀され、別のrib骚がその前にrib骚がなかった堎所に远加されたす。 そのような改革のためのオプションの数を蚈算する必芁がありたす。



たた、問題の状況に応じお、私たちの改革が連結グラフに぀ながるべきであるこずを芚えおいたす。 接続されたコンポヌネントが1぀。 最初は、ばらばらの䞊䜍郜垂のグルヌプの数はいく぀でもかたいたせん。



明らかに、接続されおいるコンポヌネントの数が3぀以䞊の堎合、1぀の゚ッゞを远加しお接続グラフを䜜成するこずはできたせん。2぀のグルヌプを盞互に接続するだけで、さらに倚くのグルヌプがあるからです。 このオプションの図は次のずおりです。







したがっお、この最も単玔なケヌスでは、答えはれロオプションです。



2぀のグルヌプを扱う堎合、぀たり2぀の接続されたコンポヌネントがある堎合、オプションの数は次のように蚈算されたす。



たず、どのリブが「ブリッゞ」であるかを芋぀ける必芁がありたす。これらのリブを削陀するず、䞊蚘の最初のオプションにすべおが取り蟌たれるためです。 問題の条件に応じお、゚ッゞがなかった堎所にのみ远加できるため、それらを元に戻すこずはできたせん。 最終的に接続グラフを取埗する必芁があるため、远加された゚ッゞは異なる接続コンポヌネントから頂点を接続する必芁がありたす-接続されおいないグラフから接続されたグラフを䜜成したす。 NおよびM頂点の2぀のグルヌプは、NxMメ゜ッドによっお盞互接続できたす。 したがっお、埗られる改革の数はNxMxCです。ここで、Cは、ブリッゞである゚ッゞを陀く゚ッゞの数です。







最初に接続されたグラフがある堎合の3番目のケヌスは、最も耇雑なものです。 この堎合、接続されたコンポヌネントは1぀ですが、䞀郚の゚ッゞはブリッゞになりたす。 その結果、改革オプションの数は2぀の甚語の合蚈になりたす。1぀目はrib骚非ブリッゞを陀去するためのオプション数、2぀目はrib骚ブリッゞを陀去するためのオプション数です。



゚ッゞの総数は、頂点の数によっお蚈算できたすn *n-1/ 2n =頂点の数。 远加できる゚ッゞの数は、䜿甚可胜な゚ッゞの総数から差し匕くこずで蚈算されたす。 したがっお、最初の項-ブリッゞではない゚ッゞの数に、远加可胜な゚ッゞの数を掛けたものを取埗したす。







「ブリッゞ」を削陀する堎合、2぀の結果ずしお接続されたコンポヌネントを、゚ッゞの分離された頂点グルヌプで接続する必芁がありたす。 これを行う方法の数は、問題の条件によっおブリッゞを戻すこずができないため、ブリッゞの右偎の頂点ずブリッゞの巊偎の頂点の数の積に等しくなり、1぀枛少したす。



その結果、この問題を解決するには、グラフ理論からの次のアルゎリズムの知識が必芁です。





接続されおいるコンポヌネントの数を芋぀ける



これを解決するために、深床トラバヌサルアルゎリズムを適甚できたす。 原則は単玔です。すべおの頂点を再垰的に巡回し、蚪問枈みずしおマヌクしたす。 党員が回るずすぐに、接続されおいるコンポヌネントの数を1぀ず぀増やしながら、ただアクセスしおいない最初のものに移動したす存圚する堎合。 そしお、すべおのピヌクがなくなるたで続けたす。



アルゎリズムの説明ず䟋 e-maxx.ru/algo/connected_components



橋を芋぀ける



ブリッゞを芋぀けるためのアルゎリズムは、「サむクル」-ピヌク間の代替パスの怜玢に基づいおいたす。 そのようなパスが芋぀からない堎合、リブはブリッゞです。



アルゎリズムの説明ず䟋 e-maxx.ru/algo/bridge_searching



このアルゎリズムを修正しお、ブリッゞの異なる偎の頂点の数を芋぀けるこずができたす。



ペレストロむカタスクに合栌する詊みは621回あり、そのうち137回が成功したした22。



RussianCodeCup.Ru問題の声明

RussianCodeCup.Ruタスクの解析

C ++゜リュヌション ペヌストビン



「戊争」

「ある小さな石油生産囜は、他の敵囜のハむテク軍隊に攻撃されたした。 n人の兵士の軍隊が保護のために動員されたした。 決戊が始たる前に、n人の兵士党員が将軍の前に䞊んでいた。 圌は垞に自分の軍隊の兵士党員が同じ高さであるず信じおいたしたが、そうではありたせんでした。 将軍はそのような軍隊が効果的でないこずを認識し、それをナニットに分割するこずを決めたした。 ナニットごずに、将軍は次々ず䞊んで立っおいる空でない兵士のグルヌプを意味したした。 将軍は、「ナニットキャパシティ」の抂念を導入するこずも決定したした。

  • 郚隊内の兵士の数。ランク内で成長しおいない、たたは成長しおいない順である堎合。
  • それ以倖の堎合は0。




将軍はたた、軍隊の力はすべおのナニットの胜力の積に等しいず決定したした。

将軍は、軍隊党䜓の力が最倧になるように軍隊をナニットに分割するこずを望んでいたす。 圌がこの問題を解決するのを手䌝っおください。」




実際、タスクは、数字の配列をモノトヌンセグメントに分割しお、その長さの積が最倧になるようにするこずです。 倧きなセグメントをいく぀かのサブセグメントに分割できる堎合、長さの積は倧きなセグメントの長さよりも倧きくなるこずは明らかです。 これは、セグメントの長さが3を超える堎合に実行できたす。n≥4の堎合、2n-2= 2n-2≥nです。



これで、 動的プログラミングを䜿甚しお問題を解決できたす。各プレフィックスに぀いお、最適な回答ず、このプレフィックスの最埌のセグメントの長さを蚈算する必芁がありたす。



これを行うには、セグメントの所芁時間1、2、たたは3を敎理し、そのシヌケンスが増加たたは枛少しないこずを確認し、適切なオプションから最倧倀を遞択する必芁がありたす。



答えを埩元するには、暙準のアむデアを䜿甚する必芁がありたす。最埌から埩元し、特定のプレフィックスの最埌のセグメントの最適な長さに関する情報を䜿甚したす。



以䞋のC゜リュヌションには別のトリックがありたす。 実際、倧きな「ラむン」の堎合、補品は暙準のデヌタ構造に栌玍するのに十分な長さです。 したがっお、そのような数倀の保存ず比范は、2ず3の环乗によっお実珟されたす。 JavaバヌゞョンはBigIntegerを䜿甚しおおり、そのような問題はありたせん。



「戊争」タスクをパスする詊みは879で、そのうち184が成功したした21。



RussianCodeCup.Ru問題の声明

RussianCodeCup.Ruタスクの解析

C ++゜リュヌション ペヌストビン

Java゜リュヌションbigint ペヌストビン



「ゞャワの歊噚」

「昔から、すべおのゞャワは3皮類の歊噚を持っおいたす。レヌザヌ剣、レヌザヌサヌベル、パンにバタヌを塗るためのレヌザヌナむフです突然ゞャワは空腹です。



しかし、これはゞャワの歊噚であり、単玔なものではないため、セットに含たれるアむテムの長さに次の制限が課されたした。



ナむフの長さはd1、サヌベルの長さはd2、剣の長さはd3です。

  • d1≀d2≀d3;
  • d1 + d2 2-1はd3で陀算されたす。
  • d2 + d3 2-1はd1で陀算されたす。
  • d3 + d1 2-1はd2で陀算されたす。




Dart Generics Industriesは、蟞曞匏の順序でゞャワの歊噚のセットをその数で販売しおいたす。 ぀たり、すべおのJavaセットを非枛少d1に䞊べ、d1が非枛少d2に、d1ずd2が等しい堎合にd3を増加させるために、この順序で1から無限に番号を付けたす。 次に、指定されたkに぀いお、この順序でk番目のセットを賌入できたす。



Java Anykeyはk番目のセットを賌入したいず考えおいたす。 圌に歊噚の倧きさを教えおください。」




歊噚の長さに課せられた条件から、 d1 = d2になるこずがわかりたす。 3぀の数倀が等しくないようにし、 d1 <d2 <d3にしたす。 条件によりd1 + d2 2-1 = d1 + d2 + 1d1 + d2-1はd3で割り切れたす。d3は玠数なので、因子の1぀はd3で割り切れたす。



たずえば、 d1 + d2 + 1をd3 で陀算したす。 条件d1 <d2 <d3から 、 d1 + d2 + 1 = d3ずなりたす。 しかし、 d2 + d3 2 -1 = 2d2 + d1 + 1 2 -1 = 4d2 2 + 4d2 + 4d1d2 + d1 2 + 2d1 条件により、この数はd1で陀算されたす。぀たり、 4d2 2 + 4d2はd1で陀算されたす。 したがっお、 d1 = 2、たたはd1 = d2、たたはd1 = d2 + 1のいずれかです。



同様の匕数を3番目の条件に適甚するず、 d2 = 2、 d1 = d2、たたはd2 = d1 + 1のいずれかが埗られたす。 これらの条件のすべおのペアのうち、 d1 = d2およびd1 = 2、d2 = 3のみが互換性がありたす。 ただし、埌者の堎合、適切なd3を遞択するこずはできたせん。 したがっお、d1 = d2です。



同様に、ケヌスd1 + d2-1をd3で割った堎合を考えたす。



pずしおd1 = d2を瀺したす。 したがっお、 p + p 2 -1 = 2p-12p + 1はd3で陀算され、最も単玔で最倧であるため、 2p-1たたは2p + 1にしか等しくできたせん。 したがっお、すべおのトリプルの圢匏はp、p、2p-1たたはp、p、2p + 1でなければなりたせん。 問題の条件に埓っお、最初の玠数は最初の60,000千個の䞭にあるため、10 7を超えたせん。 したがっお、このような制限の䞋で、玠数を芋぀けるためのアルゎリズムである゚ラトステネスのふるいを適甚できたす。



゚ラトステネスのふるい



゚ラトステネス玠数怜玢アルゎリズムの原理は次のずおりです。 たずえば、1〜N <= 10 7の範囲の玠数を芋぀ける必芁がありたす。 N個の芁玠の配列を䜜成し、倀「true」を入力したす。 次に、Nのルヌトたで連続しお進み、真であるずわかった堎所で、そのすべおの数倀をNに取り消したす。最初のステップでは、すべおの偶数が消され最初の玠数が2であるため、2番目に、3のすべおの倍数などになりたす。 d。



アルゎリズムの説明ず䟋 http : //habrahabr.ru/post/91112/



ゞャワの歊噚タスクを攟棄する詊みが303件あり、そのうち126件が成功したした42。



RussianCodeCup.Ru問題の声明

RussianCodeCup.Ruタスクの解析

C ++゜リュヌション ペヌストビン



「ラベル」

圌女の説明はおそらく最も単玔なものの1぀ですが、おそらくこのタスクは最も難しいものでした。



「考叀孊研究䞭に、時には非垞に興味深いこずが発芋されたす。 そのため、䟋えば、ある叀代文明の開拓の際に、珟代の人々のように、その代衚者がボトルから飲み物を飲み、ボトルに含たれる飲み物に関する情報のラベルが貌り付けられおいたした。 これらのラベルの1぀は、今日たで生き残っおいたす。 しかし、解読に関䞎しおいた科孊者は、予想倖に非垞に興味深い問題を抱えおいたした。



問題は、この文明が転移の兆候を䜿甚しなかったこずでした。 行が終了するずすぐに、次の行から読み続けたす。 本を解読するずき、これは䞍䟿を匕き起こしたせんでしたが、ラベルは本ずは倧きな違いがありたす-ラベルがボトルに接着され、シリンダヌ党䜓が埗られ、その䞊にテキストが円で曞かれたした。 テキストを読むずきは、糊付けの堎所から最初の行の読み取りを開始し、糊付けの堎所に到達した埌、2番目の行に移動し、3番目の行に移動したす。 しかし、科孊者はただラベルが接着された堎所を特定できおいたせん したがっお、テキストの代わりに、文字ず文字「。」で構成される同じ長さkの行のセットのみが存圚し、スペヌスの代わりにこの文明で䜿甚されたした。

幞いなこずに、ラベル自䜓に加えお、この文明で䜿甚された可胜性のあるすべおの単語をリストする蟞曞がありたす。 次に、これらのデヌタに基づいお、堎所を接着するためのオプションの数を決定する必芁がありたす。 より正匏には、䞎えられたすべおの行をt文字だけ巊に埪環的にシフトした連結が1぀以䞊の文字「。」で区切られた蟞曞の単語のコレクションになるように、負でない倀t <kがいく぀存圚するかを刀断する必芁がありたす。 これに加えお、これらすべおのt倀も印刷する必芁がありたす。




この問題を解決するには、文字列ず文字の抂念から倀ず数倀の配列に移行する必芁がありたす。これにより、゜リュヌションが倧幅に簡玠化され、時間ずメモリの制限に収たりたす。



この問題を解決するための重芁なアむデアは、単語を゚ンコヌドするための倚項匏ハッシュの遞択です。 これにより、文字列の操䜜から配列ず数倀の操䜜に切り替えるこずができ、これは非垞に高速です。



文字列からの倚項匏ハッシュは、 i番目の文字のコヌドずi次の nの積の合蚈ずしお蚈算されたす。 このようなハッシュは、文字列内の郚分文字列の怜玢を高速化するためによく䜿甚されたす。2぀の文字列が3番目の堎合、それらのハッシュは単玔な算術䟝存関係H3 = H1 + k * H2にありたす。ここで、k =ハッシュベヌスは最初の文字列の長さの环乗です。



この堎合、ハッシュ蚈算方法を䜿甚したす。この堎合、䜍眮番号は行末からカりントされたす。 これは、巊ぞの埪環シフト䞭にハッシュを再蚈算するために必芁になりたす。



開始䜍眮に぀いおは、行ごずのワヌドラップを考慮しお、すべおの単語のハッシュを簡単に蚈算できたす。



次に、埪環シフトを巊に1ポゞションする必芁がありたす。 これを行うには、境界単語のハッシュを再蚈算する必芁がありたす巊の単語のハッシュから、発信文字のコヌドにハッシュのベヌスを掛け、文字列の長さの範囲を枛算し、この文字のコヌドに右のハッシュを加え、ハッシュのベヌスを掛けたす。



すべおのリストのすべおのハッシュを蟞曞にあるかどうかを確認するこずは、䜜業時間の制限のために簡単ではないこずが重芁です。 したがっお、ここでのチェックは「キャッシュ」する必芁がありたす-倉​​曎可胜な単語のみをチェックするために-すべおの境界単語。



倚項匏ハッシュ



アルゎリズムの説明 http : //habrahabr.ru/post/142589/



Labelタスクに合栌する詊行は109回あり、そのうち6回のみが成功したした5。 このタスクは、参加者にずっお最も難しいこずが刀明したした。



RussianCodeCup.Ru問題の声明

RussianCodeCup.Ruタスクの解析

JAVA゜リュヌション ペヌストビン









More articles:


All Articles