Блогоо дахин бичиж эхлэв. SRM 588

Удаан завсарласны эцэст тэмцээнд оролцсон тэмдэглэлээ дахин хөтлөж эхлэхээр боллоо. Мөн блог маань xongor.mn гэдэг домайн дээр байрлаж байгааг анзаарсан биз ээ. CodeForces-д мөн идэвхтэй оролцож тэмдэглэлээ хөтлөнө өө.

Өнөөдөр бага зэрэг алдаа гаргаснаг эс тооцвол ерөнхийдөө дажгүй орлоо.

Easy:
N ширхэг дуу өгөгдсөн. Дуу бүр нь өөрийн гэсэн хугацаа болон өнгөтэй. Нэг дууг дуулж дуусаад дараагийн дууг дуулахад тодорхой хэмжээний завсарлага хэрэгтэй. Энэ хугацаа нь ABS(tone[i]-tone[j]). Өгөгдсөн T хугацаанд хамгийн ихдээ хичнээн дуу дуулж чадах вэ?

Санаагаа харьцангуй хурдан олсон. Оновчтой хариунд дуугаа дуулах дараалал нь дууны өнгөөрөө эрэмбэлэгдсэн байна. Тиймээс бүх дууг tone-р нь эрэмбэлчихвэл бодлого энгийн DP болж хувирна. f(i,j)-р эхний i дуугаас яг j ширхэг (i-р дууг дуулна) дууг дуулахад зарцуулах хамгийн бага хугацааг тэмдэглээд хялбархан бодож болно. O(N^3). Кодоо нэлээд хурдан бичсэн ч жижигхэн алдаагаа олохгүй маш удсан....

Medium:
Цайзад N тооны хаалга бий. Хаалга бүр тодорхой хэмжээний ногоон болон улаан түлхүүрний хослолоор онгойно. Хаалгыг онгойлгож өрөөнд орвол тэнд мөн хэд хэдэн улаан, ногоон, цагаан өнгийн түлхүүрүүд байх бөгөөд та тэднийг авч болно. Цагаан түлхүүр нь ногоон болон улаан цоожинд аль алинд нь таардаг. Танд анх хэд хэдэн цагаан, улаан, ногоон түлхүүрүүд өгөгдөв. Та хамгийн ихдээ нийт хичнээн түлхүүртэй болж чадах вэ (Аялалаа хэзээ ч зогсоож болно)?

N<=12
1 өрөөнд байгаа түлхүүрний тоо, анх өгөгдөх түлхүүрний тоо өнгө тус бүр <= 10

Хамгийн энгийн бодолт бол ямар дарааллаар хаалгуудаа онгойлгохоо шийдээд түүнийхээ дагуу симуляц хийх. O(N!) орчим болох бөгөөд энэ нь хэтэрхий удаан. Үүнийг динамик програмчлал ашиглан бодож болно. f(set, r)-р set олонлогт багтах бүх хаалгуудыг онгойлгосны дараа яг r ширхэг улаан түлхүүртэй байж чадах уу гэдгийг тэмдэглэе. Ногоон түлхүүрний тоо нь тогтмол олдох бөгөөд энэ мэдээлэл нь дараагийн хаалгуудаа онгойлгоход хангалттай. Удахгүй код оруулах бөгөөд тэр үед тодорхой харагдах байх.

Санаагаа ч дажгүй хурдан олоод кодоо бичээд шууд ажиллачихлаа, илгээлээ. Нэлээд дээгүүр жагсаж байна. f(set, r) төлөвийн r хамгийн ихдээ 260 байж болно гэдэгийг 120 гэж алдсан байлаа. Practice roomd үүнийг засаад давсан, үнэхээр харамсалтай.

Rating change:
-38 Бас ч гэж дажгүй шүү :)