0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

AtCoder Problems Training Easy(11~20)

Last updated at Posted at 2020-08-24

#目次

1~10
11~20 ← 今ココ
21~30
31~40
41~50
51~60
61~70
71~80
81~90
91~100

#11. ABC068 B - Break Number

Difficulty:77

$\ 2\ $で割れる回数を最大にしようとする場合、$\ 2 \times 2 \times \dots \ $ となるので、答えは全て$\ 2^i\ $になる。
あとは$\ N\ $以下の条件を満たす$\ 2^i\ $を探す。

n = int(input())
ans = 1
while True:
    ans *= 2
    if ans > n:
        ans = ans // 2
        break
print(ans)

#12. ABC160 C - Traveling Salesman around Lake

Difficulty:126

例2 のように反時計回りに訪ねた方が最短になる場合を考える。
家の位置を$\ 0,5,15\ $ではなく、$\ 20,25,15\ $と考えれば求めやすくなる。
このことから$\ A_1 + K,A_2 + K \dots A_{N-1} + K\ $を$\ A\ $に追加しておく。
その後、家の移動にかかる距離を$\ A_{i+n-1}-A_i\ $で求める。
例2 では、最終的にリスト$\ A\ $は$\ 0,5,15,20,25\ $になっている。

k,n = map(int,input().split())
a = list(map(int,input().split()))
ans = 10 ** 8
for i in range(n-1):
    a.append(a[i]+k)
for i in range(n):
    ans = min(ans,a[i+n-1] - a[i])
print(ans)

#13. AGC014 A - Cookie Exchanges

Difficulty:178

例2 のように、もし全員の持っているクッキーの数が同じだった場合、偶数枚なら全員が$\ (A+B)/2=C\ $、つまり$\ (14+14)/2=14\ $となり、何度交換しても枚数が変わらないので$\ -1\ $になる。
そうでないなら、誰かの枚数が奇数になるまでに何回交換できるか実際に交換を行い続ける。
ただし、元から誰かの枚数が奇数ならそもそも交換できないので$\ 0\ $になる。

a,b,c = map(int,input().split())
if a == b == c:
    if a % 2 == 0:
        print(-1)
        exit(0)
    else:
        print(0)
        exit(0)
ans = 0
while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
    al = b // 2 + c // 2
    bl = a // 2 + c // 2
    cl = a // 2 + b // 2
    a = al
    b = bl
    c = cl
    ans += 1
print(ans)

#14. ABC161 C - Replacing Integer

Difficulty:123

$\ |N-K|\ $を繰り返していると、$\ 0 \le N \le 10^{18}、1 \le K \le 10^{18}\ $の制約で TLE になるので、法則を探す必要がある。
$\ N=7,K=5\ $ の場合、
$\ |7-5|=2,|2-5|=3,|3-5|=2\ $となるため、$\ N \mod K\ $が答えになる。
$\ N=7,K=4\ $の場合、
$\ |7-4|=3,|3-4|=1,|1-4|=3\ $となるため、$\ K-(N \mod K)\ $になる。
この 2 つのうち、答えが小さい方を出力する。

n,k = map(int,input().split())
print(min(n % k,k - n % k))

#15. ABC132 C - Divide the Problems

Difficulty:90

問題数を同じになるように分類するには$\ N/2\ $ずつに分ける必要がある。
難易度もバラバラなので$\ d\ $をソートし、$\ d_1 \dots d_{N/2}\ $が ABC 、$\ d_{N/2+1} ... d_N\ $を ARC として考える。
上の条件を守りつつ難易度$\ K\ $を決めようとすると、考えられる$\ K\ $の範囲は$\ \max($ ABC $)<K \le \min($ ARC $)\ $になる。

n = int(input())
d = list(map(int,input().split()))
d.sort()
a = n // 2
b = a - 1
print(d[a] - d[b])

#16. ABC142 C - Go to School

Difficulty:86

例1 から$\ A\ $が$\ 2,3,1\ $なら$\ 1\ $の生徒は$\ 2\ $番目、$\ 2\ $の生徒は$\ 3\ $番目、$\ 3\ $の生徒は$\ 1\ $番目となる。
別のリスト$\ L\ $を用意して、$\ L_{A_i}\ $に$\ i\ $を代入すれば、最終的に生徒が登校した順に$\ L\ $に格納されている。

n = int(input())
a = list(map(int,input().split()))
ans = ['0'] * n
for i in range(n):
    ans[a[i]-1] = str(i+1)
print(' '.join(ans))

#17. ABC138 C - Alchemist

Difficulty:86

例2 から具材を昇順に入れれば最大になると予想できる。
試しに$\ 3,1,4,1,5,9,2\ $の食材が与えられたとき、昇順に順番に入れると$\ 6.53125\ $になり、これが最大値である。
一方、降順に順番に入れると$\ 1.53125\ $ととても低くなる。

n = int(input())
v = list(map(int,input().split()))
v.sort()
ans = v[0]
for i in range(1,n):
    ans = (ans + v[i]) / 2
print(ans)

#18. ABC122 B - ATCoder

Difficulty:85

前から$\ S_i\ $が ACGT か調べていく。
ACGT ではない場合、そこまでの ACGT 文字列の長さを今までの長さの最大値と比較しておく。

s = input()
acgt = ['A','C','G','T']
ans = 0
p = 0
for i in range(len(s)):
    if s[i] in acgt:
        p += 1
    else:
        ans = max(ans,p)
        p = 0
print(max(ans,p))

#19. ABC094 B - Toll Gates

Difficulty:87

ゴール$\ 0\ $か$\ N\ $に移動するためのコストを最小にするには、通過する料金所の数が少なければよい。
$\ 0 \le X\ $の間と、$\ X \le N\ $の間にある料金所の数をそれぞれ調べ、数が少ない方に移動し続ければコストが最小になる。

n,m,x = map(int,input().split())
a = list(map(int,input().split()))
le = m
for i in range(m):
    if a[i] > x:
        le = i
        break
ri = m - le
print(min(le,ri))

#20. ABC116 B - Collatz Problem

Difficulty:92

$\ s\ $を問題文通りに計算し、その都度計算した$\ s\ $をリストに追加しておく。
その後、そのリストに同じ数字が存在するか確認し、存在する場合はそのリストの長さが答えになる。
これは 例1 で$\ 4\ $が 5 回目に、 例2 で$\ 4\ $が 18 回目に今までに出た数字がもう一度出たタイミングであり、答えにもなっているからである。

s = int(input())
t = []
t.append(s)
while True:
    if s % 2 == 0:
        s = s // 2
    else:
        s = s * 3 + 1
    t.append(s)
    if t.count(s) == 2:
        print(len(t))
        break
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?