Мөн HackerRank дээр зохиогдсон онлайн тэмцээнд амжилттай оролцсон нөхдөд баяр хүргэе ээ.
Нийлбэр олох
Эхний K гишүүний нийлбэрийг S гэж үзвэл дахиад нэг баруун тийш шилжихэд S+Ak-A0 болж өөрчлөгдөнө. Энэ мэтчилэн нийлбэрийг O(1)-д олж чадах учраас бодлого O(N)-д бодогдоно.Сансарын нисгэгч
Өгүүлбэр жаахан ойлгомжгүй байсан уу даа. Би бол 1-р гарагаас бусад гараг тус бүр рүү хүрэх зайг олоод тэр зай нь F-с хэтрэхгүй, бас радиустаа багтаж байна уу гэдгийг шалгасан.Тэгш өнцөгт
Бодлого нь i*j≤n ба i≤j байдаг хэдэн хос байгааг олохтой ижил. i болон j-н аль нэгээр давтаад нөгөөхийг нь тоолоод явахад болно (O(N)). Эсвэл хоёулангаар нь давтахад ч болно, энэ тохиолдолд хугацааны үнэлгээ O(NlogN) орчим байна.Тоглоом
Тоглоомын бодлого бодоход хүнд юм шиг боловч ерөнхий санааг нь олчихсон хойно энгийн Динамик програмчлалын бодлого байдаг. Хавтангуудын урт 20-с хэтрэхгүй учир нийт 2^20 ширхэг ялгаатай тоглоомын төлөв байж болно. Хар хавтанг 0, цагаан хавтанг 1 гэвэл 20 битийн тоогоор дүрслэж чадах ба үүнийгээ бид 10-тын тооллын системийн mask тоо гэж үзье. f(mask)-г уг төлөвт 1-р тоглогч эхлэж нүүхэд хождог бол 1 үгүй бол 0 гэж үзье. f(mask_1)=0 байдаг дор хаяж ганц mask_1 төлөв рүү mask-с хүрч чаддаг байвал f(mask)=1, тийм mask_1 төлөв олдохгүй бол f(mask)=0 байна. Ингээд манай бодлого энгийн Динамик програмчлалын бодлоготой ижилхэн.Энэ бодлогыг илүү хялбар бодож болох ба дараалсан цагаан хавтангуудын тоог тоолъё. ...##.#..## байвал 3 1 2 гэсэн үг. Эндээс манай бодлого Nim game -рүү шилжиж байгаа ба Nim game-д тоонуудын XOR нь 0 байвал 2-р тоглогч, бусад бүх тохиолдолд 1-р тоглогч ялдаг.
Шагай
Дээрх тоглоом бодлогод дурдсан үндсэн санаа буюу динамик програмчлал ашиглаад эхний нэлээд хэдэн (N,M) хосуудын утгыг харвал ямар нэгэн N тооны хувьд 2-р тоглогч хождог байх яг ганц M гэсэн хос олдох нь харагдана. Уг зүй тогтлоор аль тоглогч хожихыг хялбархан мэдэж болно.Миний хувьд иймэрхүү зүй тогтол харах тоглоомын бодлогуудтай нэлээд олон таарч байсан. Хамгийн сүүлийн Topcoder SRM дээр хүртэл энэ төрлийн бодлого байсан.
Дахиад л анхны тоо
Нэгжийн оронд 1, аравтын оронд 10 mod P, зуутын оронд 100 mod P, мянгатын оронд 1000 mod P гэх мэт хариу гарна.Урт дараалал
Динамик програмчлалын бодлого. Өсдөг буурдаг тохиодлоо тусад нь бодоход болно. f(x,y)-р аль нэг цэгээс эхлээд x,y цэг дээр дуусдаг хамгийн урт дарааллыг тэмдэглэвэл f(x,y) = MAX(1, MAX(f(x', y') + 1 {бүх хөрш x', y' хувьд})) байна.Хамгаалалт
Багана болон мөр тус бүрийн хувьд хөрш тэрэгнүүдийн хамгийн хол зайг олоод үржихэд хариу гарна. Захын нөхцлүүдийг бас шалгаарай.Аялагч
Тэмцээнд миний дэвшүүлсэн бодлого хэхэ.Динамик програмчлалаар бодъё. f(k)-р k урттай бодлогын нөхцлийг хангадаг аялалын тоог тэмдэглэвэл хариу f(m) байх нь ойлгомжтой.
N=20 үед боломжит нэгэн хариуг харъя.
1 2 4 8 16 1 11 1 2 4 8 20
Дээрх хариунаас харахад манай аялал нь бие биеэсээ үл хамаарах хэд хэдэн аялалаас тогтож байна. Ногоон нь аялалын эхлэл буюу дурын хот, улаан нь төгсгөл буюу том хот (улаан болон ногоон өнгө давхцаж болно). Улаан болон ногоон өнгө хоорондохыг дэд аялал гэж үзвэл дэд аялал хамгийн ихдээ log2(N)+1 урттай байна. Учир нь ямар нэгэн тооноос эхлээд дор хаяж хоёр дахин ихэснэ.
Буцаад динамик програмчлал руугаа оръё. Бид нар f(k)-г олохыг оролдож байгаа. Дарааллын k-р гишүүн улаан өнгөтэй байх нь илт (аялалын төгсгөл буюу том хот). Тэгвэл түүнд хамгийн ойр орших улаан өнгөтэй гишүүнийг j гэж үзье. Дээр дурдсанаар энэ хоёрын хоорондох зай хамгийн ихдээ log(N) байна. Тэгвэл f(j)-д байгаа бүх хариуны ард k-j урттай дэд аялалыг залгахад k урттай ялгаатай аялалууд үүснэ. Үүнийг томъёолвол f(k)=Sum(f(j)*[k-j урттай дэд аялалын тоо]) {j=k-logN .. k-1} болно. Хэрвээ бид дурын k урттай дэд аялалын тоог олж чаддаг бол бодлого маань ямар ч гэсэн шийдэгдлээ гэсэн үг. (Мэдээж 10^18 үед амжихгүй)
g(i,j)-р i урттай сүүлийн буюу i-р гишүүний утга нь j-с хэтэрдэггүй бөгөөд гишүүн бүр нь өмнөх гишүүнээсээ дор хаяж 2 дахин их байдаг тоон дарааллын тоог тэмдэглэвэл g(i,j)=g(i,j-1)+[i урттай сүүлийн гишүүний утга нь яг j байдаг тоон дарааллын тоо]. [] нд бичсэн утга нь g(i-1,j/2) той тэнцүү гэдгийг хялбархан харж болно. g(i,j)=g(i,j-1)+g(i-1,j/2) харьцагаар бид g-г O(logN*N)-д байгуулж чадна. g-г ашиглан k урттай дэд аялалын тоог g(k,N)-g(k,N/2) гэж олж болно.
Тэгвэл f(k)=Sum(f(j)*(g(k-j,N)-g(k-j,N/2)){j=k-logN .. k-1} болох ба g-г өмнө байгуулчихсан гэж үзвэл бид f(M)-г O(M*logN)-д олж чадах нь ээ :). M = 1018 үед яагаад ч амжихгүй :(.
N=10^5 үед f(k) нь хамгийн ихдээ өмнөх 20 гишүүнээсээ хамаарна. Тэгэхээр бид f(0) .. f(19) ашиглаад f(20)-г, f(1)..f(20) ашиглаад f(21)-г олж чадна гэсэн үг. Харьцаа нь шугаман учраас бид үүнийг матриц ашиглан бодож болно. [f(i),f(i+1),...,f(i+19)]*X=[f(i+1),f(i+2),...,f(i+20)] байдаг X матриц нь бүх i-н хувьд тогтмол байх учраас анхны буюу [f(0),f(1),...,f(19)] матрицыг X-н M-19 зэргээр үржүүлэхэд [f(M-19),f(M-18),...,f(M)] матриц үүсэх ба сүүлийн матрицын 20 дахь гишүүн нь бидний хайж буй хариу юм. Одоо бодлогын хугацааг үнэлвэл g матрицыг олон тестээс хамаарахгүйгээр нэг удаа O(NlogN)-д байгуулна. Матрицын хэмжээг тогтмол logN-р авснаас тогтмол 20-р авсан нь кодчилоход хялбар байна. Нэг тестийг O(20^3*logM)-д бодох ба эндээс нийт хугацаа нь O(NlogN + T*20^3*logM) болж хангалттай амжина.
Good Job :-) Tnx
ReplyDelete