Geekly Articles each Day

ロシアコヌドカップ2015の結果ず決勝戊の分析



9月19日土曜日、RCC 2015の最終ラりンドが開催され、2011幎ず2013幎にRCCカップで2回優勝したPeter Mitrichevが300,000ルヌブルの䞻賞の勝者および勝者になりたした。 2䜍ず賞金150,000ルヌブルは、昚幎のRCCの優勝者であるGennady Korotkevichが受賞したした。 昚幎ず同様、3䜍はむゎヌルクリコフが獲埗したした。 圌の賞金は90,000ルヌブルでした。 たた、パベル・マリン、りラゞスラフ・゚ピファノフ、セルゲむ・コペリオノィッチ、ナヌリ・ピサルキク、コンスタンチン・セメノフ、ミハむル・チホミロフ、ニコラむ・カリヌニンの4〜10か所に参加した参加者から賞金30,000ルヌブルが授䞎されたした。

ラりンドのヒヌロヌ


先ほど申し䞊げたしたように 、今幎のファむナルはITチャンピオンシップ独自の圢匏で開催されたした。4時間のオンラむンショヌがWebサむトで攟送されたした。 このむベントは、ロシアの人気ショヌマン、アントン・コモロフモスクワバりマン工科倧孊の卒業生ずサラトフ州立倧孊のプログラマヌトレヌニングセンタヌ、ミハむルミルザダノフが生䞭継したした。 スタゞオのゲストは、ロシア連邊のテレコムおよびマスコミュニケヌションの倧臣であるニコラむニキフォロフ、倧手IT䌁業の代衚者、䞻芁な業界専門家でした。 攟送蚘録はhttps://it.mail.ru/rcc/で芋るこずができたす 。

それでは、タスクの分析に移りたしょう。

タスクA. リボンの曲げ


アむデアりラゞミヌルスミカロフ
実装 Dmitry Filippov
分析ドミトリヌフィリッポフ

この問題では、1×2 nのストリップが䞎えられたす。最初にnが正確に半分に折り畳たれ、次に折り返されたした。 折り畳みには2぀の方法がありたす。巊半分を右に眮くか、右半分を巊に眮くかです。 リク゚ストに応答するために必芁ベンドの数によっお、それが䞊向きか䞋向きかを調べたす。

Olog 2 n 、぀たりO n の芁求に応答する方法を孊習したす。 リク゚ストの総数は10 5を超えないため、これで十分です。 各リク゚ストの曲げプロセスを゚ミュレヌトしたす。 珟圚のリボンの長さず曲げ番号がわかれば、この番号がどちらの半分にあるかが簡単にわかりたす。次に、どちら偎で半分に曲げが行われるかがわかり、2回切断されたリボンの新しい曲げ䜍眮を芋぀けるこずもできたす。 リク゚ストに答えるために、折り目が珟圚どの方向に向いおいるのかを同時にサポヌトしたす。 合蚈、O qn で解を取埗したす。ここで、 qはク゚リの合蚈数です。

タスクB. コむンの収集


アむデア Vitaly Aksenov
実装 Boris Minaev
分析ボリス・ミナ゚フ

タスクには、プレむダヌが歩くためのセルに分割されたテヌプが䞎えられたす。 毎秒、各セルには、各セルに固定された䞀定数のコむンが衚瀺されたす。 プレヌダヌは、次のセルにすぐに移動するか、珟圚のセルにずどたるこずができたす。 プレむダヌが特定のセルにいるたびに、その䞭にあるすべおのコむンを収集したす。 プレヌダヌがt秒以内に収集できるコむンの最倧数を蚈算する必芁がありたす。

各セルに぀いお、プレむダヌがそのセルにいた最埌の瞬間のみを知るこずが重芁であるこずに泚意しおください。 プレむダヌの最埌からの道を考えおください。 セルの特定の連続したセグメントに぀いおの各瞬間に、圌らの蚪問の最埌の瞬間はすでに知られおいたすが、他のセルに぀いおはそうではありたせん。 したがっお、動的プログラミング方法を䜿甚できたす。この方法の状態は、蚪問したセルのセグメントず珟圚の時刻になりたす。 さらに、プレヌダヌの珟圚の䜍眮を保存する必芁がありたす。 プレヌダヌが蚪問枈みセルのセグメントの䞀端に立っおいる堎合にのみ、これらの䜍眮を保存できるこずに泚意しおください。 各状態からの遷移は2぀たでです。プレヌダヌは、既に蚪れたセルの巊たたは右のセルに蚪れるこずができたす。 したがっお、アルゎリズムの実行時間はO n 2 t です。

問題C. トポロゞカル゜ヌトず子


アむデア Artem Vasiliev
実珟 Vitaliy Aksyonov
分析ノィタリヌ・アクショノフ

問題では、いく぀かの芁玠が削陀されたグラフずそのトポロゞカル゜ヌトが䞎えられたす。 トポロゞカル゜ヌトを正しく埩元する必芁がありたす。

最初にアルゎリズムを怜蚎し、次にその正圓性を蚌明したす。 順序が䞎えられる頂点はラベル付き、残りはラベルなしず呌ばれたす。 トポロゞカル゜ヌトで䜿甚されなかった数字はわかっおいたすが、最倧の頂点から最小の頂点たで1぀ず぀公開したす。 別の歪みのない数倀がありたす。 たず、すでにマヌクされおいるすべおの排氎管を削陀したす。 次に、ラベルなしの各流出に぀いお、逆゚ッゞから到達可胜なラベル付き頂点の最倧倀を芋぀けたす。 各頂点に぀いお、この数は事前に蚈算できたす。グラフのトポロゞカルな䞊べ替えを芋぀けお、動的プログラミングの問題を解決したす。 歪みのない数倀の察応する頂点ずしお、蚈算された最倧の数倀を持぀シンクを遞択し、グラフから削陀したす。

数倀の事前蚈算はO V + E で実行されたす。 各反埩は可胜な限り迅速に実行する必芁がありたす。したがっお、各頂点には、そこから残っおいる出力゚ッゞの数を栌玍したす。 シンク、そこに゚ッゞがあるすべおの頂点を削陀するず、出力次数は枛少し、この次数がれロになったら、この頂点をセットの蚈算倀に配眮したす。 したがっお、すべおのストックはセットに保存され、必芁なものを遞択するには、セットから最埌の頂点を取埗するだけです。 各頂点はセットに入れられ、䞀床だけ匕き出されたす。 アルゎリズムの合蚈実行時間O V・log V + E 。

ここで、アルゎリズムの正確性を蚌明したす。 アルゎリズムの最初のステップが正しいこずを蚌明するだけで十分であるこずに泚意しおください。その埌、数孊的垰玍法を䜿甚したす。 マヌクされたすべおのシンクを以前に砎棄した、正しく蚭定されたトポロゞカル゜ヌトpを考えたす。 次に、最倧数のアルゎリズムで遞択したシンクsず、トポロゞヌ゜ヌトpでそれに察応するシンクを怜蚎したす。 順列の倧きなpsのすべおの数を1぀枛らし、遞択した最倧数sを䞎えるず、順列は正しいたたです。 操䜜は正しく行われたしたラベル付けされおいない頂点のトポロゞカル゜ヌトプロパティを保持し、ラベル付けされた頂点に぀いおは、頂点遞択プロパティspsがラベル付けされた頂点のトポロゞカル゜ヌト倀よりも倧きいため、トポロゞカル゜ヌトの倀は倉曎されたせんでした。

タスクD. 右の庭


アむデア Artem Vasiliev
実装 Artem Vasiliev
分析アルチョム・ノァシリ゚フ

この問題では、平面䞊の点のセットが䞎えられ、 適切な点のセットの抂念が導入されたす。 優れた点のセットは、座暙軞に平行で、䞎えられた点で角床が反察の非瞮退長方圢に、このセットからの少なくずも1぀の他の点が境界内たたは境界に含たれる点のセットです。 特定のポむントセットにこのプロパティがあるかどうかを確認する必芁がありたす。

たず、同等のプロパティを蚌明したす。ポむントのセットは、このような長方圢の各コヌナヌにこの角床に隣接する蟺にポむントがある堎合にのみ適切です。 明らかに、このプロパティが満たされるず、タスクの条件に蚘述されたプロパティも満たされたす。 ただし、反察方向の結果も同様です。点AずBに角床を持぀任意の長方圢を考えたす。 仮定により、この長方圢の内偎たたは境界にセット内に別のポむントがありたす。これをCず呌びたしょう。 この点が既にAに隣接する偎にある堎合、ステヌトメントはtrueです。 それ以倖の堎合は、ポむントAずCで構築された長方圢を考えおください。その面積は元の長方圢の面積よりも厳密に小さく、セットには有限数のポむントがありたす。い぀かAに隣接する偎にあるポむントを遞択したす。

定匏化されたプロパティは解に到達するのに圹立ちたす。点 x i 、y i に぀いお、䞎えられた集合に点 x、y i が存圚するように、 å·Šiに最倧x <x iを瀺したす。 この倀が定矩されおいない堎合、マむナスの無限倧に等しいず芋なしたす。 同様に、倀i 、 down i 、 up iを導入したす。 領域 å·Ši 、 右i × 例i 、䞊i を考えたす。 この領域に指定されたセットから別のポむントがある堎合、構築された長方圢がプロパティに違反する2぀のポむントを芋぀けるこずができたす。 この領域のすべおのポむントが適切であるわけではないこずに泚意しおください。 2番目のポむントは垞に適切です。たずえば、ナヌクリッド距離たたはマンハッタン距離に最も近い点です。 この領域にポむント x i 、y i のみがある堎合、すべおの長方圢には、それに隣接する偎に別のポむントが含たれたす。 したがっお、解決策は、内郚に耇数のポむントが存圚するかどうかをn個の長方圢でチェックするこずに芁玄されたした。

平面䞊の長方圢内のポむント数をカりントできるデヌタ構造を䜿甚しお、このようなチェックを実装できたすセグメントの2次元ツリヌオンラむン゜リュヌションたたはスキャン盎線ずセグメントの1次元ツリヌを䜿甚したオフラむン゜リュヌション。 このような゜リュヌションは、O n log n で実装できたす。

タスクE. Interfluve


アむデア Vitaly Aksyonov
実装むリダ・ズバン
分析むリダ・ズバン

この問題には、 n個の単調な砎線ず凞倚角圢が含たれおいたす。 各ポリラむンに、適甚されたポリゎンのいずれか境界䞊たたはポリゎン内ずの共通点が少なくずも1぀あるように、ポリゎンをアタッチする必芁のある最小回数を調べる必芁がありたす。

倚角圢は凞であり、砎線は単調で亀差しないので、次の事実が真であるこずに泚意しおください倚角圢が砎線i、kず亀差する堎合、i≀j≀kのようなjに぀いお 、この倚角圢はj番目の砎線ずも亀差したす。 この事実を䜿甚しお、問題を熱心に解決したす1番目からi 1番目たでのすべおの砎線ず亀差するポリゎンが存圚する最倧i 1を芋぀け、それを答えに远加し、続けたすポリゎンが存圚する最倧i 2を芋぀けたすi 1 + 1からi 2たでの砎線をカバヌしたす。 䜿甚する必芁があったポリゎンの数が答えになりたす。

ç Žç·ši kに぀いお孊習し、倀i k + 1 を芋぀けたす。 これは、 i k + 1番目ずi k + 1番目のポリラむンをカバヌするポリゎンが存圚する最倧むンデックスです。 たず、より単玔な問題を解決したす。ポむントAずセグメントBCがありたす。このポむントずセグメントのいく぀かのポむントの䞡方を含むポリゎンが存圚するかどうかを確認する必芁がありたす。 これを行うには、このポリゎンずそれ自䜓のミンコフスキヌ和を、0、0に関しお反転したす぀たり、笊号が反察のすべおの点の座暙を䜿甚。 これはいく぀かの新しいポリゎンです。O n 頂点を持ち、その䞭にポむント0、0を含むPず呌びたしょう。 ポむント0、0がポむントAに移動するようにシフトし、セグメントBCがシフトされたポリゎンPず亀差するこずを確認したす。これが必芁十分条件であるこずを確認するのは簡単です。

ポむントずセグメントを亀差するポリゎンが存圚するかどうかを確認するために、2぀のポリゎンで同じこずを確認するこずは難しくありたせん1本の折れ線䞊のセグメントを反埩し、ポリゎンPでミンコフスキヌ和を䜜成し、新しい凞ポリゎンが2番目の折れ線の䞀郚ず亀差するかどうかを確認したす。

kをすべおの砎線䞊の頂点の総数ずしたす。 䜿甚する操䜜の挞近的挙動を芋぀けたす-O n でポリゎンPを構築し、O n でミンコフスキヌ和Pおよび折れ線のセグメントを構築し、Olog n で凞ポリゎンずセグメントの亀差を確認したす。 ポリゎンは最倧kで構築する必芁があり、最悪の堎合、各ポリゎンは各セグメントず亀差する必芁があるため、実行時の結果の挞近的な動䜜はO nk + k 2 log n です。

問題F. 朚の䞊のロボット


アむデア Boris Minaev
実装 Boris Minaev
分析ボリス・ミナ゚フ

この問題では、n≀10頂点の無向朚が䞎えられたす。 各rib骚は、その匷床wiが15を超えないこずが知られおいたす。ロボットは、最初はランダムな頂点にある朚の呚りを動きたす。 毎回、ロボットは同様に、通過できる゚ッゞから゚ッゞを遞択し、それに沿っお移動したす。 ロボットが゚ッゞに沿っお通過するたびに、その匷床は1぀枛少したす。 匷床がれロになるず、rib骚は陀去されたす。 ロボットに远埓できるrib骚がない堎合、停止したす。 ロボットの経路長の数孊的期埅倀を蚈算する必芁がありたす。

たず、より簡単な問題を解決したす。 経路の長さの数孊的期埅倀ではなく、ロボットが進むこずができる異なる経路の数を蚈算する必芁があるず仮定したす。 ロボットがそのパスを開始および終了するピヌクず、ロボットが各゚ッゞを通過した回数を蚘録したずしたす。 これらの数量の制限を考慮しおください。 たず、ロボットが正の回数通過した゚ッゞは、゜ヌスツリヌの接続されたサブグラフを圢成する必芁がありたす。 次に、特定の頂点ず、ロボットがこの頂点に隣接するすべおの゚ッゞを通過した回数を考慮したす。 この頂点がパスの終点である堎合、それに隣接する各゚ッゞは正確にwi回䜿甚する必芁がありたす。 頂点に隣接する最倧2぀の゚ッゞを奇数回䜿甚する必芁がありたす。 さらに、この頂点が開始から終了たでのパス䞊にある堎合、正確に2぀の゚ッゞを奇数回䜿甚する必芁がありたす。 開始頂点ず終了頂点䞀臎しない堎合には、奇数回䜿甚される゚ッゞが1぀だけ存圚する必芁がありたす。頂点が䞀臎する堎合はれロになりたす。 他のすべおの頂点の堎合、隣接するすべおの゚ッゞを偶数回䜿甚する必芁がありたす。

これらすべおの条件が満たされた堎合、問題の条件を満たすパスの数をカりントし、゚ッゞを固定回数䜿甚する方法を孊習したす。 各頂点に぀いお、それに隣接するすべおの゚ッゞを考慮したす。 ロボットがそれぞれを通過した回数を知っおいたす。 ロボットが指定された頂点からの方向に゚ッゞに沿った回数を簡単に蚈算できたす。 ロボットはどの順序でこれらのwhat骚に沿っお歩くこずができたすか たず、ロボットが旅を終えた最䞊郚ぞの道にある端に沿っお、ロボットは最埌に行く必芁がありたす。 他のすべおのrib骚では、圌は任意の順序で行くこずができたす。 このようなメ゜ッドの数を数えるこずは暙準的なタスクです。 ロボットが移動できるパスの総数を蚈算するには、各頂点の蚈算倀を乗算する必芁がありたす。

動的蚈画法を䜿甚しお、パスの総数を蚈算できるこずに泚意しおください。 特定の゚ッゞを指定された回数だけ通過し、䜕らかの方法でこのツリヌによっお制限されるサブツリヌを通過するパスの数を蚈算しおみたしょう。 さらに、パスが゚ッゞを䞊るたびに、圌はすぐにそれに沿っお戻るず考えられおいたす。 動的蚈画法の倀を蚈算するには、サブツリヌに入る各゚ッゞに沿っおロボットが歩いた回数を修正し、サブツリヌで既に蚈算された倀を乗算するだけでなく、サブツリヌに遷移を配眮する方法の数を修正する必芁がありたす。 頂点のサブツリヌを順番に怜蚎し、ロボットが合蚈で怜蚎されたすべおのサブツリヌに行く回数を修正したす。 次のサブツリヌを考慮しお、ロボットがこのサブツリヌに入る回数を゜ヌトしたす。 サブツリヌからの動的プログラミングの䟡倀に察する答えず、他のトランゞションの䞭でサブツリヌぞのトランゞションを配眮する方法の数を掛けたす。

元のタスクに戻りたしょう。 ここで、メ゜ッドの数の代わりに、そのようなパスを遞択する確率ずその長さの期埅倀を保存したす。 確率の蚈算は、メ゜ッドの数の蚈算ずは異なり、゚ッゞに沿った各遷移で、この頂点に入射する゚ッゞの数で倀を陀算する必芁がありたす。 この堎合に発生する唯䞀の問題は、ロボットの移動䞭に゚ッゞが削陀されるため、頂点の次数が䞀定でないこずです。 ゚ッゞの動的プログラミング倀を蚈算するには、次のアむデアを䜿甚したす。 ゚ッゞが削陀されるすべおのサブツリヌず、ロボットが゚ッゞに沿っお䞊から移動する合蚈回数を修正したす。 最埌からパスを埩元したす。 区別する必芁がある可胜性のある2぀のオプションがありたす。 たたは、ロボットが削陀されない゚ッゞに沿っお移動する堎合、ロボットがさらに小さなタスクに移動する必芁がある゚ッゞの数を枛らす必芁がありたす。 たたは、ロボットは削陀される゚ッゞに沿っお移動し、ロボットが移動する必芁がある゚ッゞの合蚈数たで、この゚ッゞに沿っお移動する回数を远加し、既存の入射゚ッゞの数を1぀増やす必芁がありたす。

合蚈で、特定の゚ッゞの動的蚈画法にはO2぀の子wi wi 状態があり、それらの間の遷移はO1で実行されたす。 ゚ッゞが䜿甚された回数ごずに動的プログラミングの倀を蚈算する必芁があるため、アルゎリズムの合蚈実行時間はO2 n ∑ wi  2 になりたす。

Source: https://habr.com/ru/post/J267347/

More articles:


All Articles