GoogleCodeJam2004
¤³¤Îʸ¾Ï¤Ï¡¢2004/09/18¤«¤é2004/09/25¤Î¥Ö¥í¥°¤òÊÔ½¸¤·¤¿¤â¤Î¤Ç¤¹¡£
QualificationRound? †
¡¡Google Code Jam ¤È¤¤¤¦¤Î¤Ï¡¢Google¤¬¿Íºàȯ·¡¤òÌÜŪ¤È¤·¤ÆTopCoder?¾å¤Ç¹Ô¤Ã¤Æ¤¤¤ë¥×¥í¥°¥é¥ß¥ó¥°¥³¥ó¥Æ¥¹¥È¤Ç¤¹¡£µîǯ¤â¤ä¤Ã¤Æ¤¤¤¿¤é¤·¤¤¤Ç¤¹¡£
¡¡¿½¤·¹þ¤ß > Qualification Round > Round1 > Round2 > Championship Round
¤È¤¤¤¦Î®¤ì¤Ç¡¢º£¤Ï Round1 ¤Î¼êÁ°¤Ç¤¹¡£
¡¡¤È¤ê¤¢¤¨¤º Qualification Round ¤ÏÄ̤ê¤Þ¤·¤¿¡£1000ÅÀÌäÂê¤ÇÂ缺ÇÔ¤·¤¿¤Î¤Ç¤¹¤¬¡¢400ÅÀÌäÂ꤬Æñ¤·¤«¤Ã¤¿¤Î¤Ç±¿¤è¤¯Ä̤ä¿´¶¤¸¤Ç¤¹¡£
¡¡¼ºÇԤȤ¤¤¦¤Î¤Ï¡¢¥³¡¼¥Ç¥£¥ó¥°Â®ÅÙ¤òµá¤á¤ë¥³¥ó¥Æ¥¹¥È¤Ê¤Î¤Ë¡¢ºÇŬ¤Ê¥¢¥ë¥´¥ê¥º¥à¤ò¹Í¤¨¤Æ¤·¤Þ¤Ã¤¿¤³¤È¡¦¡¦¡¦¡£ÉáÃʤλŻö¤Ç¤Ï¥È¥í¤¤¥¢¥ë¥´¥ê¥º¥à¤Ê¤ó¤Æ»È¤¤Êª¤Ë¤Ê¤é¤Ê¤¤¤Î¤Ç¡¢¤Ä¤¤¤ä¤Ã¤Æ¤·¤Þ¤¤¤Þ¤·¤¿¤¬¡¢¥Ù¥¿¤ÊÊýË¡¤Ç¼ÂÁõ¤·¤Æ¤·¤Þ¤¦¤Û¤¦¤¬Îɤ¤¤è¤¦¤Ç¤¹¡£¤È¤ê¤¢¤¨¤º¡¢ÁíÅö¤ê¤Ë¤·¤Æ¤ª¤¤¤Æ¡¢¤½¤ì¤Ç¥¿¥¤¥à¥¢¥¦¥È¤·¤Æ¤·¤Þ¤¦¤è¤¦¤À¤Ã¤¿¤é¡¢´Êñ¤Ê¥Á¥§¥Ã¥¯¤òÆþ¤ì¤Æ¤ß¤ë¤È¤¤¤¦ºîÀ郎Îɤµ¤½¤¦¡£
¡¡¤Á¤Ê¤ß¤Ë¡¢»²²Ã¼Ô¸þ¤±¤Ë¾Ü¤·¤¯¸À¤¦¤È¡¢¥®¥¢ÈæÌäÂê¤Ç¡¢ÁíÅö¤ê¤Ç¤Ï¤Ê¤¯¡¢¿ô³ØŪ¤Ë²ò¤³¤¦¤È¤·¤Æ¤·¤Þ¤¤¤Þ¤·¤¿¡£ÁíÅö¤ê¤Ç²ò¤¯¤ÈÈó¾ï¤Ë´Êñ¤Ç¤¹¤¬¡¢¥Þ¥¸¥á¤Ë²ò¤¯¤ÈÆñ¤·¤¤ÌäÂê¤Ç¤¹¡£
¡¡¤â¤¦°ìÌä¤Ï¡¢¥¢¥ó¥Á¥¨¥¤¥ê¥¢¥¹ÌäÂê¡¢¤³¤Á¤é¤ÎÊý¤¬1000ÅÀÌäÂê¤è¤ê¤âÌÌÅݤǡ¢»²²Ã¤·¤¿Room¤ÎÀµÅú¼Ô¤¬¾¯¤Ê¤«¤Ã¤¿¸¶°ø¤Î¤è¤¦¤Ç¤¹¡£
¡¡¼¡²ó¤ÎRound1¤Ï¡¢9/20 9:00 PM ET¤Ç¤¹¡£ÆüËÜ»þ´Ö¤Ë¤¹¤ë¤È¡¢9/21 10:00 AM JST ¤Ç¤¹¡£¤ä¤Ã¤Ñ¤êÆüËܤ«¤é¤À¤È»²²Ã¤·¤Ë¤¯¤¤»þ´Ö¤Ç¤¹¤Í¡£
¡¡¤Þ¤¡¡¢¼ÂÎÏŪ¤ËTOP50¤Ï̵Íý¤À¤í¤¦¤±¤É¡Ê¤È¤¤¤¦¤«³¤³°¤Þ¤Ç¹Ô¤¯µ¤¤Ê¤¤¤·¡Ë¡¢Round2¤Þ¤Ç¤Ï»Ä¤ê¤¿¤¤¤È¤³¤í¤Ç¤¹¡£
»ÈÍѸÀ¸ì †
¡¡TopCoder?¤Î¥³¥ó¥Æ¥¹¥È¤Ç¤Ï¡¢C++, C#, Java, VB¤¬»ÈÍѤǤ¤Þ¤¹¡£
¡¡¤É¤Î¸À¸ì¤ò»ÈÍѤ·¤Æ¤¤¤ë¤«¤Ï¡¢Summary¤Î³Æ¥¹¥³¥¢¤Î¿§¤ÇȽÃǤ¹¤ë¤³¤È¤¬¤Ç¤¤Þ¤¹¡£¤â¤Á¤í¤ó¡¢Ä¾ÀÜ¥³¡¼¥É¤ò¸«¤Æ¤â¤ï¤«¤ê¤Þ¤¹¡£
¡¡¤Á¤Ê¤ß¤Ë¡¢
²«¿§¡¡C++
ÀÄ¿§¡¡C#
Îп§ Java
¿å¿§ VB
¤Ç¤¹¡£
¡¡¤»¤Ã¤«¤¯¤Ê¤Î¤Ç¡¢»²²Ã¼Ô¤Î»ÈÍѸÀ¸ì¤Ë¤Ä¤¤¤ÆÄ´¤Ù¤Æ¤ß¤Þ¤·¤¿¡£³ÆRoom¤ÎTOP16¡Ê¹ç·×160̾¡Ë¤Î»ÈÍѸÀ¸ì¤Ç¤¹¡£
C++ 107¿Í (66.8%)
Java 44¿Í (27.5%)
C# 8¿Í (5.0%)
VB 1¿Í (0.6%)
¡¡¤¢¤¯¤Þ¤Ç¤â¥³¥ó¥Æ¥¹¥È¤Ë»²²Ã¤·¤¿Ãæ¤ÇÀµÅú¤òÁ᤯½Ð¤»¤¿¿Í¤ÎÅý·×¤Ç¤¹¡£
¡¡¸Ä¿ÍŪ¤Ê´¶ÁۤȤ·¤Æ¤Ï¡¢C++¤¬·òºß¤Ç¤Á¤ç¤Ã¤È°Â¿´¤·¤Þ¤·¤¿¡£C#¤ò»È¤¦¿Í¤Ï°Õ³°¤È¾¯¤Ê¤¯¤Æ¡¢½ÏÎýÅÙ¤ÎÄ㤤¿Í¤¬Â¿¤¤¤è¤¦¤Ç¤¹¡£µÕ¤Ë¹Í¤¨¤ë¤È¡¢¿·¤·¤¯¸À¸ì¤ò³Ð¤¨¤ë¿Í¤¬C#¤«¤éÆþ¤ë¤³¤È¤¬Â¿¤¤¤Î¤«¤â¤·¤ì¤Þ¤»¤ó¡£VB¤Ï¤ä¤Ï¤ê¾¯¤Ê¤¤¤è¤¦¤Ç¤¹¡£Java¤ÏÂÅÅö¤Ê¥Ñ¡¼¥»¥ó¥Æ¡¼¥¸¤Ç¤·¤ç¤¦¡£¥Ý¥¹¥ÈC++¤È¤·¤ÆC#¤¬ÉáµÚ¤¹¤ë¤¿¤á¤Ë¤Ï¡¢Microsoft°Ê³°¤¬¤â¤Ã¤È´èÄ¥¤é¤Ê¤¤¤È¥À¥á¤«¤â¤·¤ì¤Þ¤»¤ó¡£
¡¡¤Á¤Ê¤ß¤Ë¡¢QualificationRound? ¤Î»²²Ã¼Ô¤Ï2564¿Í¡¢»þ´ÖÆâ¤ËÀµÅú¤ò½Ð¤»¤¿¡Ê¥Ý¥¤¥ó¥È¤¬£±°Ê¾å¡Ë¿Í¤Ï1197¿Í(46.7%)¤Ç¤·¤¿¡£
ÁÇÁᤤ¥³¡¼¥Ç¥£¥ó¥° †
¡¡¥½¡¼¥¹¤ò¸«¤Æ¤¤¤Æ¡¢¥Þ¥¯¥í¤ò»È¤¦¿Í¤¬Â¿¤¤¤³¤È¤Ëµ¤¤¬ÉÕ¤¤Þ¤·¤¿¡£
¡¡¤·¤«¤â¡¢
#define FORI(A,B) for (int i = (A); i < (B); i++)
¤Î¤è¤¦¤ÊÄ̾ï¤Ç¤Ï»È¤ï¤Ê¤¤¤è¤¦¤Ê¥Þ¥¯¥í¤Ç¤¹¡£
¡¡¹Í¤¨¤ë¤Ë¡¢¤³¤ì¤ÏÁÇÁᤤ¥³¡¼¥Ç¥£¥ó¥°¡¢¤Ä¤Þ¤ê¥¿¥¤¥×Î̤ò¸º¤é¤¹¤¿¤á¤Î¼êË¡¤Ê¤Î¤Ç¤·¤ç¤¦¡£
¡¡Ä̾ï¤Î¥³¡¼¥Ç¥£¥ó¥°¤Ç¤³¤ó¤Ê¤³¤È¤ò¤·¤¿¤é¡¢²ÄÆÉÀ¤ÎÄ㤤¥³¡¼¥É¤ò½ñ¤¯¤Ê¡¢¤ÈÅܤë¤È¤³¤í¤Ç¤¹¡£
¡¡¥Þ¥¯¥í¤Î»ÈÍѤϡ¢¤½¤Î²ÄÆÉÀ¤ÎÄã²¼¤ò¹Íθ¤·¤Æ¤â¾¤ÎÍø±×¤¬Â礤¤¤È¤¤ä¡¢Å¸³«¤·¤Æ½ñ¤¤¤¿Êý¤¬²ÄÆÉÀ¤¬²¼¤¬¤ë¤È¤¤Ë¸Â¤ë¤Ù¤¤Ç¤¹¡£
¡¡¤·¤«¤·¡¢¥³¡¼¥Ç¥£¥ó¥°Â®ÅÙ¤ò¶¥¤¦¤È¤¤ËºÇ¤âÍ¥À褵¤ì¤ë¤â¤Î¤Ï®Å٤Ǥ¹¤«¤é¡¢¥á¥ê¥Ã¥È¤¬Â礤¤¡¢¤Ä¤Þ¤ê»È¤Ã¤Æ¤âÎɤ¤¤È¹Í¤¨¤é¤ì¤Þ¤¹¡£
¡¡¤ª¤½¤é¤¯TopCoder?¤Ë´·¤ì¤Æ¤¤¤ë¿Í¤Ê¤Î¤À¤È»×¤¤¤Þ¤¹¤¬¡¢ÂçÎ̤Υޥ¯¥í¤ò½¾¤¨¤Æ¥³¥ó¥Æ¥¹¥È¤Ë˾¤ó¤Ç¤¤¤ë¿Í¤â¤¤¤Þ¤¹¡£
¡¡¤â¤Ï¤ä¡¢C++¤Ç¤Ï¤Ê¤¯¡¢C++¤ò¥Ù¡¼¥¹¤Ë¤·¤¿¿·¤·¤¤¸À¸ì¤È¸À¤Ã¤Æ¤·¤Þ¤Ã¤Æ¤âÎɤ¤´¶¤¸¤Ç¤¹¡£
Round1 †
¡¡¤Þ¤¿¤·¤Æ¤âÂ缺ÇÔ¡£
¡¡250ÅÀÌäÂê¤Ç¡¢ÆþÎϾò·ï¤òÆɤó¤Ç¤Þ¤»¤ó¤Ç¤·¤¿¡£¥¿¥¤¥à¥¢¥¦¥È¤¹¤ë¤è¤¦¤ÊÌäÂê¤Ç¤Ï¤Ê¤¤¤«¤é¡¢Âç¾æÉפÀ¤í¤¦¤È»×¤Ã¤Æ¸«¤Þ¤»¤ó¤Ç¤·¤¿¤¬¡¢int ¤Ç¤ÏÆþ¤é¤Ê¤¤¤È¤¤¤¦æ«¤¬¤¢¤ê¤Þ¤·¤¿¡£long long ¤« double¤Ë¤·¤Ê¤¤¤È¥À¥á¤Ç¤·¤¿¡£
¡¡¤ä¤Ã¤Ñ¤ê±Ñ¸ì¤ÎÊɤÏÂ礤¤¤«¤Ê¤¡¡£
¡¡¤Ã¤Æ¡¢Ã±¤ËÃí°ÕÎϤ¬Â¤ê¤Ê¤¤¤À¤±¤«¡£
¡¡1000ÅÀÌäÂê¤ÏÈó¾ï¤Ë¸·¤·¤¤ÌäÂê¤Ç¤·¤¿¡£
¡¡Ã±½ã¤ÊÁíÅö¤ê¤À¤È¿ʬ¥¿¥¤¥à¥¢¥¦¥È¤¹¤ë¤·¡£
¡¡¼ÂºÝ¤Ë1000ÅÀÌäÂê¤ò¥¯¥ê¥¢¤·¤¿¿Í¤Ï¡¢20¿Í¤·¤«¤¤¤Þ¤»¤ó¡£¤·¤«¤·¡¢¾å°Ì¤Î¿Í¤Î¥½¡¼¥¹¤ÏÌÇÃã¶ìÃãû¤¤¡ªÀä̯¤Ê¥¢¥ë¥´¥ê¥º¥à¤Ç²ò¤«¤ì¤Æ¤¤¤Þ¤¹¡£¤³¤Î¥½¡¼¥¹¤ò¸«¤ë¤¿¤á¤Ë»²²Ã¤·¤Æ¤¤¤ë¤È»×¤Ã¤Æ¤âÎɤ¤¤¯¤é¤¤¤Ç¤¹¡£ÍµÙ¤È¤Ã¤Æ»²²Ã¤·¤Æ¤ë¹ÃÈ夬¤¢¤ê¤Þ¤¹¡Ê¾Ð
¡¡1000ÅÀÌäÂê¤Ï°Ê¾å¤ÎÄ̤ê¤Ç¤¹¤¬¡¢250ÅÀ¡¢500ÅÀÌäÂê¤â¡¢¤«¤Ê¤ê¤Î¿Í¤¬system test ¤òÄ̤뤳¤È¤¬¤Ç¤¤Ê¤«¤Ã¤¿¤è¤¦¤Ç¤¹¡£·ë²ÌŪ¤Ë¡¢¼¡¤Î¥é¥¦¥ó¥É¤Ø¤Î¥Ü¡¼¥À¡¼¥é¥¤¥ó¤Ç¤¢¤ë250°Ì¤Ï¡¢188.85ÅÀ¤ÈÄ㤤ÅÀ¿ô¤Ç¤·¤¿¡£¤½¤Î¤¿¤á¡¢500ÅÀÌäÂê¤ò¥¯¥ê¥¢¤·¤¿¿Í¤Ï¡¢¿ô¿Í¤ÎÎã³°¤ò½ü¤¤¤Æ250°ÊÆâ¤Ë¼ý¤Þ¤Ã¤Æ¤¤¤Þ¤¹¡£
¡¡»ä¤â¡¢À®ÀӤˤĤ¤¤Æ¤ÏÈó¾ï¤ËÉÔËþ¤Ǥ¹¤¬¡¢¤Þ¤¿¤·¤Æ¤â±¿¤è¤¯Ä̲á¤Ç¤¤Þ¤·¤¿¡£
¡¡Round2¤Ç50°Ì°ÊÆâ¤ËÆþ¤ë¤Ë¤Ï¡¢1000ÅÀÌäÂê¤ËÄ©À路¤Ê¤±¤ì¤Ð¥À¥á¤Ç¤·¤ç¤¦¤Í¡£¤Þ¤¡¡¢»þ´Ö¤ËÄɤï¤ì¤ë¶ÛÄ¥´¶¤ò³Ú¤·¤ß¤¿¤¤¤È»×¤¤¤Þ¤¹¡£¤Ã¤Æ¡¢¤Þ¤¿ÍµÙ¤Ç¤¹¤«¡¦¡¦¡¦¡Ê¤Á¤Ê¤ß¤Ëº£Æü¤Ï¡¢Ìò½ê¤Ë¹Ô¤¯¤È¤¤¤¦ÍÑ»ö¤â¤¢¤ê¤Þ¤·¤¿¡Ë
ÆüËܤ«¤é¤Î»²²Ã¼Ô †
º£²ó¤ÎÅý·×¡Ê¾¡¼ê¤ËÄ´¤Ù¤Æ¤Þ¤¹¡Ë
¡¡Round1¤ÎÁí»²²Ã¼Ô¿ô¤Ï442¿Í(»²²ÃΨ88.4%)¤Ç¤·¤¿¡£
¡¡¤µ¤Æ¡¢ÆüËܤ«¤é¤Î»²²Ã¼Ô¿ô¤Ï¤É¤ì¤¯¤é¤¤¤¤¤ë¤Î¤Ç¤·¤ç¤¦¤«¡£
»²²Ã¼Ô¤ÎÅÐÏ¿¹ñ̾¤¬¸«¤é¤ì¤ë¤Î¤Ç¡¢¤½¤ì¤ÇÆüËܤ«¤é¤Î»²²Ã¼Ô¤ò¿ô¤¨¤Æ¤ß¤Þ¤·¤¿¡£
¡¦QualificationÄ̲á 9¿Í(Á´ÂΤËÂФ¹¤ë³ä¹ç1.8%)
¡¦Round1Ä̲á 4¿Í(1.6%)
¡¡Qualification¤Î»²²Ã¼Ô¿ô¤ÏÌÌÅݤʤΤÇÄ´¤Ù¤Æ¤Þ¤»¤ó¤¬¡¢ÈæΨ¤Ç¸À¤¨¤Ð¡¢45¿ÍÁ°¸å¤À¤È»×¤ï¤ì¤Þ¤¹¡£
¡¡¤Á¤Ê¤ß¤Ë¡¢ÅÐÏ¿¹ñ̾¤Ç¤¢¤Ã¤Æ¡¢ÆüËܿͤ«¤É¤¦¤«¤Ïʬ¤«¤ê¤Þ¤»¤ó¡£ÆüËܤ«¤é¤Î»²²Ã¼Ô¤Ç¥È¥Ã¥×¤Î¿Í¤Ï¡¢¤ª¤½¤é¤¯ÆüËܿͤ¸¤ã¤Ê¤¤¤·¡£
¡¡¤½¤¦¤¤¤¨¤Ð¡¢TopCoder?¤ÎÅý·×¡Ê¥ª¥Õ¥£¥·¥ã¥ë¡Ë¤Ç¡¢¹ñÊ̤Υé¥ó¥¯¤¬¤¢¤ë¤Î¤Ç¤¹¤¬¡¢¤½¤³¤ËÆüËܤϤ¢¤ê¤Þ¤»¤ó¡£¤É¤¦¤ä¤éÆüËܤ«¤é¤Î´Ø¿´¤ÏÄ㤤¤è¤¦¤Ç¤¹¡£ÆüËܿ͵»½Ñ¼Ô¤ÎÈó¥°¥í¡¼¥Ð¥ë¤µ¤¬È¿±Ç¤µ¤ì¤Æ¤¤¤ë¤è¤¦¤Ê´¶¤¸¤¬¤·¤Þ¤¹¡£
1000ÅÀÌäÂê¡õ²òÅú †
1000ÅÀÌäÂê¤Î²òÀâ¤Ç¤¹¡£
¤Á¤Ê¤ß¤Ë1000ÅÀÌäÂê¤Ï¡¢¤³¤¦¤¤¤¦ÌäÂê¤Ç¤·¤¿¡£
=========
¡¡¥Õ¥¡¥¤¥ë¤òHDD¤Ë³ÊǼ¤¹¤ë¤È¤¡¢Ï¢Â³¤Ç¤Ï¤Ê¤¯¥Õ¥é¥°¥á¥ó¥È¤¬È¯À¸¤¹¤ë¤³¤È¤¬¤¢¤ë¤¬¡¢¤³¤ì¤ò¥Õ¥¡¥¤¥ë¤´¤È¤ËϢ³¤·¤¿¥»¥¯¥¿¤Ëľ¤»¡£
¡¡¥Ç¥£¥¹¥¯¤Î¥Ç¥Õ¥é¥°Á°¤Î¥»¥¯¥¿ÇÛÃÖ¾ðÊó¤¬vector<string>¤ÇÅϤµ¤ì¤ë¡£³Æstring¤¬£±¤Ä¤Î¥Õ¥¡¥¤¥ë¤òɽ¤·¡¢£±¤Ä¤ÎȾ³Ñ¥¹¥Ú¡¼¥¹¶èÀÚ¤ê¤ÎÀ°¿ôÃͤǥ»¥¯¥¿¤ò¼¨¤¹¡£¤¿¤È¤¨¤Ð¡¢"4 9 6 59 41"¤Ï¡¢¥Õ¥¡¥¤¥ë¤ÎÀèƬ¤¬¥»¥¯¥¿4¤Ë³ÊǼ¤µ¤ì¤Æ¤¤¤Æ¡¢¼¡¤Ë9, 6, 59¡¢ºÇ¸å¤Ë41¤È³ÊǼ¤µ¤ì¤Æ¤¤¤ë¤³¤È¤òɽ¤¹¡£¤³¤Î¾ì¹ç¡¢¥Ç¥Õ¥é¥°¤Ç¤Ï¥»¥¯¥¿4-9¤ËÊ¤Óľ¤»¤Ð¤è¤¤¡£
¡¡¤Þ¤¿¡¢¥Ç¥£¥¹¥¯¤ÎÁí¥»¥¯¥¿¿ô¤¬int n ¤ÇÅϤµ¤ì¤ë¡Ê¥»¥¯¥¿0¤«¤én-1¤Þ¤Ç»ÈÍѤǤ¤ë¡Ë¡£
¡¡¥»¥¯¥¿£²¤Äʬ¤ò³ÊǼ¤Ç¤¤ë¥á¥â¥ê¤¬¤¢¤ë¡£
¡¡¤³¤Î¤È¤¡¢¥»¥¯¥¿¤Î°ÜÆ°²ó¿ô¤ÎºÇ¾®ÃͤòÊÖ¤¹´Ø¿ô¤òºî¤ì¡£
¡¡Áí¥»¥¯¥¿¿ô¤Ï¡¢10¤«¤é100¡£
¡¡¥Õ¥¡¥¤¥ë¿ô¤Ï¡¢1¤«¤é12¡£
¡¡£±¤Ä¤Î¥Õ¥¡¥¤¥ë¾ðÊó¤Ï¡¢1¤«¤é50ʸ»ú¡£
=========
¡¡°Ê²¼¡¢²ò¤Êý¤Î³µÍפǤ¹¡£
¡¡°ìÉô¤Î¥Õ¥¡¥¤¥ë¤ÎÇÛÃ֤ˤĤ¤¤Æ¤Î¡¢ÉôʬÌäÂê¤Ëʬ¤±¤Æ¹Í¤¨¤ë¤Î¤¬¥ß¥½¤Ç¤¹¡£
¡¡¤¿¤À¤·¡¢¥»¥¯¥¿¤Î½ÅÊ£¤Ê¤É¤¬²ò·è¤Ç¤¤ë¤è¤¦¤Ê¥Ç¡¼¥¿¤Î»ý¤ÁÊý¤ò¤·¤Ê¤¤¤È¤¤¤±¤Þ¤»¤ó¡£¤³¤ì¤¬¤Ê¤«¤Ê¤«»×¤¤¤Ä¤¤Þ¤»¤ó¡£
¡¡ÇÛÎó int [n + 1] ¤òÍÑ°Õ¤·¤Æ¡Ên¤ÏºÇÂ祻¥¯¥¿ÈÖ¹æ¡Ë¡¢¤½¤Î¥»¥¯¥¿Èֹ椫¤é¿·¤·¤¤¥Õ¥¡¥¤¥ë¤ò»Ï¤á¤ë¾ì¹ç¤ËɬÍפʥ³¥¹¥È¤ò³ÊǼ¤·¤Þ¤¹¡£[x]¤Î¥³¥¹¥È¤¬1¤Î¾ì¹ç¡¢[x+1]°Ê¹ß¤Î¥³¥¹¥È¤â1¤È¤Ê¤ê¤Þ¤¹¤¬¡¢¤³¤ì¤Ï¾Êά¤·¤Þ¤¹¡£
¡¡¤¿¤È¤¨¤Ð¡¢¥Õ¥¡¥¤¥ë¤ò²¿¤âÇÛÃÖ¤·¤Ê¤¤¤È¤¡¢[0] = 0¤Ç¤¹¡£
¡¡¥Õ¥¡¥¤¥ë1¡Ê½é´ü¾õÂÖ¤Ç{5,8,7}¡Ë¤Î¾ì¹ç¡¢0¤«¤éÇÛÃÖ¤¹¤ë¤È3¤Ä¤Î¥»¥¯¥¿¤òÆþ¤ìÂؤ¨¤ëɬÍפ¬¤¢¤ë¤Î¤Ç¡¢¥³¥¹¥È3¤Ç¤¹¡£¤·¤¿¤¬¤Ã¤Æ¡¢[3] = 3¤Ç¤¹¡£[0],[1],[2]¤Ï¥³¥¹¥È¡ç¤Ç¤¹¡£Æ±Íͤˡ¢5¤Î¾ì¹ç¥³¥¹¥È1¤Ê¤Î¤Ç¡¢[8] = 1¤Ç¤¹¡£
¡¡¤³¤Î¤è¤¦¤Ë¤·¤Æ¡¢¥Õ¥¡¥¤¥ë1¤È¥Õ¥¡¥¤¥ë2¤òÆÈΩ¤ËÇÛÃÖ¤·¤¿¤È¤·¤Þ¤¹¡£¼¡¤Ë¥Õ¥¡¥¤¥ë1,2¤ò¤¢¤ï¤»¤¿ÇÛÃÖ¤ò¹Í¤¨¤Þ¤¹¡£
¡¡ºÇ½ªÅª¤Ë¡¢Á´¤Æ¤Î¥Õ¥¡¥¤¥ë¤òÇÛÃÖ¤·¤¿¤È¤¤ÎºÇŬ²ò¤¬ÆÀ¤é¤ì¤Þ¤¹¡£
¡¡O(2^(n-1))¤Î¥¢¥ë¥´¥ê¥º¥à¤Ç¤¹¤¬¡¢n¤ÏºÇÂç¤Ç12¡¢ÇÛÃÖ¤ÎÁȤ߹ç¤ï¤»¤Ç¸À¤¦¤È4096¤Ç¤¹¤Î¤Ç¡¢½½Ê¬¤Ë»È¤¨¤Þ¤¹¡£¡Ê¥³¥ó¥Æ¥¹¥È¤Ç¤Ï¡¢¼Â¹Ô»þ´Ö¤¬8Éäò±Û¤¨¤ë¥×¥í¥°¥é¥à¤Ï̵¸ú¤È¤Ê¤ê¤Þ¤¹¡Ë
Round2 †
¡¡Æñ¤·¤«¤Ã¤¿¡¦¡¦¡¦
¡¡¤Þ¤º¡¢ÌäÂê¤òÍý²ò¤¹¤ë¤Î¤Ë»þ´Ö¤¬¤«¤«¤Ã¤¿¡£
¡¡¤³¤ì¤Ï±Ñ¸ìÎÏÉÔ¡£
¡¡¥¢¥ë¥´¥ê¥º¥à¤¬»×¤¤¤Ä¤«¤Ê¤«¤Ã¤¿¡£
¡¡¤³¤ì¤Ï¥×¥í¥°¥é¥Þ¤È¤·¤ÆÏäˤʤê¤Þ¤»¤ó¤Í¡£
¡¡¤·¤«¤â¡¢375ÅÀÌäÂê¤Ï¡¢¤¤¤í¤¤¤í¾ì¹çʬ¤±¤ò¹Í¤¨¤ëµ¤ÎϤ¬Ìµ¤«¤Ã¤¿¤È¤¤¤¦ÌäÂê³°¤ÎÍýͳ¤Ç¤¹¡£¤â¤¦¥â¥Á¥Ù¡¼¥·¥ç¥óÍî¤Á¤Þ¤¯¤ê¡£
¡¡·ë¶É¡¢550ÅÀÌäÂꤷ¤«½ÐÍè¤Þ¤»¤ó¤Ç¤·¤¿¡£550ÅÀÌäÂê¤Ï¡¢¶Ë¾®¤¬ºÇ¾®¤Ë¤Ê¤ë´Ø¿ô¤Î¶ËÃͤòµá¤á¤ëÌäÂê¤À¤È»×¤¤¤Þ¤¹¡£ËÜÅö¤Ë¶Ë¾®¤¬ºÇ¾®¤Ë¤Ê¤ë¤«¤Ï³Îǧ¤·¤Æ¤¤¤Þ¤»¤ó¤¬¡¢Ê·°Ïµ¤Åª¤Ë¤½¤ó¤Ê´¶¤¸¡£Å¬Åö¤Ê¿ôÃÍ·×»»¤ò¤¹¤ì¤Ð¤¤¤¤¤Î¤Ç¤¹¤¬¡¢¤â¤ÎÀ¨¤¯¸¶»ÏŪ¤ÊÊýË¡¤Ç²ò¤¤Þ¤·¤¿¡£»Å»ö¤Ç»È¤¦¤³¤È¤â¤¢¤ë¤Î¤Ë¡¦¡¦¡¦¡£ Challenge Phase ¤¬¤Á¤ç¤Ã¤ÈÃѤº¤«¤·¤«¤Ã¤¿¤Ç¤¹¡£
¡¡825ÅÀÌäÂê¤Ï¡¢ÃÙ¤½¤¦¤Ê¥¢¥ë¥´¥ê¥º¥à¤·¤«»×¤¤¤Ä¤¤Þ¤»¤ó¤Ç¤·¤¿¡£
¡¡ÌäÂêŪ¤Ë¤Ï¡¢¤ª¤½¤é¤¯
¡¦375ÅÀÌäÂê¡¡¾ì¹çʬ¤±
¡¦550ÅÀÌäÂê¡¡¿ôÃÍ·×»»
¡¦825ÅÀÌäÂê¡¡ºÇŬ²½
¤È¤¤¤¦´¶¤¸¤Ç¤¹¡£
¡¡º£²ó¤Î¥Ü¡¼¥À¡¼¥é¥¤¥ó¤Ï820.48ÅÀ¤Ç¤·¤¿¡£825ÅÀ¤ò³Î¼Â¤Ë²ò¤¤¤Æ¡¢Â¾¤ÎÌäÂê¤Ç¥×¥é¥¹¤·¤Ê¤¤¤ÈÄ̤ì¤Þ¤»¤ó¡£
¡¡ÏäÏÊѤï¤Ã¤Æ¡¢º£²ó¤Î»²²Ã¼Ô¿ô¤Ç¤¹¤¬¡¢Round2¤Ï¼«Æ°ÅÐÏ¿¤Ê¤Î¤Ç¡¢ËÜÅö¤Î»²²Ã¿Í¿ô¤ÏÉÔÌÀ¤Ç¤¹¡£¥¢¥¯¥»¥¹¤·¤Ê¤¯¤Æ¤â0¥Ý¥¤¥ó¥È¤È¤·¤Æ·ë²Ì¤¬½Ð¤Þ¤¹¡£
¡¡ÆüËܤ«¤é»²²Ã¼Ô¤Ç¤Ï¡¢¸æÆóÊý¤ÏÉÔ»²²Ã¤Ç¤·¤¿¡£
¡¡»Ä¤ê¤ÎÆó¿Í¤âºÇ½ª¥é¥¦¥ó¥É¤Ë¤Ï»Ä¤ì¤Þ¤»¤ó¤Ç¤·¤¿¡£
Áíɾ
¡¡¤³¤¦¤¤¤¦¥·¥¹¥Æ¥à¤Î¥×¥í¥³¥ó¤Ï½é¤á¤Æ¤À¤Ã¤¿¤Î¤Ç¶½Ì£¿¼¤«¤Ã¤¿¤Ç¤¹¡£Â®¤¯½ñ¤¯¥¹¥¥ë¤¬°ìÈÖ½ÅÍ׻뤵¤ì¤ë¤Î¤Ç¤¹¤¬¡¢Â¾¤Î¿Í¤Î¥³¡¼¥É¤òÆɤó¤Ç¥Ð¥°¤òõ¤¹¥¹¥¥ë¤âɬÍפÊÅÀ¤¬ÌÌÇò¤¤¤Ç¤¹¡£¤¿¤À¡¢¤³¤Î¥·¥¹¥Æ¥à¤Ã¤ÆÆõö¤¬¼è¤é¤ì¤Æ¤¤¤ë¤È¤¤¤¦ÏäʤΤǡ¢¼«Á°¤Çºî¤ë¤ï¤±¤Ë¤Ï¤¤¤«¤Ê¤ó¤Ç¤¹¤è¤Í¡£¤Þ¤¿¡¢¾å°Ì¤Î¿Í¤¿¤Á¤Ï¡¢¥ì¥Ù¥ë¤¬°ã¤¦´¶¤¸¤Ç¤·¤¿¡£
¡¡½ÐÂê¤Ï¡¢¡ÊÆä˹âÆÀÅÀÌäÂê¤Ç¡ËºÇŬ²½ÌäÂ꤬¿¤¯¤Æ¤Á¤ç¤Ã¤È¸ÍÏǤ¤¤Þ¤·¤¿¡£¤È¤¤¤¦¤«¡¢²ò¤±¤Þ¤»¤ó¤Ç¤·¤¿¡£¤³¤ì¤Ï¡¢º£¸å¤Î²ÝÂê¤Ë¤·¤¿¤¤¤È»×¤¤¤Þ¤¹¡£
¡¡¤Ä¤¤¤Ç¤Ë¤¤¤¦¤È¡¢±Ñ¸ì¤¬¤Þ¤ë¤Ç¥À¥á¤Ê¤Î¤¬Ïª¸«¤·¤¿´¶¤¸¡£¤³¤ì¤ÇÁêÅö¤Ë»¤ò¤·¤Æ¤Þ¤¹¡£
¡¡TOPCODER¤ÎCompetition¤ÇÆüÍ˳«ºÅ¤Î¤â¤Î¤ä¡¢¸áÁ°Ãæ¡ÊÆüËÜ»þ´Ö¤À¤È¸á¸å¡Ë¤Ë³«ºÅ¤µ¤ì¤ë¤â¤Î¤Ê¤éµ¤·Ú¤Ë»²²Ã¤Ç¤¤ë¤Î¤Ç¡¢º£¸å¤âŬÅö¤Ë»²²Ã¤·¤Æ¤ß¤è¤¦¤È»×¤¤¤Þ¤¹¡£
Êä †
¡¡Round2¤ÎÉÔ»²²Ã¿Í¿ô¤ò¿ô¤¨¤Æ¤ß¤Þ¤·¤¿¡£
¡¡Á´ÌäÂêunopen¤Î¿Í¤Ï17¿Í¤Ç¤·¤¿¡£
¥³¥á¥ó¥È †
- shoe lifts 2013-09-16 (·î) 14:39:14
Usually I don’t learn article on blogs, but I wish to say that this write-up very pressured me to take a look at and do so! Your writing style has been amazed me. Thank you, very