This is a review article for beginners of competition professionals. Click here for the contests you participated in. https://atcoder.jp/contests/panasonic2020
The code I write here is written while looking at other people's answers and explanations. It was not actually submitted.
A - Kth Term The problem is to output the nth term of the input given from a predetermined sequence.
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
i = int(input())
print(li[i-1])
Note that the item numbers are counted from 1.
B - Bishop $ H \ times W $ It is a question to answer the range where the corner can move on the board of the square.
Note that the corner cannot move even one step when there is only one horizontal or vertical size (one loss).
The code I submitted looks like this.
import math
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
w_odd = math.ceil(H/2)
w_even = H // 2
N_odd = math.ceil(W/2)
N_even = W // 2
print(w_odd * N_odd + w_even * N_even)
The number of squares that can be moved differs between the even-numbered and odd-numbered squares counting from the left. The number of cells in these two cases and the number of columns corresponding to each were calculated separately.
You can actually write it more concisely.
Simply half of all the squares are movable. If you divide by 2 and there is a remainder, the lower right cell that is the remainder is always in the (odd, odd) position. Since it is a movable position, it will increase by one more square.
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
print((H * W + 1) // 2)
Also, there is no need to import math into the round-up process.
C - Sqrt Inequality For input A B C
The problem of determining if.
I submitted the following, thinking that it would be useless.
a, b, c = map(int, input().split())
if a**0.5 + b**0.5 < c**0.5:
print("Yes")
else:
print("No")
It was bad. You can't even use math.
Let's square both sides of equation (1).
I saw the commentary. (2) is further transformed.
When both sides are positive, square both sides
So the answer. This should have been noticed as it shouldn't be difficult.
a, b, c = map(int, input().split())
if 0 < c - a - b and 4 * a * b < (c - a - b)**2:
print("Yes")
else:
print("No")
D - String Equivalence
The problem is to arrange all the character string patterns that exist with the number of characters N (≤10).
I didn't know how to do it, so I tried to solve it by arranging all the patterns once and then erasing them. Actually, I was stuck in the middle of writing and could not submit it, but I wrote the following code.
import itertools
N = int(input())
alp = [chr(ord('a') + i) for i in range(N)]
allS = list(itertools.product(alp, repeat=N))
answers = []
PatternList = []
for s in allS:
pattern = []
letters = []
for l in s:
if not l in letters:
letters.append(l)
pattern.append(letters.index(l))
if not pattern in PatternList:
PatternList.append(pattern)
answers.append(s)
for answer in answers:
print(''.join(answer))
I thought it would be possible to reach N = 10, but TLE came out in the second half.
I saw the commentary. The standard form condition is replaced with the following formula.
It seems that you should search with DFS so as to satisfy these two conditions. The maximum value information is stored in the variable mx that holds the maximum value information, and it is passed by a recursive function.
The following is made according to the sample.
n = int(input())
def dfs(s, mx):
if len(s) == n:
print(s)
else:
for i in range(0, mx + 1):
c = chr(ord('a') + i)
if i == mx: dfs(s+c, mx+1)
else: dfs(s+c, mx)
dfs('', 0)
E - Three Substrings Given the three substrings a, b, and c taken from the string s, this is the problem of guessing the original string s.
I prepared an empty array with the length of a + b + c as the character string s, and started writing with the policy of applying the three of a, b, and c from one end, but there are some elements that get stuck. I gave up because I saw TLE coming out.
I saw the commentary. Get the "relative positions" that can exist for each of a and b, b and c, and a and c as an array. Store this as ab [] `` `, ac [] , `` `bc [] . From there, if the positional relationship between a and b is represented by i and the positional relationship between a and c is represented by `` j```, the positional relationship between b and c is obtained by `ji```. I can do it.
This turns i and `j```, and ```ab [i] and ```ac [j] ```, `` bc [ji] ] `` `It can be obtained by calculating the number of characters when the three conditions are met. Note that a, b and c can be up to $ \ pm 4000 $ respectively.
I just rewrote most of the explanation to Python, but the following code passed. Even with Pypy3, this algorithm is very quick, and the time is just 1991 ms. For example, just put `True``` and False``` in ```ab [] `` instead of 1 and 0 to get a TLE. There seems to be a faster method (I haven't seen it yet), as some people are getting a few times faster calculation time and some are doing this in Python.
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000
for i in range(A):
if a[i] == '?':
continue
for j in range(B):
if b[j] != '?' and a[i] != b[j]:
ab[i-j+8000]= 0
for i in range(B):
if b[i] == '?':
continue
for j in range(C):
if c[j] != '?' and b[i] != c[j]:
bc[i-j+8000]= 0
for i in range(A):
if a[i] == '?':
continue
for j in range(C):
if c[j] != '?' and a[i] != c[j]:
ac[i-j+8000]= 0
ans = 6000
for i in range(-4000, 4000):
for j in range(-4000, 4000):
if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
L = min(0, min(i, j))
R = max(A, max(B+i, C+j))
ans = min(ans, R-L)
print(ans)
That's all for this article. If possible, I would like to add question F later.
Recommended Posts