Beginning of Beginners Contest 001 解説

A問題
B問題
C問題
D問題
E問題
F問題

A問題

$A+B>C$ が成り立つかどうかで場合分けをすれば良いです．出力文のタイプミスには注意してください（サンプルの出力をコピペすると確実です）．

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

if A+B>C:
  print('Correct :)')
else:
  print('Wrong :(')

B問題

各 $i$ に対して愚直に $S_i=A_1+A_2+\cdots+A_N$ を計算すると，全体で $O(N^2)$ 回の計算を行う必要があるためTLEしてしまいます．

そこで， $S_i=S_{i-1}+A_i$ であることを利用すれば，計算量を削減し $O(N)$ で解くことができます．

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

ans = 0
S = 0

for a in A:
  S += a
  S %= MOD
  ans += S
  ans %= MOD

print(ans)

もしくは， $\displaystyle\sum_{i=1}^{N}S_i=\sum_{i=1}^{N}(N+1-i)\,A_i$ であることを利用して $O(N)$ で解くことができます．

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

ans = 0

for i in range(N):
  ans += A[i]*(N-i)
  ans %= MOD
  
print(ans)

C問題

$N$ を素因数分解して，2番目に大きい正の約数を求めれば良いです．

$2$ 以上 $N$ 以下の整数 $x$ について， $N$ が $x$ で割り切れるかどうかを調べようとすると，最悪の場合に $O(N)$ の計算量がかかりTLEしてしまいます．

ここで，仮に $N$ が $p>\sqrt{N}$ を満たす約数 $p$ を持つならば， $N/p$ も $N$ の約数であり $N/p\lt\sqrt{N}$ が成り立ちます．言い換えれば， $N$ が $2$ 以上 $\sqrt{N}$ 以下のすべての整数で割り切れなければ， $N$ は $1$ か $N$ でしか割り切れない素数であることが分かります．

よって， $2$ 以上 $\sqrt{N}$ 以下の整数 $x$ について $N$ が $x$ で割り切れるかどうかを調べれば良いので， $O(\sqrt{N})$ の計算量で問題を解くことができます．

また，今回は2番目に大きい正の約数にしか興味がないので，正の約数すべてを列挙する必要はなく，

$N$ が素数のとき， $1$
$N$ が素数でないとき， $N$ の最小の素因数を $p$ として， $N/p$

を答えれば良いです．

N = int(input())

# 小数の丸め誤差を考慮して，念のため√N+1まで調べる
for x in range(2,int(N**0.5)+2):
    if N%x==0:
        print(N//x)
        exit()

# Nが素数の場合
print(1)

D問題

この問題でやっていることはバブルソートそのものであることに気付ければ，条件を満たすかどうかは転倒数から判定できることが分かります．転倒数とは $i\lt j$ かつ $h_i>h_j$ を満たす $(i,j)$ の個数であり，愚直に計算すれば $O(N^2)$ の計算量がかかりますが，BITなどのデータ構造を用いれば $O(N\log N)$ で求めることができます．

しかし，今回の場合はソート回数が3回までと限定されているので，愚直なシミュレーションを行うことが可能です．数列を順に見ていき入れ替えるべきところ（ $h_{i}>h_{i+1}$ となっているところ）を見つけたら，そこを入れ替えるという操作を3回まで行うようにすれば良いです．計算量は $O(N)$ です．

N = int(input())
h = list(map(int,input().split()))

for k in range(3):
    for i in range(N-1):
        if h[i]>h[i+1]:
            h[i],h[i+1] = h[i+1],h[i]
            break

ok = True
for i in range(N):
    if h[i]!=i+1:
        ok = False
        break

if ok:
    print('Yes')
else:
    print('No')

E問題

$X$ を $10$ で割った商と余りをそれぞれ $d,r$ とすると， $X$ 円を支払う際には1円硬貨を $r$ 枚，10円硬貨を $d$ 枚を使用することになります．よって， $d+r=N$ を満たす $X$ の個数を求める問題であると言い換えることが出来ます．

考えられる $X$ の値は最大で $10^{18}$ になるため，全探索ではTLEしてしまいます．

しかし， $X$ の値からある程度それぞれの硬貨の使用枚数に目星をつけられることが分かります．

$X\lt 10\,(N-10)$ のとき，10円硬貨を $N-10$ 枚より多く使うと支払額が $10(N-10)$ 円を超えるため，10円硬貨は高々 $N-10$ 枚までしか使われず，さらに1円硬貨は高々 $9$ 枚までしか使われないため，硬貨の使用枚数は $N$ 枚より少ない．
$X>10N$ のとき，10円硬貨は最低 $N$ 枚使う必要があり，加えて1円硬貨または10円硬貨を $1$ 枚以上使うことになるので，硬貨の使用枚数は $N$ 枚を超える．

以上をふまえると， $10(N-10)\le X\le 10N$ の範囲のみを調べれば良いことが分かります．この範囲内に整数は高々 $101$ 個しか存在しないため，全探索が可能です．

N = int(input())

ans = 0
for x in range(max(1,10*N-100),10*N+1):
  if (x//10)+(x%10)==N:
    ans+=1

print(ans)

よりスマートな解法を示します．ポイントは，1円硬貨は高々 $9$ 枚までしか使用されないことと，1円硬貨の使用枚数と $N$ が決まれば，10円硬貨の使用枚数と $X$ も一意に決まることです．

$N\le 9$ のとき，

$X=N+9\times 0$ （1円硬貨を $N$ 枚，10円硬貨を $0$ 枚）
$X=N+9\times 1$ （1円硬貨を $N-1$ 枚，10円硬貨を $1$ 枚）
　　　︙
$X=N+9\times N$ （1円硬貨を $0$ 枚，10円硬貨を $N$ 枚）

の $N+1$ 通りが考えられます．

$N\ge 10$ のとき，

$X=10N-9\times 9$ （1円硬貨を $9$ 枚，10円硬貨を $N-9$ 枚）
$X=10N-9\times 8$ （1円硬貨を $8$ 枚，10円硬貨を $N-8$ 枚）
　　　︙
$X=10N-9\times 0$ （1円硬貨を $0$ 枚，10円硬貨を $N$ 枚）

の $10$ 通りが考えられます．

よって，求める答えは $\min(N+1,10)$ です．

N=int(input())
print(min(N+1,10))

F問題

$X_K$ は $X_0$ に関して単調増加になっているので，二部探索で答えを求めることができます．計算量は $O(K\log N)$ です．

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

l = 1
r = 10**18
while r-l:
  mid = (l+r)//2
  X = mid
  for i in range(1,K+1):
    X = ((X-1)//i+1)*i
  if X>=N:
    r = mid
  else:
    l = mid+1

print(l)

きゃねろぐ

とある「おひさま」の徒然日記

Beginning of Beginners Contest 001 解説

A問題

B問題

C問題

D問題

E問題

F問題