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(21~30)

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

#21.ABC149 C - Next Prime

Difficulty:135

$\ X\ $に対して$\ 2 \le i \le X-1\ $が$\ X \mod i \neq 0\ $かどうかを調べる。
もしすべての$\ i\ $で$\ X \mod i \neq 0\ $を満たすなら$\ X\ $が答えの整数であり、違うなら$\ X\ $を 1 増やして条件を満たすまで上の条件で調べ続ける。
制約が$\ 2 \le X \le 10^5\ $であり、 例3 の出力から$\ X \le i \le 100003\ $の範囲で素数かどうか調べたらいいことが分かる。

x = int(input())
for i in range(x,100004):
    flg = True
    for j in range(2,i):
        if i % j == 0:
            flg = False
            break
    if flg:
        print(i)
        break

#22.AGC027 A - Candy Distribution Again

Difficulty:122

子供が欲しがっているキャンディの合計を$\ S\ $とする。
$\ S=x\ $なら、子供全員に丁度渡せるため$\ N\ $人全員が満足する。
$\ S<x\ $なら、子供全員に丁度渡した後、余ったキャンディを誰かに渡さないといけないため、$\ N-1\ $人が満足する。
$\ S>x\ $なら、$\ a_1 \dots a_N\ $の各子供が満足する個数を$\ x\ $個がなくなるまで渡し続ける。
喜ぶ子供の人数を最大化するため、$\ a\ $をソートしておき、喜ぶ個数が少ない順に渡していく。

n,x = map(int,input().split())
a = list(map(int,input().split()))
if sum(a) == x:
    print(n)
elif sum(a) < x:
    print(n - 1)
else:
    ans = 0
    a.sort()
    for i in range(n):
        if a[i] > x:
            break
        else:
            x -= a[i]
            ans += 1
    print(ans)

#23.ABC092 B - Chocolate

Difficulty:91

残ったチョコレート$\ X\ $に$\ N\ $人が食べたチョコレートの数を足して復元する。
$\ i\ $ 人目がチョコレートを食べた日は、問題文にあるように $\ 1,A_i+1,2A_i+1\ $なので、まとめると$\ \lceil D/A_i \rceil \ $ ということが分かる。
1 日目に全員が食べることと、$\ D\ $日目も食べることに注意する。

from math import ceil
n = int(input())
d,x = map(int,input().split())
a = list(int(input()) for i in range(n))
for i in range(n):
    x += ceil(d / a[i])
print(x)

#24.日立製作所 社会システム事業部 プログラミングコンテスト2020 B - Nice Shopping

Difficulty:94

まず、$\ \min(A)\ $円の冷蔵庫と$\ \min(B)\ $円の電子レンジを買った時の金額を求める。
その後、クーポン通りに購入した時に、上より安くなるか調べる。
例2 のように、クーポンは 1 つしか使えず、同じ組み合わせでもクーポンによって値段が違うことに注意する。

a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(m)]
x,y,c = [list(i) for i in zip(*l)]
ans = min(a) + min(b)
for i in range(m):
    ans = min(ans,a[x[i]-1] + b[y[i]-1] - c[i])
print(ans)

#25.ABC150 C - Count Order

Difficulty:338

順列$\ 1 \dots N\ $の重複なしの並びを全て格納したリストを用意する。
その後、$\ P\ $と$\ Q\ $の位置を調べ、その差を出力する。

import itertools
n = int(input())
a = list(range(1,n+1))
a = list(itertools.permutations(a,n))
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
print(abs(a.index(p) - a.index(q)))

#26.ABC153 D - Caracal vs Monster

Difficulty:120

最初のモンスターの体力を半分にすると、モンスターの数が 2 倍に増える。
増えたモンスターの体力を全て半分にすると、モンスターの数がさらに 2 倍に増える。
このことから体力を半分にするたび、攻撃回数は$\ 2^0,2^1 \dots \ $と増える。
これを$\ H\ $が 0 になるまで繰り返す。

h = int(input())
ans = 0
i = 0
while h > 0:
    h = h // 2
    ans += 2 ** i
    i += 1
print(ans)

#27.ABC158 B - Count Balls

Difficulty:106

$\ A+B \le N\ $の場合、青いボールは少なくとも$\ (\lfloor N/(A+B) \rfloor) \times A\ $個は出現する。
さらに$\ N \mod (A+B)\ $ 個のボールの中で、青いボールが何個出現するか数える。

n,a,b = map(int,input().split())
c = a + b
z = n // c
if n % c != 0:
    m = n % c
    if a <= m:
        print(z * a + a)
    else:
        print(z * a + m)
else:
    print(z * a)

#28.ABC081 B - Shift only

Difficulty:98

実際に$\ N\ $個の整数を 2 で割り切れるか調べる。

n = int(input())
a = list(map(int,input().split()))
ans = 0
flg = True
while flg:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

#29.ABC114 B - 754

Difficulty:111

文字列$\ S\ $から、長さ 3 の部分文字列を取り出す。
それを数値化し、 753 との差の絶対値を調べる。

s = input()
ans = 999
for i in range(len(s)-2):
    n = int(s[i:i+3])
    ans = min(ans,abs(753 - n))
print(ans)

#30.ABC108 B - Ruined Square

Difficulty:140

実際に書いてみると法則を探しやすく、画像は 例2 を参考にしている。
まず$\ x_1,x_2\ $の差と、$\ y_1,y_2\ $の差を求める。
それぞれ、$\ c-a,d-b\ $になり、これを$\ n,m\ $として考える。
次に$\ x_3,y_3,x_4,y_4\ $を求める。
$\ x_3,y_3\ $は$\ x_2-m\ $、$\ y_2+n\ $で求まる。
$\ x_4,y_4\ $は$\ x_1-m\ $、$\ y_1+n\ $で求まる。
スクリーンショット (31).png

a,b,c,d = map(int,input().split())
x = c - a
y = d - b
print(c - y,d + x,a - y,b + x)
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?