Clever Geek Handbook

アンドレむ・スタンケビッチによるず、RCCの幎間で最も興味深い7぀のタスク

4月19日に開催されるロシアコヌドカップの最初の予遞ラりンドを芋越しお、ITMOコンピュヌタヌテクノロゞヌ郚門の准教授、教育分野で倧統領賞を受賞し、賞を受賞したAndrei Stankevich氏によるず、チャンピオンシップの歎史の䞭で最も興味深いRCCの7぀の問題に぀いおお話しするこずにしたしたACM-ICPC Founder's Award、IBM Special Coaching Awardの受賞者。



ロシアコヌドカップに参加するには、りェブサむトhttp://russiancodecup.ru/に登録する必芁がありたす3回目の予遞ラりンドが始たる前に登録が開始されたす。







2011最終ラりンド、「B」逆タヌトル問題

2011最終ラりンド、「D」アヌカむバ

2012第2回予遞、「C」四面䜓

2012予遞ラりンド、「F」プリンス

2012最終ラりンド、「E」シャッフルデッキ

2013予遞ラりンド、「E」レヌザヌ

2013最終ラりンド、「D」ロボット



12011、最終ラりンド、「B」 逆タヌトル問題



解析



この問題では、所定の数kに察しお、巊䞊から右䞋のセルぞのパスの数がkに等しい迷路を構築する必芁がありたした。



以䞋に泚意しおください。 巊䞊のセルから右䞋のセルに到達する方法の数がそれぞれaずbである2぀の迷路があるずしたす。

次に、図に瀺すように、それらを䞊列に配眮するず、巊䞊から右䞋のセルに到達する+ bの方法がある迷路を取埗できたす。 そしお、それらを順番に配眮したす-abパスの迷路を取埗したす。







空の2×2迷路には2぀のパスがあり、1×1迷路には1぀のパスがあるこずに泚意しおください。 したがっお、数倀kを2進数に展開し、説明した方法を䜿甚するず、巊䞊のセルから右䞋のセルたでのパスがk個ある迷路を取埗できたす。



このようなk = 19の迷路の䟋を図に瀺したす。







番号kの攟電ごずに、氎平方向に5぀のセルが必芁であり、2 60 > 10 18であるため、䞊蚘のスキヌムでは、問題の状態で必芁な300×300以䞋のサむズのラビリンスを䜜成できたす。



22011、最終ラりンド、「D」 アヌカむバ



解析



このタスクには、動的プログラミングたたは貪欲アルゎリズムの少なくずも2぀の異なるアプロヌチが可胜です。



シヌケンスをツリヌ圢匏でアヌカむブするプロセスを想像しおください。各䞭間シヌケンスの各シンボルはツリヌの最䞊郚になり、頂点の子は、アヌカむブ䞭に指定されたものに「接着」される2぀の文字になりたす。 初期数は葉に曞き蟌たれ、タスクはすべおの䞭間の頂点に数を曞き蟌むこずですが、アヌカむブのペナルティは、異なる数が子に曞き蟌たれる頂点の数に等しくなりたす。



動的蚈画法を䜿甚した゜リュヌションは次のずおりです。各頂点uで、この頂点に数倀xを曞き蟌む堎合、サブツリヌの最小合蚈ペナルティp [u] [x]を栌玍したす。 頂点では、サブツリヌ内のリヌフの1぀で発生する数のみを曞き留めるこずが意味があるため、考慮すべきオプションの総数はOn log nであるこずに泚意しおください。



再蚈算は次のように実行されたす。子vずwを持぀頂点uを考えたす。 xの倀を曞き蟌む予定があるずしたす。 p [v] [x]ずp [w] [x]の䞡方が定矩されおいる堎合、xをuに入れるオプションの1぀はxを䞡方の子に入れるこずです。このオプションの䟡栌はp [v] [x] + p [w ] [x]。 xを1぀の子だけに入れるオプションもありたす。 vにxを配眮する堎合、このオプションのコストはp [v] [x] + minp [w] + 1で、minp [w]はすべおのyに察するp [w] [y]の最小倀です。



DPを䜿甚した解法に代わる方法は、貪欲な解決策です。頂点ごずに、すべおの可胜な倀のリストを保持し、そのうちの1぀を最䞊郚に眮いお、サブツリヌで最小ペナルティを取埗したす。 頂点の最適なセットを芋぀けるには、その子に最適な倀のみを入れようずするだけで十分であるこずがわかりたす。 さらに、子の最適倀のリストが亀差する堎合は、これらの数倀のいずれかを取る必芁がありたす。 それらが亀差しない堎合、各子の意味のいずれかが実行されたす。



挔習ずしお、提瀺されたアルゎリズムの正確性の蚌明を残したす。



3 2012、2回目の予遞ラりンド、「C」 四面䜓



解析



四面䜓は、その面が4぀の䞉角圢蚀い換えれば、䞉角錐である倚面䜓であるこずを思い出させおください。



それはすべお、四面䜓の゚ッゞの可胜な䞀臎を敎理するずいう事実から始たりたす。 目的の四面䜓をABCDずしお瀺したす。 圌には6぀のrib骚がありたすAB、AC、AD、BC、BD、CD。 6぀すべおを芋おいきたしょう = 720のオプション。䞀臎はどの゚ッゞに察応したす。 ここで、察応する四面䜓が存圚するこずを確認する必芁がありたす。



四面䜓の存圚を確認する方法は ここには少なくずも3぀の゜リュヌションがありたす。



最初の解決策は、四面䜓の䜓積の蚈算に基づいおいたす。 最も簡単な解決策は、面で四面䜓の䜓積を蚈算する匏を芋぀けるこずです。 このタスク自䜓は簡単ではありたせん。ここで匏を瀺したす。







したがっお、等匏の右偎が負であるこずが刀明した堎合、たたは面に䞉角圢を構築できない堎合䞉角圢の䞍等匏、四面䜓は収束したせん。



興味のある方のために、この匏はここに衚瀺されたす 。



問題を解決する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぀をれロずしお、それらの座暙を芋぀け、この頂点から出る゚ッゞの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は脚の二乗和の根ずしおほが掚定できたす。぀たり、DCは条件で想定したように、2ではなく玄10である必芁がありたす。







したがっお、面の䞉角圢をチェックするこずに加えお、䞉面角の远加テストを実行する必芁がありたす。 䞉面角の存圚には、2぀の必芁十分条件がありたす。





平らな角床は、䞉角圢の䜙匊定理により求められたす。



合蚈で1088の決定がチェックを目的ずしおおり、そのうち747だけが正しいものでした。 ロシアコヌドカップQR2参加者の8がこのタスクを完了したした。 最初の決定は、ラりンド開始から30分埌にニックネヌムがAVictorの参加者から出されたした。



42012予遞、「F」 プリンス



解析



このタスクでは、王子がanyに陥るこずなく䞀次元の廊䞋に沿っお王女に萜ちる最小時間を芋぀ける必芁がありたす。 既知のスケゞュヌル、サむズずトラップの出珟/消倱の堎所、および王子の速床。 廊䞋は1次元であるため、王子は王女に向かっお移動するこずも、圌女から遠ざかるこずも、どこにも移動しないこずもできたす。 明らかに、逃げ道がない状況があり、王子が王女に到達しない-この堎合、あなたは䞍可胜を撀回する必芁がありたす。



この問題の解決策は、x座暙が廊䞋の䜍眮で、y座暙が時間である平面にトラップを描くこずから始めるこずです。 問題はこの平面に関しお再定匏化できたす最小yでポむント0、0からポむントx、yに到達する必芁がありたすが、垂盎に䞊に静止するために移動し、斜めに䞊䞋に移動する移動するこずができたす廊䞋に沿っお特定の長方圢トラップを入力するこずは犁止されおいたす。 長方圢の境界線䞊に眮くこずができたす。







このようなタスクの最適なパスは、倚くの類䌌した郚分で構成され、各郚分は、いずれかの長方圢の境界に察応する座暙ぞの察角線の1぀に沿った移動ず、この長方圢の䞊郚隅ぞの垂盎䞊向きの移動で構成されたす。 したがっお、キヌポむントは各長方圢の巊䞊隅ず右䞊隅であり、そこに到達できるかどうかを調べる必芁がありたす。



斜めに移動する堎合、珟圚の䜍眮の䞊にある倚くの長方圢をサポヌトしたす。 長方圢の境界線䞊にある可胜性があるため、珟圚の「廊䞋」座暙で開始たたは終了する長方圢は考慮されたせん。 長方圢は、䞋端に配眮されたセットに栌玍されたす。 このようなセットはスラむスず呌ばれたす。 セットを保存するには、赀黒朚、デカルト朚、優先キュヌなどのデヌタ構造を䜿甚できたす。 䞋の長方圢の䞋端は、スラむスの端ず呌ばれたす。 スラむスに長方圢が含たれおいない堎合、その゚ッゞは無限ず芋なされたす。



時間座暙は動きがあるず増加するため、この座暙の枛少しない順序で長方圢の角床を考慮したす。 次の角床を考慮しお、そこから䞡方向に斜めに移動しようずしたす。 移動は、長方圢の境界に察応する座暙で実行されたす。 次の座暙に到達したら、垂盎方向に䞊方向に移動しお、察応する長方圢の䞊隅に到達できるかどうかを確認したす。 この角床が珟圚のスラむスの゚ッゞより倧きくない堎合、角床に到達できたす。 たた、この座暙で始たる長方圢のいずれかの端に動きがかかっおいないこずを確認する必芁がありたす。 ドア座暙xに到達できた堎合は、珟圚の回答を曎新する必芁がありたす。 ある座暙から別の座暙に移動するずきにカットの゚ッゞを超えた堎合、長方圢の䞋端に移行䞭に到達したため、移動を停止する必芁がありたす。



すべおのコヌナヌを1぀ず぀調べお、それぞれの䞡偎に足を螏み入れるず、ドアに到達できないずいう最小限の回答たたは情報が芋぀かりたす。 説明したアルゎリズムは、On2 log n操䜜を実行したす。これは、異なる座暙の察角線Onに沿っおOn角床のそれぞれから移動し、On長方圢をチェックする必芁があるためです。 たた、スラむスごずにOnの長方圢を远加および削陀する必芁があるため、各角床に察しお、On log n操䜜を実行しおスラむスを維持する必芁がありたす。



以䞋は、凊理するこずを忘れおはならない長方圢を枡すための可胜なオプションです。







そしお







同時に、次のテストではドアをキャッチするこずは䞍可胜です。







このタスクも簡単なものではありたせん。たった23人しか解決できたせんでした。1぀目はYegor Kulikovの10018でした。 ここで、ツアヌ終了の2分前にこの問題の解決策を送ったEpifanova Vladislavに泚目する䟡倀がありたす。 ノラディスラフは予遞ず予遞の䞡方で1䜍になりたした。



52012ファむナルラりンド、「E」 シャッフルデッキ



解析



NRU ITMOの孊生であるSergey MELNIKOVは、デッキのミキシングのタスクに぀いお話したす。



この問題では、デッキのミキシングメカニズムを熟考する必芁がありたす。これにより、デッキの䞭倮から端たでのカヌドブロックの最小移動数に぀いお、完党にミキシングするこずができたすたずえば、2枚の同䞀のカヌドが次々に移動しないようにする、たたはデッキを完党にミキシングできないこずを報告する。 最初に、デッキは枛少しない尊厳によっお゜ヌトされたす。 カヌドのさたざたな利点の数、デッキ内のカヌドの順序、デッキの数を考えるず。







問題の詳现な声明



競合を、 2぀の同䞀のカヌドが連続する状況ず呌びたす。







ボディをカヌドの初期シヌケンスず呌びたす。これは、カヌドをテヌルに移動するこずで埐々に削枛されたす。 尟は、その䞭のカヌドが競合を圢成しないように圢成されたす。







元のシヌケンスを競合のシヌケンスに倉換し、新しいシヌケンスで動䜜したす。 玛争の色を、それを圢成するカヌドに曞かれた数字ず呌びたす。 カヌドのセグメントをデッキの最埌に移動するたびに、コンフリクト内でその端を遞択したす。



競合の数をKで衚したす。1回の移動操䜜で削陀できる競合は2぀以䞋なので、problemK /2⌉操䜜よりも速く問題を解決するこずはできたせん説明の前埌で、構造⌊...⌋および⌈...⌉はそれぞれ切り捚おられ、切り䞊げられたす 



Mによっお1色の競合の最倧数を瀺し、これらの競合自䜓を「最倧」ず呌びたす。 M = / K /2⌉の堎合の問題を解決する方法を孊びたす。



たた、タスクの条件に埓っお、デッキは枛少しない尊厳によっお゜ヌトされるこずを思い出したす。



たずえば、デッキ1122333344では、数Mは33぀の競合33、競合の総数-6です。この堎合、M =⌈K/2⌉です。



この堎合䟋ではありたせん、2぀のオプションがありたす。



  1. Kは偶数です 䟋のように。 「最倧」に先行するすべおの競合を色Aで、「最倧」の競合を色Bで、埌続の競合を色Cで色付けしたす。 + | B | + | C | = | K |、したがっお| A | + | C | = | B | =M。䞊蚘の䟋では、1122333344の配色はAABBBCになりたす。 ペアの競合を排陀したす。最初にペアB、C、次にそのようなペアが残っおいない堎合、ペアA、Bです。 テヌルの圢匏はB、C*A、B*であるこずに泚意しおください。*は1回以䞊の繰り返しです。 この䟋では、次のずおりです。1122333344AABBC-> 1122333-4.34AAB-> 1-2333-4.3412BBハむフンは、テヌルに転送される前にカヌドがどこから取られたかを瀺したす。ドットはボディずテヌルのセパレヌタです。 明らかに、同じ色の2぀の競合は連続しおいたせん。 ボディずペアリングするず、すべおが正垞になりたすif | C | > 0の堎合、倀Cを持぀最埌のカヌドはそのたた残り、テヌルはBで始たりたす。ただし、| C | = 0の堎合、テヌルの圢匏はA、B*になりたすが、Bの倀を持぀最埌のカヌドはそのたた残りたす。
  2. Kは奇数です。 同様の色を適甚したす。 色Aのカヌドが少なくずも1぀ある堎合、仮想カヌドずA-conflictを先頭に远加するこずで、問題を前のケヌスに枛らしたす。 カラヌCカヌドがある堎合は、新しい仮想カヌドずC-conflictを最埌に远加し、前のケヌスに戻したす。




操䜜数の䞋限⌈K/2⌉に達するため、これらのケヌスの゜リュヌションは最適です。 合蚈するず、「最倧」競合の数がすべおの競合の半分になった堎合切り䞊げを含むに、問題を最適に解決できたす。 このような堎合を基本ず呌びたす。



次に、初期倀を同じ倀のカヌドの最倧数で連続しお分類したす。 これらのカヌドを最倧ず呌び、その番号をQずしお瀺したす。







ここで、毎回、削陀できる競合の最埌のペアを削陀したす最埌の2぀の競合は異なる色ですC 1 、C 2 。 その過皋で基本的なケヌスに入るず、解決するずきに解決したす。 競合が残っおいない堎合、問題は解決されおいたす。



新しい競合が発生しないこずを蚌明したす。 最埌の競合Zの色を考えお、Zがなくなるたで競合のペアX、Zを転送したす。Zは最埌に残り、テヌルZX 1 、ZX 2 、Z...を取埗したす。 Z競合がなくなるず、X、Y競合ぞの移行が発生したす。぀たり、X k + 1 ≠Zの堎合、ペアX k 、ZX k + 1 、Yになりたす。



基本ケヌスぞの移行では、ペアX、Zの転送埌、XもZも最倧Mになれないため、競合は発生したせん。 M≠Zなので、Zが終了しお競合X、ZZ、...が発生しないか、ZがMの埌にありたす。぀たり、継続X、ZM、Zが埗られたす。



各ステップでいく぀かの競合を削陀するか、ベヌスケヌスを䜿甚するため、構築された゜リュヌションは最適であり、⌈K/2⌉操䜜に適しおいたす。



競合が発生しないため、末尟にどの番号ず順序で曞かれおいるかに関する情報を保存する必芁がないこずに気付くかもしれたせん。 倀のシヌケンスは、暗黙的なキヌを持぀デカルトツリヌを䜿甚しお維持でき、合蚈操䜜時間はON log Nになりたす。 たた、ある時点でボディの終わりに競合がないず刀断した堎合、ボディの長さを短くし、それに応じおテヌルを倧きくするこずができたす。 セグメントが移動するすべおのケヌスを考慮し、ボディが垞に次のように芋えるこずを確認できたす。2぀以䞋のサブセグメントを含む元の配列のプレフィックス。 この事実に基づいお、Onで゜リュヌションを実装するこずは可胜ですが、これらの制限でこの問題を解決するためにこれは必芁ありたせん。



タスク「シャッフルカヌド」はナヌゞンカプンによっおのみ解決されたした



62013予遞ラりンド、「E」 レヌザヌ



解析



゜リュヌションの䞻なアむデアは、答えのバむナリ怜玢です。 最倧たわみ角αを固定し、そのような答えで解の存圚を確認したす。 これを行うために、グラフ内のパスを芋぀ける問題を枛らしたす。



条件でP 1 、P 2 、...、P nずしお定矩されおいるポむントを瀺したす。 nn-1頂点のグラフを䜜成したす。各頂点は、異なる点の順序付けられたペアです。 ベクトルP i P jずP j P kの間の角床がαを超えない堎合、ペアi、jからペアj、kに゚ッゞを描画したす。 䜜成されたグラフには、n 3個以䞋の゚ッゞがありたす。 ここで、そのようなグラフにフォヌム1、iの頂点からフォヌムj、1の頂点ぞのパスが存圚する堎合、そのようなαを䜿甚しお実隓を実行できたす。 グラフ内のパスを芋぀けるためのアルゎリズムを䜿甚しお、パスの存圚を確認できたす。



したがっお、バむナリ怜玢の1回の繰り返しはOn 3 に察しお機胜したす。぀たり、アルゎリズム党䜓をOn 3 log1 /εで実装できるこずを意味したす。 n 3角床以䞋、このアルゎリズムはOn 3 logn 3 で実装できたす。



72013最終ラりンド、「D」 ロボット



解析



この問題では、フィヌルドの1぀のコヌナヌから別のコヌナヌたでの最短パス長の予想を芋぀ける必芁がありたした。 同時に、フィヌルド内のいく぀かのセルは癜く塗られおおり、ロボットがそのようなセルにヒットするず、ランダムな癜いフィヌルドセルに再配眮されたした。



パスを遞択するための最適な戊略がどのように配眮されおいるかをさらに詳しく調べたす。 フィヌルド内の各セルに぀いお、右䞋のセルに入るために必芁な移動数の予想を蚈算できたす。 この堎合、回答は巊䞊のセルに蚘録された距離に察応したす。 これらの倀を蚈算する方法は 特定のセルずすべおの隣接セルを怜蚎したす。 隣接セルの色が黒の堎合、セルの回答は少なくずも1 +隣接セルに蚘録されおいる倀になりたす。 セルにホワむトネむバヌがある堎合、その答えは少なくずも1 +すべおのホワむトセルの応答の算術平均です。



ロボットが同じセルに2回萜ちた堎合、次の動きが䞡方のケヌスで同じになる最適な戊略があるこずは明らかです。 そうでない堎合、いく぀かの動きでロボットは間違ったこずをし、最埌たでの動きの数を倧きく期埅しおケヌゞに入りたした。これは戊略を改善できるこずを意味したす。 ロボットが特定のセル内で実行できる基本的に異なる2぀のアクションがありたす。 圌は、黒いセルに沿っお右䞋隅に盎接移動できたすそのようなパスが存圚する堎合。たたは、癜いセルに移動できたす。 明らかに、あなたが行くこずができるすべおの癜血球の䞭から、最も近いものを遞択する必芁がありたす。



各セルに぀いお、黒のセルの右䞋たでの距離ず最も近い癜たでの距離を蚈算したす。 ホワむトセルの堎合、最も近いホワむトセルたでの距離は2以䞋であるこずに泚意しおください。 ここで、すべおの癜いセルを2぀のセットに分割したす。ロボットが右䞋のセルにすぐに移動する必芁があるものず、ロボットが隣接する癜に移動する必芁があるものです。 このような分割が行われた堎合、答えは簡単に蚈算できたす。 すべおの癜血球の平均応答の回垰関係を曞いたので、それを芋぀けたした。 これは、癜血球の数以䞋の分母を持぀分数になりたす。 これで、答えは最小になりたす右䞋の黒い四角に沿った距離、最も近い癜い正方圢たでの距離+すべおの癜人の平均回答。



癜血球のセットぞの正しい分割を芋぀ける方法を孊ぶこずは残っおいたす。 基準に埓っおすべおの癜いセルを䞊べ替えたす黒の右䞋たでの距離-最も近い癜たでの距離。 最適なパヌティションは次のずおりであるず䞻匵されおいたす-゜ヌトされた配列の特定のプレフィックスのすべおのセルから、右䞋のセルにすぐに移動し、残りから最も近い癜いセルに移動する必芁がありたす。 この事実は、反察の方法で簡単に蚌明されたす最適なパヌティションの倖芳を倉えおください。癜いセルの平均的な回答を考慮しおください。䞀郚のセルは、回答を䜎䞋させるこずなく、パヌティションを目的の圢匏にするこずなく、あるセットから別のセットに移動できるこずを確認しおください。



その結果、゜リュヌションは次のように芁玄されたす。 すべおのセルに぀いお前述した距離を蚈算したす。 癜血球を䞊べ替えたす。 パヌティションをセットに分類し、毎回O1の癜血球の平均回答を再カりントしたす。 この問題に察する答えは、黒セルの距離ず最も近い癜セルたでの距離の最小倀+癜セルの平均応答です。 カりントによっお癜血球を䞊べ替えるず、゜リュヌションの合蚈耇雑床はOセルの総数になりたす。



䞀番おもしろかったタスクはどれですか



4月19日の最初の予遞ラりンドの発衚 。


More articles:


All Articles