2020-12-01

【AtCoder】ARC109の問題を初心者的書き方で解説する with Python

ここではAtCoderの問題を解説していきます。
AtCoderの解説は基本的にC++が多く、私のような初心者には難しく書かれていたりするため、
A~Cの問題を基本的な書き方で書いていきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。

A問題 Hands

100階建ての建物 A , B があります。
$i=1,\cdots,100$ について、建物Aの $\,i\,$ 階とBの $\,i\,$ 階は廊下で繋がれています。また、 $i=1,\cdots,99$ について、建物Aの $\,i+1$ 階とBの $\,i$ 階は廊下で繋がれています。
どの廊下も双方向に通行可能で、移動には $\,x$ 分かかります。また、A,Bどちらの建物にも階段があり、 $i=1,\cdots,99$ について、同じ建物の $\,i$ 階と $\,i+1$ 階は階段で繋がれています。どの階段も双方向に通行可能で、移動には $y$ 分かかります。建物Aの $a$ 階から建物Bの $b$ 階に移動するのにかかる最短時間を求めてください。
入力は以下の形式で標準入力から与えられる。
$a \hspace{1cm}b \hspace{1cm}x\hspace{1cm}y$

解説にあるようにひとまとめに計算してもいいですが、分かりやすく場合分けをして考えてみました。
こういう問題は図を書いてイメージするのが大事ですね。

f:id:amadeus_salieri:20201201174729j:plain

1. $a=b$ の場合
この場合は普通に廊下を $x$ 分かけて渡るだけです。
仮に一つ別の解を利用した場合、階段を降りる(or上る)時間 $y$ + 廊下を渡る時間 $x$ + 階段を上る(or降りる)時間 $y$ を計算しなければならず、
必ず $x$ 分より大きくなります。

2. $a>b$ の場合
この場合は $a$ から $b$ に降りる場合となります。
この時、とりあえず先に建物Bまで移動して、そのあとどのように降りれば早いかを考えるとわかりやすいです。

AからBに移動する際には、斜めの廊下を使うのが一番早いです。この時点で $a$ と $b$ の階数差は $a-1-b$ になります。

そのあとどのように降りればよいかというと、以下の図のように2パターン考えられます。

f:id:amadeus_salieri:20201201175528j:plain

すなわち、1階分降りる時間である $2x$ と $y$ を比較し、小さい方の値を選択すればいいことが分かります。

3. $a < b$ の場合
この場合は $a$ から $b$ に上る場合となります。
この場合は先に $b$ と同じ高さまで上り、(階数差は $b-a$ )そのあとBに普通の廊下を使って移動することを考えればよいです。
この際、2と同様に $2x$ と $y$ のどちらが早いかを考えて選択すればよいです。

解答は以下の通り。

a,b,x,y = list(map(int, input().split()))
 
#同じ階の場合
if a == b:
    print(x)
 
#降りる場合
elif a>b:
    if 2*x<=y:
        print(x + (a-1-b)*2*x)
    else:
        print(x + (a-b-1)*y)
 
#上る場合
else:
    if 2*x<=y:
        print((b-a)*2*x + x)
    else:
        print((b-a)*y + x)

2020-09-02

【AtCoder】ABC177の問題を初心者的書き方で解説する with Python

A問題 Don't be late

高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家から $D$ メートル離れた地点であり、待ち合わせの時刻は $T$ 分後です。高橋君は今から家を出発し、分速 $S$ メートルで待ち合わせ場所までまっすぐ移動します。待ち合わせに間に合うでしょうか？
入力は以下の形式で標準入力から与えられる。
$D \hspace{1cm}T \hspace{1cm}S$

小学生の時からお馴染みの公式
(時間) = (距離)÷(速さ)
を使えばいいと思います。すなわち、かかった時間 $\frac{D}{S}$ が目標の時間 $T$ よりも長いか短いかで判断します。

かかった時間がT分以下ならYesを、T分よりも大きいならNoを出力するコードを書けばいいです。

解答は以下の通り。

s = list(map(int, input().split())) 
D = s[0]
T = s[1]
S = s[2]
 
if D/S <= T:
    print("Yes")
else:
    print("No")

B問題 SubString

2つの文字列S, Tが与えられます。Tが Sの部分文字列となるように、Sのいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。
入力は以下の形式で標準入力から与えられる。
S
T
Sを書き換える文字数の最小値を出力せよ。

書き換える文字数の最小値は何かという問題は、SとTで最小何文字異なっているか答える問題と同じです。そのため、
①SからT文字分取り出す(この文字列をUとします)
②UとTで何文字異なっているか数える
③各Uに対して異なっている数をリストに数える
④最後にそのリストの最小値を答える
という手順で行います。

問題例に挙げられている
S：cabacc
T：abc
を用いて考えると、
①S：cabaccからTの文字数である3文字分を頭から取り出します。
U：cab
T：abc
②この場合いずれの文字も異なっているため3文字分異なっています。
③リストに3を追加します。
score = [3]

この操作を繰り返していきます。次は1文字分ずらして、
①S：cabaccからTの文字数である3文字分を頭から1文字ずらして取り出します。
U：aba
T：abc
②この場合"ab"の2文字が一致しているため、1文字分異なっています。
③リストに1を追加します。
score = [3,1]

これを繰り返して、最後にリストの最小値を求めればよいです。

S = input()
T = input()

score = []
for i in range(len(S)-len(T)+1):
    U = S[i: i+len(T)]
    cnt = 0
    for j in range(len(T)):
        if U[j] != T[j]:
            cnt = cnt + 1
    score.append(cnt)
print(min(score))

C問題 Sum of product of pairs

$N$ 個の整数 $A_{1},\cdots,A_{N}$ が与えられます。
$1$ $\leq$ $i$ $<$ $j$ $\leq N$ を満たす全ての組 $(i,j)$ についての
$A_{i}\times A_{j}$ の和を $mod(10^{9}+7)$ で求めてください。
入力は以下の形式で標準入力から与えられる。
$N$
$A_{1},\cdots,A_{N}$

問題の答え自体は、以下のコードで行うことが出来ますが、TLEになってしまいます。2重ループが存在することが原因です。

N = int(input())
A = list(map(int, input().split())) 
 
goukei = 0
for i in range(N):
    for j in range(i+1,N):
      goukei = goukei + A[i] * A[j]
k = 10**9 + 7
print(goukei%k)

そのため2重ループをなくすことを目標にコードを書き換えていきましょう。
例えば
$A_{1},A_{2},A_{3},A_{4},A_{5}$
という数値を入力したとき、まず $A_{1}$ に対しては
$A_{2},A_{3},A_{4},A_{5}$
をかけていきます。つまり、
$A_{1}\times A_{2} + A_{1}\times A_{3} + A_{1}\times A_{4} + A_{1}\times A_{5}$
ですが、まとめると
$A_{1}\times (A_{2}+A_{3}+A_{4}+A_{5})$
で表されます。同様に $A_{2}$ に対しては
$A_{2}\times (A_{3}+A_{4}+A_{5})$
を計算していきます。
すなわち、
①リストAの合計値をあらかじめ求める(A[0]+…A[4])
②リストAから最初の値を取り出す(A[0])
③リストAから最初の値を取り除く(A = [A1,…A4])
④①の合計値から取り除いた値を引く
⑤④で得た値と取り出した②で取り出した値をかけて、新しい合計値とする
これを全ての要素に対して行えばよいです。

N = int(input())
A = list(map(int, input().split())) 
 
goukei = 0

sumA = sum(A)
for i in range(N):
    a = A[i]
    sumA = sumA - a
    goukei = goukei + sumA*a

k = 10**9 + 7
print(goukei%k)

2020-08-25

【AtCoder】ABC176の問題を初心者的書き方で解説する with Python

ここではAtCoderの問題を解説していきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。

A問題 Takoyaki

高橋君はたこ焼きが好きです。
たこ焼き器を使うと、1度に最大で $X$ 個のたこ焼きを作ることができます。これにかかる時間は作る個数によらず $T$ 分です。
$N$ 個のたこ焼きを作るためにかかる時間の最小値を答えよ。
入力は $N\,\,X\,\,T$ の標準入力で与えられる。

具体例を考えてみましょう。
1度に10個のたこ焼きを作ることができるたこ焼き器に対して、20個のたこ焼きを焼きたい場合、2回焼けばいいことが分かると思います。
これはただ単に20÷10を計算しているだけですね。

一方、
1度に10個のたこ焼きを作ることができるたこ焼き器に対して、23個のたこ焼きを焼きたい場合、20個焼いた時点で3つ余りが出てきてしまいます。
この余りの分を焼くためにもう一度だけたこ焼き器を稼働させなければなりません。

つまりこの問題は、焼きたいたこ焼きの数 $N$ をたこ焼き器の容量 $X$ で割った時、余りがあるかないかで場合分けをする必要があります。

その後焼く回数が分かれば、あとは(焼く回数)×(1回焼くのにかかる時間)を計算すればよいです。

解答は以下の通り。

i = list(map(int, input().split())) 

N = i[0]
X = i[1]
T = i[2]
 
#焼く回数をkとします.
if N%X == 0:
    k = N/X
else:
    k = int(N/X)+1
print(int(T*k))

B問題 Multiple of 9

整数 $N$ が9の倍数であることと、 $N$ を十進法で表したときの各桁の数の和が 9の倍数であることは同値です。
$N$ が9の倍数であるか判定してください。
入力は $N$ の標準入力で与えられる。

例えば $N = 123456789$ であれば、各桁の総和が45となり、9の倍数であるため $N$ は9の倍数になります。
この問題の趣旨は、各桁の数字を計算できる形に直していくことになります。

そのため、一度 $N$ を文字列として受け取った後、大きい位から順に数字として
[1,2,3,4,5,6,7,8,9]
のようにリストに追加し、このリストの要素を全て足すことで、それが9の倍数かどうかを判定していきます。

N = input()

lists = []
for i in range(len(N)):
    lists.append(int(N[i]))
goukei = sum(lists)
if goukei%9 == 0:
    print("Yes")
else:
    print("No")

実はPythonではほかの言語とは異なり、多倍長整数という大きい桁の数でもそのまま扱うことが出来る性質があるため、
以下のコードでも倍数判定をすることが可能です。

N = int(input())

if N%9 == 0:
    print("Yes")
else:
    print("No")

C問題 Step

$N$ 人が1列に並んでおり、前から $i$ 番目の人の身長は $A_{i}$ です。
それぞれの人の足元に、高さが0以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件：踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。
入力は以下の形式で標準入力から与えられる。
$N\\ A_{1},\cdots,A_{N}$

感覚としては、前から2番目の人が1番目の人より身長が高ければそのままにしておき、
2番目の人が1番目の人より身長が低ければ、
(1人目の身長)-(2人目の身長)
の差分を踏み台の高さとすることで、2人目の人は1人目の人の身長と同じ高さになります。
それを繰り返していけばいいことになります。

ここでは $i$ 番目の人よりも前にいる人の集合をBとし、 $i$ 番目以降の、これから比較する人の集合をAとしてリストにしていきます。

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if max(B) > A[i+1]:
        k = max(B)-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))

しかし、このやり方でやるとTLEになってしまいます。
これはmax関数を用いたことにより、計算量が多くなってしまっているからです。
よくよく考えると、リストBの最後の要素はリストBの中で一番大きい値になっているため、max関数を使わずに表記することが可能です。

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if B[i] > A[i+1]:
        k = B[i]-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))

これで計算量も抑えられ、ACすることができます。