AtCoder Beginner Contest 165 Participation Report

AtCoder Beginner Contest 165 Participation Report

Suddenly I was surprised to be 10 minutes late. I feel lucky that I solved the C and D problems. Well, it's good sometimes because I often get confused if I miss the solved problem.

ABC165A - We Love Golf

Break through in two and a half minutes. A chicken that spins a loop while thinking that it can be written with * O * (1).

K = int(input())
A, B = map(int, input().split())

for i in range(A, B + 1):
    if i % K == 0:
        print('OK')
        exit()
print('NG')

Postscript: I also wrote in * O * (1).

K = int(input())
A, B = map(int, input().split())

if (B // K) * K >= A:
    print('OK')
else:
    print('NG')

ABC165B - 1%

Break through in 4 minutes. When I saw X ≤ 10 18 </ sup>, I thought that TLE was possible even though it was a B problem, but even if I gave 10 18 </ sup> in the code test, it wasn't at all. I was fine, so I was wondering what it was, AC.

X = int(input())

t = 100
result = 0
while t >= X:
    t += t // 100
    result += 1
print(result)

ABC165C - Many Requirements

It broke through in 23 and a half minutes. The moment I saw the problem, my head turned white, but I managed to solve it. The moment I AC, I thought that the current ranking was amazing, but everyone solved the D problem first and even so far I didn't (laughs).

Well, I wondered if I should do a brute force attack, but if I generate it including invalid ones, it seems that * O * (10 10 </ sup>) will not work. Pay attention to 1 ≤ M ≤ 10. , M -1 is 0-9, so it can be expressed as a character string, so I decided to generate all the valid sets of character strings. After that, I thought that I would do brute force. TLE, but without AC ..

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

m = M - 1


def f(s):
    if len(s) == N:
        return [s]
    result = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, m + 1):
        result.extend(f(s + str(i)))
    return result


result = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            t += d
    result = max(result, t)
print(result)

Postscript: It seems that I didn't have to do my best to generate all the sets by myself. Python is great.

from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

result = 0
for A in combinations_with_replacement(range(1, M + 1), N):
    t = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            t += d
    result = max(result, t)
print(result)

ABC165D - Floor Function

Break through in 20 minutes. I thought that there should be a maximum value at the timing when Ax / B increases, so when I solve the equation of Ax / B = n, x = Bn / A, so x is incremented by 1 by N. I tried turning it until it became. However, since this is the case when A <B, I tried turning it to A for that case. When I put it out with a messy combination, AC came and I was surprised myself. I didn't understand much, but I solved it ...

The moment I solved the D problem, I had a dream of blue performance because I was in the 900s, but I'm sorry that I couldn't solve the E problem and retreated to the 1500th place.

from math import floor

A, B, N = map(int, input().split())


def f(x):
    return floor(A * x / B) - A * floor(x / B)


result = 0
for x in range(min(A + 1, N + 1)):
    result = max(result, f(x))

if B > A:
    for i in range(10 ** 20):
        x = (i * B + A - 1) // A
        if x > N:
            break
        result = max(result, f(x))

print(result)

Postscript: I used to go through well (sweat). However, the difficulty levels of D and C problems are completely switched.

A, B, N = map(int, input().split())

x = min(B - 1, N)
print(A * x // B - A * (x // B))

ABC165E - Rotation Matching

Lost. I knew that I should set the distance to 1, 2, ..., M, but I couldn't figure out how to pack the combinations that satisfy it between M.

Addendum: The condition is that the difference between a and b is different, but since it is circular, it may be the same even if the difference is different (for example, (1, 4) when N = 4). (2, 3) seems to be different by 3 difference and 1 difference, but since 4 is next to 1, both are 1 difference). In conclusion, if the distance is 1, 2, ..., M Good. In this case, it is unique even if it circulates from the condition of M × 2 + 1 ≤ N. Next, how to take the combination, first take the longest 1 and M + 1. Of course, inside it Since the one with the distance M-1 does not enter, take it with M + 2 and 2M + 1 next to it. Next, since it is the distance M-2, it enters between 1 and M + 1, so take it with 2 and M. Next is the distance M-3, so I think it's okay to take it at M + 3 and 2M, so divide it into two parts and pack them inside like a Matryoshka doll.

N, M = map(int, input().split())

for i in range(1, M + 1):
    if i % 2 == 1:
        j = (i - 1) // 2
        print(1 + j, M + 1 - j)
    else:
        j = (i - 2) // 2
        print(M + 2 + j, 2 * M + 1 - j)

Recommended Posts

AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Grand Contest 041 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Regular Contest 104 Participation Report
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Library Practice Contest Participation Report (Python)