ç§ã¯ Google HashCode World Championship Finals 2017 ã®æºåãããŠããŸãããããã¯ãGoogle ãäž»å¬ããã¢ã«ãŽãªãºã åé¡ãæ±ãæ倧ã®ã³ã³ãã¹ãã§ãã
ç§ã¯ XNUMX 幎çã®ãšãã« C++ ããŒãããåŠã³å§ããŸããã ç§ã¯ããã°ã©ãã³ã°ãã¢ã«ãŽãªãºã ãããŒã¿æ§é ã«ã€ããŠäœãç¥ããŸããã§ããã ããæç¹ã§ãæåã®ã³ãŒãè¡ãæžããŸããã XNUMX ãæåŸãããã°ã©ãã³ã° ã³ã³ãã¹ããç®åã«è¿«ã£ãŠããŸããã èªåã®ããã°ã©ãã³ã°åŠç¿ã¹ã¿ã€ã«ãã©ãã ãå¹æãããã®ãââãç¥ãããã£ãã®ã§ãã ããã¯çµ¶å¥œã®æ©äŒã§ããã
XNUMXæ¥éã®ç«¶æã®åŸãçµæãåºãŸãããç§ã¯éã¡ãã«ãç²åŸããŸããã
ç§ã¯ã·ã§ãã¯ãåããŸããã ç§ã¯ 5 幎ã®çµéšãæã€ç«¶åä»ç€Ÿãããå ãè¡ã£ãŠããŸããã äžçæžåœåªåããŠããããšã¯åãã£ãŠããŸãããããã®ææã¯ç§ã®æåŸ ããã¹ãŠäžåããŸããã ã¹ããŒã ããã°ã©ãã³ã°ãèªåã®ããŒãã§ããããšã«æ°ã¥ããçã£åããããã«åãçµã¿ãŸããã
ç§ã¯äœãç§ãæåã«å°ããã®ããç¥ã£ãŠããã®ã§ããããçãããšå
±æããããšæããŸãã
ãã®èšäºã¯ EDISON Software ã®ãµããŒããåããŠç¿»èš³ãããŸãããããã°ã©ããŒã®å¥åº·ãšæé£ã®äžè©±ãããŸã ãšã«ã¹ã¿ã ãœãããŠã§ã¢ãéçºããŸã .
ã©ã®ããã°ã©ãã³ã°èšèªãéžæããã
- C++ - 匷ããå§ãããŸã! 圌ã¯ãšãŠãéãã§ãã STL ã«ããã¢ã«ãŽãªãºã ã®å®è£ ã«ã¯ã»ãšãã©æéãããããŸããã C++ ã¯ãã¹ãŠã®ã³ã³ãã¹ãã§åãå ¥ããããŸãã æåã®ã³ãŒãè¡ã¯ C++ ã§æžããŸããã
- C - STL ã®ããã« C++ ãåŠã³ãŸãã C ã®ç¥èãããå Žåã¯ãC++ ã§ããã°ã©ãã³ã°ããããšãã§ããŸãã
- Java ã¯é ãããã°ã©ãã³ã°èšèªã§ãã Big Integer ã¯ã©ã¹ããããŸãããããŸã圹ã«ç«ã¡ãŸããã 競æã«å¶éæéãããå Žåã§ããJava ã䜿ãã°å¿ ãå¶éæéãè¶ ããããšãã§ããŸãã Java ã¯ãã¹ãŠã®ã³ã³ãã¹ãã§åãå ¥ããããããã§ã¯ãããŸããã
ã©ãã§ç·Žç¿ã§ããŸãã
ç§ã¯ãå§ã
ãŸãã¯åºç€ç¥èã磚ãå¿ èŠããã
èšèªã®æ§æã«æ £ãããšãå æãã¹ãåé¡ãããã€ããããŸãã ç·Žç¿ãå¿ èŠãªç°¡åãªåé¡ããå§ããŠãã ããã ãã®æ®µéã§éèŠãªã®ã¯ãããã°ã©ãã³ã° ã¹ã¿ã€ã«ã決å®ããããšã§ãã 空çœãå€ãå«ãã³ãŒããæžãã®ã奜ããªäººããããããããŸããããããã§ãªã人ããããããããŸããã æ¬åŒ§ããifããšåãè¡ã«çœ®ãããšããå¥ã®è¡ã«çœ®ãããšãã§ããŸãã
ããã¯ããªãã®ã¹ã¿ã€ã«ãªã®ã§ãèªåã®ããã°ã©ãã³ã° ã¹ã¿ã€ã«ãèŠã€ããå¿ èŠããããŸãã
ãããæ¢ããšãã¯ã次㮠XNUMX ã€ã®åºæ¬ååãæãåºããŠãã ããã
- ã³ãŒãã¯å®è£ ãç°¡åã§ããå¿ èŠããããŸãã æãã€ãããœãªã¥ãŒã·ã§ã³ãå®å¿ããŠå®è£ ã§ããã¯ãã§ãã ãªãïŒ ãªããªãã競æäžã«ã³ãŒãã«å€¢äžã«ãªãããšã¯çµ¶å¯Ÿã«é¿ãããããã§ãã ã³ãŒãã®å®è£ ãç°¡ç¥åããæ¹æ³ãèããããã«è¿œå ã® 5 åãè²»ãããã»ãããã³ãŒããç解ããã®ã« 10 åãè²»ãããããåžžã«åªããŠããŸãã
- ã³ãŒãã¯èªã¿ããããªããã°ãªããŸããã ã³ãŒããèªã¿ããããšããããã°ãç°¡åã§ãã æ£çŽã«èšã£ãŠããã°ã¯åžžã«çºçããŸãã æ®ã 10 åãªã®ã«ééããèŠã€ãããªããšãã®ãã®æ°æã¡ãããããŸãã? ãã¡ããããã§ãããã ãã®ç¶æ³ãåé¿ããã«ã¯ãèªã¿ãããã³ãŒããäœæããŠãã ããã ãããã°ãéå§ãããšãã³ãŒãã¯èªç¶ã§ç解ãããããã®ã«ãªãã§ãããã
éçºã¹ãã«ãåäžãããæ¹æ³
ç·Žç¿ãç·Žç¿ããããŠãã£ãšç·Žç¿ã æåã® 250 åã®æã解決å¯èœãªåé¡ã«åãçµãããšããå§ãããŸãã
ããã®åé¡ã¯ç§ã«ã¯é£ããããã®ã§ã次ã®åé¡ã解ããŠã¿ãŸãããšã¯èšããªãã§ãã ããã æè ã®èãæ¹ã¯ããã ã
çŽãšéçãçšæããŠãã ããã èããŠã¿ãŠãã ããã 解決çãèŠã€ãããããããªãããèŠã€ãããªããããããªãã å°ãªããšããã¢ã«ãŽãªãºã çæèãé€ãããšã«ãªããŸãã XNUMX æé以å ã«è§£æ±ºçãæãã€ããªãå Žåã¯ããã©ãŒã©ã ãŸãã¯èšäºã§æ¢è£œã®è§£æ±ºçãæ¢ããŠãã ããã
ãã®ã¢ãããŒãã§äœãéæã§ããŸãã? ã³ãŒãã䜿çšããŠã¢ã€ãã¢ããã°ããå®è£ ããæ¹æ³ãåŠã³ãŸãã ãããŠå€å žçãªåé¡ãšã¢ã«ãŽãªãºã ãå匷ããŠãã ããã
次ã«ãã¢ã«ãŽãªãºã ãšããŒã¿æ§é ããã¹ã¿ãŒããå¿ èŠããããŸãã
éå±€çãªã¢ãããŒãã«åŸããŸãã æ©ãæ¹ãç¥ããã«ã©ã³ãã³ã°ãå§ããŸãããïŒ ãããã ãã£ããããåºç€ããªããã°è¶ é«å±€ãã«ã建ãŠãããšã¯ã§ããŸããïŒ äºåºŠãšãªãã
åŠç¿ãã¹ã«æ²¿ã£ãã¹ããããç¡èŠããããšã¯ã§ããŸããã ããããç¡èŠãããšãç¥èã®ã®ã£ãããæ®ãããšã«ãªããŸãã æéãçµã€ã«ã€ããŠããããã¯æªåããã ãã§ãã
åºæ¬çãªã¢ã«ãŽãªãºã ãšããŒã¿æ§é ããå§ãã
å§ããã®ã¯é£ããã§ãã ãããããæåã«äœãå匷ããã°ãããããããªãããã§ãã ãããçç±ã§ã
ç°¡åãªåé¡ã解ãããšã«åãçµãã§ããäžéããããšã¯ãããŸããã
ç¥ããªãããšãç解ããæãå¹æçãªæ¹æ³ã¯ãå®éã«çµéšããããšã§ãã ãããã£ãŠåŠã³ãŸããã ææŠçãªã¿ã¹ã¯ãéžæããããšã§ããããŸã§èããããšã®ãªãå€ãã®æ°ãããã¯ããã¯ãåŠã³ãŸããã
XNUMX çªç®ã®åé¡ã«åãçµãããšã«ãäœãæ°ããããšãåŠã¹ãã¯ãã§ãã åé¡ãéžæãããšãã¯ãã泚æããŠãã ããã ããé£ããåé¡ãéžæããŠãã ããïŒ
SPOJ ã®ããã 250 ã®åé¡ãå®äºãããšãã¹ããŒã ããã°ã©ãã³ã°ã®æ žãšãªããããã¯ã®åºæ¬ãç解ã§ããããã«ãªããŸãã åºæ¬çãªã¢ã«ãŽãªãºã ã®èåŸã«ããããžãã¯ãæ·±ãç解ããŠããã°ãé«ã¬ãã«ã®ã¢ã«ãŽãªãºã ã¯ããã»ã©è€éã§ã¯ãªãããã«èŠããŸãã ããããããšã§ãèªåã®ç¥èãæ倧éã«æŽ»çšããããšãã§ããŸãã
ããããã®äž»èŠããŒããããã«æ·±ãæãäžãã
æ°ããããšãåŠãã åŸã«ç¥èã匷åããªããšãããã«ãã¹ãŠãå¿ããŠããŸããŸãã
æ°ããã¢ã«ãŽãªãºã ãåŠç¿ããããå®éã«äœ¿çšããããšããå§ãããŸãã 2 ïœ 3 ã€ã®ã¿ã¹ã¯ãå®è¡ããŠãã ããã SPOJ ã§ã¢ã«ãŽãªãºã ã¿ã°ãæ¢ããŸãã ããã§ã¯ããã®ã¢ã«ãŽãªãºã ã解決ããå¿
èŠãããåé¡ãèŠã€ãããŸãã ãŸããããã®åé¡ã«å¯ŸåŠããŠãã ããã
åçããã°ã©ãã³ã°ããã¹ã¿ãŒããŠãã ããããããããªããåå©ã«å°ããŸã
ç§ã®çµéšããèšãã°ãã©ã®ç«¶æã«ãå°ãªããšã XNUMX ã€ã¯åé¡ããããŸã
ãããŠãããã¯è¯ãããšã§ãã åçããã°ã©ãã³ã°ãç解ããŠããã°åãŠãããã§ãã
ç§ã¯åçããã°ã©ãã³ã°ã奜ãã§ãäžçªå¥œããªãããã¯ã§ãã åçããã°ã©ãã³ã°ã®ç§å¯ã¯ãããŒã«ã«ãªéžæã ãã§ãªããã°ããŒãã«ã«æé©ãªéžæãè¡ãããšã§ãã åé¡ãããåçŽãªãµãåé¡ã«åå²ããå¿
èŠããããŸãã ãããã®äžäœåé¡ã¯ãããã XNUMX åã ã解決ããŠãã ããã 次ã«ã解決ãããéšååé¡ãçµã¿åããããœãªã¥ãŒã·ã§ã³ãäœæããŸãã
æ°ããæŠå¿µãåŠã³ãªããã次ã®ããšã確èªããŠãã ãã
äžçæžåœåã
äœå¹Žãç·Žç¿ããã«ãªãªã³ããã¯ã§åªåããã¢ã¹ãªãŒãã®ããšãèããããšããããŸãã? ç§ã¯éããŸãã
æ¯å¹Žãã³ã³ãã¥ãŒã¿ãŒ ãªãªã³ããã¯ã®æºå㯠XNUMX æã«å§ãŸããXNUMX æã«çµäºããŸããã
ãã®8ãæéãç§ã¯æ¯æ¥5æéç·Žç¿ããŸããã
ã¯ããç§ã¯ãã® 5 æéãã¢ã«ãŽãªãºã ã®åââé¡ã解ãã ãã«è²»ãããŸããã 8æéãå Žåã«ãã£ãŠã¯10æéãç·Žç¿ããæ¥ã ãæãåºããŸãã ãªãïŒ å¥œãã ã£ãããã æ¯æ¥åŠæ ¡ãã家ã«åž°ããšãç§ã¯å¯å®€ã«çŽè¡ããã³ã³ãã¥ãŒã¿ãŒã®åã«åº§ã£ãŠãæ°ããåé¡ã®åæãå§ããŸããã ãããã¯ããã®åé¡ã解決ããããã«ç¥ãå¿ èŠã®ããæ°ããã¢ã«ãŽãªãºã ãåŠãã§ããŸããã
åã¡ãããã°ãåãããšãããªããã°ãªããŸããã åé¡ãéžæããããã«åºå·ããŸãã ã¹ãŒããŒã«è¡ããšããè»ãé転ããªããèããŠã¿ãŠãã ããã
ç¡ç äžãè³ã¯ãã®æ¥ã«åéããæ
å ±ãæçå解é€ããããšããåç¥ã§ãã? 圌ã¯æ¬æ£ã«æ¬ãã¢ã«ãã¡ãããé ã«ç©ã¿äžããŠããããã ã åºæ¬çã«ãããªãã®è³ã¯ããªããçŽé¢ããŠããããŸããŸãªåé¡ã«ã€ããŠèããŸãã
ããã¯äžæã«äœ¿ããŸããã å¯ãåã«é£ããåé¡ãèªãã§ãããã解決ããããã«äœãå¿ èŠããæãåºããŠãã ããã ãã®æ®µéã§ã¯ã解決çèªäœãæ¢ãå¿ èŠã¯ãããŸããã å¯ãã ããªãã®è³ã¯ãã®åé¡ãåŠçãå§ããŸãã ç®ãèŠãããšãå¯ãŠããéã«è§£æ±ºçãèŠã€ããããšã«é©ãã§ãããã
èªåã§è©ŠããŠã¿ãŠãã ããã ãŸãã§éæ³ã®ããã§ãã
åç»ããã°ãäœããŸãã
ãã®çã段èœã¯ã¹ããŒãçªçµãšã¯é¢ä¿ãããŸããã ããããªããXNUMX代ã§ãç§ãäžçãã©ã®ããã«èŠãŠãããçåã«æã£ãŠãããªãããã²ãã§ãã¯ããŠã¿ãŠãã ããã
è³¢ãä»äºããã
ãããæåã®ç§èš£ã§ãã ç®æšãå¿ èŠã§ãã
ç§ãã¡ã¯äººéã§ãããããã奜ãã§ã
å 延ã°ãçãå æããæ¹æ³
èªåèªèº«ã®ç®æšãèšå®ããŸãã æ°ããããšãåŠã¹ãèå³æ·±ãåé¡ãå¿ ãèŠã€ãããŸã (äžèšã®ãªãœãŒã¹ã確èªããŠãã ãã)ã ãããããããã®åé¡ã¯åã«èªãã ãã§ã¯ãªãã解決ããå¿ èŠããããŸãã
ããã§ç§ãå 延ã°ãçãå æããæ¹æ³ãã玹ä»ããŸãã ç§ã¯çŽã®ã«ã¬ã³ããŒãå§ããŠã解決ãããåé¡ãæ¯æ¥è©°ã蟌ã¿ãŸããã ç§ã¯ãã€ãXNUMXæ¥åã«åé¡ãèšå ¥ããŠããŸããã ãã®ããããã®åŸã®æ°æ¥éã§æéã管çããæ¹æ³ãããããŸããã
ã ããç§ã¯åžžã«ã¢ãããŒã·ã§ã³ãä¿ã£ãŠããŸããã ã«ã¬ã³ããŒã®æ¬¡ã®æ¥ãåããããã«ãããã€ãã®åé¡ã解決ããæ°ããåé¡ãèŠã€ããå¿
èŠããããŸããã 解決ããåé¡ãæ¶ããŠããã®ã¯ãšãŠãæ°æã¡ããã§ãã ããªããæ°ã«å
¥ã£ãŠãããšæããŸãã
èªåã ãã®çŽã«ã¬ã³ããŒãæã«å ¥ããŸãããã ææ¥å¿ããŠããŸããããªå¥ã® ToDo ãªã¹ããæºåž¯é»è©±ã«äœæããªãã§ãã ããã
å¹æçã«ãããã°ããæ¹æ³
ããã«ãªãããã§ããïŒ ããã§ããã°ããé ã®äžã§ãããã°ãããå¿
èŠããããŸãã
ããã¯ãããã¬ãŒããŸã£ããå¿
èŠãšããªããããç§ãç¥ã£ãŠããäžã§æãå¹ççãªãããã°ææ³ã§ãã ããªãã®è³ã¯è€æ°ã®ã³ãŒããã©ã³ããäžåºŠã«èª¿ã¹ãŠãã³ãŒãã®ããåºç¯ãªæŠèŠãåŸãããšãã§ããŸãã
èªåèªèº«ãããã§ã¹ããã¬ã€ã㊠3 æå ãèããã°ã©ã³ããã¹ã¿ãŒã«ããšããããšãã§ããŸãã
ç§ã¯ãã®ãã¯ããã¯ãæåã®é²åŸ¡ç·ãšããŠã®ã¿äœ¿çšããŸãã 次ã«ãå®éã®ãããã¬ã䜿çšããŸãã
é ã®äžã§ãããã°ããæ¹æ³ãåŠã¶ã«ã¯ãç·Žç¿ããå¿ èŠããããŸãã åé¡ã®è§£æ±ºçãæ€èšŒããŠãééã£ãçãããåŸãããå Žåã¯ãããã«ãããã¬ãŒ ãã¿ã³ã«é²ãŸãªãã§ãã ããã ã³ãŒããããäžåºŠèªãã§ãããã®è¡ã§äœãèµ·ãã£ãŠããã®ã?ãããããã® "if" ã¯ããã°ã©ã ã«ã©ã®ãããªåœ±é¿ãäžããã®ã?ãããã«ãŒããçµäºãããšãã®å埩åã®å€ã¯äœã?ããèããŠãã ããã
ããããããšã§èªåã§èããããšãã§ããŸãã æéãçµã€ã«ã€ããŠãã³ãŒããæžããŠãã®å Žã§ãããã°ããæ¹æ³ãåŠã³ãŸãã
èè ã«ã€ããŠ
Andrei Margeloiu ã¯ãèµ·æ¥å®¶ç²Ÿç¥ãã¹ã¿ãŒãã¢ãããã¢ãŠããã¢ã«èå³ãæã€ç±å¿ãªããã°ã©ããŒã§ãã 圌ã«é£çµ¡ã§ããŸã
翻蚳: ãã€ã¢ãã»ã·ã§ã¬ããšã¯
åºæïŒ habr.com