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(71~80)

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

#71. ABC042 B - 文字列大好きいろはちゃんイージー

Difficulty:209

$\ N\ $個の文字列をソートしてから、全て結合する。

n,l = map(int,input().split())
s = list(input() for i in range(n))
s = sorted(s)
print(''.join(s))

#72. ABC097 B - Exponential

Difficulty:210

$\ b^p\ $を順番に試し、最大のべき乗を調べる。

x = int(input())
ans = 0
for i in range(1,1000):
    for j in range(2,1000):
        if i ** j <= x:
            ans = max(ans,i ** j)
        else:
            break
print(ans)

#73. AGC021 A - Digit Sum 2

Difficulty:346

$\ len(N)=1\ $の場合、$\ N\ $をそのまま出力するしかない。
それ以外の場合、上一桁を除いた桁が全て 9 なら各桁の和、違うなら上一桁を$\ -1\ $し、$\ (len(N)-1) \times 9\ $を足した合計になる。
例えば$\ 5000\ $なら$\ 4999\ $、$\ 4999\ $なら$\ 4999\ $、$\ 4998\ $なら$\ 3999\ $、例3の$\ 31415926 \dots\ $なら$\ 29999999 \dots\ $となる。

n = list(input())
n = [int(i) for i in (n)]
m = len(n)
if m == 1:
    print(n[0])
else:
    flg = False
    for i in range(1,m):
        if n[i] != 9:
            flg = True
            break
    if flg:
        print(n[0] - 1 + 9 * (m - 1))
    else:
        print(sum(n))

#74. ABC095 C - Half and Half

Difficulty:220

$\ AB\ $ピザは 2 枚買うと$\ A\ $と$\ B\ $それぞれ 1 枚とカウントするため、あらかじめ$\ C\ $の値段を 2 倍しておく。
そして、$\ 0 \le i \le \max(X,Y)\ $の範囲で$\ AB\ $ピザを$\ i\ $枚買い、足りない分を$\ A\ $、$\ B\ $単体で買って補い、一番安くなった値段を答える。

a,b,c,x,y = map(int,input().split())
c *= 2
ans = 10 ** 16
for i in range(max(x,y) + 1):
    p = 0
    p += c * i
    p += a * (max(0,x - i))
    p += b * (max(0,y - i))
    ans = min(ans,p)
print(ans)

#75. ABC115 C - Christmas Eve

Difficulty:243

近い値同士で$\ h_\max-h_\min\ $を調べたほうがいいので、$\ h\ $をソートする。
前から順番に調べると、$\ K\ $本の中で$\ h_\max-h_\min\ $は$\ h_{i+k-1}-h_i\ $と固定できる。

n,k = map(int,input().split())
h = list(int(input()) for i in range(n))
h.sort()
ans = max(h) - min(h)
for i in range(n-k+1):
    ans = min(ans,h[i+k-1] - h[i])
print(ans)

#76. ABC151 C - Welcome to AtCoder

Difficulty:303

まだ AC していない問題の場合、その問題で WA した回数を数えておく。
WA した回数が答えに含まれるタイミングはその問題を初めて AC したときであり、既に AC した問題を WA しても答えに含まない。
AC した問題を何度 AC しても答えに含むのは最初の 1 回のみである。
最後まで AC できなかった問題は、何度 WA していても答えに含まない。
$\ M\ $が 0 のケースに注意する。

n,m = map(int,input().split())
if m != 0:
    l = [list(input().split()) for i in range(m)]
    p,s = [list(i) for i in zip(*l)]
t = [0] * n
ac = 0
wa = 0
for i in range(m):
    if s[i] == 'WA' and t[int(p[i])-1] != 'AC':
        t[int(p[i])-1] += 1
    elif s[i] == 'AC' and t[int(p[i])-1] != 'AC':
        ac += 1
        wa += t[int(p[i])-1]
        t[int(p[i])-1] = 'AC'
    else:
        pass
print(ac,wa)

#77. AGC012 A - AtCoder Group Contest

Difficulty:302

$\ a\ $をソートする。
$\ a_1 \dots a_N\ $は値が低いため、強さに含めるのに理想的ではない。
$\ a_{3N}\ $はどれだけ値が高くても強さに含めることは不可能であるが、$\ a_{3N-1}\ $は強さに含めることができ、そうなると$\ a_{3N - 2}\ $は強さに含めれない。
上を繰り返すと、最終的に$\ a_1 \dots a_N\ $を別々のチームにし、$\ a_{N+1} \dots a_{3N}\ $を前から二人ずつチームに入れることになり、これが最大の値になる。
$\ 1,2,3,7,8,9\ $の場合、$\ 1,3,7\ $、$\ 2,8,9\ $の 2 チームができ、強さの和は$\ 3+8=11\ $である。

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

#78. ABC136 C - Build Stairs

Difficulty:264

$\ H_i>H_{i-1}\ $なら$\ H_i\ $を$\ -1\ $しておく。
上の操作を前から順に行い、操作後の$\ H\ $をソートした$\ L\ $を用意して、$\ H=L\ $なら単調非減少になっている。

n = int(input())
h = list(map(int,input().split()))
for i in range(1,n):
    if h[i] > h[i-1]:
        h[i] -= 1
    else:
        pass
l = list(h)
l.sort()
if h == l:
    print('Yes')
else:
    print('No')

#79. AGC041 A - Table Tennis Training

Difficulty:370

$\ A\ $と$\ B\ $の最初の卓が 2 人とも奇数、偶数なら$\ (B-A)/2\ $回の移動で済む。
例えば$\ 3,7\ $なら$\ 4,6\ $、$\ 5,5\ $と 2 回の移動で済んでいる。
しかし$\ 4,7\ $の場合、このまま近づいても$\ 5,6\ $、$\ 6,5\ $、$\ 5,6\ $と同じ卓で試合をすることができず、両端のどちらかの卓で位置を調整する必要がある。
$\ A\ $が$\ 1$の卓に近いか、$\ B\ $が$\ N\ $の卓に近いかを判断し、近い方に 2 人とも移動し続け、片方が端まで移動し位置を調整できたら、移動後の$\ (B-A)/2\ $回の移動で同じ卓になる。
位置を調整する場合、$\ 100\ $卓あり、$\ 2,7\ $にいる場合、$\ 1,6\ $、$\ 1,5\ $、$\ 2,4\ $、$\ 3,3\ $と、$\ A\ $が同じ卓に 2 回いることを考慮しないといけない。

n,a,b = map(int,input().split())
if (a % 2 + b % 2) % 2 == 0:
    print(abs(a - b) // 2)
elif n - b < a - 1:
    p = n - b + 1
    a += n - b
    b = n
    print(abs(a - b) // 2 + p)
else:
    p = a
    b -= a - 1
    a = 1
    print(abs(a - b) // 2 + p)

#80. ABC144 C - Walk on Multiplication Table

Difficulty:266

$\ i \times j=N\ $を満たす場合、$\ i+j-2\ $が移動回数になる。
しかし、$\ 2 \le N \le 10^{12}\ $の制約から、全部試すと TLE になる。
例1の$\ 10\ $は$\ 2 \times 5\ $と$\ 5 \times 2\ $どちらでも判別可能であり、$\ 5\ $まで試さなくても答えが判別できることが分かる。
$\ 100\ $では、最大でも$\ 10 \times 10\ $まで調べれば答えを網羅できることから、調べる量は$\ \lfloor \sqrt{N} \rfloor\ $まででよい。

from math import sqrt
from math import floor
n = int(input())
ans = 10 ** 12
m = floor(sqrt(n))
for i in range(1,m+1):
    if n % i == 0:
        j = n // i
        ans = min(ans,i+j-2)
print(ans)
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?