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)

AtCoder Problems Training Easy(71~80)

目次