ããã«ã¡ã¯Habrãä»æ¥ã¯ãYandexã§ã®å€ã®ã€ã³ã¿ãŒã³ã·ããã®ãã¹ã課é¡ã«åæ Œããæ¹æ³ã«ã€ããŠã話ããŸãã ãã®åºçç©ã¯ãåå¿è
éçºè
ãOlympiadããã°ã©ãã³ã°ã®æ奜家ãC ++ãJavaã«ç¡é¢å¿ã§ãªã人ããŸãã¯å¿ããäžæ¥ã®åŸã«èå³æ·±ãèšäºãèªã¿ãã人ã«åœ¹ç«ã¡ãŸãã
ãã®èšäºã«äœãæåŸ
ããŸããïŒ
- ã¯ããã«ãYandexã§ã®ã€ã³ã¿ãŒã³ã·ãããå¿åæ¹æ³ãšææ
- ãã®èšäºãæžãåæ©
- ã¿ã¹ã¯ã®äŸãç§ã®è§£æ±ºçãããã³ç°¡åãªåæïŒæåã®2ã€ã®ãã€ã³ããå®å
šã«ã¹ãããããŠãããããéå§ã§ããŸãïŒ
ã¯ããã«
Yandexã§ã®ã€ã³ã¿ãŒã³ã·ããã®éžæã·ã¹ãã ã«è©³ãããªã人ã®ããã«ãç°¡åã«èª¬æããŸãã å€ã®æ°ãæå
ã®Yandexã®ãŠã§ããµã€ãã§ãä»äºããããéšéïŒYandex.DiskãYandex.Alisaãªã©ïŒã®åå¿è
ããããããŒåãã®ç©ºåžãçºè¡šãããŸããã åç
§ã«ãããããªãã¯ã©ãã§å匷ããŠããããäœãããŠããã®ããä»äºã®çµéšã¯äœã§ãã£ãã®ããè«æã«ã€ããŠäœãæžããã®ããªã©ã®ãã©ãŒã ã«èšå
¥ããå¿
èŠããããŸãã ãã©ãŒã ãžã®èšå
¥åŸããã¹ãã¿ã¹ã¯ãã¡ãŒã«ã«éä¿¡ãããŸãããã¹ãã¿ã¹ã¯ã¯ããã®æçŽãåãåã£ãç¬éãã1é±é以å
ã®ä»»æã®æ¥ã«6æéã§å®äºããŸãã
ä»åã¯éžã¶ã®ãé£ããã£ãã®ã§ãã»ãŒæçµæ¥ã«ãªããŸããã ãã¹ãŠã®çç±ã¯ãã©ã®ãããªãã¹ãã¿ã¹ã¯ãæåŸ
ãã¹ããããããªãã£ãããã§ãã å€ãã®èšäºãèªã¿çµããåŸãYandexãã€ã³ã¿ãŒã³ã·ããã«ã©ã®ãããªã¿ã¹ã¯ãèšå®ãããã«ã€ããŠã®åäžã®äŸãã¢ããã€ã¹ã¯èŠã€ãããŸããã§ããã ããããç§ããã®èšäºãæžãããšã«ããçç±ã§ãã ãããã®åé¡ã«å¯Ÿããæ£ãã解決çãæäŸããã®ã§ã¯ãªããå²ãåœãŠããã6æéã§ãªããšããªãããšããã§ããŸããã
ãã¹ãã¿ã¹ã¯ã«ã¯ã被éšè
ãç°ãªããè€éããç°ãªã6ã€ã®ã¿ã¹ã¯ããããŸããã æéãšæµ®åå°æ°ç¹æ°ã®ãã©ãŒãããã«é¢ããã°ã©ããç·ãåçããã°ã©ãã³ã°ãããã³ã¢ãããã¯ã«é¢ããã¿ã¹ã¯ããããŸããã
ã¿ã¹ã¯1.ãšã©ãŒ
è·åæ¡ä»¶ãŠã§ããµã€ããç¶æããæ°ããªåé¡ã远跡ããŸãã ã¯ã©ã€ã¢ã³ãã¯ãã·ã¹ãã ã«æçš¿ãè¿œå ããããšããåŸã«ãšã©ãŒãåãåããŸããã ãã®ãšã©ãŒãçºçãããµãŒããŒãææ¡ããå¿
èŠããããŸãã
nåã®ãµãŒããŒãããããããã®içªç®ã«aiããŒã»ã³ãã®èŠæ±ãããããã®ãã¡2ããŒã»ã³ãã倱æããŸãã ãµãŒããŒããšã«ããšã©ãŒãçºçãã確çãèŠã€ããŸãã
å
¥å圢åŒ
å
¥åãã¡ã€ã«ã®æåã®è¡ã«ã¯ã1ã€ã®æŽæ°nïŒ1â€nâ€100ïŒ-ãµãŒããŒã®æ°ãå«ãŸããŠããŸãã
次ã®nè¡ã«ã¯ããããã2ã€ã®æŽæ°ai biïŒ0â€aiãbiâ€100ïŒãå«ãŸããŸã-ãªã¯ãšã¹ããiçªç®ã®ãµãŒããŒã«éä¿¡ããã確çïŒããŒã»ã³ãïŒãšãããŒã»ã³ããšã©ãŒãiçªç®ã®ãµãŒããŒã§çºçãã確çã
ãã¹ãŠã®aiã®åèšã100ã§ãããã·ã¹ãã ã§ãšã©ãŒãçºçããå¯èœæ§ãããããšãä¿èšŒãããŠããŸãã
åºå圢åŒ
nè¡ãå°å·ããŸãã åè¡ã«ã¯ã1ã€ã®å®æ°ïŒ0â€piâ€1ïŒ-察å¿ãããµãŒããŒã§ãšã©ãŒãçºçãã確çãå«ããå¿
èŠããããŸãã
ååçã®çµ¶å¯Ÿèª€å·®ãŸãã¯çžå¯Ÿèª€å·®ã¯10-9ãè¶
ããŠã¯ãªããŸããã
äŸ1
å
¥ã
2
50 1
50 2
ãããã«
0.333333333333
0.666666666667
äŸ2
å
¥ã
3
10 100
30 10
60 2
ãããã«
0.704225352113
0.211267605634
0.084507042254
ãã®åé¡ã解決ããããã«ãJavaã䜿çšããããšã«ããŸããã
æŒç®ã¢ã«ãŽãªãºã ã¯éåžžã«åçŽã§ã
ãnåã®å Žå
ã«aãbãèªã¿åã
ãa ãšbãä¹ç®ããä¹ç®ã®çµæãarr [i]ã«ä¿åããçµæãå€æ°totalã«åèšããŠ100ïŒ
ãèšç®ããŸãã
åºåããã«ã¯ãarr [i]ã100ïŒ
ã§å²ãã ãã§ãã
解決çimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Locale; import java.util.StringTokenizer; public class Main { public static void main(String[] args)throws IOException { Locale.setDefault(Locale.US);
ããã ãã§ããããã¯ç§ãå®å
šã«è§£æ±ºããããšãã§ããæåãšæåŸã®ã¿ã¹ã¯ã§ããã æ®ãã®ã¿ã¹ã¯ã¯ãæ®å¿µãªããæéããããŸããã§ãããç§ã¯ãªã©ãã¯ã¹ããŠãåŸç¶ã®ãã¹ãŠã®ã¿ã¹ã¯ãåãã¬ãã«ã«ãªããšèããŠããããã§ãã æ²ããããªãããã¯ééã£ãŠããããšãå€æããŸããã 次ã®ã¿ã¹ã¯ã®ããã«ããªããšç§ã®ã³ãŒããäœæããããšããŸãã
ã¿ã¹ã¯2.ããŒãã£ã³ã°
è·åæ¡ä»¶å€§å£°ã§è©±ãåãããšã§è·å Žã®ååã«è¿·æããããªãããã«ããããã«ã圌ãã¯äžå®ã®æéã®äºçŽãåããäŒè©±ãäºçŽããŸãã äºçŽæã«ã¯ãäŒè°ã®æ¥æãäŒè°ã®æéãåå è
ã®ãªã¹ããæå®ããå¿
èŠããããŸãã åå è
ã®1人ãåæã«2ã€ã®äŒè°ãéå¬ããå ŽåãäŒè°ã¯ä»ã®äŒè°ãšéè€ãã人ã®ãªã¹ãã®è¡šç€ºã§äºçŽãæåŠãããŸãã ãã®ãããªã·ã¹ãã ã®ãããã¿ã€ããå®è£
ããå¿
èŠããããŸãã
å
¥å圢åŒ
å
¥åãã¡ã€ã«ã®æåã®è¡ã«ã¯ã1ã€ã®æ°å€nïŒ1â€nâ€1000ïŒ-èŠæ±ã®æ°ãå«ãŸããŠããŸãã
次ã®nè¡ã«ã¯ã1è¡ã«1ã€ãã€ã¯ãšãªãå«ãŸããŸãã ã¯ãšãªã«ã¯2ã€ã®ã¿ã€ãããããŸãã
APPOINTæ¥äžæék names1 names2 ... namesk
ææ¥åãå°å·
æ¥-2018幎ã®æ¥æ°ïŒ1â€æ¥â€365ïŒ
time-äŒè°æéãHHïŒMM圢åŒã®æååïŒ08â€HHâ€21ã00â€MMâ€59ïŒ
æé-ååäœã®äŒè°ã®æéïŒ15â€æéâ€120ïŒ
k-äŒè°ã®åå è
ã®æ°ïŒ1â€kâ€10ïŒ
namesiãname-åå è
ã®ååãå°æåã®ã©ãã³æåã§æ§æãããæååïŒ1â€| name |â€20ïŒã ãã¹ãŠã®ååã«ã¯äžæã®ååããããŸãã ããã«ã1ã€ã®äŒè°ã®åå è
éã§ã1ã€ã®ååã2åæ€åºãããããšã¯ãããŸããã
åºå圢åŒ
äºå®ãäœæã§ããå ŽåïŒæåã®çš®é¡ã®èŠæ±ïŒã[OK]ãå°å·ããŸãã
ãã以å€ã®å Žåãæåã®è¡ã«FAILãåºåãã次ã®è¡ã«ãäŒè°ã®æéãä»ã®äŒè°ãšäº€å·®ããåå è
ã®ååã®ãªã¹ãããååããªã¯ãšã¹ãã§äžããããé ã«å
¥åããŸãã
2çªç®ã®ã¿ã€ãã®ãªã¯ãšã¹ãã®å Žåããã®æ¥ãšåå è
ã«å¯ŸããŠããã®æ¥ã«çŸåšçºçããŠãããã¹ãŠã®ã€ãã³ãã®ãªã¹ããæç³»åã§ãè¡ããšã«1ã€ã®åœ¢åŒã§è¡šç€ºããŸãã
HHïŒMMæénames1 names2 ... namesk
åå è
ã®ååã¯ãäŒè°ã®å
ã®èª¬æãšåãé åºã§ç¶ããŸãã ãã®äººã«ãã®æ¥ã«ã€ãã³ãããªãå Žåãäœã衚瀺ããå¿
èŠã¯ãããŸããã
äŸ1
å
¥ã
7
APPOINT 1 12:30 30 2ã¢ã³ãã¬ã€ã»ã¢ã¬ãã¯ã¹
APPOINT 1 12:00 30 2ã¢ã¬ãã¯ã¹ã»ã«ã²ã€
APPOINT 1 12:59 60 2ã¢ã¬ãã¯ã¹ã¢ã³ãã¬ã€
ããªã³ã1ã¢ã¬ãã¯ã¹
ããªã³ã1ã¢ã³ãã¬ã€
1ã»ã«ã²ã€ã®å°å·
ããªã³ã2ã¢ã¬ãã¯ã¹
ãããã«
ããã£ã
ããã£ã
äžåæ Œ
ã¢ã¬ãã¯ã¹ã»ã¢ã³ãã¬ã€
12:00 30ã¢ã¬ãã¯ã¹ã»ã«ã²ã€
12:30 30ã¢ã³ãã¬ã€ã»ã¢ã¬ãã¯ã¹
12:30 30ã¢ã³ãã¬ã€ã»ã¢ã¬ãã¯ã¹
12:00 30ã¢ã¬ãã¯ã¹ã»ã«ã²ã€
ãã®åé¡ã®è§£æ±ºçãèããã®ã«å€ãã®æéãè²»ãããå€ãã®ãªãã·ã§ã³ãè©ŠããŸããããæé+æ¥+人ã®æ°ãæãå¹æçã«è©°ã蟌ãæ¹æ³ã決ããŸããã§ããã æ§é äœãæžãããã£ã{int day; int time_ms; string people [];}ããããããã¯ã¡ã¢ãªäœ¿çšéãéå¹ççã§ãã
å¥ã®ãªãã·ã§ã³ã¯ããã¹ãŠã®ææ¥ãšæéãç·åœ¢ã«è¡šãã3ã€ã®å€æ°ãä¿åããæ§é ïŒäŒè°ïŒãäœæããããšã§ã-äŒè°ã®éå§ïŒæ¥* 24 * 60ïŒïŒæé* 60 +åïŒãäŒè°ã®çµäºïŒéå§+æéïŒããã®äŒè°ã®äººã
ã®ååã ãã®æ§é ã®ãã¹ãŠã®ãªããžã§ã¯ãã¯ããã¯ãã«ïŒvecïŒã«ããã±ãŒãžåã§ããŸãã 次ã«ãæ°ããã¢ãã€ã³ãã¡ã³ããäœæãããšãã«ã次ã®ã¹ããŒãã¡ã³ããåœãŠã¯ãŸããã¯ãã«ã«ååšããäŒè°ã«äŒè°ããããã©ããã確èªããŸãã
vec[i] -> start<= meeting->start && vec[i] -> end >= meeting->start or vec[i] -> start <= meeting->end && vec[i] -> end >= meeting->end
ãã¯ããã®å Žåããã®æéãããã£ãŠãããšèšããããã§ãªãå Žåã¯ããã¯ãã«ã«æ°ããèŠçŽ ãè¿œå ããŸãã
ãŸããPythonã®dictã䜿çšããŠãã®åé¡ã解決ããããšããŸããããä»ã®ã¿ã¹ã¯ã«å€ãã®æéãè²»ãããããšã«æ°ä»ããŸããã 6æéã®çµããã®10ååã«æåéããã®ã¿ã¹ã¯ã«æ»ããŸãããã»ãšãã©èããåããªãã£ãã®ã§ãæéããããšæžããŠãå°ãªããšãäœããæž¡ããŸããã ããããããã®åé¡ã®2çªç®ã®è§£æ±ºçã ããå®æãããããOnlineJudgeã¯åãå
¥ããã§ãããã ããããç§ã¯æ¬¡ã®Javaã³ãŒããæž¡ããŸããã å®å
šã«ã¹ãããã§ããŸãããå®éã«ã¯äœãããŸããã
解決ç import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p2 { public static void main(String[] args) throws IOException { String line; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk; long unixTime = System.currentTimeMillis() / 1000L; System.out.println(unixTime); int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; ++i) { line = br.readLine(); tk = new StringTokenizer(line, " :"); String cmd = tk.nextToken(); if (cmd.compareTo("APPOINT") == 0) { int day = Integer.parseInt(tk.nextToken()); int hour = Integer.parseInt(tk.nextToken()); int minute = Integer.parseInt(tk.nextToken()); int duration = Integer.parseInt(tk.nextToken()); int peopleN = Integer.parseInt(tk.nextToken()); String people[] = new String[peopleN]; for (int j = 0; j < peopleN; ++j) { people[j] = tk.nextToken(); } int start = (hour * 60) + minute; int end = start + duration; } } } }
ã¿ã¹ã¯3.èªåè£å®
è·åæ¡ä»¶Arkadyã¯ã€ã³ã¿ã©ã¯ãã£ããªãªãŒãã³ã³ããªãŒãã·ã¹ãã ãå®è£
ããŸãããããã«ãããåæ¥èšŒæžãå«ã倧åŠã®äœåã®ããã¹ãããã°ããå
¥åã§ããããã«ãªããŸãã
ã·ã¹ãã ã¯ããã§ã«ããã¹ãã«ãããã¹ãŠã®åèªãèšæ¶ããŸãã Arkadyãå¥ã®åèªãå
¥åãããã®ç©ºã§ãªãéšåããã§ã«å
¥åãããåèªã®æ£ç¢ºã«1ã€ã®ãã¬ãã£ãã¯ã¹ãšäžèŽããå Žåãç¹å¥ãªããŒã®çµã¿åãããæŒããšãå
¥åãããéšåã«æ¢åã®åèªãããã«è¿œå ãããŸãã
ããšãã°ãArkadyã¯ãã§ã«ããŸããŸãªã·ã¹ãã ã§è«æãšèªåè£å®ãšããèšèãå
¥åããŠããŸãã 圌ãå
¥åããå¿
èŠããã次ã®åèªã®ããã€ãã®ãªãã·ã§ã³ãæ€èšããŠãã ããã
- åæ¥èšŒæž-æåã®æåãå
¥åãããšãã·ã¹ãã ã¯åæ¥èšŒæžã®ä¿®äºãåãå
¥ããŸãããé©åããŸããã
- ä»äº-æåãš2çªç®ã®æåãå
¥åããåŸãã·ã¹ãã ã¯äœãæäŸããŸããã ããã¹ãã«ã¯çŸåšã®ãã¬ãã£ãã¯ã¹ã§å§ãŸã2ã€ã®ç°ãªãåèªããããŸããã3çªç®ã®æåãå
¥åããåŸã¯1ã€ã®åèªã®ã¿ãæ®ããŸãïŒææ¡ããããªãŒãã³ã³ããªãŒããåãå
¥ããå¿
èŠããããŸãïŒã
- éã-ãªãŒãã³ã³ããªãŒãã䜿çšãããªãã·ã§ã³ã¯ã3çªç®ã®æåãå
¥åããåŸã«ã®ã¿è¡šç€ºãããŸãããä»åã¯ææ¡ããããªãã·ã§ã³ã¯åãå
¥ããããŸããã
Arkadyã«ã¯ãå
¥åããæåã®åé€ããŒããªããããããã¹ãããæåãåé€ã§ããŸããã
Arkadyã¯ãææ¡ãããåèªããã€ã€ã«ã®å§ãŸãã§ããå ŽåããªãŒãã³ã³ããªãŒãã䜿çšããªãããšã決å®ããŸããããå®å
šã«ã¯äžèŽããŸããã
Arkadyãã¢ã«ãã¡ãããæåã«å¯Ÿå¿ããããŒããŒãããŒã®ããŒã¹ãããŒã¯æ°ãæå°éã«æãããå ŽåããªãŒãã³ã³ããªãŒãæ©èœã䜿çšããåæ°ã決å®ããã®ã«åœ¹ç«ã¡ãŸãã
å
¥å圢åŒå
¥åã®æåã®è¡ã«ã¯ã1ã€ã®æŽæ°nïŒ1â€nâ€100 000ïŒ-Arkadyãå
¥åããåèªã®æ°ãå«ãŸããŸãã 2è¡ç®ã«ã¯ãnåã®åèªsiïŒ1â€| si |â€1000ïŒãå«ãŸããŸãã æååå
ã®ãã¹ãŠã®åèªã¯å°æåã®è±åã®ã¿ã§æ§æãããåäžã®ã¹ããŒã¹ã§åºåãããŸãã
ãã¹ãŠã®åèªã®åèšé·ã¯1,000,000æåãè¶
ããŸããã
åºå圢åŒ1è¡ã«1ã€ã®æŽæ°ïŒããŒããŒãã®æåããŒã®ããŒã¹ãããŒã¯æ°ïŒãåºåããŸãã
äŸ1å
¥ã3
ããã«ã¡ã¯ãããã«ã¡ã¯
ãããã«11
äŸ2å
¥ã5
ãããããã
ãããã«13
äŸ3å
¥ã5
aaaaa aaaab aaaaa abaaa abaaa
ãããã«22
ãã®ã¿ã¹ã¯ã¯ãããŒãããžãŒã«ç³ãèš³ãããŸããããå®éã«è¡ãããããšãå€æãããããã¯ããã«ç°¡åã«æããŸããã ãã®çµæãç§ã®æ±ºå®ã¯å®äºããŸããã§ãã-WAã¯14åç®ã®ãã¹ãã§åºãŠããŸããã ããã§ã¯ãã©ãã«ééããããã®ãââãç解ããããšããŠãå€ãã®æéãè²»ãããŸããããäœãã§ããŸããã§ããã ã»ããããŒã¿æ§é ã䜿çšããŠãã®åé¡ã解決ããã®ã¯ç°¡åã ãšæã£ãã®ã§ãC ++ã§æžãããšã«ããŸããã
解決ç #include <iostream> #include <set> using namespace std; int main() { set<string> myset; string in; int n; cin >> n; int count = 0; for(int i = 0;i<n;++i) { cin>>in; if(myset.empty()) { count += in.length(); myset.insert(in); } else if(myset.find(in) != myset.end()) { //if a word is in set //check if other words in set contain similar chars //count += the greatest common subsequence int max = 0; for(auto e: myset) { int temp = 0; //case when entered sequence is less than element in set if(e == in) { ++count; } if(e.length() > in.length()) { for(int j = 0; j< in.length(); ++j) { if(e[j] == in[j]) { ++temp; } else { break; } } if(temp > max) { max = temp; } } else if(e.length() <= in.length() && e != in) { for(int j = 0; j< e.length(); ++j) { if(e[j] == in[j]) { ++temp; } else { break; } } if(temp > max) { max = temp; } } } count += max; } else if(myset.find(in) == myset.end()) { //case when entered word is not in the set count += in.length(); myset.insert(in); } } cout << count<<endl; return 0; }
äžè¬ã«ããã®åé¡ã¯2ã€ã®å€§ããªã±ãŒã¹ã«åããããŸããæ°ããåèªãå°å
¥ãããïŒåèªãã»ããã«å«ãŸããªãïŒãšããã§ã«å
¥åãããŠããåèªãå
¥åãããïŒã»ããã«å«ãŸããåèªïŒã
2çªç®ã®ã±ãŒã¹ã¯ä»ã®ããã€ãã®ã±ãŒã¹ã«åå²ããã1ãå
¥ååèªãšåãæåïŒã·ã³ãã«ïŒã§å§ãŸãã»ããã«åèªããããã©ããã2ãåèªãµãã·ãŒã±ã³ã¹ãã»ããå
ã®ä»ã®åèªã§ãããã©ããããã§ãã¯ãããŸãã ã³ãŒãã§ãããããã«ãããããã®å Žåãcountå€æ°ã®ç°ãªãéã®ããŒã¹ãããŒã¯ãåèšãããŸãã
ã¿ã¹ã¯4.ããŒã ãã«ãã£ã³ã°
è·åæ¡ä»¶ããŒã ãã«ãã£ã³ã°ã¯æ¥œããéäŒã€ãã³ãã§ãã ååã¯ã³ã³ãã¹ããã¯ãšã¹ãã«ç©æ¥µçã«åå ããäžç·ã«ã²ãŒã ã®é£ãããå
æããŸãã æã
ã人ã
ã¯éåžžã«å€¢äžã«ãªããããã€ãã®æ°ãã掻åã®ããã«åœŒããåç·šæããããšã¯éåžžã«å°é£ã§ãã çŸåšããã¡ã·ãªããŒã¿ãŒã¯ãã¹ãŠã®ååã2ã€ã®ããŒã ã«åããŠãåãããŒã ã®2人ããäºããããç¥ã£ãŠããããã«ããå¿
èŠããããŸããããã¯ç°¡åãªäœæ¥ã§ã¯ãããŸããã
å人ã«1ã€ã®é ç¹ãé¢é£ä»ããããŠããã°ã©ãã衚瀺ãããŸãã ãšããžïŒuãvïŒã¯ãååuãååvãããç¥ã£ãŠããããšãæå³ããŸãïŒåæã«ãååvã¯ååuãããç¥ã£ãŠããŸãïŒã ã°ã©ãã®é ç¹ãå¿
èŠãªæ¹æ³ã§2ã€ã®ã»ããã«åå²ã§ãããã©ããã確èªããå¯èœã§ããã°ãé©åãªããŒãã£ã·ã§ã³ãå°å·ããŸãã
å
¥å圢åŒ
æåã®è¡ã«ã¯ã2ã€ã®æŽæ°nãšmïŒ2â€nâ€5000ã0â€mâ€200000ïŒ-ã°ã©ãã®é ç¹ã®æ°ãšãšããžã®æ°ãå«ãŸããŠããŸãã
次ã®mè¡ã¯ããšããžã®èª¬æã瀺ããŸãã1察ã®æŽæ°abïŒ1â€aãbâ€nãaâ bïŒã¯ãé ç¹aãšbã®éã«ãšããžãååšããããšã瀺ããŸãã
é ç¹ã®åãã¢ã1ã€ä»¥äžã®ãšããžã§æ¥ç¶ãããé ç¹ãããèªäœã«æ¥ç¶ãããŠããªãããšãä¿èšŒãããŸãã
åºå圢åŒ
å¿
èŠãªæ¹æ³ã§é ç¹ãåå²ã§ããªãå Žåã¯ã-1ãå°å·ããŸãã
ãã以å€ã®å Žåãæåã®è¡ã«æ°å€kïŒ1â€k <nïŒ-ããŒãã£ã·ã§ã³ã®ããããã®éšåã®é ç¹ã®æ°ãåºåããŸãã
次ã®è¡ã«kåã®æ°å-ããŒãã£ã·ã§ã³ã®ãã®éšåã®é ç¹ãå°å·ããŸãã
次ã®è¡ã§ã¯ãããŒãã£ã·ã§ã³ã®2çªç®ã®éšåã®é ç¹-n-kã®æ°åãå°å·ããŸãã
åé ç¹ã¯ããããã®ããŒãã®ãããã1ã€ã«å±ããŠããå¿
èŠããããŸãã
äŸ1
å
¥ã
3 1
1 2
ãããã«
2
1 2
3
äŸ1
å
¥ã
3 0
ãããã«
-1
ããããç§ã¯ãã§ã«ãããã¯ã«é¥ãå§ããæåã®åé¡ã解決ããåŸã«æããèªä¿¡ã¯è·¡åœ¢ããªãæ¶ããŸããã ç§ã¯ã©ã®ã¿ã¹ã¯ã«éäžãã¹ããåããããããããã®ã¿ã¹ã¯ã®ç¶æ
ãèªãããšãæ¥ãã ã ãããã¯ã«å¯ŸåŠããã®ã«çŽ20åããããŸããã ããã¯ãã³ã³ãã¹ãã®åé¡ã解決ããããã«å£æ»
çã«å€ãã®ããšã§ãã
ããã§ãç§ãã»ããã䜿çšããããšã«ããŸããã ããæ£ç¢ºã«ã¯ã3 Set'aïŒinitial-1ããnãŸã§ã®å€ãæ ŒçŽãããå Žæãã°ã©ãã®æåã®ãªã³ã¯ãè¿œå ãããteamAãteamAã«æ¥ç¶ãããŠããªããªã³ã¯ãããã³initialã®æ®ãã®ãã¹ãŠã®ãªã³ã¯ãè¿œå ãããteamBã
ç§ã®ã¢ã«ãŽãªãºã ã¯ã·ã³ãã«ã§ãããæããã«Yandexã¯ç§ã«ãã£ãšæåŸ
ããŠããŸãã 3çªç®ã®ã±ãŒã¹ã®WAã
æ±ºå® #include<iostream> #include<set> using namespace std; int main() { int people; cin >>people; int pairs; cin >> pairs; set<int> initial; set<int> teamA; set<int> teamB; int a; int b; if(pairs == 0) { cout<<"-1"<<endl; } else { //fill set with people for(int i = 1;i<=people;++i) { initial.insert(i); } for(int i = 0;i<pairs;++i) { cin >> a; cin >> b; // case when a and b aren't in teamB if(initial.find(a) != initial.end() && initial.find(a) != initial.end() && !teamA.empty()) { teamB.insert(a); teamB.insert(b); initial.erase(a); initial.erase(b); } else if(teamB.find(a) == teamB.end() && teamB.find(b) == teamB.end()) { teamA.insert(a); teamA.insert(b); initial.erase(a); initial.erase(b); } else if ((teamA.find(a) != teamA.end() && teamB.find(b) != teamB.end()) or (teamA.find(b) != teamA.end() && teamB.find(a) != teamB.end())) { for(auto e: teamB) { teamA.insert(e); teamB.erase(e); } } } } cout <<"teamA"<< endl; for( auto e: teamA) { cout << e<<" "; } cout <<endl<<"teamB"<< endl; for( auto e: teamB) { cout << e<<" "; } cout << endl; return 0; }
ã¿ã¹ã¯5.ã©ã€ãã©ãª
è·åæ¡ä»¶Kolyaã¯æ¬ãèªãã®ã倧奜ãã§ãæ¯æ¥å³æžé€šã«è¡ããŸãã å€æ¹ãŸã§ã«ã圌ã¯æšæ¥ãããæ£ç¢ºã«1å以äžæ¬ãèªãã å Žåã«ã®ã¿æºè¶³ããŠããŸãã ãã ããæ®å¿µãªãããåææ¥ãšæ¥ææ¥ã¯å³æžé€šãééãããŸãã ãã®ãããKolyaã¯æ¯æ¥ä»äºã«è¡ããäžåºŠã«kåã®æ¬ãåããŸã-ããªãã¯ãã¯ãã«ãŒã«ã«åŸãããšãã§ããŸããã ãã ããKolyaã¯ã以åã«æ®åœ±ããæžç±ããæ¬ãé
ããªãã£ãå Žåã§ããæ°ããkæ¬ãæ®åœ±ã§ããããšãå¬ããæã£ãŠããŸãã Kolyaã¯ãèªå®
ã®å³æžé€šã«mæ¬ã®æ¬ãããããšãåãã§ããŸãã
ä»æ¥ã¯äœææ¥ãããããŸãã Kolyaã¯æè¿èµ·ããŠãä»æ¥ã¡ããã©1åã®æ¬ãèªãããã«ãªããŸããã Kolyaã¯ãä»æ¥ããå¯èœãªéãæ¯åå³æžé€šã«è¡ãå Žåãã©ããããæºè¶³ã§ããŸããïŒ å³æžé€šã§ã®æ¬ã®äŸçµŠã¯ç¡éã§ãããšæ³å®ã§ããŸãã
å
¥å圢åŒ
å
¥åãã¡ã€ã«ã®æåã®è¡ã«ã¯3ã€ã®æŽæ°kãmãdãå«ãŸããŠããŸãã1æ¥ãããã®å³æžé€šã§æã¡èŸŒããæ¬ã®æ°ã®å¶éãKolyaã®å®¶ã®æ¬ã®æ°ãçŸåšã®ææ¥ïŒ1â€kâ€109ã0â€mâ€109ã 1â€dâ€7ïŒã åææ¥ãšæ¥ææ¥ã¯ãæ°å6ãš7ã§ç€ºãããŸãã
åºå圢åŒ
1ã€ã®æ°åãå°å·ããŸã-Kolyaãæ¯æ¥éåžžã«å€ãã®æ¬ãèªãã§æºè¶³ãç¶æã§ããæéã®æ倧æ¥æ°ã
äŸ1
å
¥ã
4 2 5
ãããã«
4
äŸ2
å
¥ã
4 3 5
ãããã«
5
ãã®åé¡ã解決ããŠãã©ãã ãèŠéããŠãããã«æ°ã¥ããŸãã
uDebug ã ç§ã®æ±ºå®ã¯10åç®ã®ãã¹ãã§WAãæããŸããã
解決ç #include<iostream> using namespace std; int main() { int bks; cin >> bks; int lib; cin >> lib; int day; cin >> day; int total = bks + lib; int count = 0; int read = 0; while(true) { ++count; ++read; if(day>=1 && day <= 5) { total -= read; if(total == 0) { break; } else { total += bks; } } else if(day == 6) { total -= read; if(total == 0) { break; } } else if(day == 7) { total -= read; if(total == 0) { break; } day = 0; } ++day; } cout << count; return 0; }
ã¿ã¹ã¯6.åå¡
ç§ã¯åºæ¬çã«ã³ã³ãã¹ãäžã«ãã®ã¿ã¹ã¯ãåããŸããã§ããã èªã¿åããšåºåå°çšã®ã³ãŒããæžããŸããã ã³ã³ãã¹ããå®äºããåŸããã以å€ã®ãã¹ãŠã®ã¿ã¹ã¯ãæŽçããŸããã æ£çŽãªãšãããç§ã¯ãŸã äœãããå¿
èŠãããããæ£ç¢ºã«ç解ã§ããŸããã ç§ã¯ããªãã®ã³ã¡ã³ãã«åãã§ããã§ãããã
è·åæ¡ä»¶ãããžã§ã¯ã "Mobilization"ãYandexã§åã³éå§ãããŸãïŒ å瀟ã¯ã3ãæéã®ãã¬ãŒãã³ã°ã®ããã«ãã¢ãã€ã«éçºã«ç±å¿ãªn人ã®è¥è
ãæ¡çšããŠããŸãã ãããžã§ã¯ãã®éå§æã«ãéçºã®åå è
iã®ã¹ãã«ãaiã管çã®ã¹ãã«ãbiãšããŠè©äŸ¡ããããã¹ããå®æœãããŸããã
ãããžã§ã¯ãã®æéäžãåå è
ã¯ãéçºè
ãšãããŒãžã£ãŒãšããåå è
ã®æ°ã«çãã2ã€ã®ããŒã ã«åå²ããå¿
èŠããããŸãã ãã¹ãŠã®åå è
ãããããç·å©çãæ倧åãããããªæ¹æ³ã§ãããè¡ãããšãèšç»ãããŠããŸãã åå è
ãéçºè
ã®åœ¹å²ãååŸããå Žåã圌ã®å©çã¯aiãããã§ãªãå Žåã¯biã«ãªããŸãã
ãããããããžã§ã¯ãã«é¢ä¿ãã人ã
ã§ãããåå è
ã¯æ°ããç¥èãåŸãæéãèŠã€ããŸãïŒ åå è
ãä¿®äºèšŒãæåºããå ŽåããããŸããéçºãŸãã¯ç®¡çã®åå è
iã®ã¹ãã«ãdiå¢å ãããšèšãããŠããŸãã ãã®ãããªå ŽåãããŒã å
šäœãæ倧éã«æŽ»çšããããã«ããŒã ãæ¹é©ããããšãæå©ãªå ŽåããããŸãïŒããŒã ã®ãµã€ãºãçããç¶æããå¿
èŠããããŸãïŒã
ããªãã®ä»äºã¯ãYandexãæ¯æŽããããšã§ãããåå è
ã«ãã£ãŠããããããããããã®æ°ãã蚌ææžãæ€èšããåŸãããŒã ã®çŸåšã®ç·å©çãèšç®ããŸãã
å
¥å圢åŒ
å
¥åãã¡ã€ã«ã®æåã®è¡ã«ã¯ãçªå·nïŒ2â€nâ€2â
105ãnã¯å¶æ°ïŒ-ãããžã§ã¯ãåå è
ã®æ°ãå«ãŸããŠããŸãã 2è¡ç®ã¯ãnåã®æŽæ°aiïŒ0â€aiâ€109ïŒãå®çŸ©ããŸã-éçºã®ååå è
ã®ã¹ãã«ã åã圢åŒã®æ¬¡ã®è¡ã¯ãbiã³ã³ãããŒã«ã®åå è
ã®ã¹ãã«ãèšå®ããŸãïŒ0â€biâ€109ïŒã
次ã®è¡ã«ã¯ãæŽæ°mïŒ1â€mâ€105ïŒ-åå è
ã«ãã£ãŠãããããã蚌ææžã®æ°ãå«ãŸããŠããŸãã 次ã®mè¡ã®ããããã«ã¯ã3ã€ã®æŽæ°numiãtypeiãdiïŒ1â€numiâ€nã1â€typeiâ€2ã1â€diâ€104ïŒãå«ãŸããŠããŸã-åå è
ã®æ°ãã¹ãã«ã®çš®é¡ïŒ1-éçºã2-管çïŒããã³å¯Ÿå¿ããã¹ãã«ã®å¢å ã®å€ã
åºå圢åŒ
æ°ãã蚌ææžã®åèŠæ±ãåŠçããåŸããã¹ãŠã®åå è
ã®çŸåšã®ç·å©çãå°å·ããŸãã
äŸ1
å
¥ã
4
7 15 3 4
10 10 0 6
3
1 1 4
4 1 6
2 2 10
ãããã«
34
35
43
ç§ããªããšãæžããã³ãŒã import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p6 { public static void main(String[] args)throws IOException { String line; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk; int n = Integer.parseInt(br.readLine()); int a[] = new int[n]; int b[] = new int[n]; tk = new StringTokenizer(br.readLine()); int aSum = 0; for(int i = 0;i<n;++i) { a[i] = Integer.parseInt(tk.nextToken()); aSum += a[i]; } int bSum = 0; for(int i = 0;i<n;++i) { b[i] = Integer.parseInt(tk.nextToken()); bSum += b[i]; } } }
ãŸãšã
å
šäœãšããŠãç§ã¯ãã®çµéšã奜ãã§ããã æåãå°œãããªãã£ãã®ã¯å°ãæ®å¿µã§ãã ããããä»ã§ã¯ãYandexã§ã®ã€ã³ã¿ãŒã³ã·ããã®ã¿ã¹ã¯ãã©ã®ãããªãã®ã§ããããããããŸããããã®èšäºãèªãã åŸãããªããç¥ã£ãŠããŸãã ãã®èšäºãããããããŠãå°ãªããšãå°ãã¯ã圹ã«ç«ãŠã°å¹žãã§ãã ç§ã¯ã³ã¡ã³ããææ¡ãå¿ããåãã§ããŸãã ãã®èšäºãæžããŠããéãç§ã¯ããªãããããã®åé¡ã解決ããããã®ãªãã·ã§ã³ãå
±æããããšãæåŸ
ããŸããã
ã¿ããªããããšãïŒ