MNPC 2011 - SMCS багийн тэмдэглэл

Би (SMCS - Э.Хонгор) энд багийнхаа MNPC 2011-т хэрхэн оролцсон тухай бичихээр шийдлээ. Юуны өмнө MNPC 2011 нь Мөнх-Очир бид хоёрын хувьд оролцох боломжтой сүүлийн жил байсан болохоор амжилттай оролцохыг хүсч байсан ба санасандаа хүртэл оролцсондоо таатай байна. Мөн багийн уламжлал ёсоор дахин нэг гишүүн маань солигдсон билээ :p. Багийн шинэ гишүүн маань уг блог-н идэвхтэй админ болох Баасанбат юм. Тэмцээний үеэр олон бодлого байсан болохоор хэн яг ямар бодлого оролдож уншсаныг мартчихаж, багийн ажиллагаа байсан гэж ойлгоорой :).

За ингээд тэмцээнээ эхэлье :). Тэмцээн эхлэв 10 бодлого ирлээ. Бодлогыг хувааж аваад уншив аа, тэгтэл J бодлого N тооны эрэмбээрээ голын тоог ол гэнэ. Шууд STL-н sort ашиглаж бичээд явуултал TLE. N<=10^6 бас multicase 10 ширхэг байсан болохоор амжсангүй. Ингээд шууд хаяад A бодлогыг хартал өгөгдсөн тоонуудын нийлбэрийг ол гэнэ. Ингээд явуулаад 6 дахь минутанд AC. Тэгтэл манайхаас өмнө 2 баг AC авсан байв, J-г хэрэггүй оролдлоо :p. C бодлого N-с хэтрэхгүй хуваарьтай бүх зөв энгийн бутархайг эрэмбэлж гаргах бодлого байв, N жижигхэн байсан болохоор шууд бичээд AC (11 минут). Ингээд тэмцээний дүнг хартал маш бага хугацааны зөрүүгээр нэгт орлоо. Амархан бодлого олохын тулд бүх бодлогыг уншиж их цаг авав, тэгээд I бодлогыг уншиж дуусахад жаахан нуугдмал Bipartite Matching байсныг олоод шууд бичээд AC (41 минут). Дүнгээ хартал бас л тэнцчихсэн, хугацаагаараа арай бага болохоор 1т. Board-с ажиглаад B бодлого хялбар байж магадгүй санагдаад B-г Мөнх-Очиртой цуг жаахан бодсоны эцэст шууд томъёог олоод AC авав (64 минут). Дараагийн бодлого - F, уг бодлого өгүүлбэрээ ойлгосны дараа жижигсэн DP байсныг олов, бичиж байх зуураа дүн хартал дахиад л тэнцчихлээ, MTC-н 1-р багтай үнэхээр ширүүн өрсөлдөж байна даа, ингээд F-ээ дуусгаад AC(75 минут). Ингээд 5 бодлоготой болоод 1 оноогоор холдсон ч удалгүй өрсөлдөгч баг маань 5 бодлоготой болж тэнцэв. Бодлогуудаа уншсаар л, амархан бодогдчих бодлого олдолгүй удав. E бодлого MIS 2D(Maximum Interval Sum) -г олох бодлого, Мөнх-Очиртой хамтраад бичиж байтал арай жаахан удаж магадгүй санагдаад дуусгалгүй өөр бодлого харав. Тэгээд Баасанбатын уншиж байсан H-г DP + BFS гэдгийг харлаа. Маш урт өгүүлбэртэй бодлого байсан болохоор Баска-н тусламжтай хурдан ойлгоод бичив. Bug гарсан болохоор гурвуулаа нийлж тестлэж засаад явуулав. Алдаж магадгүй гэсэн айдастай байсан ч AC авлаа (154 минут). Яг энэ үед манайх 7 оноотой өрсөлдөгч 5 оноотой байсан болохоор жаахан тайвширлаа. Юмаа идэх нь идээд усаа уух нь уугаад бие засах нь заслаа. Ороод иртэл нөгөө баг 6 болчихжээ, яарахгүй бол болохгүй нь. Одоо бодох дутуу гурван бодлого нь D, G, J. J бодлогыг яг баталгаатай бодох арга олоогүй ч эцсийн арга гээд нэг арга олчихсон. D бодлогыг анх хараад ямар ч санаа олсонгүй. Brute Force бичээд жижиг тохиолдлоос зүй тогтлыг олов. Гурвуулаа нийлж байгаад томъёо гаргаад явуултал WA. Итгэлгүй байсан болохоор орхив. Тэмцээний дүнд өөрчлөлт ороогүй байсан болохоор өрсөлдөгч баг манайхыг ялахын тулд дор хаяж 2 бодлого нэмж бодох ёстой ба цаг бага үлдсэн байсан болохоор тайван байлаа, гэхдээ хамаагүй тайвширч болохгүйгээ мэдэж байсан болохоор J-г эцсийн аргаараа үзээд AC авав (228 минут). Одоо л тайвширч болохоор боллоо, гэхдээ D-г эцсээ хүртэл оролдсоор байв. Ингээд манай баг дахин түрүүлж хошой аварга боллоо. Бодлогын анализ дээр зохиогч D-н бодолтоо тайлбарлатал томъёо нь яг таарж байсан ба бодолтоо тулгатал маш жижигхэн алдаа байсан ба манай бодолт зөв болж rejudge хийхэд AC авав (208 минут). Ингээд 9 оноотой гэсэн үг, гэхдээ бусад багуудын аль нь ч бодож чадаагүй болохоор ялгаагүй гэж үзээд манай баг 8 оноотой үлдэхээр шийдсэн.

Бодлого Оролдлого Минут
A 1 6
C 1 11
I 1 41
B 1 64
F 1 75
H 1 154
E 1 170
D 1 203
J 6 228

Багийнхандаа баяр хүргэе!

P.S: Удахгүй бүх бодлогын өгүүлбэрийг оруулах болно.