ABC lessons learned7 - zettsu-t/zettsu-t.github.io GitHub Wiki
ใณใณใในใใซๅๅ ใใๆ่จใใพใจใใฆใใใพใใ
ใใใใใผใธใธ ABC ๅๅ ่จ1ใธ ABC ๅๅ ่จ3ใธ
ใณใณใในใ21ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใใใ้ ็นใใใใฆA..Dๅ้กใฏ่งฃใใชใใใฐใชใใชใใE,Fๅ้กใ่งฃใใใๅคง่บ้ฒใจไบๆณใใใฎใ ใใใพใใDๅ้กใงๆๅคง็ฌ้3ๆก้ ไฝใ ใจใฏๆใใชใใฃใใCๅ้กใงๆ้ใๆบถใใใใฎใๆใใพใใใใๆใใใจใใใๅฎๅใ่ถณใใชใใ
ใณใผใใฏใใกใ
< ใงๅงใพใใ = ใไธใคไปฅไธ็ถใใ > ใง็ตใใใใจใใใฎใ่กจ็พใใใฎใซๆฉใใงใใพใฃใใๆญฃ่ฆ่กจ็พใฏใกใฟๆๅญใ่พใใ(a,b,cใซ็ฝฎๆใใใฐใใใฎใ ใ)ใๆใใจใฉใพใใ็ถๆ
้ท็งปใซใใใใใ่ใใใ ่งฃ่ชฌ้ใ ๆๅญๅใ่ตฐๆปใใใฐใใใฃใใฎใงใๆฉใฟ้ใใงใใใๆๅญใใจในใฑใผใใใชใใฆใๆญฃ่ฆ่กจ็พใง ้ใ ใ
ใใฎๆฉใฟ้ใใงๆ้ใๆบถใใใๅพใฎๆฉใพใชใใใใงWAใใใใจใซใชใใ
ใณใผใใฏใใกใ
ไฝๅบฆใ่ฆใใ่ฒ ใฎๆฐใฎไธธใใงใใใใใคใพใง็ตใฃใฆใๆ่จใงใใชใใฎใงใๆญฃ่ฒ ใซๅใใฆไฝใใ่ฃๅฎใใใ
ใณใผใใฏใใกใ
Cๅ้กใซใใฆใฏใพใใใฎ้ฃๅใง2 WAsใงใใใใใฎๆ้ใจใใใซใใฃใ็ใใ
ๅ ฅๅไพใ้ใฃใใฎใงๆๅบใใฆ1ใใ้ฃใใใไฝใๆใฃใใๅพฎไฟฎๆญฃใงใใ1ใใใ้ฃใใฃใใๆใใใซ2ใใ็ฎใฏไฝ่จใงๅท้ใใๆฌ ใใฆใใใใใใใงๆญฃๆฐใซๆปใฃใฆDๅ้กใซ็งปใฃใใๆๅบใๆใใจใฉใพใในใใ ใฃใใDๅ้กใ่งฃใใฆใใCๅ้กใซๆปใฃใใ้้ใใๅใใฃใใ
่ฑๅฐๆๅญใฏ26็จฎใใใชใใฎใงใ std::vector ใ26ๆฌไฝใฃใฆใ a..z ใไฝๆๅญ็ฎใซๅบใใ่ชฟในใใๅ
้ ญใใ std::lower_bound() ใงๅใใใ
ๅใใใฆใใใฎใฏ abc ใ็กใใฎใ้่ฆใชใใณใใ ใฃใใ
ๅท้ใซใชใฃใฆๅฆ็ใๆธใใใๆทปใๅญใฏ1-based indexingใคใพใๅ ้ ญใ1ๆๅญ็ฎใจๆฐใใใ
-
$i$ ๆๅญ็ฎใ$c$ ใจใใ -
$j = [i+1,N]$ ใซใฏ$W_i = N-i$ ๆๅญใใใใใฎไธญใซ$c$ ใไฝๅใใใๆฐใใ($M_i$ ๅใจใใ)ใใใใฏstd::lower_bound()ใงๅใใใ ็ดฏ็ฉๅ ใชใ่จ็ฎ้ใๆธใใใๅฎ่ฃ ใ้ทใใC++ใชใๅฎ่กๆ้ใ$log(|S|)$ ๅใงใTLEใใชใใ - ็ฐใชใๆๅญใๅ
ฅใๆฟใใๆนๆณใฏ
$W_i - M_i$ ้ใใใใฎใงใ็ญใใซๅ ็ฎใใ
ใใ
ไปใฎๆนใฎใณใผใใ่ชญใใงใใใฃใจ็ฐกๅใช ่งฃๆณ ใใใใจๅใใฃใใ a..z ใใฉใใซใใใใฏ็ก่ฆใใฆใใใใใไฝๅใใใๆฐใใใ a ใ
ๅ ฌๅผ่งฃ่ชฌ2ใฏใใใจใฏใพใๅฅใฎ่งฃใๆนใง้ข็ฝใใ
ใณใผใใฏใใกใ
้ๅฎ่ฃ ใใใฆๅดใซใชใฃใใ
้ ็นใใA..Dๅ้กใฏๆฉ่งฃใๅ่ฒ ใEใพใใฏFๅ้กใ่งฃใใใฐๅคงๅน ใซใใใฉใผใใณในใไธใใๅดๅใ ใจๆใฃใฆใใใๅฎ้ใซใฏDๅ้กใฎ้ฃๆๅบฆใ้ซใใฆๅดใฎไธใ ใฃใใ็ตๆ็ใซใฌใผใใฃใณใฐใๅคงๅน ใซไธๆใใใ
็ทๅฝใใใใใชใใใใชใฎใงใ็ทๅฝใใใใใฎใ ใๅฎ่ฃ ๅใใชใใจTLEใใใใงใใใC++ใฎ้ซ้ๅใใฏใใใฏใ้งไฝฟใใฆใฒใใใๅฎ่ฃ ใใใ็ทๅฝใใใฎใใๆนใฏๅ็ดใชๆนๆณใงใใใ
- ใฟใคใซใ้ธใถๆนๆณใฏ
$2^N$ ้ใใๅ จ้จ้ธใถใๅถ็ดใใ128้ใใงใใใๅ ฌๅผ่งฃ่ชฌใซใใใฐใ้ ๅใฎ้ไธญใงไฝใใใฆใใใใ - ใฟใคใซใฎ้ข็ฉใฎๅใใใน็ฎๅ จไฝใฎ้ข็ฉใฎๅใจไธ่ดใใชใใฟใคใซ้ๅใฏๅ่ฃใใ้คๅคใใ
- ใฟใคใซใฏ้ทๆนๅฝขใชใฎใงใใฟใคใซใ
$M$ ๆ้ธใใ ใใๅ่ปขใใๆนๆณ$2^M$ ้ใใงใใใๅถ็ดใใๆๅคง128้ใใงใใใ - ใฟใคใซใ่ฃ่ฟใๆๅณใๅใใใชใใฎใ ใใ่ฃ่ฟใใจใใๆ็คบใฏ็ก่ฆใใฆใใใใใงใใ
- ใฟใคใซใไธฆในใ้ ๅบใๆฑบใๆใกใใใ7ๆใใใฐ
$7! = 5040$ ้ใใงใใ - ใฟใคใซใ็ฝฎใๅ ดๆใฏใไธใฎ่กใใ้ ใซใๅทฆใใๅณใซ็ฉบใๅฐใๆขใใฆๆๅใซ็ฝฎใใๅ ดๆใงใใใใคใพใๅฏ่ฝใช้ใ่ก(็ธฆๆนๅ)ใๆใไธใงใใใฎ่กใฎๆใๅณ(ๆจชๆนๅ)ใงใใใๅถ็ดใใๆๅคง
$HW = 100$ ้ใใงใใใ
ใฟใคใซใ7ๆๅ
จ้จไฝฟใใจใใฆใ
- ใฟใคใซใๅณใพใใฏไธใซใฏใฟๅบใ็ฝฎใๆนใฏใงใใชใ
- ๆขใซๆทใใใฟใคใซใจ้ใชใ็ฝฎใๆนใฏใงใใชใ
ๅฎ่ฃ ไธใฎC++ใใฏใใใฏใจใใฆใฏใไปฅไธใไฝฟใใจๅฎๆฐๅใ้ใใชใใจๆใใๆค่จผใฏใใฆใใชใใ
- ใฟใคใซใ้ธใถๆนๆณใจใฟใคใซใๅ่ปขใใๆนๆณใฏ2ใฎ้ไนใชใฎใงใ
std::bitset<8>ใงใใใๅ จๆข็ดขใใ - ใใน็ฎๅ
จไฝใฏ
bool grid[10][10]ใจใใ้ ๅใซใใใbool grid[16][16]ใฎๆนใใขใใฌใน่จ็ฎใ้ใใใใใใชใใ - ใฟใคใซใฎๅ่ปขใฏ็ธฆๆจชใฎๅ
ฅใๆฟใใชใฎใงใ
std::swap(tile_height, tile_width)ใใใ้ซใใจๅน ใๅ็ งๆธกใใงใฏใชใๅคๆธกใใงๅใๅใฃใฆใๅ ใฎใฟใคใซใฎ็ธฆๆจชใๅ ฅใๆฟใใชใใใใซใใใ - ใฟใคใซใ็ฝฎใ้ ็ชใฏ
std::next_permutationใงๆดๆฐใใ - ใฟใคใซใ็ฝฎใใใ็ฝฎใใชใใจใใใใฉใฐใ็จๆใใฆใใใฉใฐใ็ซใฃใใforใซใผใใๅณๆใกๅใ
ใฟใคใซใฎ้ข็ฉใฎๅใใใน็ฎๅ จไฝใฎ้ข็ฉใฎๅใจไธ่ดใใชใใใฐใใใน็ฎๅ จไฝใ่ฆใใใจใใงใใชใใฎใงใใฎใใใชใฟใคใซใฎ็ตใฟๅใใใๆใกๅใใใจใใงใใใใใใ ใใงๅฎ่กๆ้ใ ๆฐๅใฎไธ ใซใชใใใณใณใในใใงใฏใใฎๅฆ็ใๅ ฅใๅฟใใฆใ็ตๆ็ใซTLEใใชใใฃใใๅฑใชใใจใใใ ใฃใใ
่ฑๆๅ้กใ่ฆใฆๆฐใไปใใใฎใ ใใใณใณใในใใฎใณใผใใฏrotateใจๆธใในใใจใใใflipใฎfใจๆธใใฆใใพใฃใใ็ขบใใซๆญฃใใๅใใฏใใใใใใใใจใงใฏใชใใ
ใณใณใในใ22ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใใใDๅ้กใฏใใใซใใฃ็กใใ ใๅฎ่ฃ ใ้ ใใEๅ้กใใฉใใใฆใ่งฃใใชใใฃใใใขใซใดใชใบใ ใ็่ฉฐใใฆ่ใใใใจใ้่ฆใ ใใในใใฑใผในใไฝใฃใฆๅ ฅๅใใใใจใๅใใใใ้่ฆใใจใใใฎใไปๅใฎๆ่จใงใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅฎ่ฃ ใใใ
ใณใผใใฏใใกใ
ๆๅญๅใ
ใณใผใใฏใใกใ
std::set ใง่จ้ฒใใ
ใณใผใใฏใใกใ
ๆน้ใฏใใ็ซใฃใใใๅฎ่ฃ ใซๆ้ใๆใ้ใใใใใใซใใฃใ็กใใฎใๆใใ
ๅทฆ็ซฏใใ 0101... ใๅทฆ็ซฏใใ 1010... ใ ๅณ็ซฏใใ ...1010 ใ ๅณ็ซฏใใ ...0101 ใจๆฑบใๆใกใใใจใใซใไฝๆๅญๅใใจใฉใใ ใใฎใณในใใซใชใใใ็ดฏ็ฉๅใงๆฑใใใ
ใใจใฏ้ฃ็ถใใไบๆๅญใไธ่ดใใๅ ดๆใ็ทๅฝใใใงๆฑใใฆใใณในใใฎ็ทๅใฎๆๅฐๅคใๆฑใใใๅทฆๅณใฎ็ซฏใ0ๅงใพใใจ1ๅงใพใใไธๆใ็ตใฟๅใใใใ
-
$N$ ใๅถๆฐใฎๅ ดๅใ01..010010..10ใพใใฏ10..101101..01ใงใใใ -
$N$ ใๅฅๆฐใฎๅ ดๅใ01..0100101..01ใพใใฏ10..1011010..10ใงใใ
ใณใผใใฏใใกใ
้้ ใคใพใใฏใจใชๅ ่ชญใฟใๆใใคใใฎใซ30ๅใใใๆใใฃใใใใใงใปใผ่ฒ ใใๆฑบใพใฃใใฎใ ใใๆฎใๆ้ใจใใใใณใณใในใใ็ตใใฃใฆใ่ชๅACใงใใชใใฃใใ
ใฏใจใชๅ ่ชญใฟใใฆ้้ ใซๅกใใคใถใใ่กใซใคใใฆ่ใใใๅใซใคใใฆใๅๆงใงใใใ
- ่ก
$a$ ใใใงใซๅกใฃใใฎใชใ็ก่ฆใใ - ใใใงใชใใใฐ่ก
$a$ ใๅกใใ่ฒ$x$ ใงๅกใฃใใในใฎๆฐใๅขใใใใฉใใ ใๅขใใใใจ่จใใจใ$W$ ใใๆขใซๅกใฃใๅๆฐใ้คใใใใฎใงใใใๆขใซๅใ่ฒ$x$ ใงๅกใฃใใใฉใใใฏ ้ขไฟใชใ ใ
ไธใใใใๅ ฅๅไพใซใๅใ่ฒใง่กใจๅใๅกใไพใฏใชใใฃใใใ็กใใใฐ่ชๅใงไฝใใฐใใใ ใใฎ่ฉฑใงใใใไธ่จใฎใในใใฑใผในใไฝใฃใฆใใใฐใณใณใในใไธญใฎๆๅบใณใผใใ้้ใฃใฆใใใใจใๅใใฃใใใขใซใดใชใบใ ใ็่ฉฐใใฆ่ใใใใจใใใในใใฑใผในใไฝใฃใฆๅ ฅๅใใใใจใๅใใใใ้่ฆใ ใฃใใ
5 5 2
1 1 1
2 1 1
ใณใณใในใ23ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใงใใใDๅ้กใฎใใใซใใฃใฏ่ใใ่ถณใใชใใฃใใใใใจใฏ้ ่ชฟใงๆฐด่ฒใซๅพฉๅธฐใงใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅฎ่ฃ ใใใๅบๅใใ่ฆ็ด ๆฐใไฝๅใใฏใๅ ฅๅใๅ จใฆๅฆ็ใ็ตใใใชใใจๅใใใชใใฎใงใ็ฉบ็ฝใจๆน่กใฎใฉใกใใๅบๅใใใๆณจๆใใใ
ใใ่ชญใใจๅบๅใฏๆ้ ใชใฎใ ใใๅ ฅๅใๆ้ ใชใฎใง็ตๆ็ใซๆญฃใใใฃใใๅฎๅ จใซ่ฆ่ฝใจใใฆใใใ้ใฃใฆใใพใฃใใ
ใณใผใใฏใใกใ
้จๅๆๅญๅใ็ทๅฝใใใงๅใๅบใใฆใ std::set<std::string> ใง้่คใชใๅๆฐใๆฐใใใ
ใณใผใใฏใใกใ
่ผชใซใชใฃใฆ่ใใใ
ๅ
จใฆใฎๆฅใฏใ1้ฑ้ใฎไฝๆฅ็ฎใใ ใใซๆๅณใใใใฎใงใ
ไฝใๅๅฃซใ่ผชใซใใฆ่ใใใในใฆใฎไฝใใๅบ้ Yes ใๅบๅใใฆ็ตไบใใใฐใใใ
ๅบ้ใฎๆไฝ้ทใฏ
ใณใผใใฏใใกใ
-1 ใงใใใ
ๆดๆฐ
-
$C$ ใฎ็ซใฃใฆใใใใใใซใคใใฆใๆๅใฎ$a$ ๅใฏ$X$ ใฎใใใใ็ซใฆใๆฎใใฎ$b$ ๅใฏ$Y$ ใฎใใใใ็ซใฆใ -
$C$ ใฎ็ซใฃใฆใใชใใใใใซใคใใฆใๆๅใฎ$d$ ๅใฏ$X,Y$ ใฎไธกๆนใฎใใใใ็ซใฆใ
ใใ ใ -1 ใงใใใใใใๅฟใใฆWAใใฆ1ใใใงใใใE,Fๅ้กใซๆ้ใๆธฉๅญใใใ็ฆใใใใใๅ
ใๆฅใใใใใ
ไธ่จใง่งฃใชใใจๅคๆญใใชใใใฐ
ใณใผใใฏใใกใ
ๅ ้ฑใฎๆ่จใๆดปใใใ
ใฏใจใชใๅ
จ้จ่ชญใใงใใใๆณใใใฐใใใ้กๆใ็่งฃใใใฎใๅคงๅคใ ใใ่ฆใใใซ
ใฏใจใชใไธ้ใ่ชญใใงใ
ใณใณใในใ24ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใใใDๅ้กใๆฎใ56็งใงACใใฆๅ่ฒ ๆ นๆงใ่ฆใใใใฎใ ใใใใใใDๅ้กใซ86ๅๆใใฆใฏใใใชใใEๅ้กใฏใณใณใในใๆ็ธพใๅบใใฎใๅพ ใฃใฆใใ้ใซ่ชๅACใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅบๅใใใ1-based indexingใงใใใใจใซๆณจๆใใใ
ใณใผใใฏใใกใ
ใในใฆใฎ็ตใฟๅใใใ็ถฒ็พ ใใใๅฎ่ฃ ใซๆณจๆใ่ฆใใ
- ่ท้ขใฏๅนณๆนๆ นใงใฏใชใใ่ท้ขใฎไบไนใๆดๆฐใงๆใค
- ใใใใใฎ็นใใใฎๆ้ ่ท้ขใฏ
std::vector<std::pair<Num,Num>>ใงๆใคใใใใใฝใผใใใฆๅ ้ ญใฎ่ฆ็ด ใ็ญใใงใใใ - ไธ่จใฎใใขใฏใ่ท้ขใ็ฌฆๅทๅ่ปขใใใใฎใจ้ ็น็ชๅทใ็ตใซใใใใฎใซใใใใใใใใฐใฝใผใใใใจใใ่ท้ขใ้ ใ้ ็นใๅ ใ่ท้ขใๅใใชใ้ ็น็ชๅทใๅฐใใ้ ็นใๅ ใซใชใ
- ้ ็น็ชๅทใ0-based indexingใง็ฎก็ใใใชใใ1-based indexingใซๆปใใใจใๅฟใใชใ
ใณใผใใฏใใกใ
Min-Maxใใใใใใใ
ใใใใ่ฒใฎใใใใใ std::map<Num, std::set<Num>> ใงๆใคใใใใใใจ่ฒใฎๅถ็ดใใใใใฏใใซใงใฏใชใ้ฃๆณ้
ๅใงๆใคใ
้ฃๆณ้
ๅใซๅ
ฅใฃใฆใใ้ๅใฎใใกใๆใๅฐใใๅคใฏ std::set::begin() ใงๅใใใใใใใใฎ่ฒใซใคใใฆใฎๆๅฐๅคใ้ใใฆใใใฎๆๅคงๅคใๆฑใใใ็ญใใใฎใฏใใใใใงใใฃใฆใ่ฒใงใฏใชใใฎใงๆณจๆใใใ
ใณใผใใฏใใกใ
86ๅ7ใใใฎๆณฅๆฒผใงใใใใฉใใใฆใใใชใซใใใใฐใซๆ้ใๆใใฃใใฎใๅใใใชใใ
ใใใใใใจใฏBFSใซไธๅทฅๅคซใงใใใไธใค็ฎใฏใๅง็นใซ่ฌใใใใฐใใฎๅ ดใง้ฃฒใใงใใจใใซใฎใผใๆญฃใฎๅคใซใใฆ็งปๅใงใใใ ใ็งปๅใใใๅง็นใซ่ฌใใชใใใฐๅใใชใใฎใง็ญใใฏ No ใงใใใ
ใใใในใฎใจใใซใฎใผใงๅใใ็ฏๅฒใฏใ็งปๅๅฏ่ฝใชใในใซไธๆๅใใใจใซใจใใซใฎใผใ1ๆธใใใจใใBFSใงๆฑใพใใใใใง่ฌใใใฃใใ้ฃฒใใงใใใใ้ฃฒใพใชใใฆใใใใใใฎใใจใฏๅ้กๆใซๆธใใฆใใใใ้ฃฒใพใชใใใฐใใใชใใจๅ้ใใใใจๅ ฅๅไพใ่งฃใใชใใใใใ็่งฃใงใใใซ็ฆใฃใใฎใๆณฅๆฒผใฎๅ ฅใๅฃใ ใฃใใ
่ฌใ้ฃฒใใฎใฏใใใฎใในใซๅฐ้ใใๆ็นใงใฎใจใใซใฎใผใฎๆข็ฅใฎๆๅคงๅค
BFSใงใญใฅใผใซไนใฃใใใจใใซใฎใผใ
ใใจใฏBFSใ็ก้ใซใผใใTLEใใชใใใใซใ็งปๅๅ ใฎใในใฎใจใใซใฎใผใๆข็ฅใฎๆๅคงๅคไปฅไธใชใ็งปๅใใชใใใใซใฌใผใใใใใใฎใใจใใ่ฌใ้ฃฒใฟใใใชใไฝๅบฆ้ฃฒใใงใๆงใใชใใจ่จใใใใใฎ่พบใฏBFSใฎๅบๆฌใ ใใ็ฆใฃใฆใใใจ่จณใๅใใใชใใชใใใดใผใซใซๅฐ้ๅฏ่ฝใใฉใใใฏunion-findๆจใซใใใใBFSใงๅฐใใคใใใฐใใใฃใใใจใใใๆๅใฎ้้ใฃใๅฎ่ฃ (่ฌใงๅฐ้ๅฏ่ฝใช็ฏๅฒใใใผใธใใ)ใๅผใใใฃใใฎใใพใใใฃใใ
22:39:04ใซๆๅบใใ่พใใใฆ4ๅฎใ ใฃใใRatedใฎใณใณใในใใงใใๅพใใใชใ็ทๅผตๆใงใใใใใใใๆๅณใงใฏๅพใใใฎใใใฃใใจ่จใใใใจใฏใใใใใพใใซใใใใฐใไธๆใใใฆACใใใฎใ็บใใฆใใใใณใณใในใใ็ตใใใEๅ้กใฏ่งฃใใฉใใใๅ้กๆใ่ชญใๆ้ใใใชใใฃใใ
ใณใผใใฏใใกใ
ใณใณใในใๆ็ธพใๅบใใๅพ
ใฃใฆใใใจใใใใใฌใผใใฃใณใฐใๅทใใใฎใ็ขบๅฎใชใฎใงใใพใ่ฆใใใชใใฎใงใใฎ้ใซ่งฃใใใ้ ็นใ็งปๅใใใใจใซ
ๆจๆง้ ใชใฎใง้ ็น1ใๆ นใจๆฑบใๆใกใใฆใไปฅไธใฎๅคใๆฑใใใDFSใงๆฑใพใใฎใง่จ็ฎ้ใฏ
- ใในใฆใฎ
$C$ ใฎๅ$sum_c = \sum_{j=1..N} C_i$ - ้ ็น
$v$ ใจใใฎๅญ้ ็นใใคใพใ$v$ ใใ่ใฎๅดใซใใ้ ็น้ๅใ$U_v$ ใจใใใ$U_v$ ใฏ$v$ ใๅซใใ -
$U_v$ ใซใคใใฆใฎ$C$ ใฎๅใ$S_v$ ใจใใใ - ้ ็น1ใใ่ท้ขใซๅบใฅใใ
$U_v$ ใซใคใใฆใฎ$f(v)$ ใคใพใ$\sum_{i \in U_v} (C_i \times d(1,i))$ ใ$W_i$ ใจใใใๆ็ต็ใซใฏ$W_1$ ใ ใใๅฟ ่ฆใ ใใ้ไธญ่จ็ฎใซใในใฆใฎ้ ็นใฎ$W$ ใ่ฆใใ
่งฃใฎไธ้ใฏ
้ ็น
-
$f(j)$ ใซๅฏใฃใใใจใง$S_j$ ใ ใๆธใ -
$v$ ใใ้ขใใใใจใง$sum_c - S_j$ ใ ใๅขใใ
ใฎใงใใฎใใใซๆดๆฐใใใ
ไปฅไธใฎใใใซ2ๅDFSใใใจใ
ใณใณใในใ25ๅ็ฎใงใใใA,B,Cใฎ3ๅฎใง้ๅปๆไฝใฎใใใฉใผใใณในใซ็ตใใฃใใDๅ้กใฏไธ่ฆใใฆ่งฃๆณใฎ็ฎ้ใ็ซใใใ่ซฆใใฆๅใใฃใEๅ้กใฎใใใใฐใๅฎไบใใๅ ฑๅใใซ็ตใใฃใใ
ใณใผใใฏใใกใ
ๅ้กๆใ็่งฃใใใฎใๅคงๅคใ ใใ่ฆใใใซ
ใณใผใใฏใใกใ
Aๅ้กใซ็ถใใฆๅ้กๆใ็่งฃใใใฎใๅคงๅคใงใใใ่ฆใใใซๆๅญใฎๅบ็พๅๆฐใๆฐใใฆใๅบ็พๅๆฐใ0ใ2ไปฅๅคใชใ No ใๅบๅใใใใฎใใใชใใจใใชใใใฐ Yes ใๅบๅใใใๆๅใซ (ๆๅญ็จฎ, ๆๅญใฎๅบ็พๅๆฐ) ใฎ้ฃๆณ้
ๅใไฝใใใใใ (ๆๅญใฎๅบ็พๅๆฐ, ๆๅญ็จฎ) ใฎ้ฃๆณ้
ๅใใใฏใฟใซๅคๆใใใๅบ็พๅๆฐ0ๅใฎใฑใผในใฏๆ็คบ็ใซ่กจใใชใใฎใง็ก่ฆใใฆใใใ
ใณใผใใฏใใกใ
้ฃ็ถใใชใใใใใใชใ้จๅๆๅญๅใฏๅฐบๅใๆณใงๆฑใใใฎใๅ
ธๅใงใใใใใใใชใใใใใซ่ใใๅใฐใใ .* ใซ X ใซๆ้ๅใใ็ตๅฑ่งฃ็ญใซ14ๅๆใใฃใใๆ้ใๆใ้ใใงใใใใใใๅฎ่กๆ้ใ 754 ms ใจใๅถ็ดๆฌก็ฌฌใงใฏTLEใ ใฃใใใใใใชใใใจใฏใใๅ
ฌๅผ่งฃ่ชฌ2ใๆญฃ่ฆ่กจ็พใชใฎใงๆณๅฎ่งฃๆณใงใฏใใ( x ใไปใใใใจใฏๆใใคใใชใใฃใ)ใ
ๅฐบๅใๆณใไฝฟใใจ ใใ ๅฎ่ฃ
ใงใใใ้ๅธธใซ็ฐกๆฝใชใณใผใใงใใใใใคใพใงใๅฐบๅใๆณใ่ฆๆใจ้ใๅใฃใฆใใใจใใใใใจใใซๆใพใใใใใใ
ใณใผใใฏใใกใ
ไธ่ฆใใฆใฉใ่งฃใใใใใใๅใใใชใใฎใง่ซฆใใฆEๅ้กใซๅใใฃใใEๅ้กใ่งฃใใชใใฃใใใจใใใใใใใฐใ็ตใใใชใใฃใใฎใงใใณใณใในใ็ตไบ็ดๅพใใ่งฃใใฆ 23:34:19 ใซ่งฃใใใ54ๅๆใใใจใใ่ฆๆฆใฏ็ขบใใซไบๆณ้ใใ ใใใชใใใใชใซๆ้ใๆใใฃใใฎใ ใใใ
ไธ่จใฎๆไฝใ็ตใใฃใๆ็นใงใ
ไธ่จใฎๆนๆณใฏๅ
ฌๅผ่งฃ่ชฌ2ใจใ ใใใๅใใงใใใtrailing zerosใฎใใๅทฆใฎ1ใ ใใๆฎใๆนๆณ n & -n ใๅฟใใฆใใใ
Trailing zeros ใซๆณจ็ฎใใใใจใฏใใๅใใฃใใใ่ค้ใชๅ ดๅๅใใๅฟ
่ฆใจๆใฃใฆๆฉใใงใใพใฃใใ
ใณใผใใฏใใกใ
Dๅ้กใจ็ฐใชใใใฒใผใ ๆจใๆงๆใใใ ใใจใใใใใฃใใ็ขบใใซใใฎ้ใใ ใใใใใซใใฃใฆ้้ใใใฎใฏ3็ฎไธฆในใฎๆ็ซๆกไปถใงใใใๅทฆใใๅณใไธใใไธใซ 0..8 ใไธฆในใๆใ็ธฆๆจชๆใใซ3ๅไธฆใถใชใ่ชใในไปฅๅคใฎๆฎใใฎ2ใในใฏไฝใใจใใ่กจใไฝใใๅฎๆฐๅ้ซ้ๅใ็ฎ่ซใใงๅคใใใผใใณใผใใฃใณใฐใใใฎใ ใใใชใใจใใใ้้ใฃใฆใใใ
0 1 2
3 4 5
6 7 8
ใใกใใๆญฃใใใ
std::vector<std::vector<Vec>> lines {
{{1,2}, {3,6}, {4,8}},
{{0,2}, {4,7}},
{{0,1}, {5,8}, {4,6}},
{{0,6}, {4,5}},
{{3,5}, {1,7}, {0,8}, {2,6}},
{{2,8}, {3,4}},
{{0,3}, {7,8}, {2,4}},
{{1,4}, {6,8}},
{{2,5}, {6,7}, {0,4}}
};ใใกใใ้้ใใงใใใใใฎ่กจใใๅใฃใฆใใใฐ 22:39:48 ใฎ ๆๅบ ใACใงใใใฎใง็ๆจใงใใใใใ่ใใใ่ชๅ็ๆใใใฐใใใฃใใฎใ ใใ่ชๅ็ๆใฎใใฐใจๆๆธใใใ่กจใฎใใฐใจใใฉใกใใใใใใฐใใใใใใๆฉใพใใใ
std::vector<std::vector<Vec>> lines {
{{1,2}, {3,6}, {4,8}},
{{0,2}, {4,7}},
{{0,1}, {5,8}, {4,6}},
{{0,6}, {4,5}},
{{3,5}, {1,7}, {0,8}, {2,6}},
{{2,8}, {3,4}},
{{0,3}, {7,8}, {2,4}},
{{1,7}, {6,8}},
{{2,8}, {6,7}, {0,4}}
};่งฃใๆนใฏใฒใผใ ๆจใฎๅฎ่ฃ
ใใฎใใฎใงใใใๅ
ฌๅผ่งฃ่ชฌใใพใใซใใใใฆใใใ std::bitset ใไฝฟใใจ้ใใชใใ
- ๅๆ=ๅ
ๆ็ชใฎ1ๆ็ฎใๆฑบใๆใกใใใ
0..8ใใน็ฎใๅๆใจใใฆใใใฎๅพใฎ็ตๆใคใพใ2ๆ็ฎใๅ ๆๅฟ ๅใจใชใๅ ดๅใไธใคใงใใใใฐๅ ๆๅฟ ๅใงใใใใใใใฎๅ ดๅใๅ ๆๅฟ ๅใงใชใใใฐๅพๆๅฟ ๅใงใใใ -
$i=2..9$ ๆ็ฎใซใใใฆใ$i$ ใๅฅๆฐใชใTakahashiใ$i$ ใๅถๆฐใชใAoki ใฎๆ็ชใงใใใ$i$ ๆ็ฎใฎๆ็ชใฎ่ ใ$P_i$ ใใใใงใชใ่ ใ$\lnot P_i$ ใจ็ฝฎใใ -
$i=2..9$ ๆ็ฎใซใใใฆใ็ฝฎใใใในใๅซใใฆ็ธฆๆจชๆใใซ่ฒใใใใใฐ$P_i$ ใฎๅฟ ๅใงใใใ -
$i=2..9$ ๆ็ฎใซใใใฆใ็ฝฎใใใในใๅซใใฆ็ธฆๆจชๆใใซ่ฒใใใใใชใใใฐใ$i+1$ ๆ็ฎใๆข็ดขใใใ$i+1$ ใฎๆ็ชใซ$P_i$ ใๅฟ ๅใฎๆ็ชใใใใฐใ ใใฎ$i$ ๆ็ฎใฏ$P_i$ ๅฟ ๅใงใใ(ใใฎๆใๆใใฐๆ็ชใฎ็ธๆใ่ฉฐใใใใใใใฎใง)ใใใฎใใใช$i+1$ ใฎๆ็ชใใชใใใฐ$\lnot P_i$ ๅฟ ๅใงใใ(ๆ็ชใฎ่ ใ่ฉฐใใงใใใฎใง)ใ - 9ๆ็ฎใง็ธฆๆจชๆใใซ่ฒใใใใใชใใใฐในใณใขใฎๅคงๅฐใงๅใก่ฒ ใใๆฑใใใใในใฎๆฐๅญใฎๅใฏๅฅๆฐใชใฎใงใๅผใๅใใฏ็กใๅๆใไปใใ
ๆฐmsecใง็ตใใใฎใงๅฎๆฐๅๆ้ฉๅใใใใฎใใใใใใฎ้้ใใงใใฃใใจใใใใๅๅธฐๆทฑๅบฆใใในๆฐใ้ ๅใง
ใณใณใในใ26ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใ36ๅ10็งใใใซใใฃ็กใใฏ่ชๅทฑๆ้ใงใใฌใผใใฃใณใฐใๆฐด่ฒใซๆปใใใ
ใณใผใใฏใใกใ
ไธๅ็ฎใใใจใใธใฑใผในใๅณใใใใใใคใ็ซใกไธใใใ้ ใๆ ้ใ ใฃใใฎใงใใใใซใใฃ็กใใงๅใๆใใใ1ใใใใใใใใใชใใ3ๅ26็งๆใใใปใใใพใใงใใใ
3ๆกใฎๆฐๅญใๆฐๅคใซๅคๆใใใฎใซๆณฅ่ญใๆธใไธใใฆใใพใฃใใใใใฃใจ็ฐกๅใซ ๆธใใ ใใใใซใใฆใ c1 ใงใฏใชใ c5 ใจๆธใใใจใใใใ็ฆใใๆใใใใฆ็ใ
ใใใ
Num c100 = s.at(3) - '0';
Num c10 = s.at(4) - '0';
Num c5 = s.at(5) - '0';
Num c = c100 * 100 + c10 * 10 + c5;const auto c = std::atoi(s.substr(3).c_str());ใณใผใใฏใใกใ
XORใ ใจๆใฃใใใใใ ใฃใใ
Aๅ้กใจๅๆงใซ็ซใกไธใใใๆชใใboolใฎๅ่ปขใใฉๅฟใใใใ ~ ใ ใ ! ใ ใ ^ ใ ใๅใใใชใใชใฃใฆใไธ้
ๆผ็ฎๅญใงๆธใใฆใใพใฃใใๆญฃใใใฏ ใใ ๆธใใ
ns.at(t) = b ? false : true;ns.at(t) = !ns.at(t);ใณใผใใฏใใกใ
ไฝ็ฝฎ
-
$A_i = i$ ใชใใใใงใซๅฎไฝ็ฝฎใชใฎใงไฝใใใชใ - ใใใงใชใใใฐ
$i$ ใจ$v = A_i$ ใจไบคๆใใใ$i$ ใฏ$p = P_i$ ใซใใใ$v$ ใฏ$P_v = i$ ใซใใใฎใงใ$A_i = i, A_p = v, P_i = i, P_v = p$ ใจใใใใใใง$i, p$ ใๅบๅใใใ
1ๅใฎๆไฝใง
ใณใผใใฏใใกใ
Dๅ้กใ9ๅ7็งใง่งฃใใใจใฏๆใใชใใฃใใE,Fๅ้กใใกใใฃใจ่ฆใๆ้่พผใฟใงใใใ
ๅ้้ขไฟ
ๅใซ
ใณใผใใฏใใกใ
ใพใใEๅ้กใ11ๅ21็งใง่งฃใใใจใฏๆใใชใใฃใใ
ๆฎ้ใซใกใขๅๅๅธฐ็ขบ็DPใงใใใๅ ้ฑใฏใฒใผใ ๆจใๅฎ่ฃ ใใใ ใใจ่งฃใฃใฆใใใฎใซใใใใฐใ็ตใใใชใใฃใใใไปๅใฏไธ็ญๆธใใงACใใใ
ๆดๆฐ
-
$v = 0$ ใชใใณในใใฏ0ใงใใ - ใใงใซใณในใ
$DP[v]$ ใๆฑใใฆใใใใกใขใใๅคใ่ฟใ
ๅๅธฐไธญใฎใใผใ
$X + DP[\lfloor v/A \rfloor]$ $6/5 \times Y + 1/5 \times \sum_{i=2..6} DP[ \lfloor v/i \rfloor]$
ๅ
ฌๅผ่งฃ่ชฌ2ใซใใใจใใๆไฝ2ใๆ้ฉใชใใๆไฝ2ใง1ใฎ็ฎใๅบใๅพใซๆไฝ1ใซไนใๆใใใใจใฏใใๅพใชใใจใใใฎใ้่ฆใงใใใใชใใชใใตใคใณใญใง1ใฎ็ฎใๅบใฆ
ๆฎใ63ๅใใฃใใ่งฃๆณใๅใใใชใใฃใใ็ฏๅฒใใใๆใใซในใฟใใฏใซ็ฉใใใ้ ๅปถใปใฐใกใณใๆจใไฝฟใใใใฉใกใใฎ่งฃๆณใๆฑบใๆใๆฌ ใใใพใพ้ ๅปถใปใฐใกใณใๆจใ้ธใใ ใใใฏใ่งฃใใใจใฏใงใใชใใฃใใ
ๅ ฌๅผ่งฃ่ชฌ1ใซๅบใฅใๅฎ่ฃ ใฏ ใใกใ ใในใฟใใฏใงใฏใชใๅๅธฐใ็ฏๅฒใๆฑใใใฎใงใฏใชใๆๅญใ้ๆฌกๅบๅใใใใจใๆใใคใใชใใฃใใๅ ฌๅผ่งฃ่ชฌ2ใฏใใใซ็ฐกๆฝใง ใใ ๅฎ่ฃ ใงใใใ
ใฉใใใฆใใใใใฎ่งฃๆณใๆใใคใใชใใฃใใ็งใซFๅ้กใฏๅณใใใจใใๆใ่พผใฟใใใ(ใฎใชใฎใช้diffใ ใฃใ)ใๅๅๅใ ๅใๆฅตๅบฆใฎ็ทๅผตใงใใใใฐใ้ฒใพใชใใฃใใฎใงไปๆฅใฏๅฐใใใใใใใใจๆใฃใใฎใใไปๅใฏใฒใฉใใใจใซใฏใชใใชใใฃใใ5ๅฎใงใพใใพใใฎ้ ไฝใ ใฃใใฎใงFๅ้กใฎ่งฃ็ญ่ ๆฐๆฌก็ฌฌใจใฏใใใใถใๆฐด่ฒใซๆปใใใจๆใฃใใใใณใณใในใไธญใซๆใใจใใใฏ่ฒใ ใใฃใใๅใซๆดๅฏๅใ่ถณใใชใใ ใใ ใฃใใ
ใณใณใในใ27ๅ็ฎใงใใใใณใณใในใไธญใซA,B,C,Dใฎ4ๅฎใใใฎ็ดๅพใซE,Fใ่ชๅACใใใDๅ้กใซๆ้ใๆใ้ใใฆใE,Fๅ้กใ่งฃใๆ้ใ็กใใฃใใๅ้ก้ธใณใไธๆใจใใใใใDๅ้กใฎใใใใฐใไธๆใใใใ
ใณใผใใฏใใกใ
ๅถ็ดใใใ
ใณใผใใฏใใกใ
ใในใฆใฎใในใ่ชฟในใฆใๆๅญใ็ฐใชใๅ ดๆใๅบๅใใใ
ใณใผใใฏใใกใ
ใใ่ใใใใใใผใซใฎๅคงใใใฏ2ใฎ็ดฏไนใชใฎใงใ2ใคใฎใใผใซใ่ถณใใฆใใใฏใใใผใซใฎๅคงใใใฏ2ใฎ็ดฏไนใงใใใใใใซๆฐใไปใใไปฅไธใฎ่งฃใๆธใใฆใใพใใTLEใใใฎใงใฏใชใใใจ็ฆใฃใใ
std::pair<std::set<Num>, Num> ใงๆใคใๅๆไฝใฏไปฅไธใฎ้ใๅฏพๅฟใใใ
- ใใผใซ
$({ A_i } , 0)$ ใ่ฟฝๅ ใใใ - 2ใคใฎใใผใซใฎ็ซใฃใฆใใใใใใ็ญไพกใงใใใใจใ่ชฟในใใใคใพใใใผใซ
$A = ( { A_1, A_2, ... } , S_A)$ ใฎใจใใใใใ${ A_1 + S_A, A_2 + S_A, ... }$ ใ็ซใฃใฆใใใๅๆงใซใใผใซ$B = ( { B_1, B_2, ... } , S_B)$ ใฎใจใใใใใ${ B_1 + S_B, B_2 + S_B, ... }$ ใ็ซใฃใฆใใใไธก่ ใไธ่ดใใใใจใ็ขบ่ชใใใ - 2ใคใฎใใผใซใฎ็ซใฃใฆใใใใใใ็ญไพกใชใใใใผใซ
$B$ ใๅ้คใใฆใใใผใซ$A$ ใฎใทใใๅคใ$S_A$ ใ1่ถณใ
ไธ่ฌ่งฃใจใใฆใฏใใใงใใฃใฆใใใฎใ ใใใใใใใใผใซใฏ2ใฎในใไนใคใพใ็ซใฃใฆใใใใใใฏๆญฃ็ขบใซ1ๅใชใฎใงใใใฃใจ็ฐกๅใชใใผใฟๆง้ ใจใใฆใ็ซใฃใฆใใใใใใใ ใ1ๅ็ฎก็ใใใฐใใใฃใใใใ ๅฎ่ฃ ใใใ
ใณใผใใฏใใกใ
Dๅ้กใฎใใใใฐใซ63ๅ36็งๆใใฃใใEๅ้กใซ27ๅ29็งใFๅ้กใซ34ๅ51็งใชใฎใงใDๅ้กใๆจใฆใฆEๅ้กใจFๅ้กใ่งฃใใๆนใ้ซๅพ็นใง้ซใใใฉใผใใณในใ ใฃใใๅ้ก้ธใณใ้้ใใใจใใใใใDๅ้กใซๆ้ใๆใ้ใใงใใใ
ๆฎ้ใซBFSใง่งฃใใใฏใใ ใฃใใฎใ ใใใคใพใง็ตใฃใฆใใใใใฐใ็ตใใใชใใใจใใใๅ ฅๅไพใใ้ใใชใใฃใใฎใงใใใซใใฃใฎๅฑฑใ็ฏใใใ
ๆนใใฆไธใใ ่งฃใ็ดใใฆ ่งฃๆณใ่ฟฝใฃใฆใฟใใใพใ็ญใใฎๆไฝๅคใฏ1ใงใใ(็ฃ็ณใฎ็ฝฎใใใฆใใชใใในใๅฐใชใใจใ1ใคๅญๅจใใใฎใง)ใใใฎไธใงใ็ฃ็ณใซๅผใใใชใใในใๆฑใใ็ฃ็ณใซๅผใใใชใใในใไธไธๅทฆๅณใซ้ฃ็ตๅฏ่ฝใชใunion-findๆจใง้ฃ็ตใใใ
็ฃ็ณใซๅผใใใชใใในใ้ฃ็ตใใฆ้ๅ
BFSใซใใใฆใ็ฃ็ณใซๅผใใใฆๆญขใพใใในใพใงใฎ็ต่ทฏใ่คๆฐใใใใใฎใงใ้่คใใฆๆฐใใชใใใใซใใใใใใใใใฎๅฆ็ใ้้ใใใใใซใๅ
ฅๅไพใฏ้ใฃใฆใWAใซใชใฃใฆใใพใฃใใจๆใใใใTLEใๆใใฎใ ใใๅใซ็ฃ็ณใซๅผใใใฆๆญขใพใใในใ้ๅ std::set<Num> ใซใพใจใใฆใ std::set<Num>::size() ใใใACใใใใใฎๅ้ฟ็ญใๆใใคใใพใง1ๆ้ๆใใฃใฆใใพใใE,Fๅ้กใ่งฃใๆ้ใ็กใใชใฃใฆใใพใฃใใTLEใใชใใใจใฏใๅ
ฌๅผ่งฃ่ชฌ1ใซ่ชฌๆใใใใใ็ฐกๅใซ่จใใฐ็ฃ็ณใซๅผใใใฆๆญขใพใใในใซใฏไธๆนๅใใใใๅฏใใชใใฎใงๆๅคงๆข็ดขๅๆฐใ set ใง
Union-findๆจใ็จใใ่งฃๆณใฏๅ ฌๅผ่งฃ่ชฌ2ใจๅใใงใใใๆๅใใๆใใคใใฆใใใฐใFๅ้กใ่งฃใๆ้ใใใฃใใๅ ฌๅผ่งฃ่ชฌใซใใ้ใใUnion-findๆจใไฝฟใใชใBFSใใๅฟ ่ฆใฏใชใใUnion-findๆจใฎๅจใใ ใ็ฃ็ณใซๅผใใใฆๆญขใพใใในใใฉใใๆข็ดขใใใฐใใใๅฎ่ฃ ใฏ ใใกใ ใ
ใณใผใใฏใใกใ
Fๅ้กใ้่ฆใชใใณใใซใชใฃใฆใใใ
ๆใ45ๅบฆๅ่ปขใใๅบงๆจ็ณป
้่ฆใช็นใจใใฆใ่ท้ขใฎๅใๅใใฎใ ใใ
-
$A = {A_i = X_i + Y_i : i = 1..N }$ ใใฝใผใใใ$A$ ใฎใใกๆใๅฐใใๅคใงๅผใใฆๅ็นใ0ใซใใ -
$A$ ใๅบงๆจๅง็ธฎใใฆใ้ซใ$N$ ๅใฎใคใณใใใฏในใซไปใๆฟใใใ -
$A$ ใฎ้้ (ใคใณใใใฏในใฎ้้ )ใซใปใฐใกใณใๆจใซ่ผใใใใปใฐใกใณใๆจใจใใฆใฏใ$A$ ใฎๅค$Atree$ ใจใ$A$ ใฎๅบ็พๅๆฐ$Ctree$ ใฎ2ๆฌใ็จๆใใใ - ่ผใใๅพใฎๆไฝใฏใ351-Fใฎ่งฃ่ชฌใๅ็ ง
ๆณจๆ็นใจใใฆใ
ๆน้ใฏๅ ฌๅผ่งฃ่ชฌ้ใใงใใใๅ็นใ0ใซๅ่ฆ็ด ใ้่ฒ ใซใใใฎใงใๅ ฌๅผ่งฃ่ชฌใซใใ้ใใปใฐใกใณใๆจใไฝฟใใพใงใใชใ็ดฏ็ฉๅใง ๆฑใพใ ใ
ๅ
ฌๅผ่งฃ่ชฌใฎๅผๅฐๅบใใณใณใในใไธญใซ่กใใฎใฏๅคงๅคใ ใใๅบงๆจใฎๆๅฐๅคใ0ใซใทใใใใใจๅณๅฝข็ใซ็่งฃใงใใใๅ
ฌๅผ่งฃ่ชฌใฎๅผใฏใ
ใณใผใใฏใใกใ
C,Dๅ้กใซๆ้ใๆใ้ใใACใใใฎใฏ11ๅ3็ง้ ใ(22:51:03)ใงใใฃใใ6ๅฎใฏใจใใใ5ๅฎใฏใใใใฃใใ
่ฒ ใฎๆฐใ่ถณใใชใๆไฝใใ0ใ่ถณใๆไฝใซ็ฝฎใๆใใใฐใใใๅฆไฝใซใใปใฐใกใณใๆจใฎๅบ็ชใงใใใ
ๆๅใซ
- ไปๆไฝใใใใจใใฆใใๅค
$A_p$ ใซใคใใฆใ ๅง็ธฎๅพใฎๅบงๆจใ$I_p$ ใจใใ -
$A_p$ ใใๅคงใใชๅคใฎๅใฏ$sum_p = Atree.prod(I_p+1, N)$ ใงใใ -
$A_p$ ใใๅคงใใชๅคใฎๅๆฐใฏ$count_p = Ctree.prod(I_p+1, N)$ ใงใใ - ๅ้กๆใฎๅ
ๅดใฎ
$\sum$ ใฎไธญใฏ$sum_p - count_p \times A_p$ ใงใใใใใใ่งฃ$total$ ใซ่ถณใใ -
$Atree[I_p]$ ใซ$A_p$ ใ่ถณใใๅใๅบงๆจใซ่คๆฐใฎ$A$ ใใใๅ ดๅใซๅฏพๅฟใใใ -
$Ctree[I_p]$ ใซ1่ถณใใไธ่จใจๅๆงใ
ใใใใฆๆฑใใ
ๅ ฌๅผ่งฃ่ชฌ5ใฎใใใซใๅบงๆจๅง็ธฎใ็กใใใฆ FenwickTree ใไฝฟใใจใใใ ใ ็ญใใชใ ใ10ๅใง่งฃใใชใใใใใๅทฅๅคซใๅฟ ่ฆใงใใใ
ใณใณใในใ28ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใฌใผใใฃใณใฐใไธใใฃใใDๅ้กใพใง23ๅ40็งใฏใพใใพใๆฉใใฃใใใใใฎๅพEๅ้กใ76ๅๆใใฆ่งฃใใชใใฃใใEๅ้กใ่งฃ่ชฌACใใใใใชใใฃใใฎใงใไปฅไธใฎๆฏใ่ฟใใใใพใๆธใใใจใ็กใใ
ใณใผใใฏใใกใ
Yes ใใใใงใชใใใฐ No ใงใใใ
ใณใผใใฏใใกใ
349-Cใใไปๅบฆใฏ
ใณใผใใฏใใกใ
้ ญใ่ฉใใๅบใฆใใ้ซใใฎๅทฎๅ
ใณใผใใฏใใกใ
ๅ้กๆใ็่งฃใใใฎใๅคงๅคใ ใฃใใ่ฆใใใซ
ใณใผใใฏใใกใ ใ่งฃ่ชฌACใงใใใ
ใฏใฉในใซใซๆณใๅน็็ใซๅฎ่กใใใใจใใใฎใฏๅใใฃใใใใฏใฉในใซใซๆณใฎ้ไธญใงใงใใฆใใ่คๆฐใฎๆๅฐๅ จๅ้จๅๆจใใฉใใใฃใฆใใผใธใใใใใใฃใฑใๅใใใชใใฃใใ
ๅ ฌๅผ่งฃ่ชฌใ่ชๅใฎ่จ่ใง่จใๆใใใ
่พบ
่พบ
ๅๆงใซ่พบ
ไปฅไธใใใ
ๆขใซใใๆๅฐๅ
จๅๆจใซใ้ ็น้ๅ
ใณใณใในใ29ๅ็ฎใงใใใใณใณใในใไธญใซA,B,C,Dๅ้กใ4ๅฎใใใใฎๅพEๅ้กใ่ชๅACใใใEๅ้กใฎ่งฃๆณใฏไธใคใงใฏใชใใใใณใณใในใไธญใซๆใใคใใชใใฃใใฎใใใใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅฎ่ฃ ใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใใทใใฅใฌใผใทใงใณใใใๅ จใฐใซใผใใใขใใฉใฏใทใงใณใซ่ชๅฐใใๅพใซในใฟใผใใใใใฎใๅฟใใชใใ
- ใขใใฉใฏใทใงใณใฎ็ฉบใๅฎน้ใ
$C := K$ ใงๅๆๅใใ - ใฐใซใผใใฎไบบๆฐใ
$G$ ใ$G \leq C$ ใชใใใใฎใฐใซใผใใ่ผใใฆ$C := C - G$ ใซใใ - ใใใงใชใใฆ
$G > C$ ใชใใใขใใฉใฏใทใงใณใในใฟใผใใใใฆ(ในใฟใผใๅๆฐใ1ๅขใใใฆ)ใ$C := K$ ใซใใใใใฎๅพ2.ใซๆปใใ - ๅ
จใฐใซใผใใ่ผใใๅพ
$C \ne K$ ใชใใ่ชๅฐใใใพใพใฎใฐใซใผใใใพใ ๆฎใฃใฆใใใฎใงใใขใใฉใฏใทใงใณใในใฟใผใใใใใใจใใใใๆฎใฃใฆใใใฏใใงใใ(ใขใใฉใฏใทใงใณใ็ฉบใฎใจใใซใขใใฉใฏใทใงใณใในใฟใผใใใใชใใฎใง)ใ
ใณใผใใฏใใกใ
ไธ่ฆใใฆ่งฃใใใใซใชใใฃใใฎใงDๅ้กใ่งฃใใEๅ้กใ20ๅๆใใฆ่งฃใใชใใฃใใฎใงCๅ้กใ่งฃใใใEๅ้กใๅพๅใใซใใใฐใใฎๅใใใฉใผใใณในใไธใใฃใใใๅฑใใC,Eๅ้กใๅ ฑๅใใซ็ตใใใจใใใ ใฃใใC,Eๅ้กใจใใซ้ฃใใใฎใ ใใ้ฃๆๅบฆใฎ่ฆๆฅตใใใพใ้ฃใใใฃใใ
ๅ
ฌๅผ่งฃ่ชฌใฏ
ใณใผใใฏใใกใ
Cๅ้กใใๆใใใฃใใ
ใใใง
ๅ ฌๅผ่งฃ่ชฌใ่ชญใใจใใใฃใจใใฃใใๅฎ่ฃ ใงใใใใใใใงใใชใใจใไปใฎๅ้กใ่งฃใๆ้ใใฒใญใๅบใใชใใ
ใณใผใใฏใใกใ
Trieๆจใๅฟใใฆใใใๅ ฌๅผ่งฃ่ชฌ2ใใใใใจใ่ฉฆใฟใฆๅคฑๆใใrolling hashใๆใใคใใใฎใฏใณใณใในใ็ตไบๅพใไธๅๆฐๅ็ตใฃใฆใใใงใใใๆน้่ปขๆใ้ ใใฆrolling hashใๆใใคใใชใใฃใใฎใฏ้ ใใชใใ
Rolling hashใฎไฝฟใๆนใฏใใคใ้ใใงใ็ด ๆฐใ่คๆฐไพใใฐ
ๅ ฌๅผ่งฃ่ชฌ2ใซใใ้ใใๆ้ ใซไธฆในๆฟใใๆๅญๅใซใคใใฆใใใๆฅ้ ญ่พใๅใๅบ้ใๆฑใใใฐใใใใชใใจใชใใใฎๆนๆณใง่กใใใจๆใฃใใใๅ ทไฝ็ใชใขใซใดใชใบใ ใซ่ฝใจใ่พผใใใจใใงใใชใใฃใใๅ ฌๅผ่งฃ่ชฌใ่ฆใฆๅฎ่ฃ ใใใใฎใ ใใกใ ใงใใใ
Trieๆจใจใฏ่ฆใใใซ็พไบบไธ้ฆใฎๆฑบใพใๅญใๆงๆใใๆจๆง้ ใงใใใๅฎ่ฃ ใใใจ ใใกใ ใๆฑบใพใๅญใฏใณใณใในใไธญใซๆใใคใใใใ็ฟๆในใฏใฉใใใใๅฎ่ฃ ใใใฎใซ51ๅๆใใฃใใฎใงใใณใณใในใไธญใซACใใใซใฏ้ใซๅใใชใใRolling hashใๆๅใซๆใใคใใใใใณใณใในใไธญใซACใงใใ่ฆ่พผใฟใฏใชใใฃใใ
้ก้กใฏ ABC 287-E ใงใๅ้กๅใฏใใฎใใฎใใฐใ Karuta ใงใใใใฝใผใใใฆ่งฃใๆนๆณใจใTrieๆจใไฝใ ๆนๆณ ใใใใ
ใณใณใในใ30ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใงใใใๆญฃ่งฃ่ ๆฐใใใใฆDใใEใฎๆนใๆใใใใ ใจๆใฃใฆE,Dใฎ้ ็ชใซ่งฃใใฎใใTLEใจWAใๅบใฆใๅท้ใซๅใ่ฟใใฆACใใใใจใใงใใใฎใงใใณใณใในใไธญใฎๆฏ่ใใใพใใพใไธๆใใชใฃใใใใงใใใใจใฏใใ4ใใใฏใใใใใงใใฌใผใใฃใณใฐๆฐด่ฒใ้ใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใใทใใฅใฌใผใทใงใณใใใฐใใใฎใ ใใใซใผใใๆใใใฟใคใใณใฐใ้้ใใใใงใใใ
-
$d = 0$ ๆฅ็ฎใงๅๆๅใใ - ๆค็ฉใ
$2^i : i \geq 0$ ไผธใฐใใ$2^i$ ใซใชใใใงใฏใชใใฎใงๆณจๆใ - ๆฅๆฐใ1ๅขใใ
ใณใผใใฏใใกใ
std::vector<std::pair<std::string, Num>> ใฏไฝ่จใ ใฃใใ
ใณใผใใฏใใกใ
350็นๅ้กใ ใจๆใฃใฆ่ญฆๆใใใใๆ ้ใซๅฎ่ฃ ใใใฐใใใฃใใ
std::vector<std::tuple<Num,Num,Num>> ใซๅ
ฅใใฆๆ้ ใซใฝใผใใใใไธ็ฌ struct operator < ใไฝฟใใใจใใใฎใฏๆ้ใฎ็ก้งใงใใใ
ๅพใฏใซใผใใๅ ้ ญใใ้ ใซๅใๅบใใๆจใฆใใๆจใฆใชใใๅคๆญใใใๅคๆญๅบๆบใฏใๅผฑใใซใผใใฏใณในใใๅใใๅฎใใชใใใฐใชใใชใใใจใใใใจใงใใใ
-
$A_{base}$ ใจ$C_{base}$ ใ็ก้ๅคงใงๅๆๅใใ -
$A_i < A_{base}$ ใใค$C_i \leq C_{base}$ ใชใใซใผใ$i$ ใๆจใฆใชใใไฝตใใฆใ$A_i := A_{base}$ ,$C_i := C_{base}$ ใซๆดๆฐใใใ -
$A_i < A_{base}$ ใใค$C_i > C_{base}$ ใชใใซใผใ$i$ ใๆจใฆใใๅ้กๆ้ใใงใใใ -
$A_i = A_{base}$ ใชใใใซใผใ$i$ ใๆจใฆใใใชใใชใๅผทใใๅใใงใณในใใไฝใใซใผใใใใใชใใใ้ใใฆใใใฏใใ ใใใงใใใ
ๅ ฌๅผ่งฃ่ชฌใฏๅผทใใงใชใใณในใใฎ้ ใซ่ตฐๆปใใฆใใใ
ใณใผใใฏใใกใ
Eๅ้กใใ้ฃใใใฃใใใEๅ้กใฎใกใขๅใๆใๅบใใชใใฃใใDๅ้กใฎๆนใๆใใใฃใใจ่จใใใ้ใฉใใจใใใง5ๅฎใงใใใ
ๅ็นใ
ๅพใฏ
- 4x4ใใน(้ข็ฉใฏ16)ใซใคใใฆใ้ข็ฉใฏ
$cx \times cy \times 16$ - ๅณใซใฏใฟๅบใใ
$rx \in {0..3}$ ๅ(้ข็ฉใฏ$r[0..3] = 0,6,12,14$ )ใซใคใใฆใ้ข็ฉใฏ$cy \times r[rx]$ - ไธใซใฏใฟๅบใใ
$ry \in {0..3}$ ่กใซใคใใฆใ้ข็ฉใฏ$cx \times ry \times 4$ - ๅณไธใซใฏใฟๅบใใ
$rx \in {0..3}$ ๅ$ry \in {0..3}$ ่กใซใคใใฆใ4x4ใฎๆฉ่ฆ่กจ$table[ry][rx]$ ใใๆฑใใใ
Num table[4][4] = {
{0,0,0,0},
{0,2,3,3},
{0,1,3,4},
{0,2,3,3}
};
331-Dใฎๆ่จใฏ็ใใฆใใใใ349-Eใฏๅฎๆฐใใผใใซใ้้ใใฆACใงใใชใใฃใใใไปๅใฏACใงใใใใใใACใใใพใง2ๅใWAใใใฎใฏ้ ใใชใใ
ใณใผใใฏใใกใ
Cๅ้กใACใใๆ็นใงใDๅ้กใใEๅ้กใๆญฃ่งฃใใไบบใๅคใใฃใใฎใงใEๅ้กใๅ ใซ่งฃใใใ็นๆฐใ้ซใใฆๆใใๅ้กใ้ธใถใฎใฏๅ็็ใงใใใใใใๅฑใใๆฒผใซใใใใใใ ใฃใใ
349-Eใ่งฃใๆใญใๆชๅคขใ้ ญใใใใใไปๅบฆใใใฏใฒใผใ ๆจใ่งฃใใฆ่ฆใใใจๆๆฐ่พผใใ ใฎใ ใใใใ่ใใใๆจใงใฏใชใใฎใงTLEใใใใชใใจใใใฃใใใชใใใใซใใฃใงใใใใ้ฟใใใๅๅ ฅๆฐดใงใใใใใใใชใใ
่งฃ่ชฌใซใฏbitDPใจใใใๅไบบ็ใซใฏ็ถๆ ใใซใผใใฎๆ็กใซๅฏพๅฟใใ็ถๆ ้ท็งปใ่พบใจใใๆๅใฐใฉใใจ็่งฃใใฆใใใๅๆ็ถๆ ใซใในใฆใฎใซใผใใใใ็ถๆ ใงDFSใใใใชใใฟใฎใฒใผใ ๆจใจๅใๆข็ดขใ่กใใ349-Eใฎ่งฃ่ชฌใจใปใผๅใใงใใใ
- ไธๆ็ฎใฎๆ็ช
$P_1$ ใฏ Takahashiใๆฌกใฎๆ็ช$P_2$ ใฏ Aoki ใใใฎๆฌกใฎๆ็ช$P_3$ Takahashi ... ใ็นฐใ่ฟใใๆ็ชใใจใซใซใผใใๆธใใฎใงใใใคใใฏๆ่ฉฐใพใใซใชใใ - ๆ็ช
$P$ ใซๅใใใซใผใใใชใใใฐๅพๆ$\lnot P$ ๅฟ ๅใงใใใ - ๆ็ช
$P$ ใซๅใใใซใผใใใใใฐใๅใฃใๅพใฎ็ถๆ ใซ้ท็งปใใใๅใฃใๅพใฎ็ถๆ ใซ$P$ ๅฟ ๅใฎๆใใใใฐใใใฎๆใๆใคใฎใง$P$ ๅฟ ๅใงใใใๅใฃใๅพใฎ็ถๆ ใซ$P$ ๅฟ ๅใฎๆใไธใคใใชใใใฐๅพๆ$\lnot P$ ๅฟ ๅใงใใใ
ๆ็ชใจใจใใซใซใผใใฏๅ่ชฟๆธๅฐใใใใๆจๆง้ ใงใฏใชใ(ใใ็ถๆ
ใซ้ท็งปใใ็ถๆ
้ท็งปๅ
ใ่คๆฐใใ)ใฎใงใใกใขๅใใชใใจTLEใใใใใใใใฃใใๅฟใใฆ15ๅใจ2ใใใใใใฃใฆใใพใฃใใๅใ้คใใใซใผใใฎ็ตใฏ
ใณใผใใฏใใกใ
ๅ
จใ่ฆๅฝใใคใใชใใฃใใฎใง่งฃ่ชฌใ่ชญใใงๅฎ่ฃ
ใใใใจใใใใupsolveใใใฎใฏๅ
ฌๅผ่งฃ่ชฌใฎใณใผใไพใจใปใผๅใใงใใใใปใฐใกใณใๆจใไฝฟใฃใ LISใฎๆฑใๆน ใจใๅบงๆจๅง็ธฎใฎไปๆนใๅญฆในใใไปใพใงๅบงๆจๅง็ธฎใฏ for(const auto& [k,v] : a std::map) ใใฆใใใใใใใใๆนๆณใใใใ
ใณใณใในใ31ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใใใE,Fๅ้กใฎๆญฃ่งฃ่ ๆฐใๅฐใชใใใฆใฌใผใใฃใณใฐใๆฐด่ฒใซใชใฃใใ
ใณใผใใฏใใกใ
้ๅ -1 ใๅบๅใใใ
std::set::erase(value) ใฏใ value ใซ่ฉฒๅฝใใ่ฆ็ด ใ้ๅใซใชใใใฐ ไฝใใใชใใ std::set::contains ใฏๅใซไบๅบฆๆ้ใงใใใ
ใณใผใใฏใใกใ
Yes ใไธใคใใชใใใฐ No ใงใใใๅ
ฌๅผ่งฃ่ชฌใฏๅฐใ็ฐใชใใ
ใณใผใใฏใใกใ
ใณใผใใฏใใกใ
ใใ่ฆใใ3็งๅถ้ใฎ2637 msใ ใฃใใใใใใใง้ใฃใใใๅ ฌๅผ่งฃ่ชฌ2ใฎๆนๆณใชใฎใงใใใฎใ ใใใ
ๅคงใใ
ๅ
ฌๅผ่งฃ่ชฌใซใใ้ใใๅฐบๅใๆณใง
ใณใผใใฏใใกใ
ไฝใจใชใ่งฃๆณใฏๅใใ(349-D)ใใใใใขใซใดใชใบใ ใซ่ฝใจใ่พผใใใจใใใจใฉใใใฆใใใใใฃใฑใๅใใใชใใ70ๅๆใใฃใฆ่งฃใใใๅ ฌๅผ่งฃ่ชฌใ่ชญใใงใ่งฃใใใๅ ฌๅผๅฎ่ฃ 2ใฎๅฎ่ฃ ไพใ่ฆใฆใใใใๅใใฃใใๅข็ๅคใฎๆฑใใใจใฆใๅคงๅคใงใใใ
349-Dใซๅฏพใใฆใๅ ็ฎใ ใใงใชใๆธ็ฎใใงใใใใใซใใฆใๅบ้ๆฐใๆใๅฐใชใๅบ้ๅๅฒใ้ธในใฐใใใๅ
ฌๅผ่งฃ่ชฌ2ใซใใใใใซๅๅธฐ็ใซใใในใใงใ
ใณใผใใฏใใกใ
ๅ จใ่งฃๆณใฎ่ฆๅฝใใคใใชใใฃใใฎใงใ่งฃ่ชฌใ่ชญใใงๅฎ่ฃ ใใใDiffใใฌใผใใฃใณใฐ+700ใใใใซใชใใจใใใใใๅ้กใ่งฃใใไบบใฏใใใใงใใญใจใใๆๆณใ ใใซใชใฃใฆใใฉใใใฃใใ่ชๅใใงใใใใใซใชใใฎใใซ่ฝใจใ่พผใใชใใ
ใณใณใในใ32ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใงใใใDๅ้กใฎๅฎ่ฃ ใๅใใใซใใใใฏใซใชใใใใ ใใ ใซใชใฃใใพใพEๅ้กใ่ฝใจใใใ
ใณใผใใฏใใกใ
ใใๆนใฏ่ฒใ
ใใใใใ ใใ std::reverse ใๅใใใใใใใคใใฌใผใฟใงๆๅฎใใๅบ้ใฏ
ใณใผใใฏใใกใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใ็ทๅฝใใใใใฐใใใ
- ๆญฃใใ้ตใฎใใฟใผใณใฏ
$0..(2^{N}-1)$ ๅใใใฎใงใ้ต$i$ ใๆญฃใใ =$i$ ใใใ็ฎใ็ซใฃใฆใใใจใใใใใใใฟใผใณใ่ฉฆใ - ๆญฃใใ้ตใฎใใฟใผใณใๆฑบใๆใกใใฆใๆญฃใใ้ตใ
$K$ ๆฌไปฅไธใงใใขใ้ใใใๆญฃใใ้ตใ$K$ ๆฌๆชๆบใงใใขใ้ใใชใใใฐใใฎๆญฃใใ้ตใฎใใฟใผใณใฏๆกไปถใๆบใใใใใใงใชใใใฐๆกไปถใๆบใใใชใใ
ใใฎๆ็นใง็ฌ้1186ไฝใชใฎใงใไปๆฅใฏใคใฑใใจๆใฃใใฎใ ใ...
ใณใผใใฏใใกใ
่งฃๆณใฏใใใซๆใใคใใใใๆดๆฐใชใผใใใญใผใฎๆฑใใๅ จใๅใใใใใใใฏใซใชใฃใใใใพใใซใๆททไนฑใใฆใปใจใใฉๆญฃใใใณใผใใๅฃใใฆใใพใใ30ๅ20็งใจ1ใใใซใชใฃใฆใใพใฃใใ
0101... ใ1ใใใ็ฎใฏ 00110011... ใจไธฆใถใ
ใคใพใ
-
$2^i$ ๅใฎ0ใจ$2^i$ ๅใฎ1ใไธฆใถใใฟใผใณใ็นฐใ่ฟใ - ใใฟใผใณใฎ้ทใ(็ซฏๆฐๅๆจใฆ)ใฏ
$C_{i} = (N+1) / 2^{i+1}$ ๅใงใใใpopcount ใฏ$C_{i} \times 2^{i}$ ๅใงใใใ - ใใฟใผใณใฎๅพใซ็ถใ็ซฏๆฐใฏ
$R_{i} = (N+1) mod 2^{i+1}$ ๅใงใใใpopcount ใฏ$max(0, R_{i} - 2^{i})$ ๅใงใใใ
ใฉใใใๅฐใ้้ใใฆใ้ใฃใฆใใพใๅ
ฅๅไพใฐใใ็จๆใใใใฟใใใงใใใๆดๆฐใชใผใใใญใผใฎๅฏพๅฆใ้้ใใไธใundoใ้ฃๆใใๅพใซๆธใใใณใผใใง / ใจ % ใ้้ใใใใจใซๆฐใไปใใชใใฃใใฎใ็ใใฃใใifใใญใใฏใซ {} ใใคใณใใณใใ็กใใไฝ่ฃใ็กใ้ใใ็ใ
ใใใณใผใใงACใใใใใใใซๅฎ่ฃ
ใ็ดใใจ ใใ ใชใใ
Rubyใงไปปๆ็ฒพๅบฆๆดๆฐใใคใใใฐ็ฐกๆฝใซ ๆธใใ ใๅ ฌๅผ่งฃ่ชฌ3ใจใปใผๅใใงใใใ
ใณใผใใฏใใกใ
ๅนณๆนๅๅฒใไฝ่จใ ใฃใใ
็ทๅใๅใใฎใซ้ ๅบใซๆๅณใฏ็กใใฎใงใ
ใณใณใในใ33ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใใณใณใในใๅพใซEๅ้กใ่งฃใใใๅ ้ฑๅๆงใDๅ้กใฎๅฎ่ฃ ใๅใใใซๆ้ใๆบถใใใEๅ้กใใใใใฐใซๆ้ใๆใ้ใใฆใณใณใในใใฎ็ท ใๅใใซใฏ้ใซๅใใชใใฃใใ
ใณใผใใฏใใกใ
ๅ้กๆใๆญฃ็ขบใซๅฎ่ฃ ใใใฐใใใฎใ ใใๆญฃ็ขบใซใใใฎใๅคงๅคใงใใใ
-
$M \leq H_i$ ใชใๆถๆฏๅฏ่ฝใใใใงใชใใใฐๆถๆฏไธๅฏ่ฝ - ๆถๆฏๅฏ่ฝใใฉใใใซ้ขใใใ
$M := M - H_i$ ใจๆดๆฐใใ
ใณใผใใฏใใกใ
ๅ้กๆใๆญฃ็ขบใซๅฎ่ฃ
ใใใฐใใใ std::toupper(c) ใฏๅคงๆๅญใๅคงๆๅญใฎใพใพๅคใใชใใ std::tolower(c) ใๅฐๆๅญใๅฐๆๅญใฎใพใพๅคใใชใใ
ใณใผใใฏใใกใ
ๅๅธฐใงๅฎ่ฃ
ใใใใฌใใซ
ใณใผใใฏใใกใ
็ญๆฏ็ดๆฐใฎๅ ฌๅผใฏ่กๅใใใใชใณใฐใใใจ้ซ้ใซๆฑใพใใใจใฏใใใๅ ฌๅผ่งฃ่ชฌใจไธ่จใ่ชญใใฐๅใใ้ใใใใพใงใใๅฟ ่ฆใฏใชใใ่กๅใฎไฝฟใๆนใๆใๅบใใฎใซ10ๅๆใใฃใใฎใ็ใใฃใใๅฎใ่จใใจ่กๅใไฝฟใใฎใฏๅฐไฝใซๅฏพใใฆ้ๅ ใๅฎ็พฉใงใใชใใจใใงใใฃใฆใใณใณใในใไธญใซๆๅบใใๆนๆณใงใฏๆๅณใ็กใใๆญฃใใใฏ ABC 293-E ใจๅๆงใซ ใใ ไฝฟใใ
ACLใฎModintใฎ pow ใฏ long long ใๅผๆฐใซๅใใฎใงใๅฎใฏใใๆธใใใ int ใ ใจๆใ่พผใใงใใฆๅจใ้ใใใใใฉใคใใฉใชใฎไปๆงใใใ็ฅใฃใฆใใใใจใ้่ฆใงใใใ
void solve(std::istream& is, std::ostream& os) {
Num n {0};
is >> n;
Num w = std::to_string(n).size();
ModInt base = ModInt(10).pow(w);
ModInt p = base.pow(n) - 1;
p *= n;
ModInt q = base - 1;
p /= q;
os << p.val() << "\n";
}ใณใผใใฏใใกใ
Dๅ้กใๆฉ่งฃใใงใใฆใใใฐใใใใ้ใซๅใฃใๅฏ่ฝๆงใใใใใใฏใๅบ็คใฎๆฉ่งฃใๅใใชใใจใๆๅพใฎไธๅใ็ฒใใชใใ
ใในใฆใฎ้ ็นใฎๅบๆฌกๆฐใ1ใใจใใใฎใ้ๅคงใชๅถ็ดใงใใใใตใคใฏใซๅคใฎ้ ็นใใใใฉใ็ใใฎใฏใใไธใคใฎใตใคใฏใซใใใฉใฎใตใคใฏใซใซใใใฉใ็ใใชใใใงใใฃใฆใ่คๆฐใฎใตใคใฏใซใซใใฉใ็ใใใจใฏใชใใ่คๆฐใฎใตใคใฏใซใซใใฉใ็ใใซใฏใๅบๆฌกๆฐใ2ไปฅไธๅฟ ่ฆใ ใใใ ใใใใจใใตใคใฏใซใใๅคใซๅบใใใจใใงใใชใ(ใใใๅบๆฌกๆฐใ2ไปฅไธๅฟ ่ฆใ ใใ)ใ
ใใฃใฆๆๅใฐใฉใใ้ใซใใฉใฃใฆใ2้ ็นไปฅไธใใๆใใตใคใฏใซใซใใฉใ็ใใใฉใใใ่ชฟในใใ
- ่ชๅทฑใซใผใใฏใใฃใใ็ก่ฆใใ
- ใตใคใฏใซใซใใ้ ็นใซใคใใฆใฏใใตใคใฏใซใๆงๆใใ้ ็นๆฐใ็ญใใงใใใSCCใงๆฑใพใใ
- ใตใคใฏใซใฎๅ็นใใๆๅใฐใฉใใ้ใซๆจใซใใฉใDFSใงใใตใคใฏใซใฎ้ ็นๆฐ+ใตใคใฏใซใใ็ใใฆใๆใฎ้ ็นๆฐใๆฐใใใใตใคใฏใซใใ1ๆ้ขใใใใจใซ1่ถณใใฐใใใใตใคใฏใซใพใงใฎ่ท้ขใจ่จใๆใใฆใใใใ
ๆฎใใฏ2้ ็นไปฅไธใใๆใใตใคใฏใซใจใ2้ ็นไปฅไธใใๆใใตใคใฏใซใซใใฉใ็ใ้ ็นไปฅๅคใ่ชฟในใใใใใฏๅบๆฌกๆฐใ0ใฎ้ ็นใใ1้ ็นใใๆใใตใคใฏใซ=่ชๅทฑใซใผใใจใใฆๅๆงใซ่งฃใใใ
ไธ่จใใพใจใใใจ็ฐกๆฝใซ ๆธใใ ใ
ๅ ฌๅผ่งฃ่ชฌใซใฏใFunctional Graph ใฏ้ฃ็ตๆๅใซ้่ทฏใไธใคใ ใๅญๅจใใใจๆธใใฆใใใใจใใใใๅ้กๅใ ใฃใใใใฎใใจใฏๅใใฃใฆใใใฎใ ใใใใใใฐใซ71ๅ21็งใๆใใฃใฆใใพใฃใใ
ใณใณใในใ34ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใงhighestๆดๆฐใงใใใF,Gๅ้กใ่งฃใๆ้ใไธญ้ๅ็ซฏใซใใใณใณใในใใซใฏ้ใซๅใใชใใฃใใใ็ฟๆฅไปฅ้ใซ่งฃใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๆญฃ็ขบใซๅ ฅๅใใใ
ใณใผใใฏใใกใ
็ดๅใฎไบบใๆๅป
-
$t \leq T_i$ ใชใๅณๆใซใใฑใใใ่ณผๅ ฅใใฆ$t := T_i + A$ ใซใชใ -
$t > T_i$ ใชใๆๅป$t$ ใซใชใใฎใๅพ ใฃใฆใใฑใใใ่ณผๅ ฅใ$t := t + A$ ใซใชใ
ใใใใใพใจใใใจใๆดๆฐๅผใฏ
ใณใผใใฏใใกใ
std::bitset::count() ใๅฝน็ซใคใ
ใณใผใใฏใใกใ
ไพกๆ ผใจใ่ๅญใฎๆฐใๅใใชใฎใงไธๆ้็ใใใ
ใ่ๅญใ -1 ใๅบๅใใใ
ใใๅ
ทไฝ็ใซใฏ
-
$A_j$ ใฎๆทปใๅญใ$j = 1$ ใงๅๆๅใใ -
$B_i \leq A_j$ ใชใ$(B_i, A_j)$ ใใใใใณใฐใใฆใ$i$ ใจ$j$ ใใใใใ1ๅขใใ -
$B_i > A_j$ ใชใ$i$ ใ1ๅขใใ -
$i > N$ ใชใใใใใณใฐใงใใชใ
ใใฎ่ฒชๆฌฒๆณใฎๆญฃๅฝๆงใฏๅ ฌๅผ่งฃ่ชฌใซใใใๅฐบๅใๆณใไฝฟใใใจใๅ ฌๅผ่งฃ่ชฌใซใใใ
ใณใผใใฏใใกใ
่จ็ฎ้ใไธใใใฎใซ่ฆๅดใใใ
ๆๅญ
ใใใๅบใซDPใ่ใใใ
-
$DP[i][from]$ ใฏใ$a_i$ ๆๅญใพใงไฝฟใฃใฆ$0 \leq from \leq K$ ๆๅญใใๆใๆๅญๅใไฝใๆนๆณใไฝ้ใใใใ็คบใ - ๅๆๅคใฏ
$DP[0][0]=1$ ,$DP[0][from]=0 : from > 0$ ใงใใ -
$a_i$ ใ$j = 0..C_i$ ๆๅญ่ฟฝๅ ใใ- ่ฟฝๅ ใใๅพใฏ
$from + j$ ๆๅญใซใชใ - ่ฟฝๅ ใใๅใฏ
$DP[i][from]$ ้ใใ่ฟฝๅ ใใๆนๆณ$C_i \choose j$ ้ใใใใใใใใฎ็ฉใ$DP[i+1][from+j]$ ใซ่ถณใ
- ่ฟฝๅ ใใๅพใฏ
- ๆ็ต็ใซ
$DP[26][1..K]$ ใฎๅใ็ญใใงใใใ
ๆๅใซ่ใใใฎใฏใ
ใณใผใใฏใใกใ
ใคใใซ็งใ้ปdiffใ่ชๅACใงใใใ100ๅใกใใฃใจๆใใฃใใฎใงใใณใณใในใใซใฏๅฐๅบ้ใซๅใใชใใฃใใใ
ๅ ฌๅผ่งฃ่ชฌใจๅใ็ต่ทฏใๆใใคใใใ่ชๅใฎ่จ่ใง่จใ็ดใใจไปฅไธใฎ้ใใงใใใ
ๆๅใซในใฟใผใใใใดใผใซใธ No ใงใใใ
ใใใใใฉใใ ใ่ฟๅใงใใใใ่ใใใๅทฆๅณๆนๅใซ่ฟๅใใฆใใไธไธใซ่ฟๅใใฆใใ่กใฃใฆๆปใใฎใง่ฟๅ่ทฏใฎ้ทใใฏๅถๆฐใงใใใใใฃใฆ No ใงใใใ
ๅพใฏ่ฟๅ่ทฏใๅฎ้ใซๆงๆใใใ่ฟๅใใชใใใฐใชใใชใๅๆฐใฏ
-
$N$ ใๅถๆฐใชใใ2่กใใคไฝฟใฃใฆใๅทฆใซ่ฟๅใไธใๅณใซ่ฟๅใ่กใใๅทฆๅณใ$D$ ๅฏพไฝใใฐใใใ -
$N$ ใๅฅๆฐใชใใ$N-3$ ่ก็ฎใพใงใฏไธ่จใจๅๆงใซใๅทฆใซ่ฟๅใไธใๅณใซ่ฟๅใ่กใใๆฎใใฏ$R = D - (M-1)((N - 3) / 2)$ ๅฏพใงใใใ$R \leq (M-1)$ ใชใใใใใพใงใจๅๆงใซๅทฆๅณใซ่ฟๅใใใใใใงใชใใใฐ$R - (M-1)$ ๅฏพใ ใใไธใใ1,2่ก็ฎใงไธไธใซ่ฟๅใใใๆๅพใซๅณไธใใดใผใซใซๆฅ็ถใใใ
ใณใผใใฏใใกใ
ใณใณใในใไธญใฏๆฎใ24ๅใง่งฃใใใจใใงใใใ็ฟๆ่ชๅACใใใๆฉใ5ๅฎใใชใใจใ6ๅ็ฎใ่งฃใๆ้ใ่ถณใใชใใ
ใใฃใใใจใใไบๆณใจใใฆใ
ใใใๅบใซDPใ่ใใใ
-
$DP[s][y,x]$ ใฏใใน$(y,x)$ ใซใใน$(S_i,S_j)$ ใใ$s$ ๅใฎ็งปๅใงใใฉใ็ใใจใใฎใใใใพใงใซๅพใๆฅฝใใใฎๅ่จใจใใใ -
$DP[0][S_i,S_j] = 0$ ,$DP[0][y,x] = - \infty : (y,x) \neq (S_i,S_j)$ ใงๅๆๅใใ - ็ธฆ(่ก)ๆนๅใซ
$dy$ , ๆจช(ๅ)ๆนๅใซ$dx$ ็งปๅใใใจใใฆใ$DP[s+1][y+dy,x+dx] = max(DP[s+1][y+dy,x+dx], DP[s][y,x] + A_{y+dy,x+dx})$ ใงๆดๆฐใใใ่ฆใใใซ็งปๅๅ ใฎๆฅฝใใใ่ถณใใฆใๆฅฝใใใฎๅ่จใๆๅคงๅใใใๅไธใฎใในใซ็ใพใใใจใฏใพใ ่ใใชใใ - ใใใ
$0 \leq s \leq HW$ ๅ็นฐใ่ฟใใใใใใใฐๅใใในใๅฐใชใใจใ2ๅบฆ่จชใใใใใซใชใใ
ๆๅคง
-
$K \leq HW$ ใชใใ$DP[K][y,x]$ ใใฎใใฎใงใใ - ใใน
$(y,x)$ ใซ็ใพใใจๆฑบใใๆใซใใใใซใใฉใ็ใใพใงใฎ็งปๅๅๆฐ$s=0..min(K,HW)$ ใซใคใใฆใๆฅฝใใใฎๅ่จใฏ$DP[s][y,x] + (k - s)A_{y,x}$ ใงใใใ$s$ ใๅฐใใใใฆใใน$(y,x)$ ใซใใฉใ็ใใชใใจใใฏๆฅฝใใใ$- \infty$ ใชใฎใง็ก่ฆใงใใใ - ใใใใในใฆใฎใในใฎใในใฆใฎ
$s$ ใซใคใใฆๆฑใใใจใๅ้กใฎ็ญใใๆฑใพใใ
ใใฎ่งฃๆณใฏๅบๆฌ็ใซๅ ฌๅผ่งฃ่ชฌ1ใจๅใใงใใใใใใพใงๅใใใชใใ24ๅใง่งฃๆณใ่ฉฐใใฆๅฎ่ฃ ใงใใใใใซใใใใ
ใณใณใในใ35ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใง้ๅปๆ้ซใใใฉใงhighestๆดๆฐใงใใใๆๅพใฎ1ๅใพใง่ซฆใใชใๆ นๆงใๅฎใฃใใ่งฃ็ญๆ้ใ 1:19-2:21-30:51-28:26-33:54 ใจใปใผ30ๅ้้ใงใA,Bๅ้กใฎๆฉ่งฃใใๆดปใใใFๅ้กใใณใณใในใๅพใซ่งฃใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅฎ่ฃ ใใใboolๅคใๆ้ปใซ0/1ใซๅคๆใใใจใณใผใใ็ญใใชใใ
ใณใผใใฏใใกใ
่ฒใๆทปใๅญใจใใ std::vector<Vec> ps ใไฝใใๆทปใๅญใซๅฏพๅฟใใๅคใซ
ใณใผใใฏใใกใ
WAใฎๅฑฑใ็ฏใใฆใใฎใใใ็ฆใฃใใ
็ธฆ(Yๅบงๆจ)ๆนๅใฎ็งปๅใฏใ่ตท็นใๅฅใจใใฆๅฟ
ใ
-
$(S_x \oplus S_y) and 1 = 0$ ใชใใ$left = S_x - d$ ,$right = S_x + 1 + d$ -
$(S_x \oplus S_y) and 1 = 1$ ใชใใ$left = S_x - 1 - d$ ,$right = S_x + d$
-
$T_x < left$ ใชใ$c = \lceil (left - T_x) /2 \rceil$ -
$right < T_x$ ใชใ$c = \lceil (T_x - right) /2 \rceil$ - ใใไปฅๅคใฏ
$c=0$
็ญใใฏ
ๅใใฃใฆใใพใใฐใใใพใงใ ใใ
ใณใผใใฏใใกใ
DPใฎๅๆๅใจใใฆใ A,B ใฏใใใใ ? ใฏ
ๅพใฏ
-
$S$ ใฎ$i$ ๆๅญ็ฎใAใชใใ$DP_{next}[ \lfloor from / 2 \rfloor ] += DP[ \lfloor from / 2 \rfloor]$ -
$S$ ใฎ$i$ ๆๅญ็ฎใBใชใใ$DP_{next}[ 2^{K-1} + \lfloor from / 2 \rfloor ] += DP[ \lfloor from / 2 \rfloor ]$ -
$S$ ใฎ$i$ ๆๅญ็ฎใ?ใชใใ ไธ่จใฎไธกๆน
ใณใผใใฏใใกใ
่งฃๆณใฏใใๅใใฃใใใๅฎ่ฃ ใใใใใฎใขใซใดใชใบใ ใๅใใใชใใฃใใ
ใใ
ใใ
- ใใฎใใใชๆฟใใชใใใฐ
$H_i$ ใพใง็ฎไธๆฏๆณจใใฎใงใๆณจใ้ใฏๅ จไฝใง$i \times H_i$ ใงใใใ - ใใฎใใใชๆฟใใใใฐ
$j$ ใใ$i$ ใพใง้ซใ$H_i$ ใๆณจใใฎใงใๆณจใ้ใฏๅ จไฝใง$A_j + (i - j) \times H_i$ ใงใใใ
็ญใใฏๆบขใใใจใใชใฎใงใ std::vector<std::pair<Num,Num>> ใงใ
std::set ใงไธๆใใใใใใปใฐใกใณใๆจใจๅบงๆจๅง็ธฎใงไธๆใใใใใๆฎใ6ๅใงในใฟใใฏใงๅฆ็ใงใใใจๅใใฃใฆๅฎ่ฃ
ใใใๆฎใ3ๅ9็งใงๆๅบใงใใใในใฟใใฏใซไนใๆใใๅฎ่ฃ
ใ2ๅ็จๅบฆใงใงใใใฎใงใๆฉ่งฃใ่จ็ทดใๅใๅฅใใใๅ
ฅๅไพใ้ใฃใใฎใงใใไปฅไธๆค่จผใใไฝ่ฃใใชใๆๅบใใฆACใงใใใฎใฏใๆฉใใฆๆญฃ็ขบใชๅฎ่ฃ
ๅใใใใใๅฎๆฆใงๆดปใใใใใใซใชใฃใใใใใA,Bๅ้กใๆฉใ่งฃใใใฎใงๆฎใ3ๅใ็ขบไฟใงใใใฎใงใๅบ็คใฎๆฉ่งฃใใๆๅณใใใใ
ๅฎใฏใปใฐใกใณใๆจใจๅบงๆจๅง็ธฎใง ไธๆใใใ ใจๅพใใ็ฅใฃใใ้ซใ apply ใซ a+b ใจๆธใใใๆญฃ่งฃใฏ max(a,b) ใชใฎใงใ่ชๅใงใไฝใใใใใฎใใใๅใใฃใฆใใชใใฃใใใใใ
ใใๅฐใใง้ใใใฉใ ใฃใใใใใฎใใใซใฏC,Eๅ้กใใใๅฐใๆฉใ่งฃใๅฟ ่ฆใใใใๅ ฌๅผ่งฃ่ชฌใซใใใจ้ ๅปถใปใฐใกใณใๆจใงใ ่งฃใใ ใฎใ ใใๅฎ่ฃ ๆนๆณใใพใใง่ฆๅฝใใคใใชใใฃใใ
ใณใผใใฏใใกใ
่ฒชๆฌฒๆณใจใใ่จ่ใ่ฆใใฆใใพใฃใใฎใง่ชๅACใใจใใใจๅพฎๅฆใ ใใใใไปฅ้ใฎ่งฃๆณใๆใใคใใใ
ใใใใๆฌกๆฐใ
ใณใณใในใ36ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใEๅ้กใๅ จใ่งฃใใชใใฃใใ่กๅใใใชใณใฐใง่งฃใใใจๆฐใฅใใใจใใฏๅใฆใใจๆใฃใใใๅฎ้ใซใฏๅฎๆใ ใฃใใ
ใณใผใใฏใใกใ
ๆๅญๅใซใใใ R ใฎไฝ็ฝฎใ M ใใๅฐใใใใฐ Yes ใใใใงใชใใใฐ No ใงใใใ
ใณใผใใฏใใกใ
0-based indexing ใง่ใใใ
ใณใผใใฏใใกใ
็ฎฑใซ่ท็ฉใ่คๆฐใใใจใใใใฎ็ฎฑใงไธ็ช่ท็ฉไปฅๅคใ็งปๅใใใใฉใใซ็งปๅใใใใฏๆฐใซใใชใใ
ใณใผใใฏใใกใ
ใใใใใใใใใผใฟใไธๆใๆด็ใใใจ่งฃใใใ
ๆญฃใฎๆนๅใๅใใฆใใ่ปใฎๅบงๆจใฎ้ๅ
ๆญฃใฎๆนๅใๅใใฆใใ่ปใฎๅบงๆจใ
ใใใใฏไบๅๆข็ดขใงๆฑใพใใๅข็ๅคใซๆณจๆใใฆไธๆใใคใใฌใผใฟๅๅฃซใๆธ็ฎใใใๆๅพใซ่ปใฎใใขใไบ้ใซๆฐใใใฎใงใๅ่จใ2ใงๅฒใใ2ใงๅฒใใชใใฆใใๆญฃใฎๆนๅใๅใใฆใใ่ปใใใ ใๆฐใใใฐใใใฃใใ
ใณใผใใฏใใกใ
ๆผธๅๅผใ่กๅใใใชใณใฐใใใฎใ ใใใจๆใฃใใใ็ญใใๅ
จใๅใใชใใฃใใ
่กๅใใใชใณใฐใงใ ๆฑใพใ ใๆผธๅๅผใฎๆญฃใใ่กๅ
- ่กๅใฎๅทฆไธ: ใใผใซใๅทฆ็ซฏใซใใฃใฆใๅทฆ็ซฏใฎใพใพใจใใใฎใฏใ
$a=1, b=1$ ใจใ$a \ne 1, b \ne 1$ ใจใชใใในใฆ็ต - ่กๅใฎๅณไธ: ใใผใซใๅทฆ็ซฏไปฅๅค
$i$ ใซใใฃใฆใๅทฆ็ซฏใซๆฅใใฎใฏใ$a=1, b=i$ ใจใ$a=i, b=1$ ใฎไบ้ใใใใใๅใใใชใใฃใใ - ่กๅใฎๅทฆไธ: ใใผใซใๅทฆ็ซฏใซใใฃใฆใๅทฆ็ซฏไปฅๅคใซๆฅใใฎใฏใ
$a=1, b \neq 1$ ใจใ$a \neq 1, b=1$ ใจใชใใในใฆ็ต - ่กๅใฎๅณไธ: ใใผใซใๅทฆ็ซฏไปฅๅคใซใใฃใฆใๅทฆ็ซฏไปฅๅคใฎใพใพใชใฎใฏใๅทฆ็ซฏใซใใ2้ใไปฅๅค
ๆๅใฏใใผใซใๅทฆ็ซฏใซใใใฎใงๅๆใใฏใใซใฏ
ๆๅพ
ๅคใฎๅฎ็พฉใใใ็ญใใฏ
ใณใณใในใ37ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใEๅ้กใซ104ๅๆใใใ34ๅใง่งฃใใFๅ้กใ่ฝใจใใใ่ฉฆๅ้ใณใไธๆใใใใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใใ
ใณใผใใฏใใกใ
2ๆฌใฎๆฐ็ด็ท
ใณใผใใฏใใกใ
ใณใผใใฏใใกใ
็ถๆ
้ท็งปใ็กๅใฐใฉใใซใใฆใ
็ตๅฑไปฅไธใฎ้ใใซใใใ
-
W= 0,B= 1, ็ฉบใใใน = 0 ใจใใใใใๅใไฝใใๅถ็ดใใๆ้ท16ใใใใงใใใ็ฉบใใในใ็ถๆ ใซๆใใใใจ$3^{16}$ ็ถๆ ใซใชใฃใฆๅคงๅคใงใใใ - ็ฉบใใในใฎๅ
้ ญไฝ็ฝฎ(ใซใผใฝใซ)ใใ0-based indexingใง็ฎก็ใใใๅถ็ดใใ
$0..14$ ใฎๅคใๅใใ - ไธ่จใใ็ถๆ
ๆฐใฏใ้ซใ
100ไธ็จๅบฆ(
$15 \times 2^{16}$ )ใงใใใ้ท็งปๅ ใ้ซใ 13ใงใใใ - ใญใฅใผใซ่ผใใ็ถๆ ใฏใใใใๅใจใซใผใฝใซใฎ็ตใซใใใใใใๅใจๆดๆฐใฏ็ธไบใซๅคๆใใใ
ๅพใฏๅๆๅคใ
ใณใผใใฏใใกใ
DFSใงใใใใจใฏๅใใใใไฝใ่ผใใใฎใใใฃใฑใใใใใชใใ
DFSใใใจใๅคงไฝใฎ่พบใฏไบๅบฆใใฉใใใไธ้จใฎ่พบใฏไธๅบฆใใใใฉใใชใใใใฃใฆไธๅบฆใใใใฉใใชใ่พบใฎ้ใฟใๆๅคงๅใใใฐใใใจๅใใใไบใคใฎ่ใฎ้ใฎๆ้ท่ท้ขใๆฑใใใใจใซ็ญใใใใณใณใในใๅพใซใๆจใฎ็ดๅพใจ่จใ่จ่ใ่ฆใใใๅ ฌๅผ่งฃ่ชฌใฏๆจใฎ็ดๅพใๅๆใซใชใฃใฆใใใ
ๆจใฎ็ดๅพใๆฑใใๆนๆณใ็ฅใใชใใใจใใๅๆใงใไปฅไธใฎๆนๆณใง่งฃใใใ
- ๆฌกๆฐใ2ไปฅไธ(ๅญใใผใใ2ๅไปฅไธใฎ)ใฎไปปๆใฎใใผใใๆ นใจใใฆ้ธใถ
- ๆ นใใDFSใใใ้จๅๆจใซใใใฆใไปฅไธใฎ็ตใๆฑใใใใใใๆจๅ
จไฝใฎๆ นใซๅใใฃใฆไผๆฌใใใ
- ้จๅๆจใฎๆ นใใ่ใฎๆ้ท่ท้ข
- ้จๅๆจใซใใใใ่ๅๅฃซใฎๆ้ท่ท้ข
- ่ใซใใใฆใฏใใฉใกใใ0ใงใใใ
- ๆฌกๆฐใ2(่ฆชใจๅญใ1ใใผใใใค)ใฎใใผใใซใใใฆใฏ
- ้จๅๆจใฎๆ นใใ่ใฎๆ้ท่ท้ขใฏใๆ นใใๅญใพใงใฎ่ท้ขใใๅญใ่ฟใใๆๅคงๅคใซ่ถณใ
- ้จๅๆจใซใใใ่ๅๅฃซใฎๆ้ท่ท้ขใฏใๅญใฎๅคใไผๆฌใใ
- ๆฌกๆฐใ3(ๅญใ่คๆฐ)ใฎใใผใใซใใใฆใฏ
- ้จๅๆจใฎๆ นใใ่ใฎๆ้ท่ท้ขใฏใๆ นใใๅญใพใงใฎ่ท้ขใใๅญใ่ฟใใๆๅคงๅคใซ่ถณใ
- ้จๅๆจใซใใใ่ๅๅฃซใฎๆ้ท่ท้ขใฏใๅญใ่ฟใใๆๅคงๅคใจใๆ นใใ็ฐใชใๅญใฎ่ใพใงๆ้ท่ท้ขใฎๅใจใใฉใกใใๅคงใใๆนใซใใใๅ่ ใฏใใฎๅญใๆ นใจใใ้จๅๆจใฎๅคใๅพ่ ใฏ็ฐใชใๅญใๆ นใจใใ้จๅๆจใซใใ่ๅๅฃซใ็ตใถใจใใฎๅคใงใใใ
ใในใฆใฎ่พบใฎ้ใใฎๅใ
ใณใผใใฏใใกใ
ใณใณใในใๅพใซ34ๅใง่งฃใใฆใใพใฃใใEๅ้กใ่ซฆใใฆFๅ้กใ่งฃใใฐ5ๅฎใงใใใ็ขบใใซๆญฃ่งฃ่ ๆฐใฏEๅ้กใใFๅ้กใฎๆนใๅฐใชใใฃใใ(่ชๅใฎใฌใผใใฃใณใฐๅธฏใ ใจ6ๅฒๅฏพ2ๅฒ)ใ็งใซใจใฃใฆใฏFๅ้กใฎๆนใ่งฃใใใใใฃใใฎใ ใใใFๅ้กใซไนใๆใใในใใ ใฃใใ่ฉฆๅ้ใณใไธๆใใใใ
-
$a=2..10^6$ ใฏ$a^b = m \leq N$ ใซใชใๅ จๆข็ดขใใฆใ้่คใชใ้ๅใซๅ ฅใใใ้่คใชใใซใใชใใจๅพใงใใใใใชใ(ไพใใฐ$2^4 = 4^2$ ใ้่คใใ) -
$a^b$ ใฎ้่คใชใ้ๅใๆ้ ใฎ้ ๅใซๅฑ้ใใ -
$L = 10^6$ ,$\lfloor \sqrt{N} \rfloor = R$ ใจใใใ$L \geq R$ ใชใไปฅไธใฎๅฆ็ใฏใใชใ(ใใฎใจใใฏไพฟๅฎไธ$R=L$ ใจใใ)ใ -
$L < a \leq R$ ใซใใ$a^b$ ใฎๅๆฐ$C$ ใฏใไธ่จใฎ้ ๅใใๅใใใstd::ranges::upper_bound(vs, R)-std::ranges::upper_bound(vs, L)ใงๆฐใใใใใ
็ญใใฏ
ใณใณใในใ38ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใ84:31ใใใซใใฃ็กใใCๅ้กใไธ็ช้ฃใใใๆฎใ14ๅใใฃใใGๅ้กใฏTLE่งฃใใๆใใคใใชใใฃใใ
ใณใผใใฏใใกใ
Red ใชใ Green ใชใ Blue ใชใ
ใณใผใใฏใใกใ
ไบ่พบใ็ด่งใฉใใใฏใๅ
็ฉใ0ใใฉใใใงๅใใใใใฃใฆ
ๅ ฌๅผ่งฃ่ชฌใฏ ไธๅนณๆนใฎๅฎ็ ใ ใฃใใ
ใณใผใใฏใใกใ
ๅ จใ่งฃใใ่ฆ่พผใฟใใชใใD,Eๅ้กใ่งฃใใๅพใซ่งฃใใใ
ๆๅฐๅคใฎๅ
็ญใ
-
$S = 0$ ใชใไฝใใใชใ -
$S > 0$ ใชใ$S$ ใๆธใใใๆๅคง$X_i - L_i$ ๆธใใใใฎใงใ$min(S, X_i - L_i)$ ใ ใ$S$ ใจ$X_i$ ใๆธใใใ -
$S < 0$ ใชใ$S$ ใๅขใใใๆๅคง$R_i - X_i$ ๅขใใใใฎใงใ$min(-S, R_i - X_i)$ ใ ใ$S$ ใจ$X_i$ ใๅขใใใ
ใใใใฆ่ฃๆญฃใใ
ๅ
ฌๅผ่งฃ่ชฌใ่ชญใใจใ่ฃๆญฃๅ
ใฏๅนณๅใงใฏใชใ
ใณใผใใฏใใกใ
Cๅ้กใ่งฃใใ่ฆ่พผใฟใใชใใพใพDๅ้กใซ่กใใDๅ้กใใใ่งฃใใใใจใซๆใใใใ็ซถๆใฏๆฐๅใฎๅใๆฟใใ้่ฆใงใใใ
้ ็นใฎ้ใฟใฏ่พบใฎ้ใฟใซ่ถณใใฆใใพใฃใฆๆงใใชใใใคใพใ้ ็น
ใใฎๆๅใฐใฉใใซใๅง็นใ้ ็น1ใ้ใฟใฎๅๆๅคใ
ใใฎๆนๆณใฏๅ ฌๅผ่งฃ่ชฌ1ใจๅใใงใใใๅ ฌๅผ่งฃๆณ2ใฎๆนๆณใฏ ใใกใ ใ
ใณใผใใฏใใกใ
ไปฅไธใใใใใฎ่ฆ็ด ใฎๅทฎ
-
$DP[][] = 0$ ใงๅๆๅใใใใใซ$DP[][1] = 1$ ใงๅๆๅใใใใคใพใๅไธใฎ่ฆ็ด ใฏใใ่ช่บซ็ญๅทฎๆฐๅใงใใใใใฎ็ตใฟๅใใใฏ1้ใใงใใใ - ๆๅใฐใฉใ
$G$ ใฎ้ ็น$i$ ใใ็ดๆฅใใฉใใ้ ็นใฎ้ๅใ$V_i$ ใจใใใ$j \in V_i$ ใจใใฆใ$k=1..(N-1)$ ใซใคใใฆ$DP[j][k+1]$ ใซ$DP[i][k]$ ใ่ถณใใใคใพใ้ ็น$i$ ใพใงใฎใในใๅใใใ็ตใฟๅใใใซ้ ็น$j$ ใ่ฟฝๅ ใใใ$G$ ใฏๅๅฒใๅๆตใใใใฎใงๆจใงใฏใชใใ
ใใใใใจๅ้ ็นใซใคใใฆ
ๅ ฌๅผ่งฃ่ชฌใDPใ ใใใฉใฎ่ชฌๆใจไธ่ดใใใๅฎใฏใใใฃใฆใใชใใ
ใณใผใใฏใใกใ
Suffix Arrayใ็ฅใใชใใฃใใฎใงใๅ
จใ่งฃใใ่ฆ่พผใฟใ็กใใฃใใ atcoder::suffix_array ใจ std::string_view ใง้จๅๆๅญๅใๅใๅบใใ std::ranges::partition_point ใงไบๅๆข็ดขใใใจ่งฃใใใๅฎ่ฃ
ใใฎใใฎใฏ็ฐกๆฝใชใฎใงใๆฎใ14ๅใใฃใใ่งฃใใใใใซใชใใใใ
ใณใณใในใ39ๅ็ฎใงใใใA,B,C,D,Eใฎ5ๅฎใ350็นๅ้กใฏไปๆฅใๅณใใใ6ๅฎใฏ้ ใใฃใใ
ใณใผใใฏใใกใ
ใณใผใใฏใใกใ
ใณใผใใฏใใกใ
ๅๆใง้ใใใ
std::string_view::substr ใไฝฟใใ้จๅๆๅญๅ std::string::substr ใ ใจ 143 msec ๆใใใ
ใณใผใใฏใใกใ
ไปๆฅใ350็นๅ้กใฏ่ฆๅดใใใใฑใฃใจ่ฆใงๅ จใ่งฃๆณใๅใใใชใใฎใงใ่ฟทใใEๅ้กใซ็งปใฃใฆใEๅ้กใACใใๅพใซ่งฃใใใ
ใใๆกๆฐ
-
$w=1$ ใชใ$i=1..9$ ใฎ9็จฎ้ก -
$w=2$ ใชใ$i=11 \times 1..9$ ใฎ9็จฎ้ก -
$w=3$ ใชใๅ ้ ญใ$i=1..9$ ใใใฎๆฌกใ$0..9$ ใฎ10้ใใใใฎๅพใฏๆใ่ฟใใชใฎใง่จ90็จฎ้ก -
$w=4$ ใชใๅ ้ ญใ$i=1..9$ ใใใฎๆฌกใ$0..9$ ใฎ10้ใใใใฎๅพใฏๆใ่ฟใใชใฎใง่จ90็จฎ้ก - ไปฅไธๅๆงใซ
$C(w) = 10 \times C(w-2)$ ใงใใใ
ใณใผใใฏใใกใ
Dๅ้กใจ้ใฃใฆๆน้ใใใ็ซใฃใใUnion-findๆจใงๆตทใๅบใใใฐใใใไปฅไธ0-based indexingใง่ใใใ
ใฐใชใใใซใปใณใใใซใๅซใใฆ
ๆตทใซๆฅใใๅณถใฎๅบ็ปใคใพใๅข็
ๅๅบ็ปใ
ใณใผใใฏใใกใ
ใณใณใในใไธญใฎๆฎใ9ๅใงใฏใชใใในใใชใใฃใใๅๅธฐใง่งฃใใใจ็ฅใฃใใฎใง่ชๅACใจใฏ่จใ้ฃใใใ่งฃ่ชฌใ่ชญใๅใซ่งฃใใใ
ไธ่จใๆบใใใใใชๆฐๅ * ใง็ตๅใใใใฎใ็ญใใงใใใ
-
$N$ ใ็ด ๆฐใฎใจใใ$N$ ใๅๆๆฐใชใใใใ็ญใใใใใงใชใใใฐ่งฃใชใ-1ใงใใใๅถ็ดใใใ$N$ ใ$10^6$ ไปฅไธใฎ็ด ๆฐใงๅฒใฃใฆใๅฒใๅใใชใใใฐ$N$ ใฏ็ด ๆฐใงใใใ -
$N$ ใฎ็ดๆฐใๆฑใใstd::to_string()ใงๆๅญๅ่กจ่จใๆฑใใใ็ดๆฐใฏไธๆใจใใไฝๅ$N$ ใๅฒใฃใฆใใใใใจใซใใใ - ๅฒใใใๆฐ
$R=N$ ใ$A$ ใ็ฉบใซๅๆๅใใใ - DFSใซใใใฆใ
$R$ ใ็ดๆฐ$f$ ใงๅฒใๅใใชใใใฐ็ก่ฆใใใ$R$ ใงๅฒใๅใใใชใ$A$ ใซ$f$ ใๅ ใใ$R$ ใ$R/f$ ใง็ฝฎใๆใใฆๅๅธฐใใใ -
$R=1$ ใชใ$A$ ใ่งฃใฎๆกไปถใๆบใใใใฉใใ่ชฟในใฆใๆบใใใชใ็ญใใๅบๅใใใ่งฃใฎๆกไปถใๆบใใใชใใใฐDFSใ็ถ็ถใใใ
ใใใ็ด ็ดใซๅฎ่ฃ
ใใใจTLEใใใฎใงใๆๅใซ่ฟฐในใ
-
$A$ ใซ$f$ ใๅ ใใใ$A$ ใๅถๆฐ้ทใซใชใใจใใ$f$ ใฏ$A$ ใฎๆๅพใฎ่ฆ็ด ใฎๅ่ปขใซ้ใ - DFSใฎๆซ็ซฏใง
$|A|$ ใๅฅๆฐ้ทใชใ$A$ ใฎๆๅพใฎ่ฆ็ด ใฏๅๆใซ้ใ - ไบใคใฎๆๅญๅใไบใใซๅ่ปขใใฉใใใฏใ
std::equal(sl.begin(), sl.end(), s.rbegin(), s.rend())ใไฝฟใใจๆๅญๅใใณใใผใใใซๅคๅฎใงใใใ4ๅผๆฐใฎstd::equalใฏใใฉใณใใ ใขใฏใปในใคใใฌใผใฟใซใคใใฆใฏ้ทใใ็ฐใชใใจใใซ$O(1)$ ใงfalseใ่ฟใใฎใง้ใใ
ๅ ฌๅผ่งฃ่ชฌใฏใกใขๅใไฝฟใฃใฆ่จ็ฎ้ใๅๆธใใฆใใใ
ใณใณใในใ40ๅ็ฎใงใใใA,B,C,Dใฎ4ๅฎใEๅ้กใฏ1 WAใซ้ปใพใใใ
ใณใผใใฏใใกใ
ใพใใใฎWAใงใใใๅ ฅๅไพ2ใ้้ใฃใฆใใใใจใซๆฐใไปใใชใใพใพๆๅบใใฆใใพใฃใใ
ๅ
ฅๅไพ2ใซใใ้ใใๆๅพใฎๆ็ใ้ฃในใ็ตๆใฏไปฅๅพใซๅฝฑ้ฟใใชใใฎใงใ
ใณใผใใฏใใกใ
ๅ้กๆ้ใๅฎ่ฃ ใใใฎใ ใใไปฅไธใๆธใใฎใซใฆๆใใใฃใฆใใพใฃใใไธไธใจๅทฆๅณใฎๅบๅฅใๅใใใชใใชใใฎใงใในใใใใใซใใๆนใใใใใใใใชใใ
std::map<char, std::pair<Num, Num>> dyxs {{'D', {1, 0}}, {'U', {-1, 0}}, {'R', {0, 1}}, {'L', {0, -1}}};ใณใผใใฏใใกใ
DPใใจๆใฃใใใใใงใฏใชใใฃใใใจใใใDPใฏEๅ้กใ ใจๅพใงๅใใใ
ใณใผใใฏใใกใ
ใฑใฃใจ่ฆใฆ่งฃๆณใๅใใใใEๅ้กใDPใจๅใใฃใใฎใงEๅ้กใซๅ ใซ็ๆใใฆใใพใฃใใๅ ใซDๅ้กใ่งฃใใฆใใใใใฃใจใใใฉใใใใฃใใใใฎ็จฎใฎๆฐๅญฆๅ้กใฎ่ๅฏใซๆ้ใๆใใใใจใใๅ้ก้ธใณใฎๅทงๆใซๅฝฑ้ฟใใฆใใใ
้ๅบ้ upper_bound ใจ lower_bound ใฎไฝฟใๅใใ็ตถๅฆใงใใใ
std::ranges::upper_bound(a, b + d) - std::ranges::lower_bound(a, b - d);-
$B_{j+D}$ ใกใใใฉใใคใใฌใผใฟใฏๆใใชใใ$B_{j+D}$ ใ่ถ ใใๆๅฐใฎ่ฆ็ด (ใชใใใฐend)ใๆใใ -
$B_{j-D}$ ใกใใใฉใใคใใฌใผใฟใฏๆใใใใใใชใใใใใใงใชใใใใใใชใใ -
$B_{j-D}$ ใกใใใฉใฎ่ฆ็ด ใใชใใใฐใ$B_{j-D}$ ใ่ถ ใใๆๅฐใฎ่ฆ็ด (ใชใใใฐend)ใๆใใ -
$B_{j-D}$ ใกใใใฉใฎ่ฆ็ด ใไธใคไปฅไธใใใฐใ$B_{j-D}$ ใกใใใฉ่ฆ็ด ใงๆใๆทปใๅญใฎๅฐใใ็ฉใๆใ
ใใจใฏใใคใ้ใใใฉใ ใๅผใๆธใใฆไบๅๆข็ดขใใๅบ้ใฎ็นใฎๆฐใ
*std::ranges::partition_point(std::views::iota(0LL, 1000000000LL), pred);ใใใใใจใ
ใณใผใใฏใใกใ
ๆฌ็ชไธญใฏ1 WAใๅใใชใใพใพใณใณใในใใ็ตใใฃใฆใใพใฃใใใณใณใในใ็ตไบๅพใซไฝใจใ่ชๅACใใใใใใใใไฝใๅฎ่ฃ ใ้้ใฃใฆใใใ
ใฏใใชใฎใ ใใใฉใใใ่จณใ 1 WA ใๅใใใซใงใณใณใในใใ็ตใใฃใฆใใพใฃใใ
ๅ ฌๅผ่งฃ่ชฌ้ใใซๅฎ่ฃ ใใใจ ใใฎใใใซ ใชใใ
- DPใงๆฑใใใฎใใพใ ้ฃในใใใใจใใใใ้ฃในใใใชใใจใใใฎ้ใใงใใใใใ้ฃในใใใชใใจใใซใใใจ้้ใใใ
-
$i$ ใพใง่ชฟในใใจใใฎ$k$ ใฏ$i$ ไปฅไธใงใใใ - 1 WAใฎๅๅ ใฏใใใใ ใใกใ ใซใใ้ใใงใใใWAใใ ใณใผใ ใ ใจไปฅไธใง2ใ่ฟใ(ไธใใ้ ใซ้ฃในใใจ2ใ ใใไธใใ้ ใซ้ฃในใใจ3ใๆญฃ่งฃใงใใ)ใ
3 10 10
2 5
2 6
6 2