ABC176参戦記 A,B,C問題のACコード(Python3)

ここ数日、DockerやJSの学習していて精進Streakが途切れてしまいました。
いろいろ手を出してるので仕方ないですね。

今回はエール花火を家族と見て楽しんだ後、ABC176に参加しました。

この記事はABC(AtCoder Beginner Contest)のABC問題のC問題を、ぎりぎり解けるか解けないかくらいのレベルの私が、自分の理解を深めるためにも問題の解き方を言語化していくものです。

A – Takoyaki
B – Multiple of 9
C – Step
Appendix ～おまけ～

A – Takoyaki

A - Takoyaki

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

標準入出力と演算子と整数の取り扱いを問われる問題。

まずは標準入力を受け取らなくては問題を解くことができません。
私が競プロを始めて、いきなり躓いたのは標準入力でした。
今回のパターンは1行に複数の変数があるパターンです。
Pythonの標準入力の受取にはいろいろとあるのですが、今の私は、map()を使用しています。

N,X,T=map(int,input().split())

標準入力の注意点は、input()で受け取る際に何も型を指定していないと、文字列(str)型になることです。
map()に慣れるまでの私は、一度、その行をリストとして受けとってから、各変数にリストの各要素の値を割振るということをしていました。

###########
##標準入力##
##20 12 6##
###########

a=list(input().split())
N=int(a[0])
T=int(a[1])
X=int(a[2])
Xstr=a[2] # strとしてデータが作成されてしまう。

print(N) # >> 20
print(T) # >> 12
print(X,type(X)) # >> 6 <class 'int'>
print(Xstr,type(Xstr)) # >> 6 <class 'str'>

この形に慣れた後に、今のようにmapを使って受け取れるようになりました。

標準入力は、1行に対して1つの変数にしてもらえると初心者には優しいような気がしますがどうなんでしょう。

さて、ここからが今回の問題です。
この問題は何回たこ焼き器を使う必要があるかを考えるとわかりやすいと思います。
実生活でも同じ状況はあって、たこ焼き器を使う回数は、丁度X個の倍数以外の場合は、追加でもう一回使用しないといけません。
この部分をコードとしてあらわすと次のようになります。

if N%X==0:
    num=N//X
else:
    num=N//X +1

あとは、この回数に1回の使用にかかる時間である、Tをかけた数字をprint()で出力すればOKです。

出力部分にこの掛け算部分を持っていくこともできるので、今までの部品とつなぎ合わせると、このようなコードになります。

# AtCoder Beginner Contest 176
# A - Takoyaki

N,X,T=map(int,input().split())

if N%X==0:
    num=N//X
else:
    num=N//X +1

print(num*T)

B – Multiple of 9

B - Multiple of 9

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

数学的な知見を問われる問題。
かと思いきや、それの答えは問題文中に書いていました。
ということで、型の性質とlistとfor文が使えるかを確認する問題になりました。
と思いきや、Pythonでは、単純に割り切れるかどうか、そのまま判定すればよかったようです。(私は解説見て知りました。)

Python特有の楽なACコード

# AtCoder Beginner Contest 176
# B - Multiple of 9

N=int(input())
if N%9==0:
    print('Yes')
else:
    print('No')

私はコンテスト中に書いたコードは、問題文に書かれている通りの方針で実装しました。

標準入力時は意図的に文字列(str)型で受け取って、各文字を要素とするlist型へ変換します。またこの時にint型へmap()を使って格納します。map()を何となく使ったらうまくいったのですが、もっとちゃんと勉強しようと思うので今回のおまけ記事はmap()についてです。

listの合計はsum()で計算ができるので、その合計値が9で割り切れるかどうかを判定すればOKです。

# AtCoder Beginner Contest 176
# B - Multiple of 9

N=input()
ls=list(map(int,N))

lssum=sum(ls)

if lssum%9==0:
    print('Yes')
else :
    print('No')

なお、実行時間についてですが、
初めに書いたPython特有のコードとして紹介したものは、215msで、
私がコンテスト中に提出した(オーソドックスな？)コードは54msでした。
大きい桁数の数字はその計算時間が大きくなるのがわかります。

C – Step

C - Step

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

for文の中で実行する処理に線形探索を使わないでコードが書けるかを問われる問題。

ここ最近ずっとABCのC問題が解けなかった私ですが、今回は解けました！
それも一発AC。
計算量の見積もりもできたうえで解けました。

前回の記事のおまけ記事のなかであげていたABC139-C – Lowerを解いた記憶が残っていて解けました。

この問題はリストのi番目を確認した時に、それより前のmaxの値を毎回探すとTLEしますが、
i番目の人とi-1番目の人を比べて、i番目の人が小さかった場合、ステップを使用して、i-1番目の人と同じ高さにしていけばO(N)で解ける問題です。
i番目の人とi-1番目の人を比べて、i番目の人が同じか大きかった場合にはステップを使う必要はありません。
この二つの場合分けの対応が済んでいれば、常にA[i]>=A[i-1]が確保されます。
また、ステップを使った場面でステップの高さを答えの変数に加算していけば、最終的に答えの変数を出力することでACします。

# AtCoder Beginner Contest 176
# C - Step

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

ans=0

for i in range (1,N):
    if Als[i]>=Als[i-1]:
        pass
    else :
        step=abs(Als[i]-Als[i-1])
        ans+=step
        Als[i]+=step
print(ans)

A[i]番目の人が常にmaxの値になるように、補正していくのがポイントなのだと思います。

TLEするコードはこちらです。

###TLEcode####

# AtCoder Beginner Contest 176
# C - Step

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

ans=0

for i in range (1,N):
    if Als[i]>=max(Als[0:i]):
        pass
    else :
        ans+= max(Als[0:i])-Als[i]
print(ans)

for文の中で書かれているmax(Als[0:i])の部分が線形探索となり、ここの部分だけでO(N)かかり、計算量はO(N**2)かかってしまい、TLEします。

Appendix ～おまけ～

今回は、コンテスト中にC問題まで解けてしまったので、復習的な考察記事として書いていたおまけの部分はあまりない感じですが、今回のおまけはmap()についてです。
map()は入力でも頻繁に使っているし、今回のB問題はたまたまあっていたけれどもよくわかっていない部分があったので、もう少し理解していこうと思います。

まずは公式のドキュメントを確認します。

map(function, iterable, …)
function を、結果を返しながら iterable の全ての要素に適用するイテレータを返します。追加の iterable 引数が渡されたなら、 function はその数だけの引数を取らなければならず、全てのイテラブルから並行して取られた要素に適用されます。複数のイテラブルが与えられたら、このイテレータはその中の最短のイテラブルが尽きた時点で止まります。関数の入力がすでに引数タプルに配置されている場合は、 itertools.starmap() を参照してください。
https://docs.python.org/ja/3/library/functions.html

むむむ。よくわかりません。
よく標準入力で使っているけれども、intって型なの関数なの？とかiterableって何？？って感じです。

まず、標準入力で使用しているintについてですが、これは組み込み関数です。
上で見た公式のドキュメントの組み込み関数のところにも紹介されています。

型変換で次のような感じの関数として使っていることも多いと思います。

a='10'
int_a=int(a)

print(a) #>> 10
print(type(a)) #>> <class 'str'> 
print(int_a) #>> 10
print(type(int_a)) #>> <class 'int'>
print(a==int_a) #>> False

次にiterableについてですが、名前を見ると、iterがable(可能)なオブジェクトと読み取れます。
？？？
iterって何？ってなりますよね？
公式ドキュメントを確認していくと、iterはイテレート(iterate)と書かれていて、iterateは繰り返しという意味です。
つまり、iterableとは繰り返し処理が可能なオブジェクトという意味のようです。

繰り返し処理で思いつくものといえば、for文です。

for文で扱えるものがiterableと考えて間違いなさそうです。

list
tuple
dict
str

この辺りがよくつかわれるものだと思います。

ここまでわかれば、公式ドキュメントをだいたい理解できるようになると思います。

関数の引数が複数取られる場合は、一番要素数が少ない状態で終了する。ということも書いていますが、現状のABCのC問題くらいまでであれば、頭の片隅に入れておく程度で良いのかなと思っています。

返ってくる値はmapオブジェクトというものなので、このままではあまり使いどころがありません。

a=map(int,['2','3','3'])
print(a) #>> <map object at 0x00F2EBD0>
print(type(a)) #>> <class 'map'>

これををlistなり、変数代入用のオブジェクトとして利用すれば良いわけですね。

listにして利用(今回のB問題で利用した形)

N='1234'
ls=list(map(int,N))
print(ls) #>> [1, 2, 3, 4]

変数代入用のオブジェクトとして利用(今回のA問題で利用した形)

N,X,T=map(int,['2','3','3'])
print(N,X,T) #>> 2 3 3

変数に代入する際には、変数の数と、mapオブジェクトの要素数が一致していないと以下のようなエラーになります。

# 3つの変数に2つの要素しかないためエラー
ValueError: not enough values to unpack (expected 3, got 2)

# 3つの変数に4以上の要素を持つためエラー
ValueError: too many values to unpack (expected 3)

なお、iterableについては、Quiitaのこの記事を読むと詳しく理解しやすく書かれています。