Geekly Articles each Day

ロシアコヌドカップ2012写真、ビデオ、䟋での決勝のタスクの詳现な分析

2012幎9月10日に、ロシアコヌドカップ2012のプログラミングチャンピオンシップは終了し、すべおがどのように起こったかに぀いおの詳现なストヌリヌが以前に公開されたした。 それらはたった6぀しかなく、それぞれが個別の興味深いストヌリヌです。


これらの問題を解決するために3時間が割り圓おられたした。 6぀の問題のうち5぀を解決したのは、ロシアコヌドカップ2012 Vladislav Epifanovの勝者だけでした 。 ファむナリストの半数未満がそれぞれ4぀のタスクを完了したした。 最初の3぀のタスクはほずんどすべおを行いたした。 1組のEvgeny Kapunだけが、カヌドのデッキに関する問題を正しく解決したした。 トヌナメントで2䜍になったのはNatalia Bondarenkoで 、圌は4぀の問題を他の問題よりも速く、少ない詊行で解決したした。



怒っおいる鳥


Mail.Ru Search Developer Divisionの責任者であるAndrey KALININが 、問題のステヌトメントに぀いお説明したす。



タスクは「Angry Birds」ず呌ばれたす。 その本質はシンプルです。 鳥がいる有限の長さのワむダヌがありたす。 䞀郚の鳥は右に行き、䞀郚の鳥は巊に行きたす。 圌らが䌚うずき-圌らは方向を倉える。 圌らはワむダヌの端に到達するず、離陞したす。 これらの各鳥がい぀飛ぶかを決定する必芁がありたす。 問題の状況に応じお、各方向に最倧10䞇矜の鳥がいる可胜性があるため、合蚈で200,000矜を超えるこずはありたせん。



問題の詳现な声明
ご存知のように、鳥はワむダヌの䞊に座るのが倧奜きです。 郡町Kには、圌が特に気に入った長いワむダヌが1぀ありたす。 ある時点で、数矜の鳥がその䞊に座っおいたした。 すべおがうたくいきたすが、ワむダヌの䞋を走っおいるブタだけが鳥を非垞に怒らせたほどのほこりの雲を䞊げたした。

怒った鳥は、このワむダヌに沿っおさたざたな方向に走り始めたした-巊の誰か、右の誰か。 この堎合、すべおの鳥は毎分1メヌトルに等しい同じ速床で走り始めたした。 互いに向かっお移動する2矜の鳥が出䌚うず、すぐに向きを倉え、反察方向に同じ速床で走り始めたす。

このプロセスは無期限に続きたすが、ワむダヌだけが最終的なものであるこずが刀明し、鳥の1匹がワむダヌの終わりに達するずすぐに離陞し、これに驚いた他のすべおの鳥は向きを倉えお反察方向に走り始めたす。 2矜の鳥が同時に端たで走った堎合、2タヌンが発生したす。たたは、同じこずをしおも䜕も起こりたせん。

ワむダの長さ、走っおいる鳥の初期䜍眮ず方向に応じお、ワむダから飛び出す時点で各鳥を芋぀けるプログラムを曞く必芁がありたす。

入力圢匏

最初の行には、単䞀の敎数L1≀L≀109-メヌトル単䜍のワむダの長さが含たれたす。

2行目には、番号n0≀n≀100 000-右に走っおいる鳥の数が含たれおいたす。 3行目には、n個の異なる敎数a i 0 <a i <Lが含たれたす。これは、ワむダの巊端から右に走る鳥たでのメヌトル単䜍の距離です。

4行目には、数倀m0≀m≀100 000-巊に走っおいる鳥の数が含たれおいたす。 5行目には、m個の異なる敎数b i 0 <b i <Lが含たれたす。これは、ワむダの巊端から巊に走っおいる鳥たでのメヌトル単䜍の距離です。
もずもず同じ堎所にいる鳥は2匹もいたせん。 少なくずも1矜の鳥が電線の䞊に座っおいるこずが保蚌されおいたす。

出力圢匏

最初の行にn個の敎数t iを出力したす -入力された説明の右に飛んでいるi番目の鳥が䜕分埌に説明の順に飛んでいきたす。 2行目では、m個の敎数u iを出力したす。これは、入力の説明の順序で巊に飛ぶi番目の鳥が䜕分埌に飛ぶかを瀺したす。

2秒の制限時間

256 MBのメモリ制限



問題の䟋が瀺されたした。 その定匏化ず解決策を明確にするために、この䟋では鳥の動きを毎分远跡するこずが有甚です。 次の入力デヌタを提䟛したす。2矜の鳥は8メヌトルず9メヌトルにあり、右に進み、さらに3矜の鳥は2メヌトル、5メヌトル、7メヌトルにあり、巊に行きたす。 ワむダヌの長さは10メヌトルです。 これが初期状態です。 鳥が飛ぶ時期を蚈算する必芁がありたす。



ご芧のずおり、1分目ず5分目に鳥は右端から飛び出し、10枚目には2矜の鳥が同時に飛び、13枚目には最埌の鳥が飛びたす。

ここで、鳥の順序は決しお倉わらないこずに泚意するこずが重芁です。 たた、鳥が瀺すゞグザグにもかかわらず、巊たたは右に移動する鳥の数はその衝突に䟝存せず、移動座暙の倉化の性質は垞に線圢のたたです。 これは、3回の衝突があった1分から5分たでの間にはっきりず芋えたす。

右の2列に鳥の䜍眮を瀺したした。 ワむダからの最初の離陞の瞬間を予枬できるこずがすぐに明らかになりたす-端の1぀に最も近い鳥からワむダの端たでの分数=メヌトルの数。

たた、離陞埌、右ぞの移動に関連付けられおいるすべおの座暙が巊ぞの移動に関連付けられおいる座暙になり、その逆も同様であるこずがわかりたす。

その結果、この問題の解決策は、2぀のデッキ、぀たり、最初たたは最埌の芁玠の削陀がO1で実行される「䞡端キュヌ」タむプのデヌタ構造の保守に限定されたす。 鳥が離陞するず、極端な芁玠がデッキから削陀され、デッキ自䜓が亀換されたす。 ペアの保持<12月; 数字にどれだけ远加する必芁があるか> O1で、次の鳥がどのくらいの長さでどの方向に飛ぶかを確認できたす。 鳥の順序は倉わらないので、鳥の元の堎所の座暙の゜ヌトされた配列を远加で保存しお、どの鳥がワむダを離れたかを刀断する必芁がありたす。

最も矎しい゜リュヌションは、Python3の゜リュヌションです。

from collections import deque length = int(input()) n = int(input()) right = deque(sorted(map(int, input().split()))) m = int(input()) left = deque(sorted(map(int, input().split()))) addLeft, addRight = 0, 0 INF = 2*10**9 ans = 0 while right or left: L = left[0] + addLeft if left else INF R = length - (right[-1] + addRight) if right else INF m = min(L, R) ans += m addLeft -= m addRight += m if L < R: left.popleft() left, addLeft, right, addRight = right, addRight, left, addLeft elif L == R: left.popleft() right.pop() else: right.pop() left, addLeft, right, addRight = right, addRight, left, addLeft print (ans)


鳥ずのタスクは、 ミハむル・ケバヌがラりンド開始から22分たでに最初に䜜成したした。 数秒埌、 Vasil BILETSKYはタスクに合栌したした。

合蚈で、40人がタスクに察凊し、11人がそれを解決し始めたした。 解決にかかる平均時間は30分です。 これらのうち、解決に芁する最倧時間は44分です゜リュヌションがたったく送信されなかった状況はカりントされたせん。 最初のタスクを最初に解決した11人すべおが、少なくずも2぀以䞊を解決したした。 11のうち2぀のケヌスを陀き、党員がタスクBに進み、次にタスクCに行きたした。぀たり、アルファベット順にタスクを完了したした。 このタスクは、コンテストが開始されたすべおのタスクの䞭で3䜍です。

トリ゜リアン


Allods OnlineのテクニカルディレクタヌであるIlya VAYSMANは、Trisoliansのタスクに぀いお次のように語っおいたす。



問題の条件により、惑星トリ゜ルの䞀郚の䜏民は、私たち人間のような単䞀の敎数ずしおではなく、k個の敎数のベクトルずしお幎霢を指定したす。 新生児のトリ゜リアンでは、幎霢ベクトルは1぀のれロで構成されおいたすが、成長する幎ごずに、幎霢ベクトルの各芁玠に特定の正の数が远加されたす。 トリ゜リアンのラむフストヌリヌは、圌が生涯を通じお持っおいたすべおの幎霢のベクトルのセットです。 同じ物語を持぀トリ゜リアンが存圚しないこずはよく知られおいたす。 科孊者は、芁玠の合蚈がnであるベクトルでラむフストヌリヌが終了するTrisolianの最倧数に興味がありたす。 この倀を玠数を法ずしお蚈算するプログラムを曞く必芁がありたす7340033 = 7 * 2 ^ 20 + 1。

たずえば、k = 2の堎合、ラむフストヌリヌは合蚈5のベクトルで終わる8぀のトリ゜リアンが存圚する可胜性がありたす。

1.0、0-1、1-2、3;
2.0、0-1、1-3、2;
3.0、0-1、2-2、3;
4.0、0-1、4;
5.0、0-2、1-3、2;
6.0、0-2、3;
7.0、0-3、2;
8.0、0-4、1。

問題の詳现な声明
最近、惑星トリ゜ルの䜏民は、私たち人間のような単䞀の敎数ずしおではなく、k個の敎数のベクトルずしお幎霢を瀺しおいるこずが知られおいたす。 新生児のトリ゜リアンでは、圌の幎霢のベクトルはk個のれロで構成されおいるず考えられおいたす。 幎をずるに぀れお、幎霢ベクトルの各芁玠に正の数が毎幎远加されたす。

トリ゜リアンのラむフストヌリヌは、圌が圌の人生の間に持っおいた圌の幎霢のすべおのベクトルのセットです。 地球科孊者たちは、同じ物語を持぀二人のトリ゜リアンがいないこずを確立したした。

科孊者は、ラむフストヌリヌが芁玠の合蚈がnであるベクトルで終わるトリ゜リアンの最倧数に興味を持っおいたす。 この倀を玠数7340033 = 7・220 + 1を法ずしお蚈算するプログラムを䜜成したす。

入力圢匏

最初の行には、2぀の敎数nおよびk-最埌の幎霢ベクトルの芁玠の合蚈、およびベクトルの芁玠数1≀n≀4239、1≀k≀10 9 が含たれたす。

出力圢匏

ラむフストヌリヌが芁玠の合蚈がnであるベクトルで終わる可胜性のあるTrisolianの最倧数を出力したす。 答えは、7340033 = 7・2 20 + 1を法ずしお掚定する必芁がありたす。


少し歎史的背景がなければ、問題の解決はおそらく䞍可胜です。 トリ゜リアンは、ホラヌ銀河の犁断地垯の奥深くに䜍眮する惑星トリ゜ルの居䜏者です。 それらは100液䜓です。 圢状を簡単に倉曎できたす。 通垞の居䜏者は平和的であり、支配゚リヌトに぀いおは蚀えたせん。 時々、圌らはお互いを飲み、キャリアのはしごに沿っおこのように動きたす。

すべおの解決策は組み合わせ論に垰着するため、タスクは比范的単玔です。 䞀方、kの可胜な範囲ベクトルの次元1≀k≀10000000000をよく芋るず、すぐにそれほど単玔ではなくなりたす。

N = 2N = 3N = 4N = 5N = 6
0,0-1,10,0-1,2
0,0-2,1		0,0-1,1-2,2
0,0-2,2
0,0-3,1
0,0-1,3
0、0-1、1-2、3;
0、0-1、1-3、2;
0、0-1、2-2、3;
0、0-2、1-3、2;
0、0-2、3;
0、0-3、2;
0、0-4、1。
0、0-1、4;
0,0-1,1-2,2-3,3
0,0-1,1-4,2
0,0-1,1-2,4
0,0-1,1-3,3
0,0-1,2-3,3
0,0-1,2-2,4
0,0-2,1-3,3
0,0-2,1-4,2
0,0-2,2-3,3
0,0-3,1-4,2
0,0-1,3-2,4
0,0-5,1
0,0-1,5
0,0-4,2
0,0-2,4
0,0-3,3
1぀のオプション2぀のオプション4぀のオプション8぀のオプション16オプション



解を理解するための重芁なアむデアは、Nの倧きな倀の「ブッシュ」が郚分的に䜎い倀の解で構成されおいるため、再垰によっお蚈算を敎理できるこずです。

グラフィカルに、特殊なケヌスk = 2の堎合、ラむフストヌリヌは、れロマヌクず盎線fx= nx䞊の軞䞊にある正の敎数マヌクを接続するセグメントのセットずしお衚瀺できたす。

N = 4の解は次のようになりたす。



N = 4ストヌリヌ、8。

次に、このストヌリヌにベクトル1,1を远加し、取埗したす



ベクトル1,1で始たる各ストヌリヌは、N = 7のストヌリヌの䞀郚になりたす。 ストヌリヌの別の郚分は、ベクトル1,2などで始たる小さな「ブッシュ」です。

他のベクタヌず同様の物語。 N = 7の履歎芁玠の䞀郚の始たりであるベクトル1,3の䟋を瀺したす。 この堎合、次のようになりたす。



぀たり、トリ゜リアンの最初の誕生幎に䞎えられたベクトルを取埗し、トリ゜リアンの生掻史のすべおのベクトルからそれを枛算し、このベクトルを捚おた埌、実際にトリ゜リアンのいく぀かの生掻史を取埗したす。最埌のベクトルの芁玠の合蚈はn-スロヌされたベクトル芁玠。

したがっお、最埌のベクトルの芁玠の合蚈がnであるすべおのストヌリヌは、䞀郚のm <nに察しお芁玠の合蚈がmである最埌のベクトルを持぀ストヌリヌから取埗でき、n-mに等しい合蚈を持぀正の芁玠のベクトルを远加できたす人生の党物語。

合蚈がnmに等しいベクトルはいく぀になりたすか 最小ベクトルには各座暙に1぀が含たれるため、すべおのベクトル、kのすべおのコンポヌネント、合蚈nmkが衚瀺されたす。 ここで、単䜍をk座暙に䞎える必芁がありたす。 これを行う方法の数は、繰り返しのある組み合わせの数です。 繰り返しのある組み合わせの数は、次のように蚈算されたす。



そしお、繰り返しのない組み合わせの数は次のように蚈算されたす



これから、繰り返しaからbたでの組み合わせの数は、繰り返しなしの組み合わせa + b-1 by bの数に等しいず簡単に掚枬されたす。

したがっお、この堎合、りェむの数は、n-m-k + k-1
k、すなわち、kのn-m-1からのC



目的の倀をans nずしお瀺すず、次の繰り返し匏が埗られたす。 ans 0 = 1ず仮定したす。アルゎリズムの実行時間はOn2です。





ここで、Cx、yは最初の匕数の2番目の匕数の組み合わせの数で、xずしお蚈算されたす。 /xy / y

トリ゜リアンの任務は、決勝戊に出垭したほが党員によっお行われたした2人を陀く。 問題を解決するのに玄18分かかりたした。 最初にそれを行ったのは11分でロヌマンリズバノフでしたが、わずかなマヌゞンがありたした-Evgeny KAPUN 。

CPU


CIO Mail.Ru GroupのAlexander GORNYがプロセッサの問題に぀いお説明したす。



このタスクには、26皮類の呜什を実行できる特定のデュアルコアプロセッサが含たれたす。 各呜什は、英語のアルファベットの文字で象城的に曞かれおいたす。 プログラムは䞀連の指瀺で構成されおいたす。 アヌキテクチャの特性䞊、2぀のコアで同時に実行できるのは同じ呜什のみであるこずがわかっおいる堎合、プロセッサが指定された2nプログラム特定の呜什の指定されたシヌケンスで構成されるを凊理するのに必芁な最小時間を蚈算する必芁があり、n-そのようなプロセッサヌの数。

プロセッサが2぀のプログラムを同時に凊理する方法の図



問題は、n個のプロセッサヌずそれぞれの2぀のコアに2n個のプログラムを効率的に分散しお、ステップ数を最小限にする方法に芁玄されたす。

問題の詳现な声明
ご存知のように、珟圚補造されおいるプロセッサのほずんどはマルチコアです。぀たり、耇数の呜什の同時実行をサポヌトしおいたす。 Paraltelは、新しいタむプのデュアルコアプロセッサを開発したした。これにより、倧文字のラテン文字で瀺される26皮類の呜什に埓うこずができたす。 このような各呜什の実行には、プロセッサの正確に1クロックサむクルが必芁です。

このプロセッサのプログラムは䞀連の呜什です。 プログラムの呜什は、プログラムに埓う順序で実行する必芁がありたす。呜什を亀換するこずはできたせん。

2぀のコアが存圚するため、プロセッサは2぀のプログラムを同時に実行できたす各コアに1぀。 ただし、アヌキテクチャ䞊の機胜により、同じプロセッサの2぀のコアで同時に実行できるのは同じ呜什のみです。

2぀のプログラムがプロセッサで実行されるず、䞡方のプログラムの実行をできるだけ早く完了するように、特別な制埡デバむスが実行を最適化したす。 たずえば、ABBおよびABCプログラムは4サむクルでプロセッサ䞊で実行できたす。最初に、異なるコアの䞡方のプログラムのAコマンドが同時に実行され、次にBコマンドが同時に実行され、次に最初のプログラムのBコマンド、秒から「C」。 同様に、「CAB」および「BAB」プログラムは4サむクルで実行されたす。

最近、䌁業の専門家がn個のプロセッサからスヌパヌコンピュヌタヌを組み立おたしたが、そのためには2n個のプログラムが必芁です。 蚈算の構成は、各プロセッサがこのセットから正確に2぀のプログラム各コアに1぀を実行する必芁があるようなものです。

すべおのプログラムの完了時間が最小になるように、n個のプロセッサヌで2n個のプログラムの実行を蚈画する必芁がありたす。

入力圢匏

最初の行には、数n1≀n≀10-プロセッサヌの数が含たれおいたす。 次に、2n行で、実行するプログラムを指定したす。 各プログラムには1〜100チヌムが含たれたす。 各コマンドは倧文字のラテン文字で瀺されおいたす。

出力圢匏

単䞀の数倀-すべおのプログラムを実行できる最小時間を印刷したす。



タスクの䟋ずしお、次のプログラムのセットが提䟛されたす。ABBBAB CAB ABC
プロセッサが2぀あるずいう情報。

2぀のプロセッサでプログラムを実行するには、次の4぀の手順が必芁です。

CPU 1コア1CPU 1コア2CPU 2コア1CPU 2コア2
[A] BB[A] BC[B] AB
A [B] BA [B] C[C] AB
AB [B]B [A] BC [A] B
AB [C]BA [B]CA [B]


問題の解決策を2぀の段階に分け、それぞれを個別に怜蚎したす。

最初のステップは、グラフを䜜成するこずです。 その頂点は、実行する必芁がある2n個のプログラムです。 グラフに重みが付けられ、2぀のプログラム間の゚ッゞの重みは、プロセッサが共同実行に費やす時間に等しくなりたす。 この倀は、プログラムの長さの合蚈から、同時に実行されるコマンドを匕いたものに等しくなりたす。 そしお、そのようなコマンドはLCSa、bだけです。ここで、aずbはプログラムを蚘述する行であり、LCS Longest Common Subsequence 、最倧共通サブシヌケンスは、2぀のシヌケンスの最倧共通サブシヌケンスを芋぀ける関数です。

その結果、rib骚の重量を芋぀ける機胜は次のようになりたす。

 int dist(String a, String b) { int[][] d = new int[a.length() + 1][b.length() + 1]; for (int[] ar : d) { Arrays.fill(ar, 1000000000); } d[0][0] = 0; for (int i = 0; i <= a.length(); ++i) { for (int j = 0; j <= b.length(); ++j) { if (i < a.length()) { d[i + 1][j] = Math.min(d[i + 1][j], d[i][j] + 1); } if (j < b.length()) { d[i][j + 1] = Math.min(d[i][j + 1], d[i][j] + 1); } if (i < a.length() && j < b.length() && a.charAt(i) == b.charAt(j)) { d[i + 1][j + 1] = Math.min(d[i + 1][j + 1], d[i][j] + 1); } } } return d[a.length()][b.length()]; }


解決策の2番目の段階は、このグラフで最倧゚ッゞの重みが最小化される完党な䞀臎を芋぀けるこずです。 この問題を解決し、時間制限に適合する最も単玔なアルゎリズムの1぀は、動的プログラミングですが、すでにサブセットになっおいたす。 サむズがk以䞋の頂点の各セットに぀いお、答えを知っおいたす。 この堎合、そのようなすべおのセットを調べお、ただ含たれおいない可胜性のあるすべおの゚ッゞに远加するず、k + 2以䞋のサむズのすべおのセットの答えを蚈算できたす。

  int[] d = new int[1 << (2 * n)]; Arrays.fill(d, 1000000000); d[0] = 0; for (int mask = 0; mask + 1 < 1 << (2 * n); ++mask) { if (d[mask] == 1000000000) { continue; } int i = 0; while ((mask & (1 << i)) != 0) { ++i; } for (int j = i + 1; j < 2 * n; ++j) { if ((mask & (1 << j)) == 0) { d[mask | (1 << i) | (1 << j)] = Math.min(d[mask | (1 << i) | (1 << j)], Math.max(d[mask], dist[i][j])); } } }


タスク「Processor」は、決勝戊に参加したほが党員によっお行われたした2人を陀く。 この問題を解決するための平均時間は玄18分です。 問題を最初に解決したのは、11分間のVladislav EPIFANOVでした。

包囲



タスク「包囲」に぀いおは、NRU ITMOの孊郚の孊生であるPavel KROTKOVに䌝えたす。



このタスクは、敵の倧矀が攻撃しようずしおいる玠晎らしい郜垂、アルダヌスバヌグに぀いお語っおいたす。 郜垂を維持するには、n個のアヌティファクトの障壁を立お、[i]個の「マヌリン」の魔法の゚ネルギヌで各i番目のアヌティファクトをアクティブにする必芁がありたす。 その埌、b [i]“ Merlins”を䜿甚しお、敵は遠くからこのアヌティファクトを砎壊できたす。 街のディフェンダヌは、敵の歊噚である魔法の゚ネルギヌのマグリン、Bマヌリンを持っおいたす。 町の人々は、敵の魔術垫による砎壊の埌、アヌティファクトの最倧数がアクティブのたたになるように、アヌティファクトをアクティブにするこずにしたした。 郜垂の防衛者が掻性化するアヌティファクトを遞択できるようにする必芁がありたす。

問題の詳现な声明
茝かしいアルダヌスベルクの街には困難が蚪れおいたす。 数分から数え切れないほどの敵の倧矀が攻撃を始めたす。 魔法の壁だけが郜垂を維持するのに圹立ちたす。

垂の防衛者の兵噚庫には、障壁を立おるためにn個のアヌティファクトがありたす。 i番目のアヌティファクトをアクティブにするには、 iマヌリン魔法の゚ネルギヌの単䜍が必芁です。 その埌、ビヌマヌリンを䜿甚しお、敵は遠くからアヌティファクトを砎壊できたす。

街のディフェンダヌは、敵のBマヌリンの兵噚庫に魔法の゚ネルギヌのマグリンを持っおいたす。 魔法の゚ネルギヌは補充されたせん。 町の人々は、敵の魔術垫による砎壊の埌、最倧数がアクティブのたたになるように、アヌティファクトをアクティブにするこずにしたした。

アクティブにするアヌティファクトを郜垂の防衛者が遞択できるようにしたす。

入力圢匏

最初の行には、スペヌスで区切られた3぀の敎数A、B、およびn0≀A、B≀105、0≀n≀1000が含たれおいたす。 次のn行には、数倀aiずbiのペアが含たれおいたす1≀a i 、b i≀105。

出力圢匏

最初の行に、競合の䞡偎の最適なアクション䞭にアクティブのたたになるアヌティファクトの数を印刷したす。 2行目には、郜垂の防埡者がアクティブ化する必芁があるアヌティファクトの数ず、これらのアヌティファクトの数を印刷したす。 1行の数字はスペヌスで区切りたす。

アヌティファクトには、入力で指定された順序で1から番号が付けられたす。


少し歎史的な背景。 アルダヌスベルクは、䞖界の端に䜍眮する4぀の北王囜の1぀である゚ヌディルネで2番目に倧きい郜垂です。 アルダヌスベルクの街は、゚ヌディヌンの囜境を守る芁塞の壁の呚りに建おられたした アンドゞェ・サポコフスキヌ 

街の防埡者が倚くのアヌティファクトをアクティブにしたずしたす。 敵にずっお最適な戊略は、b iが増加する順に敵を砎壊するこずです。 実際、敵の目暙はできるだけ倚くのアヌティファクトを砎壊するこずです。 簡単なタヌゲットがある限り、䞍滅のアヌティファクトに倚くの゚ネルギヌを費やすこずは意味がありたせん。

アヌティファクトの番号を非降順b iに付け盎したす。 敵が防埡偎の最適なアクションで砎壊できない最初のアヌティファクトが番号kであるこずを知ろう。 この仮定に基づいお、防埡偎の行動を説明したす。 最初のk − 1アヌティファクトから、砎壊に費やされる合蚈゚ネルギヌが少なくずもB − b k +1マヌリンであり、掻性化゚ネルギヌが最小になるように、いく぀かを遞択する必芁がありたす。 k番目のアヌティファクトをアクティブにしたす。 最埌に、゚ネルギヌ消費の増加順に最埌のn − kアヌティファクトをアクティブ化したす。

残念ながら、kは事前にはわかりたせん。 敵が砎壊できない最初のアヌティファクトの数を敎理し、この仮定に最適な答えを構築したす。

D ijを、i以䞋1000たでの数のアヌティファクトをアクティブにするために必芁な最小゚ネルギヌずし、jの砎壊のためにjのマヌリンの゚ネルギヌ10䞇たでが必芁になるようにしたす。 遷移D i、j = minD i − 1 、j、D i − 1 、j − b i + a i 。 これらの2぀のケヌスは、最適なD ijを実珟するためにアヌティファクト番号iをアクティブにする必芁があるかどうかに察応したす。

配列Dから、敵がk番目のアヌティファクトを砎壊できないために必芁な゚ネルギヌがわかりたす。 その埌、私たちは熱心に残りを取り、掻性化するのに十分な゚ネルギヌがありたす。 その結果、すべおのkを通過しお、最適な答えが芋぀かりたす。

説明されおいるアプロヌチの実行時間はOnB + nです。 完党な゜リュヌションにするには、情報ストレヌゞを远加しお回答を埩元する必芁がありたすが、これは挞近的な動䜜には圱響したせん。

゜リュヌションのボトルネックは、䜿甚されるメモリである可胜性がありたす。 D配列に保存できるのは最埌の行のみであるこずに泚意しおください。 さらに、各ペアi、jに぀いお、最適なD ijを達成するためにアヌチファクト番号iをアクティブにする必芁があるかどうかを知るだけで十分です。 メモリの制限を満たすために、このビットの情報を栌玍するために2バむト以䞋を䜿甚する必芁がありたした。

包囲タスクは19人によっお解決されたした。 Peter MITRICHEVは87分でこのタスクに誰よりも速く察凊したしたSiegeタスクの前に、Peterは最初の3぀を成功裏にパスしたした。

シャッフルデッキ


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



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



問題の詳现な声明
自動化ずコンピュヌタヌ化は、私たちの生掻のあらゆる分野に急速に浞透しおいたす。 , , — . — .

, , 1 t. , .

. , 1, — t. , , .

, .

, : i j , i- j- .
, , .



x — , . x .

. n — . n , . , , 1.

200000.



, , «-1», , , . , k — , . k , i j — , , .



, , :



, , . , .



. , . , .

K. , ⌈K / 2⌉ ( ⌊
⌋ ⌈
⌉ — ).

M «». , M = ⌈K / 2⌉.

, .

, 1122333344 3 ( 33), – 6. M = ⌈K / 2⌉.

( ) :

  1. K — ( ). , «» A, «» B, — C. |A| + |B| + |C| = |K|, |A| + |C| = |B| = M. 1122333344 AABBBC.

    : (B, C), , — (A, B). , (B, C)* (A, B)*, * — .

    :
    1122333344 (AABBC) ->1122333-4.34 (AAB) -> 1-2333-4.3412 (BB)

    ( , . – )

    , . : |C| > 0, C , B. |C| = 0, (A, B)*, B .

  2. K — . . A, , A-. C, C- , .


, ⌈K / 2⌉. , , «» ( ). .

. Q.



, ( ) (C 1 , C 2 ). , , . , .

, . Z, (X, Z) Z , Z Z (X 1 , Z) (X 2 , Z)
. Z- , (X, Y) , (X k , Z) (X k+1 , Y), X k+1 ≠ Z.

, (X, Z) X Z (M). M ≠ Z, Z (X, Z) (Z, ...) , Z M, (X, Z) (M, Z).

, , ⌈K / 2⌉ .

, , , . , O(N log N). , - , , . , , , : . O(n), .

« » .


():



N . , , .

, . , . , , , . , , .

, .

, , .

, .

3 258 , –1000 1000, .

Russian Code Cup .

— .

.

, . , , , . , .

, . , .

, . , , , , .

, . , , .




, . , . , . .



. , — . .

O(n 3 ) , O(n 2 ) O(n) . O(n) O(n 2 ) O(n 2 ). , O(n 3 ).

« » . , 93- .

Russian Code Cup 2012 . , , , - ( , , ), – - ( ) . , , , . , , , , ?



Mail.Ru Group

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

More articles:


All Articles