TopCoder SRM 428 Div 1

어제 9시에 열린 매치.. 이번 매치에서는 문제가 너무 구리게 나온 덕분에(?) 역대 최고의 성적을 올렸다.. -_-;; 250점은 너무 쉬운 문제가 나왔고.. 500, 1000은 상당히 어려웠다.. 덕분에 많은 고랩들이 250점짜리만 풀고 줄줄이 삽질하는 바람에.. 별볼일없는 내가 그냥 평소대로 했더니 높은 등수가 되었다.. -_-;; 하긴 이런 이상한 매치도 가끔 있어야 나도 먹고살지..;;

덕분에 rating이 무려 176점이나 올랐다.. 3연속 상승인데.. 이제 좀 떨어질때가 됐군.. ㅋㅋ 볼라도 무려 500가까이 되고.. 아무래도 다음 매치에서는 몸사려야할듯..?

Level1 - TheLuckyString

Problem Statement
     
John and Brus are studying string theory at the university. According to Brus, a string is called lucky if no two consecutive characters are equal. John is analyzing a string s, and he wants to know how many distinct lucky strings can be generated by reordering the letters in s. If s is a lucky string in its original ordering, it should also be considered in the count.
Definition
   
Class:
TheLuckyString
Method:
count
Parameters:
string
Returns:
int
Method signature:
int count(string s)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 10 characters, inclusive.
-
Each character of s will be a lowercase letter ('a' - 'z').
Examples
0)
 
   
"ab"
Returns: 2
Two lucky strings - "ab" and "ba".
1)
 
   
"aaab"
Returns: 0
It's impossible to construct a lucky string.
2)
 
   
"aabbbaa"
Returns: 1
"abababa" is the only lucky string that can be generated.
3)
 
   
"abcdefghij"
Returns: 3628800
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

어떤 단어가 모든 이웃하는 문자가 모두 같지 않으면 lucky 하다고 할때, 주어진 문자들로 만들 수 있는 lucky한 단어의 개수 세기..

letter의 개수가 최대 10이기때문에 그냥 next_permutation으로 다 돌렸다..

나름 문제도 빨리 이해하고 잽싸게 코딩해서 245점에 서밋했는데도 방에서 5등.. -_-;;
문제가 아무리 쉽다고는 하지만.. 도대체 249점을 맞는 사람은 뭐지..;;
c++ string 사용법을 몰라서 항상 char 배열로 바꾼다음에 코딩하는데..
이거랑 sorting에서 시간을 좀 낭비한 것 같다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int comp(const void* x, const void* y)
  9 {
 10     char* a = (char*)x;
 11     char* b = (char*)y;
 12     return *a - *b;
 13 }
 14
 15 class TheLuckyString {
 16 public:
 17
 18 int count(string s)
 19 {
 20     int len, cnt, i;
 21     char buf[100];
 22     strcpy(buf, s.c_str());
 23     len = strlen(buf);
 24     qsort(buf, len, sizeof(char), comp);
 25     cnt = 0;
 26     do {
 27         for (i = 1; i < len ;i++) {
 28             if (buf[i-1] == buf[i])
 29                 break;
 30         }
 31         if (i == len)
 32             cnt++;
 33     } while (next_permutation(buf, buf+len));
 34     return cnt;
 35 }
 36
 37 };

Level2 - TheLongPalindrome

Problem Statement
     
John and Brus are studying string theory at the university. Their task is to create a list of all the palindromes that contain between 1 and n lowercase letters ('a'-'z'), inclusive. A palindrome is a string that reads the same forward and backward. Additionally, each palindrome in their list must contain no more than k distinct letters. Return the number of palindromes in the list modulo 1234567891.
Definition
   
Class:
TheLongPalindrome
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)
   
 
Constraints
-
n will be between 1 and 1,000,000,000, inclusive.
-
k will be between 1 and 26, inclusive.
Examples
0)
 
     
1
1
Returns: 26
All palindromes in the list are single character strings.
1)
 
   
2
10
Returns: 52
Now we have single and double character palindromes.
2)
 
   
3
2
Returns: 728
A slightly longer list.
3)
 
   
44
7
Returns: 240249781
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

n과 k가 주어질 때, 길이 n 이하의 문자열 중에 k개 이하의 문자만 사용하여 만들 수 있는 palindrome의 개수 구하기..


to be updated..



Level3 - TheStringGame

Problem Statement
     
John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.
Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.
You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity).
Definition
   
Class:
TheStringGame
Method:
winner
Parameters:
string
Returns:
string
Method signature:
string winner(string s)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 16 characters, inclusive.
-
Each character of s will be 'X', 'O' or 'L'.
-
s will not contain "LOL" as a substring.
Examples
0)
 
   
"XXOXXXLXLX"
Returns: "John 1"
John can win by changing the 'X' between the two 'L's into a 'O'.
1)
 
   
"LXXLXXL"
Returns: "Brus 2"
Brus can win this game after John's first move, regardless of what John does.
2)
 
   
"LLOOLLOOLLOOLLOO"
Returns: "Draw"
No moves available.
3)
 
   
"XXXXXXXXXXXXXXXX"
Returns: "Brus 16"
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

to be updated..