先週はABCがなかったため、1週間ぶりのコンテスト!
ABCクラスのコンテストでここ4回連続でAB2完でC問題が解けない状態が続いたため、
今回こそ
今回 も Cが解けませんでした。
を断ち切る!
と意気込んで臨んだコンテスト。
結果やいかに!?
本記事は、競プロ灰色コーダーによる、M-SOLUTIONS プロコンオープン 2020のABCの各問題のACに至るまでの思考回路の整理と、Python3のACコードがあります。
今回のおまけ記事はTLEマスターの私が、灰~茶(一部緑を含む)diffの問題でTLEする理由と、対応策をまとめています。
- A – Kyu in AtCoder
- B – Magic 2
- C – Marks
- Appendix ~おまけ~
- ABC073 C – Write and Erase
- ABC152 C – Low Elements
- ABC154 D – Dice in Line
- ABC155 C – Poll
- ABC159 D – Banned K
- ABC144 C – Walk on Multiplication Table
- ABC072 C – Together
- ABC172 C – Tsundoku
- ABC137 C – Green Bin
- ABC127 D – Integer Cards
- ABC142 C – Go to School
- ABC139 C – Lower
- ABC143 D – Triangles
- ABC055 B – Training Camp
- ABC158 D – String Formation
A – Kyu in AtCoder
愚直にif文を書く問題。または、法則を見出して、割り算の商を利用する問題。
問題文中に載っている範囲をすべてif文で書けばACします。ちょっと格好悪いし、書く量多いし、書く量多いってことは間違える箇所も増えるし、なによりスマートではない感じはしますが、私はコンテスト中この方針で提出しました。
X=int(input())
if 400<=X<=599:
print(8)
exit()
if 600<=X<=799:
print(7)
exit()
if 800<=X<=999:
print(6)
exit()
if 1000<=X<=1199:
print(5)
exit()
if 1200<=X<=1399:
print(4)
exit()
if 1400<=X<=1599:
print(3)
exit()
if 1600<=X<=1799:
print(2)
exit()
if 1800<=X<=1999:
print(1)
exit()
この問題の法則は、以下の2点です。
- 200点毎に級の数字は1減る。
- 点数を200で割った商の部分と、級の数字を合わせると10になる。
つまり、級は、10からその商の部分を引いた数になる。
上でいっぱい書いたのが馬鹿らしくなるくらいすっきりしました!
X=int(input())
kyu= 10 - X//200
print(kyu)
ちなみに、解説PDFは1行で書かれています!
すごい!
B – Magic 2
if文と繰り返し処理を同時に扱う問題。
理想の状態(赤<緑<青)にするためには、
まずは、赤<緑なら何もしない。違う(赤>=緑)なら、魔法を1回使用し、緑を ×2 する。
赤<緑の状態が出来上がったら、
次に、緑<青なら何もしない、違う(緑>=青)なら、魔法を1回使用し、青を ×2 する。
これらの操作が、K回以内に収まれば’Yes’で、K回を超える場合は’No’を出力する。
K回以内に収まるかどうかの判定は2つあって、
- 繰り返し処理をK回実施して、理想の状態になっているかを判定する。
- 繰り返し処理を実施し、理想の状態になるための魔法使用回数を数えて、Kと比較して判定する。
繰り返し処理については、forとwhileどちらでも良いと思いますが、私はwhile文が苦手なので、for文を使用し、上記の判定は1を採用しています。
R,G,B=map(int,input().split())
K=int(input())
for _ in range (K) :
if R < G :
pass
else:
G*=2
continue
if G < B :
pass
else:
B*=2
continue
if R < G < B :
print('Yes')
else :
print('No')
練習のため、whileを使用、K回以内に終わるかの判定は上記方針の内、2を使用したコードも書いてみました。
こっちのコードでもACしました。
R,G,B=map(int,input().split())
K=int(input())
M=0
while R>=G or G>=B:
if R>=G:
G*=2
M+=1
if G>=B:
B*=2
M+=1
if M<=K:
print('Yes')
else:
print('No')
C – Marks
掛け算を構成する要素を理解しているかの確認と、数の大小を比較する問題。
前期と今期の評点で、掛け算の要素がかぶっている部分は共通で、評点の大小にかかわるのは、i学期と、i-K学期の得点だけなことに気づけば、掛け算の計算すらする必要はなく、簡単なif文を書けばOKです。
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range (K,N):
if A[i]>A[i-K]:
print('Yes')
else:
print('No')
と、ACコードを書いていますが、私はこの問題、コンテスト中に解けませんでした。
今回こそはC問題解けない病を克服しようと思って臨みましたが、叶いませんでした。
これ以降は、誤回答を披露しつつ、なぜダメだったのか、試したことの考察をメモで残します。
また、一部、ほかのコンテストの問題のネタバレを含むので、気になる方はこれ以降読むのをお控えください。
誤回答その1 愚直に計算し、リストに格納
問題を見た瞬間、累積和の積verをリストにして格納し、判定していけば良さそうだと思って提出したコードがこちら。
また、格納する値は、i番目の累積の積ではなく、評点で格納するようにしました。
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[1]
for n in range (N):
if n<K:
S.append(A[n]*S[-1])
else:
S.append(A[n]*S[-1]/A[n-K])
for i in range (K+1,N+1):
if S[i]>S[i-1]:
print('Yes')
else:
print('No')
この時点で、A[n-K]で割っているので、気づいても良さそうなもんですが、気づけませんでした。
この提出コードでの結果は「TLE」。
TLEが出ても対策はいろいろと学んだので大丈夫です!精進のたまもの!
リストで情報を持っているのが原因と考え、改善を試みました。
誤回答その2 愚直に計算し、辞書型に格納
格納する情報がリスト型であるのがTLEの原因かと思い、ハッシュテーブルで管理するdic型へ格納するようにしました。
持つ情報をリスト型から辞書型に変えて、成功した事例は、
ABC159 D – Banned Kなどで
で経験したため、辞書型の利用を試しました。
N,K=map(int,input().split())
A=list(map(int,input().split()))
dictS={}
dictS[0]=1
for n in range (1,N+1):
if n-1<K:
dictS[n]=A[n-1]*dictS[n-1]
else:
dictS[n]=A[n-1]*dictS[n-1]/A[n-1-K]
for i in range (K+1,N+1):
if dictS[i]>dictS[i-1]:
print('Yes')
else:
print('No')
この提出コードでも結果はTLE・・・ぐぬぬ。
コードを見ると、後半のif文を分ける必要がなさそうなことに気づき、改善を試みました。
誤回答その3 辞書型に格納していき、都度結果を出力
一度、データを格納してからもう一度for文を実行すると、余計に時間がかかると思い、一回目のfor文で都度結果を判定するようにしました。
N,K=map(int,input().split())
A=list(map(int,input().split()))
dictS={}
dictS[0]=1
for n in range (1,N+1):
if n-1<K:
dictS[n]=A[n-1]*dictS[n-1]
else:
dictS[n]=A[n-1]*dictS[n-1]/A[n-1-K]
if n>K:
if dictS[n]>dictS[n-1]:
print('Yes')
else:
print('No')
これもTLEなわけで、所持するデータの型がリスト型だから、とか辞書型だから、というのが原因ではなさそうという結論になりました。
誤回答その4 評点を大きい素数(10**9+7)で割った余りで持つ
保持するデータの型がTLEの問題ではないということが分かったので、次は各計算の実行時間の問題を疑いました。
計算する桁が大きい場合、計算する時間自体が長くなることをコンテスト当日の精進で知ったからです。
今回も制約から、各テストの点数が10**9と大きくなる場合があることが分かったので、素数の余りをとってみようとして、試したのがこちらのコード。
N,K=map(int,input().split())
A=list(map(int,input().split()))
dictS={}
dictS[0]=1
P=10**9+7
for n in range (1,N+1):
if n-1<K:
dictS[n]=(A[n-1]*dictS[n-1])%P
else:
dictS[n]=(A[n-1]*dictS[n-1]/A[n-1-K])%P
if n>K:
if dictS[n]>dictS[n-1]:
print('Yes')
else:
print('No')
お!?結果を見てみると、
TLEじゃなくて、WAになりました。やはり、TLEになっていたのは掛け算自体の実行時間が長かったことのようです。
しかし、結果はWA。
割り算がダメなのか素数が小さくてダメなのかの理解はできていませんが、大きな素数をWikipediaで調べて、
P=170141183460469231731687303715884105727
この数で試してみましたが、結果は変わらずWAでした。
そうこうしているうちに、時間は過ぎ去り、結果的にCを解くことはできませんでした。
Appendix ~おまけ~
今回のC問題もコンテスト中に解くことはできませんでしたが、
TLEになっている部分の予想と改善が出来ただけでも進歩していると捉えることにして、引き続き精進します。
灰色競プロerの私が解いた中で、TLEを経験した問題とTLEの回答、ACした回答をご紹介します!
TLEの原因考察も併せて書いていきます。
以下、解いた順番に記載しています。
ABC073 C – Write and Erase
リストで情報を管理するとTLE。
リストに存在するかを確認するために毎回O(N)かかっていたからと思われる。
setで情報を管理するとAC。
ABC152 C – Low Elements
for文の中で無駄に新しい配列を作ってTLE。
新しい配列を無駄に作るのにO(N)かかっていたことと思われる。
必要な情報を既存のデータから直接取得することでAC。
ABC154 D – Dice in Line
区間累積和の作り方を知らず、区間のリストを都度作って、合計を計算していたらTLE。
毎回、部分的なリストを作るために、O(N)かかってたと思われる。
区間の累積和の作り方はわかっていませんでしたが、対象外になる部分をひいて、新しく対象になる部分を毎回足して計算してAC。
ABC155 C – Poll
文字列と、文字列の出現回数を管理するリストを2つ用意して計算したらTLE。
二つのリストで同じ位置を探すためにindex()で使用していたため毎回O(N)消費してたと思われる。
collectionsモジュールのCounterを利用してAC。
ABC159 D – Banned K
リストを複数作成し、必要な情報を毎回リストから取得して計算したらTLE。
リスト間の位置の情報をindexで探していたため、その探索にO(N)かかっていた模様。
辞書型に情報を持たせて計算したらAC。
ABC144 C – Walk on Multiplication Table
素因数分解して、素因数の組み合わせをbit全探索でa*bの形になるa,bの組み合わせの最小値を求めるとTLE。
最初から、a*bとなるような組合わせをN**0.5まで全探索してAC。
素因数分解でN**0.5、素因数の数(mとする)に応じて変動するが、bit全探索で2**mかかっていたが、a*bとなる組を探すのも素因数分解するのも同じ計算量でした。
ABC072 C – Together
各aに対して、a-1,a,a+1の数を保持したリストを作成して、Xの値を0からaのリストのmax+2まで全部調べて~。ってしたらTLE。
先にXのリストを作って、各aからa-1,a,a+1の値をXの各indexに+して一番大きいXの値が答え。とするとAC。
これは、発想の転換が必要で、どんなに考えてもこの発想には至れなかったですね。
ABC172 C – Tsundoku
リストに調べたい要素を追加して、ソートし直して、追加した要素のindex番号を調べているとTLE。
上記内容は二分探索(Pythonでは、bisectを使用)で高速に調べられるので二分探索を実装したらAC。
ABC137 C – Green Bin
文字列と、文字列の出現回数を管理するリストを2つ用意して計算したらTLE。
複数のリストの位置情報を探すのにindexを利用していたので、その探索に毎度O(N)消費していた模様。
辞書型を利用してAC。
ABC127 D – Integer Cards
書いてある内容を愚直に実装しようとして、二重ループの中で毎度ソートしながらカードを受け取るとTLE。
一度入力を全部受け取ってしまってから、ソートすることで結果的にACできました。
なお、numpyは早いらしいとのことで、この問題はnumpyを利用しました。
問題文中の「出力が32bit 整数型に収まらない場合があります。」に惑わされて、numpyで取り扱うデータタイプを64bit整数にしたらTLEが続いて途方に暮れていたけれども、
出力の合計値が32bit整数に収まらない場合があるだけということに気づいて、numpyで取り扱うデータタイプを32bit整数にしたらAC。
ABC142 C – Go to School
答えの順番をindex()の線形探索で探すとTLE。
先に必要な長さのリストを作成して、Aiの順番で探して準備したリストに書き込んでいくとAC。
たきお(@tachyon_kpr)さんに教えてもらうまで、index()が線形探索だということに気づいていませんでした。
これも上のABC072-Cと同様、自分ではなかなか気づけないですね。
ABC139 C – Lower
各場所から進める距離を調べていくとTLE。
調べる箇所が左一個前以下ならカウンターを回していって、高くなった時点でリセット。カウンターが最高値を上回っていたら最高値更新。としていくコードでAC。
Python3では、for文の最後に実行するelseを忘れないよう注意。
各箇所からの値を調べるのにそれぞれO(N)かかるため、TLE。
発想を切り替えて、1回調べるだけで答えがわかることに気が付いてAC。
ABC143 D – Triangles
3本の組合わせを全探索するとTLE。
2本の組を固定して三角形ができる3本目の本数を二分探索して答えに追加していくとAC。
二分探索する前提条件として、リストが単調増加である必要があるのでリストのソートが必要ですね。
ABC055 B – Training Camp
愚直に ×2 してていき、最終的に10**9+7で割った余りを答えとするとTLE。
計算途中で1回毎に10**9+7で割った余りを更新するとAC。
ABC158 D – String Formation
文字を反転させなくても、文字列の先頭と末尾にそれぞれ文字列を追加していくとTLE。
先頭に追加する文字列だけ別管理して後で結合するとAC。
先頭に追加すると、それ以降のindexをそれぞれ書き換える必要があるため、処理時間がかかるという理解。
Python3では、dequeを使用すると、リストの両端に処理時間短く追加できるため、こちらでも提出したらAC。
あれ、思ってたよりTLEだった問題少なかったw
30問くらいあるイメージだったけど。
コメント